Диагоналният аргумент на Кантор

Първият диагонален аргумент на Кантор

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

Първо, дробните числа се подреждат в масив, както следва:

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 3 3 4 3 5 ⋯ 4 1 4 2 4 3 4 4 4 5 ⋯ 5 1 5 2 5 3 5 4 5 5 5 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccc}{\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 &\\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 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 4 5 5 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}{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}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}}

По този начин се отчитат дробните части:

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 3 1 3 1 4 2 3 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 }\[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}{{ccccccccccccc}{\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}\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 }&{\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{array}}}

По този начин съществува пълна биекция, която свързва дроб с всяко естествено число. С други думи: двете множества имат еднакъв кардинален брой. Днес множествата, които имат същия брой елементи като множеството на естествените числа, се наричат изброими. Множества, които имат по-малко елементи от множеството на естествените числа, се наричат най-много преброими. С тази дефиниция множеството на рационалните числа/дробите е изброимо.

Безкрайните множества често имат свойства, които противоречат на интуицията: Дейвид Хилбърт показа това в един експеримент, наречен "Парадоксът на Хилбърт в Гранд Хотел".

Реални числа

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

Той започва с конструктивно доказателство на следната теорема:

Ако 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 трябва да е неизброим.