Argumentul diagonalei lui Cantor

Exemplul de mai jos utilizează două dintre cele mai simple seturi infinite, cel al numerelor naturale și cel al fracțiilor pozitive. Ideea este de a arăta că ambele seturi, N {\displaystyle \mathbb {N} } și Q + {\displaystyle \mathbb {Q^{+}}. } au aceeași cardinalitate.

În primul rând, fracțiile sunt aliniate într-o matrice, după cum urmează:

1 1 1 1 1 2 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 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 4 5 ⋯ 5 1 5 2 5 3 5 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccccc}{\tfrac {1}{1}}}&&{\tfrac {1}{2}}&&&{\tfrac {1}{3}}&&&{\tfrac {1}{4}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&&\cdots \&&&&&&&&&\\\{\tfrac {2}{1}}&&{\tfrac {2}{2}}&&&{\tfrac {2}{2}}&&&{\tfrac {2}{3}}&&{\tfrac {2}{4}}&&{\tfrac {2}{5}}&\cdots \&&&&&&&&&\{\{\tfrac {3}{1}}&&{\tfrac {3}{2}}&&{\tfrac {3}{3}{3}}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\\&&&&&&&&&&\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&{\tfrac {4}{5}}\cdots \\&&&&&&&&&\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&&{\tfrac {5}{3}&&&{\tfrac {5}{4}}&&&{\tfrac {5}{5}}&&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\\end{array}}}}.

În continuare, numerele sunt numărate, după cum se arată. Fracțiile care pot fi simplificate sunt omise:

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 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 4 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 3 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclclclc}{\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}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&\\\{\tfrac {2}{1}}}\ _{\color {Blue}(3)}&&&{\tfrac {2}{2}{2}}\ {{\tfrac {{\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}}\ {\tfrac {\color {Albastru}(8)}&&&{\tfrac {3}{3}}\ {\tfrac {\color {Albastru}(\cdot )}&&{\tfrac {3}{4}}&&&{\tfrac {3}{5}}&&\cdots \\&{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&&&&\\{\tfrac {4}{1}}\ _{\color {Albastru}(9)}&&{\tfrac {4}{2}}\ _{\color {Albastru}(\cdot )}&&{\tfrac {4}{3}}&&&{\tfrac {4}{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}}}}

În acest fel, fracțiunile sunt numărate:

1 2 3 4 5 6 7 7 8 8 9 10 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 2 3 1 3 1 3 1 4 2 3 3 3 3 2 4 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccccc}{\color {Blue}1}}&{\color {Albastru}2}&{\color {Albastru}3}&{\color {Albastru}4}&{\color {Albastru}5}&{\color {Albastru}6}&{\color {Albastru}7}&{\color {Albastru}8}&{\color {Albastru}9}&{\color {Albastru}10}&{\color {Albastru}11}&{\color {Blue} {Blue}\cdots }\[3pt]{\color {MidnightBlue} {MidnightBlue} {downarrow }&{\color {MidnightBlue} {downarrow }&{\color {MidnightBlue} {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}}}}

Prin omiterea fracțiilor care mai pot fi simplificate, există o bijecție care asociază fiecare element al numerelor naturale cu un element al fracțiilor:

Pentru a arăta că toate numerele naturale și fracțiile au aceeași cardinalitate, trebuie adăugat elementul 0; după fiecare fracție se adaugă negativul acesteia;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 2 - 1 2 2 - 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 - 2 3 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}7}&{\color {Albastru}8}&{\color {Albastru}9}&{\color {Albastru}10}&{\color {Albastru}11}&{\color {Albastru}12}&{\color {Albastru}13}&{\color {Albastru}14}&{\color {Albastru}15}&{\color {Blue} {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 }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\\[3pt]0&1&-1&&{\tfrac {1}{2}}&-{\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}}}}

În acest fel, există o bijecție completă care asociază o fracție fiecărui număr natural. Cu alte cuvinte: ambele seturi au aceeași cardinalitate. Astăzi, seturile care au același număr de elemente ca și setul numerelor naturale se numesc numărabile. Seturile care au mai puține elemente decât numerele naturale se numesc cel mult numărabile. Cu această definiție, ansamblul numerelor raționale / fracțiilor este numărabil.

Seturile infinite au adesea proprietăți care contravin intuiției: David Hilbert a arătat acest lucru într-un experiment numit Paradoxul lui Hilbert de la Grand Hotel.

Ansamblul numerelor reale nu are aceeași cardinalitate cu cea a numerelor naturale; există mai multe numere reale decât numere naturale. Ideea expusă mai sus a influențat demonstrația sa. În articolul său din 1891, Cantor a considerat setul T al tuturor secvențelor infinite de cifre binare (adică fiecare cifră este zero sau unu).

El începe cu o demonstrație constructivă a următoarei teoreme:

Dacă s₁ , s₂ , ... , s_n , ... este orice enumerare de elemente din T, atunci există întotdeauna un element s din T care nu corespunde niciunui s_n din enumerare.

Pentru a demonstra acest lucru, dată fiind o enumerare de elemente din T, ca de exemplu.

Secvența s este construită prin alegerea primei cifre ca fiind complementară primei cifre din s₁ (schimbând 0 cu 1 și invers), a doua cifră ca fiind complementară celei de-a doua cifre din s₂ , a treia cifră ca fiind complementară celei de-a treia cifre din s₃ și, în general, pentru fiecare n, a n^th cifră ca fiind complementară celei de-a n^th cifre din s_n . În exemplu, rezultă:

Prin construcție, s diferă de fiecare s_n , deoarece cele n cifre^th diferă (evidențiate în exemplu). Prin urmare, s nu poate apărea în enumerare.

Pe baza acestei teoreme, Cantor folosește apoi o demonstrație prin contradicție pentru a arăta că:

Setul T este nenumărabil.

El presupune pentru contradicție că T era numărabil. În acest caz, toate elementele sale ar putea fi scrise ca o enumerare s₁ , s₂ , ... , s_n , ... ... . Aplicarea teoremei anterioare la această enumerare ar produce o secvență s care nu aparține enumerării. Cu toate acestea, s a fost un element al lui T și, prin urmare, ar trebui să facă parte din enumerare. Acest lucru contrazice ipoteza inițială, deci T trebuie să fie nenumărabil.