Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 30

Inna typowa forma argumentacji w dowodzeniu twierdzenia polega na założeniu, że twierdzenie jest fałszywe, a następnie wykazanie, że założenie to prowadzi w oczywisty sposób do fałszywych wniosków, nazywanych sprzecznością. Tego typu rozumowania używamy często w codziennym życiu, jak w poniższym przykładzie.

Przykład 0.23

Jack widzi Jill, która przed chwilą była na świeżym powietrzu. Zauważa, że nie zmokła, toteż wie, że nie pada deszcz. Jego „dowód”, że nie pada, polega na tym, że gdyby padało (założenie, że twierdzenie jest fałszywe), Jill by zmokła (oczywiście fałszywy skutek). Tym samym nie może padać.

■

Teraz spróbujmy dowieść nie wprost, że pierwiastek kwadratowy z 2 jest liczbą niewymierną. Liczba jest wymierna, jeśli jest ułamkiem m/n, gdzie m i n są liczbami całkowitymi; mówiąc inaczej, liczba wymierna jest ilorazem liczb całkowitych m i n. Na przykład 2/3 w oczywisty sposób jest liczbą wymierną. Liczbę nazywamy niewymierną, jeśli nie jest wymierna.

Twierdzenie 0.24

√ 2 jest liczbą niewymierną.

Dowód Na potrzeby dowodu nie wprost zakładamy, że √ 2 jest liczbą wymierną. Tym samym

,

gdzie m i n są liczbami całkowitymi. Jeśli obie liczby m i n są podzielne przez tę samą liczbę całkowitą większą od 1, dzielimy obie przez największą taką liczbę (skracamy ułamek). Działanie takie nie zmienia wartości ułamka. W rezultacie przynajmniej jedna z liczb m i n musi być liczbą nieparzystą.

Mnożymy obie strony równania przez n i uzyskujemy

n√ 2 = m.

Podnosimy obie strony do kwadratu i uzyskujemy

2n² = m².

Ponieważ m² jest podwojeniem liczby całkowitej n², wiemy, że m² jest liczbą parzystą. Zatem samo m również jest parzyste, gdyż kwadrat liczby nieparzystej zawsze jest nieparzysty. Możemy zatem zapisać m = 2k, gdzie k jest pewną liczbą całkowitą. Podstawiając 2k za m, otrzymujemy

2n² = (2k)²

= 4k².

Dzieląc obie strony przez 2, otrzymujemy

n² = 2k².

Jednak wynik ten pokazuje, że n² jest parzyste, a tym samym n jest parzyste. Wykazaliśmy zatem, że zarówno m, jak i n są parzyste. Jednak wcześniej wykonaliśmy redukcję m i n (skróciliśmy ułamek), a więc obie jednocześnie nie mogą być parzyste – sprzeczność.