Metoda przekątniowa

Rozumowanie przekątniowe to 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. Natychmiastowy wniosek z tego faktu podawany jest obrazowo: liczb rzeczywistych jest więcej niż liczb naturalnych.

Rozumowanie przekątniowe i jego modyfikacje ma jednak znacznie więcej zastosowań, 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.

Od tego czasu stosowane było ono wielokrotnie – w logice, topologii, teorii mnogości i wielu innych działach matematyki. 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 przebiega jak następuje: każda liczba rzeczywista $0\le x\le 1$ ma swoje rozwinięcie dziesiętne, skończone lub nie. Jeśli jest ono skończone, dopiszemy na jego końcu zera tak, by otrzymać rozwinięcie formalnie nieskończone.

Załóżmy, że możemy ponumerować wszystkie liczby rzeczywiste $0\le x\le 1$ liczbami naturalnymi, a następnie ustawić je jedna za drugą, na przykład w ten sposób:

1. 0,267888928717743...
2. 0,271673820983098...
3. 0,219212212222222...
4. 0,342111334423422...
5. 0,213421113344234...
6. 0,954112122893457...
7. 0,739208396716263...
8. ...

Pamiętajmy – założyliśmy, że powyższy ciąg zawiera wszystkie liczby rzeczywiste z przedziału $0\le x\le 1$.

Skonstruujemy teraz liczbę rzeczywistą, która jednak w powyższym ciągu na pewno nie wystąpi. Mianowicie, kolejne cyfry naszej liczby tworzymy tak, że nasza liczba ma na k-tym miejscu po przecinku cyfrę o 1 większą niż ma na k-tym miejscu liczba stojąca w powyższym ciągu na miejscu k-tym, lub 0 jeżeli tą cyfrą była 9.

W naszym przykładzie wyglądałaby ona tak:

0,3802334...

Ponieważ założyliśmy, że zbiór zawiera wszystkie liczby rzeczywiste z przedziału $0\le x\le 1$ to znaczy, że nowo skonstruowana liczba musi być równa którejś z liczb już tam występujących. Załóżmy, że jest równa n-tej liczbie - wtedy, w szczególności, powinna mieć na n-tym miejscu po przecinku taką samą cyfrę - dochodzimy więc do sprzeczności ponieważ skonstruowaliśmy liczbę tak, że na n-tym miejscu ma inną cyfrę. Z dowolności wyboru n mamy, że liczba ta nie występowała wcześniej w naszym zbiorze. Otrzymana sprzeczność pokazuje, że zbiory liczb naturalnych i rzeczywistych z przedziału $[0,1]$ nie są równoliczne.

Zobacz też

• zbiór przeliczalny