Диагональный аргумент
Диагональный аргумент (диагональный метод Кантора) — доказательство теоремы Кантора о том, что множество всех подмножеств данного множества имеет бо́льшую мощность, чем само множество. В частности, множество всех подмножеств натурального ряда имеет мощность большую, чем алеф-0, и, значит, не является счётным[1]. Доказательство этого факта основано на следующем диагональном аргументе:
- Пусть есть взаимнооднозначное соответствие, которое каждому элементу множества ставит в соответствие подмножество множества Пусть будет множеством, состоящим из элементов таких, что (диагональное множество). Тогда дополнение этого множества не может быть ни одним из А следовательно, соответствие было не взаимнооднозначным.
Кантор использовал диагональный аргумент при доказательстве несчётности действительных чисел в 1891 году. (Это не первое его доказательство несчётности действительных чисел, но наиболее простое)[2].
Диагональный аргумент использовался во многих областях математики. Так, например, он является центральным аргументом в теореме Гёделя о неполноте, в доказательстве существования неразрешимого перечислимого множества и, в частности, в доказательстве неразрешимости проблемы остановки[3].