Metoda przekątniowa

Argument Cantora z przekątnej to matematyczna metoda dowodzenia, że dwa nieskończone zbiory mają tę samą kardynalność. Cantor opublikował na ten temat artykuły w latach 1877, 1891 i 1899. Jego pierwszy dowód argumentu z przekątnej został opublikowany w 1890 roku w czasopiśmie Niemieckiego Towarzystwa Matematycznego (Deutsche Mathematiker-Vereinigung). Według Cantora dwa zbiory mają tę samą kardynalność, jeśli do każdego elementu pierwszego zbioru można przyporządkować element z drugiego zbioru, a do każdego elementu drugiego zbioru można przyporządkować element z pierwszego zbioru. To stwierdzenie sprawdza się w przypadku zbiorów o skończonej liczbie elementów. Jest mniej intuicyjne dla zbiorów z nieskończoną liczbą elementów.

Pierwszy argument Cantora z przekątnej

Poniższy przykład wykorzystuje dwa najprostsze nieskończone zbiory, zbiór liczb naturalnych i zbiór ułamków dodatnich. Chodzi o to, by pokazać, że oba te zbiory, N { {{displaystyle \mathbb {\i0}} } $\mathbb {N}$ i Q + { {displaystyle \mathbb {Q^{+}} } $\mathbb {Q^{+}}$ mają tę samą kardynalność.

Najpierw ułamki są wyrównywane w tablicy, w następujący sposób:

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

Następnie liczby te są liczone w sposób przedstawiony na rysunku. Ułamki, które można uprościć, pomijamy:

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 { {begin{array}{lclclclclc}{tfrac {1}{1}}}}}{{tfrac {1}{2}}} {{tfrac {1}{3}}} {{color {Blue}(5)}&&{{color {MidnightBlue}}&&{tfrac {1}{4}}} _{color {Blue}(6)}&{tfrac {1}{5}}} _{color {Blue}(11)}&{{color {MidnightBlue}}rightarrow }&&{color {MidnightBlue}}swarrow }&&{color {MidnightBlue}}nearrow }&{{tfrac {2}{1}}}}&&{tfrac {2}{1}}} {{tfrac {2}{1}}} {{tfrac {2}{1}}} {{tfrac {2}{1}}}(3)}&&&{{tfrac {2}{2}}} {{tfrac {2}{3}}} {{color {Blue}(7)}&&{tfrac {2}{4}}} {{color {Blue}(\ot )}&&&&&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}(\ot )}&&{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}}}&&&{tfrac {5}{2}}&&{tfrac {5}{3}}&&{tfrac {5}{4}}&&{tfrac {5}{5}}&&&cdots &&vdots &&vdots &&vdots &&vdots &&vdots &&end{array}}} ${\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 {Blue}(10)}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}$

W ten sposób liczone są ułamki:

{{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}}{{color {Blue}}}&{color {MidnightBlue}}&{color {MidnightBlue}}&{color {MidnightBlue}}}&{color {MidnightBlue}}}{{color {MidnightBlue}}downarrow }&{color {MidnightBlue}downarrow }&{color {MidnightBlue}}downarrow }&{{color {MidnightBlue}}downarrow }&{color {MidnightBlue}}&{color {MidnightBlue}}downarrow }&{color {MidnightBlue}}&{color {MidnightBlue}}}1&{tfrac {1}{2}}&2&3&1}{3}}&{tfrac {1}{3}}&{tfrac {1}{4}}&{tfrac {2}{3}}&{tfrac {3}{2}}&4&5&{tfrac {1}{5}}&{tfrac {1}{5}}}&}end{array}}} ${\begin{array}{cccccccccccccccc}{\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}}$

Pomijając ułamki, które nadal można upraszczać, istnieje bijekcja, która kojarzy każdy element liczb naturalnych z jednym elementem ułamków:

Aby pokazać, że wszystkie liczby naturalne i ułamki mają tę samą kardynalność, trzeba dodać element 0; po każdym ułamku dodaje się jego ujemną wartość;

{{color {Blue}2}&{color {Blue}3}&{color {Blue}4}&{color {Blue}5}&{color {Blue}6}&{color {Blue}7}&{color {Blue}}{{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}}{{color {Blue}}}&{color {MidnightBlue}}&{color {MidnightBlue}}&{color {MidnightBlue}}}&{color {MidnightBlue}}&{color {MidnightBlue}}}&{color {MidnightBlue}}}{{color {MidnightBlue}}&{color {MidnightBlue}}&{color {MidnightBlue}}&{color {MidnightBlue}}}&{color {MidnightBlue}}&{{color {MidnightBlue}}}}{{color {MidnightBlue}}}&{color {MidnightBlue}}&{color {MidnightBlue}}&{color {MidnightBlue}}}&{color {MidnightBlue}}}&{color {MidnightBlue}}}&{color {MidnightBlue}}}&{{color {MidnightBlue}}}}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 \i0}end{array}}} ${\begin{array}{cccccccccccccccc}{\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}}$

W ten sposób istnieje pełny bijekcja, która przypisuje ułamek do każdej liczby naturalnej. Innymi słowy: oba zbiory mają tę samą kardynalność. Dziś zbiory, które mają tyle samo elementów co zbiór liczb naturalnych nazywamy policzalnymi. Zbiory, które mają mniej elementów niż liczby naturalne nazywamy co najwyżej policzalnymi. Przy takiej definicji, zbiór liczb racjonalnych / ułamków jest policzalny.

