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

В теории множеств диагональный аргумент Кантора , также называемый аргументом диагонализации , аргументом диагональной косой черты , антидиагональным аргументом , диагональным методом и доказательством диагонализации Кантора , был опубликован в 1891 году Георгом Кантором как математическое доказательство существования бесконечных множеств . которому нельзя поставить однозначное соответствие с бесконечным множеством натуральных чисел . ^{[1] [2] : 20–  [3]} Такие множества теперь известны как несчетные множества ., а размер бесконечных множеств теперь рассматривается с помощью теории количественных чисел , которую начал Кантор.

Диагональный аргумент не был первым доказательством Кантора несчетности действительных чисел , появившимся в 1874 году. ^{[4] [5]} Однако он демонстрирует общую технику, которая с тех пор использовалась в широком диапазоне доказательств, [ ^6] первая из теорем Гёделя о неполноте ^[2] и ответ Тьюринга на Entscheidungsproblem . Аргументы диагонализации часто также являются источником противоречий, таких как парадокс Рассела ^{[7] [8]} и парадокс Ричарда . ^{[2] : 27}

Кантор рассматривал множество T всех бесконечных последовательностей двоичных цифр (т . е. каждая цифра равна нулю или единице). ^{[примечание 1]} Он начинает с конструктивного доказательства следующей леммы :

Далее строится последовательность s путем выбора 1-й цифры как дополнительной к 1-й цифре _s1 ( замена 0s на 1s и наоборот), 2-й цифры как дополнительной ко 2-й цифре s2 _, 3 -й цифры как дополнительно к 3-й цифре s ₃ , и вообще для каждого n , n ^-я цифра является дополнительной к n ^-й цифре s _n . Для приведенного выше примера это дает:

По построению s является элементом T , который отличается от каждого s _n , поскольку их n ^-е цифры различаются (выделено в примере). Следовательно, s не может встречаться в перечислении.

Доказательство начинается с предположения, что T счетно . Тогда все его элементы можно записать в виде перечисления s ₁ , s ₂ , ... , s _n , ... . Применение предыдущей леммы к этому перечислению дает последовательность s , которая является членом T , но не входит в перечисление. Однако, если T перечисляется, то каждый член T , включая этот s , находится в перечислении. Это противоречие означает, что исходное предположение неверно. Следовательно, T несчетно. ^[1]

Иллюстрация диагонального аргумента Кантора (по основанию 2) существования несчетных множеств . Последовательность внизу не может встречаться нигде в перечислении последовательностей выше.

Бесконечное множество может иметь ту же мощность , что и собственное подмножество самого себя, как демонстрирует изображенная биекция f ( x ) = 2 x от натуральных до четных чисел . Тем не менее, как показывает диагональный аргумент Кантора, существуют бесконечные множества различной мощности.

Функция tan: (−π/2,π/2) → R

Иллюстрация обобщенного диагонального аргумента: множество T = { n ∈ : n ∉ f ( n )} внизу не может встречаться нигде в диапазоне f : → P ( ). Пример отображения f соответствует примеру перечисления s на картинке выше .${\ Displaystyle \ mathbb {N}}$${\ Displaystyle \ mathbb {N}}$${\ Displaystyle \ mathbb {N}}$