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

---

Трансфинитная индукция — метод доказательства, обобщающий математическую индукцию на случай несчётного числа значений параметра.

Пусть ${\displaystyle M}$ — фундированное множество (то есть частично упорядоченное множество, в котором каждое непустое подмножество имеет минимальный элемент), ${\displaystyle P(x)}$ при ${\displaystyle x\in M}$ — некоторое утверждение. Пусть для любого ${\displaystyle x\in M}$ из того, что ${\displaystyle P(y)}$ истинно для всех ${\displaystyle y<x}$, следует, что верно ${\displaystyle P(x)}$. Тогда утверждение ${\displaystyle P(x)}$ верно для любого ${\displaystyle x}$.

Математическая индукция является частным случаем трансфинитной индукции. Действительно, пусть ${\displaystyle M}$ — множество натуральных чисел (частный случай вполне упорядоченного множества). Тогда утверждение трансфинитной индукции превращается в следующее: если для любого натурального ${\displaystyle n}$ из одновременной истинности утверждений ${\displaystyle P(1)}$, ${\displaystyle P(2)}$, ${\displaystyle \ldots }$, ${\displaystyle P(n-1)}$ следует истинность утверждения ${\displaystyle P(n)}$, то истинны все утверждения ${\displaystyle P(n)}$. При этом база индукции, то есть ${\displaystyle P(1)}$, оказывается тривиальным частным случаем при ${\displaystyle n=1}$.

Во многих случаях трансфинитная индукция используется совместно с теоремой Цермело, утверждающей, что любое множество можно вполне упорядочить. Теорема Цермело эквивалентна аксиоме выбора, поэтому доказательство получается неконструктивным.

В качестве примера докажем, что можно провести некоторое множество окружностей так, чтобы через каждую точку плоскости проходило ровно 2 окружности. (В данном случае можно привести и явную конструкцию, однако для случая трёх окружностей доказательство ниже лишь слегка изменяется, а явная конструкция пока неизвестна).

---