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

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

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

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

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

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

Примечания

1. Диагональный метод Кантора  (неопр.). studfiles.net.
2. Gray, Robert (1994), "Georg Cantor and Transcendental Numbers" (PDF), American Mathematical Monthly, 101: 819—832, doi:10.2307/2975129, Архивировано (PDF) 21 января 2022, Дата обращения: 15 января 2019 Источник  (неопр.). Дата обращения: 15 января 2019. Архивировано 21 января 2022 года.
3. John B. Bacon, Michael Detlefsen, David Charles McCarty. Diagonal argument // Logic from A to Z: The Routledge Encyclopedia of Philosophy Glossary of Logical and Mathematical Terms. — Routledge, 2013-09-05. — 126 с. — ISBN 9781134970971.