>>5921
Представь, что у тебя задана некоторая формальная система с правилом (правилами) вывода. Построим ориентированный граф, вершинами которого является некоторое множество А синтаксически корректных высказываний твоей системы, а ориентированными ребрами - импликации между ними.

Такой граф будет задавать некоторое отношение на некотором множестве высказываний. Как и в любом орграфе, в нем существует ядро - то есть подмножество вершин, из которых потенциально достижимы все остальные вершины. Это ядро будет являться базисом индукции. Шагом индукции будет применение этого отношения к множеству вершин (то есть однократный переход из вершины в вершину по стрелочкам). Если ты сумеешь доказать, что все выражения в ядре орграфа истинны и он при этом связен, то из этого немедленно следует, что, двигаясь из ядра по стрелочкам, мы можем в итоге посетить все вершины графа - и, следовательно, ВСЕ выражения, принадлежащие множеству А, истинны.

То есть, индукция - это просто частный случай волнового алгоритма. Математики пользуются его элементарной версией и не прямо, а косвенно, через параметризацию некоторого математического объекта и использованием особенностей структуры множества значений параметра. Например, доказывая по индукции выражение для суммы арифметической прогрессии, мы параметризуем это выражение (выделяя переменную n, значения которой принадлежат множеству натуральных чисел) и используем тот факт, что на множестве N существует линейный порядок - то есть бесконечную ориентированную цепь с ядром в вершине 1. Сначала мы доказываем истинность выражения в ядре этого орграфа (он же базис, он же истинность выражения при значении параметра n = 1), а потом доказываем его связность (т. н. шаг индукции, или наличие импликации между вершинами k и k + 1 для любого k > 1).

Аналогичный фокус мы можем выполнить для любого количества параметров и для любых множеств, на которых задано какое-то отношение. Наш орграф может быть не только цепью, как в классическом случае, а иметь самую причудливую форму.