Metoda przekątniowa

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Rozumowanie przekątniowe)
Skocz do: nawigacja, szukaj

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 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 . 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 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ść zera 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 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ą , która w powyższym ciągu na pewno nie wystąpi. Mianowicie, kolejne cyfry liczby 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 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 ma na k-tym miejscu cyfrę 0.

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

0,3802334...

W efekcie liczba rzeczywista 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 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 nie są równoliczne.

Uwagi

  1. dla x=1 przyjmujemy rozwinięcie 0,(9)=0,99999... (zob. 0,(9))
  2. ale liczba o skończonym rozwinięciu oraz liczba ze zmniejszoną ostatnią znaczącą cyfrę o 1 i uzupełnioną cyframi 9 reprezentują tę samą liczbę rzeczywistą, np. 0,416=0,415(9).

Zobacz też[edytuj]