Metoda przekątniowa

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 $[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 $[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 $0\leqslant x\leqslant 1$ ma swoje rozwinięcie dziesiętne z zerową cyfrą jedności, 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ą.

Załóżmy, że możemy ponumerować wszystkie liczby rzeczywiste $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ą $0\leqslant a\leqslant 1,$ która w powyższym ciągu na pewno nie wystąpi. Mianowicie, kolejne cyfry liczby $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 $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 $a$ ma na k-tym miejscu cyfrę 0.

W naszym przykładzie liczba $a$ wyglądałaby tak:

0,3802334...

W efekcie liczba rzeczywista $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 $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 $[0,1]$ nie są równoliczne.

Zobacz też

• zbiór przeliczalny