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

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

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

Пусть есть взаимнооднозначное соответствие, которое каждому элементу [math]\displaystyle{ x }[/math] множества [math]\displaystyle{ X }[/math] ставит в соответствие подмножество [math]\displaystyle{ s_x }[/math] множества [math]\displaystyle{ X. }[/math] Пусть [math]\displaystyle{ d }[/math] будет множеством, состоящим из элементов [math]\displaystyle{ x }[/math] таких, что [math]\displaystyle{ x\in s_x }[/math] (диагональное множество). Тогда дополнение этого множества [math]\displaystyle{ s=\overline d }[/math] не может быть ни одним из [math]\displaystyle{ s_x. }[/math] А следовательно, соответствие было не взаимнооднозначным.

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

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