Zbiory nieskończone często mają własności sprzeczne z intuicją: David Hilbert pokazał to w eksperymencie, który nazywany jest paradoksem Hilberta z Grand Hotelu.

Liczby rzeczywiste

Zbiór liczb rzeczywistych nie ma tej samej kardynalności co zbiór liczb naturalnych; liczb rzeczywistych jest więcej niż liczb naturalnych. Przedstawiona powyżej idea wpłynęła na jego dowód. W swoim artykule z 1891 roku Cantor rozważał zbiór T wszystkich nieskończonych ciągów cyfr binarnych (tzn. każda cyfra jest zerem lub jedynką).

Zaczyna od konstruktywnego dowodu następującego twierdzenia:

Jeżeli s1, s2, ... , _sn, ... jest dowolną wyliczanką elementów z T, to zawsze istnieje element s z T, któremu nie odpowiada żaden _sn w wyliczance.

Aby to udowodnić, podajemy wyliczenie elementów z T, takie jak np.

s1 =	(0,	0,	0,	0,	0,	0,	0,	...)
s2 =	(1,	1,	1,	1,	1,	1,	1,	...)
s3 =	(0,	1,	0,	1,	0,	1,	0,	...)
s4 =	(1,	0,	1,	0,	1,	0,	1,	...)
s5 =	(1,	1,	0,	1,	0,	1,	1,	...)
s6 =	(0,	0,	1,	1,	0,	1,	1,	...)
s7 =	(1,	0,	0,	0,	1,	0,	0,	...)
...

Sekwencję s konstruuje się wybierając pierwszą cyfrę jako komplementarną do pierwszej cyfry s1 (zamieniając 0 na 1 i odwrotnie), drugą cyfrę jako komplementarną do drugiej cyfry s2, trzecią cyfrę jako komplementarną do trzeciej cyfry s3, oraz ogólnie dla każdego n, n-tą cyfrę jako komplementarną do n-tej cyfry _sn. W przykładzie otrzymujemy:

s1	=	(0,	0,	0,	0,	0,	0,	0,	...)
s2	=	(1,	1,	1,	1,	1,	1,	1,	...)
s3	=	(0,	1,	0,	1,	0,	1,	0,	...)
s4	=	(1,	0,	1,	0,	1,	0,	1,	...)
s5	=	(1,	1,	0,	1,	0,	1,	1,	...)
s6	=	(0,	0,	1,	1,	0,	1,	1,	...)
s7	=	(1,	0,	0,	0,	1,	0,	0,	...)
...

s	=	(1,	0,	1,	1,	1,	0,	1,	...)

Z konstrukcji wynika, że s różni się od każdego _sn, ponieważ ich n-te cyfry są różne (zaznaczone w przykładzie). Stąd s nie może wystąpić w wyliczeniu.

Na podstawie tego twierdzenia Cantor przeprowadza następnie dowód przez sprzeczność, aby wykazać, że:

Zbiór T jest niepoliczalny.

Zakłada on dla sprzeczności, że T jest policzalny. W takim przypadku wszystkie jego elementy można by zapisać w postaci wyliczenia s1, s2, ... , _sn, ... . Zastosowanie poprzedniego twierdzenia do tej wyliczanki dałoby ciąg s nie należący do tej wyliczanki. Jednak s było elementem T, a więc powinno być w wyliczeniu. Jest to sprzeczne z pierwotnym założeniem, więc T musi być niepoliczalne.

Pytania i odpowiedzi

P: Czym jest argument diagonalny Cantora?

O: Argument przekątniowy Cantora to matematyczna metoda dowodzenia, że dwa nieskończone zbiory mają tę samą liczność.

P: Kiedy Cantor opublikował artykuły na temat swojego argumentu diagonalnego?

O: Cantor opublikował artykuły na temat swojego argumentu diagonalnego w latach 1877, 1891 i 1899.

P: Gdzie został opublikowany pierwszy dowód argumentu przekątniowego Cantora?

O: Pierwszy dowód argumentu przekątniowego Cantora został opublikowany w 1890 roku w czasopiśmie Niemieckiego Towarzystwa Matematycznego (Deutsche Mathematiker-Vereinigung).

P: Kiedy według Cantora dwa zbiory mają tę samą liczność?

O: Według Cantora dwa zbiory mają tę samą liczność, jeśli możliwe jest przyporządkowanie elementu drugiego zbioru do każdego elementu pierwszego zbioru oraz przyporządkowanie elementu pierwszego zbioru do każdego elementu drugiego zbioru.

P: Czy twierdzenie Cantora o kardynalności działa dobrze dla zbiorów o skończonej liczbie elementów?

O: Tak, twierdzenie Cantora działa dobrze dla zbiorów o skończonej liczbie elementów.

P: Czy twierdzenie Cantora o kardynalności jest intuicyjne dla zbiorów o nieskończonej liczbie elementów?

O: Nie, twierdzenie Cantora o kardynalności jest mniej intuicyjne dla zbiorów o nieskończonej liczbie elementów.

P: Ile razy Cantor opublikował artykuły na temat swojego argumentu diagonalnego?

O: Cantor opublikował artykuły na temat swojego argumentu diagonalnego trzy razy - w 1877, 1891 i 1899 roku.