Математическая индукция – это метод доказательства некоторого утверждения P(n) для всех значений натурального параметра n; n = 0, 1, 2, … . Доказательство проводится по следующей схеме.
· Начальный шаг: утверждение P(n) доказывается для n = 0 (база индукции);
· Индуктивный шаг: утверждение P(n) считается истинным для значения n (индуктивное предположение) и доказывается для значения n + 1.
Переменная n называется индукционной переменной. Метод математической индукции базируется на аксиоме индукции:
( P(0) & "k.[ P(k) Þ P(k + 1) ] ) Þ "n.P(n) . (3.2)
На практике используются различные обобщения метода в зависимости от природы утверждения P(n). База индукции может быть отлична от нуля. Шаг индукции может быть отрицательным. Индукционных переменных может быть несколько. Эти и другие особенности учитываются методами полной индукции и структурной индукции. Их доказательство реализуется применением классического метода математической индукции. Индукционное предположение для полной индукции определяет истинность P(j) для всех j £ k; при его использовании требуется доказать P(k + 1).
Далее будем использовать метод, сочетающий структурную и полную индукцию. Пусть утверждение, которое требуется доказать, есть W(t); t Î X. Параметр t определяет одну или несколько индукционных переменных. На множестве X задан строгий частичный порядок ⊏, удовлетворяющий свойству (3.1) обрыва бесконечных убывающих цепей. Метод структурной (и полной) индукции определяется следующей формулой:
"t Î X. [ ("y Î X. y ⊏ t Þ W(y) ) Þ W(t) ] . (3.3)
Если элемент t в формуле (3.3) является минимальным, то формула (3.3) вырождается в "t Î X. W(t). Это значит, что для минимальных элементов доказательство W(t) надо проводить отдельно, что соответствует начальному шагу классической схемы. Пусть истинное значение предиката b(t) определяет набор значений t, составляющих базу индукции, которая, по меньшей мере [11], должна содержать все минимальные элементы. Тогда формула (3.3) переписывается в виде
"t Î X. [ (b(t) Þ W(t)) & "y Î X. (Øb(t) & y ⊏ t Þ W(y) ) Þ W(t) ] . (3.4)
Формула (3.4) определяет общую схему доказательства по индукции.