Indukcja po wszystkich koniach

9 listopada 2018
Blog szalonych naukowców

Jednym z kluczowych w arytmetyce pojęć jest indukcja matematyczna. Bez niej właściwie dzisiejsza matematyka nie istnieje.

Pierwszymi liczbami, o których uczy się w szkole, są liczby naturalne. 0, 1, 2 itd., bez końca, czyli do nieskończoności. Matematyka jest nauką ścisłą i sformułowania typu „i tak dalej” niezbyt lubi. Żeby ich uniknąć, stosuje się pewną sztuczkę.

Dzisiejsza matematyka bazuje na aksjomatach. Każdy zapewne pamięta ze szkoły jakieś twierdzenia: Pitagorasa, Talesa, o trzech ciągach… Skąd wiemy, że twierdzenie jest prawdziwe? Bo zostało to dowiedzione. Ale co znaczy „dowiedzione”? Znaczy to, że przedstawiono dowód. Czyli co właściwie? Wykazanie, że coś jest prawdziwe? Ale rozumowanie takie opierać się musi na jakichś przesłankach. Od czegoś trzeba zacząć. Niekiedy są to przesłanki tak podstawowe, że ich nie zauważamy. Tak więc dowód to, najprościej mówiąc, skończony ciąg zdań, począwszy od przesłanek, gdzie każde następne po nich wynika z poprzednich zgodnie z pewnymi ustalonymi regułami wnioskowania, aż do tego dowodzonego (dowiedzionego?).

Ale skądś trzeba te pierwsze przesłanki wziąć. Tak więc wyodrębnia się pewien zbiór zdań, z których wynikać mają wszystkie inne (wszystkie inne, które mogą zostać dowiedzione, udowodniono bowiem, że każdy taki skończony zestaw przesłanek zawierający arytmetykę nie wystarcza do dowiedzenia wszystkich twierdzeń sformułowanych w tym samym języku). Przesłanki te noszą nazwę aksjomatów, czyli pewników. Najsławniejsze są na pewno aksjomaty Euklidesa, stanowiące podstawę geometrii płaskiej przestrzeni. Zmieniając jeden z tych pewników, można otrzymać inne geometrie – eliptyczną bądź hiperboliczną. Aksjomaty arytmetyki sformułował Giuseppe Peano. Wymyślił, że liczby naturalne (dalej tu nie wyjdziemy) można określić, przyjmując istnienie pewnej początkowej liczby (dzisiaj dwie odrębne szkoły zaczynają od 0 bądź od 1, to kwestia umowy), pojęcie następnika (następnej liczby naturalnej, np. po 0 następna jest 1, a po 143 następna jest 144). Dalej przyjmuje się, że jeśli dwie liczby naturalne mają równe następniki, to same też są równe, a wspomniana początkowa liczba (dajmy na to 0) nie jest następnikiem żadnej innej liczby naturalnej. I tutaj wchodzi aksjomat indukcji.

Weźmy zbiór o dwóch własnościach:
• należy do niego 0
• jeśli liczba naturalna n należy do tego zbioru, to i należy do niego jej następnik.

Matematycy lubią to zapisywać czymś w rodzaju skrzyżowania hieroglifów i pisma klinowego, ale myślę, że formalizację możemy sobie pominąć. Niezależnie od zapisu zbiór o powyższych dwóch własnościach zawiera wszystkie liczby naturalne. To właściwie wszystko, co trzeba podać, by scharakteryzować liczby naturalne. Oczywiście gdybyśmy chcieli coś na nich liczyć bądź wprowadzać relację porządku (liczby naturalne już tak mają, że jak weźmiemy dwie, to jedna będzie mniejsza lub równa drugiej; nie wszystkie zbiory liczb mają taką właściwość), to trzeba zdefiniować te działania czy relacje za pomocą dodatkowych aksjomatów. Dodawanie np. definiuje się znowu przez indukcję; dla dowolnej liczby naturalnej a:

• a + 0 = a
• a + następnik (b) = następnik (a+b)

