Kantoro įstrižainės argumentas

Pirmasis Kantoro įstrižainės argumentas

Toliau pateiktame pavyzdyje naudojamos dvi paprasčiausios begalinės aibės - natūraliųjų skaičių ir teigiamų trupmenų aibės. Norima parodyti, kad abi šios aibės, N {\displaystyle \mathbb {N} } ir Q + {\displaystyle \mathbb {Q^{+}} } yra vienodo kardinalumo.

Pirmiausia frakcijos išlyginamos į masyvą taip:

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

Tada skaičiai suskaičiuojami, kaip parodyta paveikslėlyje. Dalys, kurias galima supaprastinti, neįtraukiamos:

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}{lclclclclc}{\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 {Mėlyna}(10)}&&{\tfrac {5}{2}}&&&{\tfrac {5}{3}}&&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}}

Taip bus skaičiuojamos dalybos:

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

Atmetus trupmenas, kurias vis dar galima supaprastinti, gaunama bijekcija, kuri kiekvieną natūraliųjų skaičių elementą susieja su vienu trupmenos elementu:

Norint parodyti, kad visi natūralieji skaičiai ir trupmenos turi tą patį kardinalumą, reikia pridėti elementą 0; po kiekvienos trupmenos pridedamas jos neiginys;

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}{\ccccccccccccccccccccc}{\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}15}&{\color {Mėlyna}\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}}&-{\tfrac {2}{3}}&\cdots \\\\end{array}}}

Tokiu būdu yra visiška bijekcija, kuri kiekvienam natūraliajam skaičiui priskiria frakciją. Kitaip tariant, abiejų aibių kardinalumas vienodas. Šiandien aibės, turinčios tiek pat elementų, kiek ir natūraliųjų skaičių aibė, vadinamos suskaičiuojamomis. Aibės, turinčios mažiau elementų nei natūraliųjų skaičių aibė, vadinamos daugiausiai suskaičiuojamomis. Pagal šią apibrėžtį racionaliųjų skaičių / trupmenų aibė yra suskaičiuojama.

Begalinės aibės dažnai pasižymi intuicijai prieštaraujančiomis savybėmis: Davidas Hilbertas tai įrodė eksperimente, kuris vadinamas Hilberto "Grand Hotel" paradoksu.

Realieji skaičiai

Realiųjų skaičių aibės kardinalumas nėra toks pat kaip natūraliųjų skaičių; realiųjų skaičių yra daugiau nei natūraliųjų skaičių. Pirmiau išdėstyta mintis turėjo įtakos jo įrodymui. 1891 m. straipsnyje Kantoras nagrinėjo visų begalinių dvejetainių skaitmenų sekų (t. y. kiekvienas skaitmuo yra nulis arba vienetas) aibę T.

Jis pradeda konstruktyviu šios teoremos įrodymu:

Jei s₁ , s₂ , ... , s_n , ... yra bet koks T elementų išvardijimas, tai visada yra T elementas s, kurio išvardijime neatitinka joks s ._n

Norėdami tai įrodyti, turėdami T elementų sąrašą, pvz.

Seka s sudaroma pasirenkant 1-ąjį skaitmenį kaip papildantį 1-ąjį s₁ skaitmenį (sukeičiant 0 su 1 ir atvirkščiai), 2-ąjį skaitmenį kaip papildantį 2-ąjį s₂ skaitmenį, 3-iąjį skaitmenį kaip papildantį 3-iąjį s₃ skaitmenį ir apskritai kiekvienam n - n^th skaitmenį kaip papildantį n^th skaitmenį s_n . Pateiktame pavyzdyje gaunama tokia seka:

Pagal konstrukciją s skiriasi nuo kiekvieno s_n , nes skiriasi jų n^th skaitmenų (pavyzdyje jie paryškinti). Todėl s negali atsirasti išvardijime.

Remdamasis šia teorema, Kantoras įrodo, kad:

Aibė T yra neįskaitoma.

Jis daro prielaidą, kad T buvo suskaičiuojamas. Tokiu atveju visus jos elementus galima užrašyti kaip išvardijimą s₁ , s₂ , ... , s_n , ... . Taikant ankstesnę teoremą šiam išvardijimui, gautume seką s, kuri nepriklauso išvardijimui. Tačiau s buvo T elementas, todėl jis turėtų būti išvardijime. Tai prieštarauja pradinei prielaidai, todėl T turi būti nesuskaičiuojama.