Argument Cantora z przekątnej to matematyczna metoda najczęściej wykorzystywana do wykazania, że pewne zbiory nie mają tej samej kardynalności — innymi słowy, że nie istnieje między nimi bijekcja. Autorem tej idei jest Cantor, który publikował prace dotyczące kardynalności i teorii mnogości w drugiej połowie XIX wieku. Jego najbardziej znane obserwacje związane z argumentem przekątniowym i wynikiami na temat zbioru liczb rzeczywistych oraz zbioru podzbiorów pojawiły się w pracach z tego okresu. Argument przekątniowy jest mniej intuicyjny niż wprowadzenie pojęcia bijekcji dla zbiorów skończonych, dlatego warto zaprezentować go w kilku wariantach i z pełnym dowodem.

Co to znaczy mieć tę samą kardynalność?

Dwa zbiory A i B mają tę samą kardynalność wtedy i tylko wtedy, gdy istnieje bijekcja (jeden‑do‑jednego i na) f: A → B. Dla zbiorów skończonych intuicja jest prosta. Dla nieskończonych zbiorów pojęcie to prowadzi do różnych „wielkości nieskończoności” — przykładowo zbiór liczb naturalnych jest przeliczalny (ma taką samą kardynalność jak N), zaś zbiór liczb rzeczywistych nie jest przeliczalny; właśnie to ostatnie stwierdzenie najczęściej dowodzi się argumentem przekątniowym.

Wersja dla ciągów binarnych (dowód nieprzeliczalności)

Rozważmy zbiór wszystkich nieskończonych ciągów cyfr 0 i 1 (czyli funkcji x: N → {0,1}). Załóżmy dla kontrastu, że ten zbiór jest przeliczalny, tzn. można wszystkie takie ciągi wypisać jako listę:

  • c1 = (c11, c12, c13, ...)
  • c2 = (c21, c22, c23, ...)
  • c3 = (c31, c32, c33, ...)
  • …

Teraz skonstruujmy nowy ciąg d = (d1, d2, d3, ...), gdzie dn = 1 − cnn (czyli zmieniamy n‑ty wyraz n‑tego ciągu). Ten ciąg d różni się od każdego ci przynajmniej na pozycji i — stąd nie może występować w liście. To przeczy założeniu, że lista zawiera wszystkie ciągi. Wniosek: zbiór wszystkich nieskończonych ciągów {0,1}^N jest nieprzeliczalny.

Ta wersja jest najbardziej elementarna i unikamy tu problemów z reprezentacją rozwinięć dziesiętnych (np. 0,4999... = 0,5000...) przez pracę w systemie binarnym albo przez dopuszczenie jedynie rozwinięć, które nie kończą się na nieskończoną sekwencję 9.

Wersja klasyczna dla liczb rzeczywistych

Zwykły argument pokazuje, że nie istnieje bijekcja między N a zbioru liczb rzeczywistych w przedziale (0,1). Zakłada się listę wszystkich liczb w postaci rozwinięć dziesiętnych i konstruuje nową liczbę różniącą się od n‑tej liczby na n‑tej pozycji (np. zastępując cyfrę 5 cyfrą 4, inaczej niż w n‑tym rozwinięciu). W ten sposób uzyskuje się liczbę, która nie występuje na liście — sprzeczność. Stąd liczby rzeczywiste są nieprzeliczalne.

Cantorowskie twierdzenie o zbiorze potęgowym (uniwersalny dowód przekątniowy)

Argument przekątniowy ma uogólnienie, które daje silniejszy wynik: dla dowolnego zbioru X zbiór wszystkich podzbiorów P(X) (zbiór potęgowy) ma ściśle większą kardynalność niż X. Formalnie: nie istnieje surjekcja f: X → P(X). Dowód jest prosty i elegancki.

Załóżmy przeciwnie, że istnieje funkcja f: X → P(X) będąca surjekcją. Zdefiniujmy podzbiór D ⊆ X przez

D = { x ∈ X : x ∉ f(x) }.

Teraz, ponieważ f jest surjekcją, istnieje element y ∈ X taki, że f(y) = D. Pojawia się jednak pytanie: czy y należy do D?

  • Jeśli y ∈ D, to z definicji D mamy y ∉ f(y) = D — sprzeczność.
  • Jeśli y ∉ D, to z definicji D mamy y ∈ f(y) = D — także sprzeczność.

Obie możliwości prowadzą do sprzeczności, więc nasze początkowe założenie, że f jest suriekcją, było fałszywe. Wniosek: nie istnieje bijekcja między X a P(X), a zatem |P(X)| > |X|.

Konsekwencje i uwagi

  • Hierarchia nieskończoności: Z twierdzenia Cantora wynika, że dla każdego zbioru X istnieje zbiór o większej kardynalności (P(X)), co prowadzi do nieskończonej wieży coraz większych kardynalności.
  • Nieprzeliczalność continuum: Argument przekątniowy daje konstruktywny dowód, że zbiór liczb rzeczywistych ma większą kardynalność niż zbiór liczb naturalnych; tę większą kardynalność nazywa się często continuum.
  • Kontrowersje historyczne i filozoficzne: Odkrycia Cantora wywołały silne reakcje wśród współczesnych mu matematyków i filozofów; teoria mnogości i pojęcie różnych rozmiarów nieskończoności miały istotny wpływ na dalszy rozwój matematyki.
  • Uwaga techniczna: Przy dowodach dla rozwinięć dziesiętnych trzeba uważać na liczby o dwóch rozwinięciach (np. 0,4999... = 0,5000...); typowym obejściem jest użycie rozwinięć binarnych lub ograniczenie się do rozwinięć nieskończonych niekończących się w samych dziewiątkach.

Argument przekątniowy jest jednym z najbardziej przejrzystych i siłowych narzędzi teorii mnogości — pokazuje nie tylko, że pewne zbiory są większe niż inne, lecz także daje konstrukcję konkretnego elementu (przekątnej), który nie może należeć do zakładanej listy lub obrazu funkcji.