Cantor diagonális érve

Cantor első diagonális érve

Az alábbi példa a legegyszerűbb végtelen halmazok közül kettőt használ, a természetes számok és a pozitív törtek halmazát. Az ötlet az, hogy megmutassuk, hogy mindkét halmaz, N {\displaystyle \mathbb {N} } és Q + {\displaystyle \mathbb {Q^{+}} } ugyanolyan kardinalitásúak.

Először is a törteket egy tömbbe rendezzük a következőképpen:

1 1 1 1 2 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 2 2 2 3 2 4 2 2 5 ⋯ 3 1 3 2 2 3 3 3 3 3 3 4 3 5 ⋯ 4 1 4 2 4 3 4 4 4 4 4 5 ⋯ 5 1 5 2 5 3 5 4 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccccccccc}{\tfrac {1}{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}{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}{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}}}}

Ezután a számokat megszámoljuk, ahogyan az látható. Az egyszerűsíthető törteket kihagyjuk:

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 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 3 5 4 5 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclclclclc}{\tfrac {1}{1}}\ _{\color {Blue}(1)}&{\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}{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}}}

Így a törteket is megszámoljuk:

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

A még egyszerűsíthető törtek elhagyásával egy olyan bijekciót kapunk, amely a természetes számok minden egyes elemét a törtek egy-egy eleméhez társítja:

Ahhoz, hogy megmutassuk, hogy az összes természetes szám és a törtek kardinalitása megegyezik, a 0 elemet kell hozzáadni; minden tört után a negatívját is hozzáadjuk;

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 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccccccccccc}{\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 {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 }&{\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}}}}

Így létezik egy teljes bijekció, amely minden természetes számhoz egy törtet társít. Más szóval: mindkét halmaznak ugyanaz a kardinalitása. Ma azokat a halmazokat, amelyeknek ugyanannyi elemük van, mint a természetes számok halmazának, megszámlálhatónak nevezzük. Azokat a halmazokat, amelyeknek kevesebb elemük van, mint a természetes számok halmazának, legfeljebb megszámlálhatónak nevezzük. Ezzel a definícióval a racionális számok/törtek halmaza megszámlálható.

A végtelen halmazok gyakran rendelkeznek olyan tulajdonságokkal, amelyek ellentmondanak az intuíciónak: David Hilbert ezt egy kísérletben mutatta ki, amelyet Hilbert Grand Hotel-paradoxonjának nevezünk.

Valós számok

A valós számok halmaza nem azonos kardinalitású a természetes számok halmazával; több valós szám van, mint természetes szám. A fent vázolt gondolat befolyásolta a bizonyítását. Cantor 1891-es cikkében a bináris számjegyek (azaz minden számjegy nulla vagy egy) végtelen sorozatainak T halmazát vizsgálta.

A következő tétel konstruktív bizonyításával kezdi:

Ha s₁ , s₂ , ... , s_n , ... a T elemek bármelyik felsorolása, akkor mindig van a T-nek egy olyan s eleme, amely nem felel meg a felsorolásban szereplő s elemnek._n

Ennek bizonyítására, adott a T elemeinek felsorolása, mint pl.

Az s sorozatot úgy állítjuk össze, hogy az 1. számjegyet az s₁ 1. számjegyének komplementerének választjuk (a 0-kat felcseréljük az 1-ekkel és fordítva), a 2. számjegyet az s₂ 2. számjegyének komplementerének, a 3. számjegyet az s₃ 3. számjegyének, és általában minden n esetében az n^th számjegyet az s_n n^th számjegyének komplementerének:

A konstrukció szerint s különbözik minden s_n -től, mivel n^th számjegyük különbözik (a példában kiemelve). Ezért s nem fordulhat elő a felsorolásban.

E tétel alapján Cantor ezután egy ellentmondásos bizonyítással kimutatja, hogy:

A T halmaz megszámlálhatatlan.

Ellentmondás esetén feltételezi, hogy T megszámlálható volt. Ebben az esetben minden elemét fel lehetne írni egy felsorolásként s₁ , s₂ , ... , s_n , ... ... . Az előző tételt erre a felsorolásra alkalmazva egy olyan s sorozatot kapnánk, amely nem tartozik a felsoroláshoz. Azonban s a T eleme volt, és ezért a felsorolásban kell lennie. Ez ellentmond az eredeti feltételezésnek, tehát T-nek megszámlálhatatlan kell lennie.