Jak widzimy, 0 jest elementem neutralnym (dodanie go nie zmienia żadnej liczby naturalnej), dodawanie 1 do a oznacza wzięcie następnika a, dodawanie 2 oznacza wzięcie następnika następnika itd., do nieskończoności, co można sprawdzać ad mortem defecatam, jak to się mówi w polityce.

Wiele twierdzeń dowodzi się, korzystając z indukcji. Dowodzi się twierdzenia najpierw dla początkowej liczby (zwykle 0 bądź 1), następnie zakłada się, że coś zachodzi dla n, i dowodzi dla n+1. Jeśli zachodzi dla liczby początkowej i jeśli zachodzi dla n, to zachodzi dla n+1, to z aksjomatu indukcji zachodzi dla wszystkich liczb naturalnych. Przykładowo jeśli dany zbiór ma N elementów, to zbiór wszystkich jego podzbiorów (tzw. zbiór potęgowy) ma elementów 2 do potęgi N.

• Jeśli zbiór ma 0 elementów (zbiór pusty), to ma tylko 1 podzbiór: również zbiór pusty. Jest 1 taki podzbiór, a 2 do potęgi 0 wynosi 1. Zgadza się.
• Załóżmy, że zbiór N-elementowy ma 2 do potęgi N podzbiorów.
• Stwórzmy z niego zbiór mający N+1 elementów, dodając 1 dodatkowy element (możemy to zrobić, bo dwa zbiory zawsze mają swoją sumę, to akurat jeden z aksjomatów teorii mnogości). Ile podzbiorów będzie miał nowy zbiór? Ano po pierwsze zawierać będzie wszystkie podzbiory, które miał wyjściowy zbiór. Ponadto każdemu z tych podzbiorów odpowiada podzbiór różniący się od nich o tyle tylko, że zawiera ten jeden element, który dodaliśmy. Będzie ich tyle samo, czyli całkowita liczna podzbiorów zwiększy się dwa razy. Jeśli wcześniej podzbiorów było 2 do N, to teraz mamy ich 2*2 do N, czyli 2 do potęgi N+1. Zgadza się. Twierdzenie udowodnione. Matematycy nabazgraliby kwadracik bądź quod erat demonstrandum (co było do pokazania).

To teraz weźmy inny przykład, tzw. paradoks koni. Spróbujemy udowodnić, że wszystkie konie są tej samej barwy.

• Aby uniknąć absurdu związanego z pustym zbiorem koni (jak nie ma koni, to nie mają żadnej barwy), zacznijmy od 1. W zbiorze 1 konia każdy koń ma tę samą barwę. Dla liczby początkowej 1 mamy dowiedzione.
• Załóżmy, że zbiór n koni jest zbiorem koni o tej samej barwie.
• Doprowadźmy do tego zbioru kolejnego konia o numerze n+1. Następnie usuńmy jednego z wcześniej już obecnych koni (o tej samej barwie co pozostałe z obecnych od początku w naszym zbiorze). Otrzymujemy w ten sposób znowuż zbiór n koni. Z założenia wszystkie te konie mają tę samą barwę, a więc nowy koń jest tej samej barwy co poprzednie. Doprowadźmy teraz konia, któregośmy wcześniej usunęli. Ma tę samą barwę co wszystkie pozostałe w tym zbiorze. A więc zbiór n+1 koni jest zawsze zbiorem koni o tej samej barwie.

Dowiedliśmy zdanie dla liczby początkowej 1 i dowiedliśmy, że jeżeli zdanie zachodzi dla n, to zachodzi dla n+1. Zdanie zachodzi więc dla każdej liczby naturalnej. Każdy zbiór koni jest zbiorem koni o tej samej barwie. Również zbiór wszystkich koni. Ergo: wszystkie konie są tej samej barwy.

Jak widać, wniosek jest absurdalny, niezgodny z doświadczeniem. Pytanie brzmi: gdzie jest błąd?

Ilustracja: Koń w liczbie 1. Zdjęcie wykonane przez autora.