Cantorjev diagonalni argument

Cantorjev prvi diagonalni argument

V spodnjem primeru sta uporabljeni dve najpreprostejši neskončni množici, množica naravnih števil in množica pozitivnih ulomkov. Ideja je pokazati, da sta obe množici, N {\displaystyle \mathbb {N} } in Q + {\displaystyle \mathbb {Q^{+}} } imata enako kardinalnost.

Najprej deleže poravnamo v matriko, kot sledi:

1 1 1 1 2 1 3 1 4 1 5 ⋯ 2 1 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 5 ⋯ 5 1 5 2 5 3 5 4 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}}}

Nato preštejemo številke, kot je prikazano na sliki. Deleži, ki jih je mogoče poenostaviti, so izpuščeni:

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 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}}}

Na ta način se preštejejo ulomki:

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

Če izpustimo ulomke, ki jih je še vedno mogoče poenostaviti, dobimo bijekcijo, ki vsak element naravnih števil poveže z enim elementom ulomkov:

Da bi pokazali, da imajo vsa naravna števila in ulomki enako kardinalnost, je treba dodati element 0; za vsakim ulomkom je dodan njegov negativ;

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 }\[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}}}

Tako obstaja popolna bijekcija, ki vsakemu naravnemu številu pripiše ulomek. Z drugimi besedami: obe množici imata enako kardinalnost. Danes množice, ki imajo enako število elementov kot množica naravnih števil, imenujemo števne. Množice, ki imajo manj elementov kot množica naravnih števil, se imenujejo kvečjemu števne. S to definicijo je množica racionalnih števil / ulomkov števna.

Neskončne množice imajo pogosto lastnosti, ki so v nasprotju z intuicijo: David Hilbert je to pokazal v poskusu, ki se imenuje Hilbertov paradoks Grand hotela.

Realna števila

Množica realnih števil nima enake kardinalnosti kot množica naravnih števil; realnih števil je več kot naravnih. Zgoraj opisana zamisel je vplivala na njegov dokaz. V svojem članku iz leta 1891 je Cantor obravnaval množico T vseh neskončnih zaporedij binarnih številk (tj. vsaka številka je nič ali ena).

Začne s konstruktivnim dokazom naslednjega izreka:

Če je s₁ , s₂ , ... , s_n , ... poljubno naštevanje elementov iz T, potem vedno obstaja element s iz T, ki mu ne ustreza noben s_n v naštevanju.

To dokažemo tako, da imamo na voljo naštevanje elementov iz T, kot je npr.

Zaporedje s sestavimo tako, da izberemo 1. števko kot komplementarno 1. števki s₁ (zamenjamo 0 za 1 in obratno), 2. števko kot komplementarno 2. števki s₂ , 3. števko kot komplementarno 3. števki s₃ in na splošno za vsak n števko n^th kot komplementarno števki n^th s_n . V primeru to daje

Po konstrukciji se s razlikuje od vsakega s_n , saj se n^th številke razlikujejo (v primeru so označene). Zato se s ne more pojaviti v naštevanju.

Na podlagi tega izreka Cantor s pomočjo dokaza s protislovjem pokaže, da:

Množica T je nepregledna.

Zaradi protislovja predpostavlja, da je bil T prešteven. V tem primeru bi lahko vse njegove elemente zapisali kot naštevanje s₁ , s₂ , ... , s_n , ... . Če bi za to naštevanje uporabili prejšnji izrek, bi dobili zaporedje s, ki ne spada v naštevanje. Vendar pa je s element T in bi zato moral biti v naštevanju. To je v nasprotju s prvotno predpostavko, zato mora biti T nešteven.