Diagonaalbewijs van Cantor

In het onderstaande voorbeeld worden twee van de eenvoudigste oneindige verzamelingen gebruikt, die van de natuurlijke getallen en die van de positieve breuken. Het idee is om aan te tonen dat beide verzamelingen, N {\displaystyle \mathbb {N} en Q+ {Q^{+}} dezelfde kardinaliteit hebben.

Eerst worden de fracties als volgt in een matrix geplaatst:

1 1 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 3 2 4 2 5 ⋯ 3 1 3 2 3 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}{cccccccc}{{tfrac {1}{1}}&&&{tfrac {1}{2}&&{{tfrac {1}{3}}&&{tfrac {1}{4}}&&&{\displaystyle {{array}{cccccccc}&{{tfrac {1}{1}}&&&{&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&&{\&&&&&&&&}&{\tfrac {2}{1}&&{\tfrac {2}{2}&{\tfrac {2}{3}}&&{\tfrac {2}{4}&&{\tfrac {2}{5}}&\&&&&&&&&}&&{\tfrac {3}{1}}&&{\tfrac {3}{2}&&&{\tfrac {3}{3}}&&{\tfrac {3}{4}&&{\tfrac {3}{5}}&\\&&&&&&&&&&{\tfrac {4}{1}&&&{\tfrac {4}{2}&&{\tfrac {4}{3}&&{\tfrac {4}{4}&&{\tfrac {4}{5}}&\&&&&&&&& }{\tfrac {5}{1}}&&{\tfrac {5}{2}&&{\tfrac {5}{3}}&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&&\dots &&\dvdots &&\dvdots &&\dvdots &&\dvdots &&dvdots &&dvdvdots &&dvdvdots &dith{array}}

Vervolgens worden de getallen geteld, zoals afgebeeld. Breuken die vereenvoudigd kunnen worden, worden weggelaten:

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 5 ⋯ ⋮ ⋮ ⋮ {{{displaystyle}{lclclclc}{lclclclc}{{tfrac {1}{1}}}}{{{color {Blue}(1)}&{\color {MidnightBlue}}&{\tfrac {1}{2}} _{\color {Blue}(2)}&&{\tfrac {1}{3}} _{\color {Blue}(5)}&{\color {MidnightBlue}}&{\tfrac {1}{4}} _{\color {Blue}(6)}&&{\tfrac {1}{5}} _{\color {Blue}(11)}&Nachtblauw, nachtblauw, nachtzwaluw, nachtzwaluw, nachtzwaluw, nachtzwaluw{\color {MidnightBlue}}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&{\tfrac {2}{1}}{\tfrac {2}{2}}} _{\tcolor {Blue}(\cdot )}&&{\tfrac {2}{3}} _{\tcolor {Blue}(7)}&&{\tfrac {2}{4}} _{\tcolor {Blue}(\cdot )}&&{\tfrac {2}{5}}&&{\\\\\\\\\\\kleurenblauw}&{\\kleurenblauw}&&{\\\kleurenblauw}&&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&{\tfrac {3}{1}}&&{\tfrac {3}{2}}} _{\tcolor {Blue}(8)}&&{\tfrac {3}{3}} _{\tcolor {Blue}(\cdot )}&&{\tfrac {3}{4}}&@ @tfrac {4}{1}}&&& @tfrac {4}{2}}&&{\color {Blue}(\cdot )}&&&{\tfrac {4}{3}}&&&{\tfrac {4}{4}&&{\tfrac {4}{5}}&&{\}}&{\color {MidnightBlue}}&{\color {MidnightBlue}}&{\nearrow }&&&&&&&& &{\tfrac {5}{1}}&&&{\tfrac {5}{2}&&&{\tfrac {5}{3}&&&{\tfrac {5}{4}}&

Op die manier worden de breuken geteld:

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 3 1 4 2 3 3 2 4 5 1 5 ⋯ {\displaystyle {begin{array}{cccccccccccccccccccccccccccccccccccc}{{color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{Blue}6}& {Blue}7}& {Blue}8}& {Blue}9}& {Blue}10}& {Blue}11}&{\a6}&{\a6}&\a6}&{\a6}&\a6}&{\a6}&{\a6}&{\a9}&{\a9}&{\a9}&{\a9}&{\a9}&{\a7}&{\a9}&{\a9}&{a8}&{\a9}&{\a9}{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&...en...en...en...en...en...en...en...en...en...en...{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\olor {MidnightBlue}\downarrow }&{\olor {MidnightBlue}\l3pt]1&{\tfrac {1}{2}}&2&3&{{tfrac {1}{3}}&{{tfrac {1}{4}}&{{tfrac {2}{3}}&{{tfrac {3}{2}&4&5&{{tfrac {1}{5}}&{{array}}

Door het weglaten van fracties die nog vereenvoudigd kunnen worden, is er een bijectie die elk element van de natuurlijke getallen associeert met een element van de fracties:

Om aan te tonen dat alle natuurlijke getallen en de breuken dezelfde kardinaliteit hebben, moet het element 0 worden toegevoegd; na elke breuk wordt het negatief toegevoegd;

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 ⋯ {\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}&{Blue}8}& {Blue}9}& {Blue}10}& {Blue}11}& {Blue}12}& {Blue}13}& {Blue}14}& {Blue}15}&{\color {Blue}{\a6}&{\a6}&{\a6}&{\a6}&{\a6}&{\a6}&{\a6}&{\a9}&{\a9}&{\a9}&{\a9}&{\a9}&{\a9}&{a9}{a9}}...en...en...en...en...en...en...en...en...en...en...{\an5}&{\an5}&{\an5}&{\an5}&{\an5}&{\an5}&{\an5}&{\an5}&{\an5}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}{\an8}}&{\an8}{\an8}}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}}

Op die manier is er een volledige bijectie, die aan elk natuurlijk getal een breuk toekent. Met andere woorden: beide verzamelingen hebben dezelfde kardinaliteit. Tegenwoordig heten verzamelingen die evenveel elementen hebben als de verzameling van natuurlijke getallen telbaar. Stellen die minder elementen hebben dan de natuurlijke getallen noemen we hoogstens telbaar. Met die definitie is de verzameling van rationale getallen/fracties telbaar.

Oneindige verzamelingen hebben vaak eigenschappen die tegen de intuïtie ingaan: David Hilbert toonde dit aan in een experiment dat Hilbert's paradox van het Grand Hotel wordt genoemd.

De verzameling van reële getallen heeft niet dezelfde kardinaliteit als die van de natuurlijke getallen; er zijn meer reële getallen dan natuurlijke getallen. Het hierboven geschetste idee beïnvloedde zijn bewijs. In zijn artikel uit 1891 beschouwde Cantor de verzameling T van alle oneindige reeksen van binaire cijfers (d.w.z. elk cijfer is nul of één).

Hij begint met een constructief bewijs van de volgende stelling:

Indien s1, s2, ... , _sn, ... een willekeurige opsomming is van elementen uit T, dan is er altijd een element s van T dat met geen _sn in de opsomming overeenkomt.

Om dit te bewijzen, gegeven een opsomming van elementen uit T, zoals b.v.

De rij s wordt geconstrueerd door het eerste cijfer te kiezen als complementair met het eerste cijfer van s1 (waarbij 0's worden verwisseld met 1's en vice versa), het tweede cijfer als complementair met het tweede cijfer van s2, het derde cijfer als complementair met het derde cijfer van s3, en in het algemeen voor elke n, het n-de cijfer als complementair met het n-de cijfer van _sn. In het voorbeeld levert dit op:

Volgens de constructie verschilt s van elke _sn, aangezien hun n-de cijfers verschillen (in het voorbeeld gemarkeerd). Daarom kan s niet in de opsomming voorkomen.

Gebaseerd op deze stelling, gebruikt Cantor een bewijs van tegenspraak om aan te tonen dat:

De verzameling T is niet telbaar.

Hij neemt voor tegenspraak aan dat T telbaar was. In dat geval zouden al zijn elementen geschreven kunnen worden als een opsomming s1, s2, ... , _sn, ... . Toepassing van de vorige stelling op deze opsomming zou een reeks s opleveren die niet tot de opsomming behoort. Echter, s was een element van T en zou dus in de opsomming moeten staan. Dit is in tegenspraak met de oorspronkelijke aanname, dus moet T ontelbaar zijn.