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

В приведенном ниже примере используются два простейших бесконечных множества - множество натуральных чисел и множество положительных дробей. Идея состоит в том, чтобы показать, что оба эти множества, N {\displaystyle \mathbb {N} } и Q+ {\displaystyle \mathbb {Q^{+}}  имеют одинаковую кардинальность.

Сначала дроби выравниваются в массив следующим образом:

1 1 1 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 2 3 2 4 2 5 ⋯ 3 1 3 2 3 3 4 3 5 ⋯ 4 1 4 2 4 3 4 4 5 ⋯ 5 1 5 2 5 3 5 4 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccc}{\tfrac {1}{1}}&&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&\cdots \\\&&&&&&&&&\\{\tfrac {2}{1}}&&&{\tfrac {2}{2}}&&&{\tfrac {2}{3}}&&{\tfrac {2}{4}}&&{\tfrac {2}{5}}&\cdots \\\&&&&&&&&&\\{\tfrac {3}{1}}&&&{\tfrac {3}{2}}&&{\tfrac {3}{3}}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\\&&&&&&&&&&&\\\\{\tfrac {4}{1}}&&&{\tfrac {4}{2}}&&&{\tfrac {4}{3}}&&&{\tfrac {4}{4}}&&&{\tfrac {4}{5}}&\cdots \\\&&&&&&&&&\\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&&{\tfrac {5}{3}}&&&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\end{array}}}.

Далее подсчитываются числа, как показано на рисунке. Дроби, которые можно упростить, опускаются:

1 1 ( 1 ) → 1 2 ( 2 ) 1 3 ( 5 ) → 1 4 ( 6 ) 1 5 ( 11 ) → ↙ ↙ 2 1 ( 3 ) 2 2 ( ⋅ ) 2 3 ( 7 ) 2 4 ( ⋅ ) 2 5 ⋯ ↓ ↙ 3 1 ( 4 ) 3 2 ( 8 ) 3 3 ( ⋅ ) 3 4 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 4 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclc}{\tfrac {1}{1}}\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{2}}\ _{\color {Blue}(2)}&&&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}\ _{\color {Blue}(6)}&&&{\tfrac {1}{5}}\ _{\color {Blue}(11)}&&{\color {MidnightBlue}\rightarrow }\\\&{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&&{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&\\\\{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&&&{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {2}{3}}\ _{\color {Blue}(7)}&&&{\tfrac {2}{4}}\ _{\color {Blue}(\cdot )}&&&&{\tfrac {2}{4}}&{\tfrac {2}{5}}&\cdots \\\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&.{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&\\{\tfrac {3}{1}}\ _{\color {Blue}(4)}&&&&{\tfrac {3}{2}}\ _{\color {Blue}(8)}&&&{\tfrac {3}{3}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {3}{4}}&&&&{\tfrac {3}{5}}&\cdots \\\&{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&&&&\\\{\tfrac {4}{1}}\ _{\color {Blue}(9)}&&&{\tfrac {4}{2}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {4}{3}}&&&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\\{\tfrac {5}{1}}\ _{\color {Blue}(10)}&&&{\tfrac {5}{2}}&&&{\tfrac {5}{3}}&&&{\tfrac {5}{4}}&&&{\tfrac {5}{4}}&{\tfrac {5}{5}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\\\\end{array}}}}

Таким образом, дроби будут подсчитаны:

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 1 2 2 3 1 3 1 4 2 3 2 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}\cdots }\\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\\\[3pt]1&{\tfrac {1}{2}}&2&3&{\tfrac {1}{3}}&{\tfrac {1}{4}}&{\tfrac {2}{3}}&{\tfrac {3}{2}}&4&5&{\tfrac {1}{5}}&\cdots \\\\end{array}}}.

Если опустить дроби, которые еще можно упростить, то получится биекция, которая связывает каждый элемент натуральных чисел с одним элементом дробей:

Чтобы показать, что все натуральные числа и дроби имеют одинаковую кардинальность, необходимо добавить элемент 0; после каждой дроби добавляется ее отрицательная часть;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 2 - 1 2 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 ⋯ {\displaystyle {\begin{array}{cccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}& {\color {Blue}3}& {\color {Blue}4}& {\color {Blue}5}& {\color {Blue}6}& {\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}12}&{\color {Blue}13}&{\color {Blue}14}&{\color {Blue}15}& {\color {Blue}15}&{\color {Blue}\cdots }\\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\\\[3pt]0&1&-1&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&2&-2&3&-3&{\tfrac {1}{3}}&-{\tfrac {1}{3}}&{\tfrac {1}{4}}&-{\tfrac {1}{4}}&{\tfrac {2}{3}}&-{\tfrac {2}{3}}&\cdots \\\end\end{array}}}}.

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

Бесконечные множества часто обладают свойствами, которые противоречат интуиции: Дэвид Гильберт показал это в эксперименте, который называется парадоксом Гильберта в Гранд Отеле.

Множество действительных чисел не имеет той же кардинальности, что и множество натуральных чисел; действительных чисел больше, чем натуральных. Идея, изложенная выше, повлияла на его доказательство. В своей статье 1891 года Кантор рассмотрел множество T всех бесконечных последовательностей двоичных цифр (т.е. каждая цифра - ноль или единица).

Он начинает с конструктивного доказательства следующей теоремы:

Если s₁ , s₂ , ... , s_n , ... - это любое перечисление элементов из T, то всегда существует элемент s из T, которому соответствует ни один s_n в этом перечислении.

Чтобы доказать это, зададим перечисление элементов из T, например.

Последовательность s строится путем выбора 1-й цифры, дополняющей 1-ю цифру s₁ (меняя 0 на 1 и наоборот), 2-й цифры, дополняющей 2-ю цифру s₂ , 3-й цифры, дополняющей 3-ю цифру s₃ , и, вообще говоря, для каждого n, цифры n^th , дополняющей цифру n^th s_n . В примере это дает:

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

Основываясь на этой теореме, Кантор использует доказательство через противоречие, чтобы показать, что:

Множество T является несчетным.

Он предположил, что T является счетным. В этом случае все его элементы можно записать в виде перечисления s₁ , s₂ , ... , s_n , ... . Применение предыдущей теоремы к этому перечислению дало бы последовательность s, не принадлежащую перечислению. Однако s является элементом T и поэтому должна быть в перечислении. Это противоречит первоначальному предположению, поэтому T должно быть несчетным.