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

Пусть есть взаимнооднозначное соответствие , которое каждому элементу ${\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 году. (Это не первое его доказательство несчётности действительных чисел, но наиболее простое) .

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

Примечания