Диагональный аргумент

Диагональный аргумент (диагональный метод Кантора) — доказательство теоремы Кантора о том, что множество всех подмножеств данного множества имеет бо́льшую мощность, чем само множество. В частности, множество всех подмножеств натурального ряда имеет мощность большую, чем алеф-0, и, значит, не является счётным. Доказательство этого факта основано на следующем диагональном аргументе:

Диагональный аргумент Кантора: Каждое множество записывается как последовательность 0 и 1, где 1 на месте $x$$x$ значит, что $x$$x$ является элементом множества. Красным выделена последовательность на диагонали. Последовательность $s$$s$ является дополнением этой последовательности: $s(x)=1-<!--\; -\; -->s_x(x)$$s(x)=1-s_{x}(x)$. Тогда $s$$s$ отличается от всех $s_x$$s_{x}$ хотя бы в одном месте (а именно — в месте $x$$x$).

Пусть есть взаимнооднозначное соответствие, которое каждому элементу $x$$x$ множества $X$$X$ ставит в соответствие подмножество $s_x$$s_{x}$ множества $X.$$X.$ Пусть $d$$d$ будет множеством, состоящим из элементов $x$$x$ таких, что $x\in <!--\; \in \; -->s_x$$x\in s_{x}$ (диагональное множество). Тогда дополнение этого множества $s=\stackrel{¯<!--\; ¯\; -->}{d}$$s={\overline {d}}$ не может быть ни одним из $s_x.$$s_{x}.$ А следовательно, соответствие было не взаимнооднозначным.

Кантор использовал диагональный аргумент при доказательстве несчётности действительных чисел в 1891 году. (Это не первое его доказательство несчётности действительных чисел, но наиболее простое).

Диагональный аргумент использовался во многих областях математики. Так, например, он является центральным аргументом в теореме Гёделя о неполноте, в доказательстве существования неразрешимого перечислимого множества и, в частности, в доказательстве неразрешимости проблемы остановки.