Трансфинитная индукция

Трансфини́тная инду́кция, принцип, позволяющий утверждать суждение ${\displaystyle A(x)}$ для любого элемента ${\displaystyle x}$ вполне упорядоченного класса ${\displaystyle E}$, если установлено, что для всякого ${\displaystyle z\in E}$ из истинности ${\displaystyle A(y)}$ для всех ${\displaystyle y<z}$ следует истинность ${\displaystyle A(z)}$:

${\displaystyle \forall z(\forall y(y<z\rightarrow A(y))\longrightarrow A(z))\longrightarrow \forall xA(x)}$.

Когда ${\displaystyle E}$ – отрезок ординалов, меньших ${\displaystyle \alpha }$, эквивалентна такая формулировка: если ${\displaystyle A(0)}$, ${\displaystyle A(\sigma )\rightarrow A(\sigma +1)}$ и ${\displaystyle A(\sigma )}$ сохраняется при предельном переходе

${\displaystyle {\text{ (т. е. }}\left.\sigma =\sup \left\{\sigma _{i}\right\}\wedge \forall iA\left(\sigma _{i}\right)\rightarrow A(\sigma )\right)}$,

то ${\displaystyle A(\sigma )}$ для любого ${\displaystyle \sigma <\alpha }$. Частным случаем трансфинитной индукции является математическая индукция. Если отношение ${\displaystyle <}$ на классе ${\displaystyle E}$ задаёт фундированное дерево (т. е. дерево, все ветви которого обрываются), то трансфинитная индукция для такого ${\displaystyle E}$ эквивалентна бар-индукции: из того, что ${\displaystyle A}$ верно для всех концевых вершин и наследуется при движении от них к корню, следует, что ${\displaystyle A}$ верно для корня. Эта форма важна в интуиционистской математике. Доказуемостью трансфинитной индукции до различных ординалов измеряют дедуктивную силу формальных систем.