Rozumowanie przekątniowe

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Rozumowanie przekątniowe to klasyczny przykład rozumowania w dowodzie nie wprost. Za jego pomocą można wykazać na przykład, że moc zbioru 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, często prowadząc prostą drogą do pięknych i zadziwiających rezultatów. 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:

0,267888928717743...
0,271673820983098...
0,219212212222222...
0,342111334423422...
0,213421113344234...
0,954112122893457...
0,739208396716263...
...

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, 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...

Na której pozycji w powyższym ciągu miałaby wystąpić tak skonstruowana liczba? Nie na pierwszej (różni się od pierwszej liczby pierwszą cyfrą), nie na drugiej (z tej samej przyczyny), nie na trzeciej, itd. Nie może ona wystąpić w powyższym ciągu na żadnej pozycji, a przecież ciąg ten z założenia zawierał wszystkie liczby z przedziału [0, 1]. Otrzymana sprzeczność pokazuje, że zbiory liczb naturalnych i rzeczywistych z przedziału [0, 1] nie są równoliczne.