Metoda przekątniowa

Zasugerowano, aby zintegrować ten artykuł z artykułem twierdzenie Cantora (dyskusja). Nie opisano powodu propozycji integracji.

Ten artykuł od 2021-03 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Rozumowanie przekątniowe – klasyczny przykład rozumowania w dowodzie nie wprost. Za jego pomocą można wykazać na przykład, że moc zbioru liczb rzeczywistych z przedziału ${\displaystyle [0,1]}$ jest większa od mocy zbioru liczb naturalnych; formułuje się to obrazowo: liczb rzeczywistych jest więcej niż liczb naturalnych.

Rozumowanie przekątniowe i jego modyfikacje ma znacznie więcej zastosowań, stosowane jest m.in. w logice, topologii, teorii mnogości. Wykorzystywane jest zwykle do konstrukcji obiektów mających, lub nie, określone własności. Po raz pierwszy w dowodzie matematycznym rozumowania przekątniowego użył twórca teorii mnogości Georg Cantor.

Generalnie, jako metoda dowodzenia metoda przekątniowa polega na skonstruowaniu elementu, o którym wiemy, że nie należy do rozpatrywanego zbioru, dzięki czemu możemy wykazać, że pewne założenie o elementach owego zbioru jest nieprawdziwe: w przykładzie poniższym założeniem jest możliwość ponumerowania liczb rzeczywistych z przedziału ${\displaystyle [0,1].}$ Metoda przekątniowa jest narzędziem do konstruowania takich właśnie elementów.

Rozumowanie opiera się na następującym fakcie: każda liczba rzeczywista ${\displaystyle 0\leqslant x\leqslant 1}$ ma swoje rozwinięcie dziesiętne z zerową cyfrą jedności^[a], skończone lub nie. Jeśli jest ono skończone, to uzupełniamy rozwinięcie o nieskończoną ilość zer tak, by otrzymać rozwinięcie formalnie nieskończone. Jest też odwrotnie – każdy ciąg cyfr po przecinku reprezentuje pewną liczbę rzeczywistą^[b].

Załóżmy, że możemy ponumerować wszystkie liczby rzeczywiste ${\displaystyle 0\leqslant x\leqslant 1}$ liczbami naturalnymi, czyli ustawić je w nieskończony ciąg. Na przykład w ten sposób:

1.   0, 2 6 7 8 8 8 9 2 8 7 1 7 7 4 3 ...
2.   0, 2 7 1 6 7 3 8 2 0 9 8 3 0 9 8 ...
3.   0, 2 1 9 2 1 2 2 1 2 2 2 2 2 2 2 ...
4.   0, 3 4 2 1 1 1 3 3 4 4 2 3 4 2 2 ...
5.   0, 2 1 3 4 2 1 1 1 3 3 4 4 2 3 4 ...
6.   0, 9 5 4 1 1 2 1 2 2 8 9 3 4 5 7 ...
7.   0, 7 3 9 2 0 8 3 9 6 7 1 6 2 6 3 ...
8.   ...

Skonstruujemy teraz liczbę rzeczywistą ${\displaystyle 0\leqslant a\leqslant 1,}$ która w powyższym ciągu na pewno nie wystąpi. Mianowicie, kolejne cyfry liczby ${\displaystyle a}$ tworzymy wg zasady:

• jeśli k-ta liczba ciągu ma na k-tym miejscu po przecinku jedną z cyfr 0,1,...8, to liczba ${\displaystyle a}$ ma na k-tym miejscu cyfrę o 1 większą;
• jeśli k-ta liczba ciągu ma na k-tym miejscu po przecinku cyfrę 9, to liczba ${\displaystyle a}$ ma na k-tym miejscu cyfrę 0.

W naszym przykładzie liczba ${\displaystyle a}$ wyglądałaby tak:

0,3802334...

W efekcie liczba rzeczywista ${\displaystyle a}$ od pierwszej liczby ciągu różni (co najmniej) pierwszą cyfrą, od drugiej liczby ciągu różni (co najmniej) drugą cyfrą, ... od k-tej liczby ciągu różni (co najmniej) k-tą cyfrą. Tzn. liczba ${\displaystyle a}$ nie występuje w ciągu, wbrew temu, że ciąg zawierał wszystkie liczby rzeczywiste. Otrzymana sprzeczność pokazuje, że zbiory liczb naturalnych i rzeczywistych z przedziału ${\displaystyle [0,1]}$ nie są równoliczne.