Kolega przedstawił ostatnio rozumowanie udowadniające za pomocą indukcji matematycznej że wszystkie koty są czarne.
Ufam indukcji matematycznej, ale oczywiście wniosek z rozumowania jest fałszywy i falsyfikowalny empirycznie, więc postanowiłem poszukać co tu nie gra.
Trafiłem na Wikipedię gdzie zagadnienie jest znane jako
"Paradoks koni" czyli użycie indukcji matematycznej do uwodnienia że wszystkie konie są tej samej maści. Artykuł jest krótki i nie przedstawia jasno gdzie tkwi błąd w rozumowaniu, choć końcowa konkluzja wskazuje gdzie jest pies pogrzebany. Był też tekst angielski
"All horses are the same color", który rozjaśnił mi bardziej o co chodzi. Jednak dopiero po dodaniu do układanki definicji indukcji z pierwszych stron "Matematyki konkretnej" Donalda E. Knuth'a ułożyłem (chyba) sobie wszystko po kolei.
Indukcja z artykułu polskiego.
1. Teza do udowodnienia
Wszystkie konie są tej samej maści.
2. Baza indukcji
Zbiór złożony z jednego konia jest zbiorem koni jednej maści.
To oczywiście jest prawdą.
3. Założenie indukcyjne
Zakładamy że mamy dowód że wszystkie konie w każdym n-elementowym zbiorze koni są tej samej maści.
4. Krok indukcyjny
Przechodzimy z n do n+1.
Każdy zbiór o liczności n+1, możemy rozbić na zbiory o liczności n, przez odprowadzenie jednego konia innego niż ten właśnie dodany.
Możemy to zrobić na n sposobów, za każdym razem odprowadzając innego konia.
Z założenia indukcyjnego wynika wszystkie konie w każdym n-elementowym zbiorze koni są tej samej maści, zatem ostatecznie wszystkie konie w zbiorze (n+1)-elementowym są tej samej maści, zatem na mocy zasady indukcji matematycznej teza jest prawdziwa dla dowolnego n.
Indukcja z artykułu angielskiego.
W treści artykułu angielskiego nie widać wprost indukcji z n do n+1, jest raczej dowód dlaczego założenie indukcyjne dla n jest prawdziwe, przez podział na kolejne coraz mniejsze zbiory aż do n=0 gdzie spotykamy bazę indukcji.
Rozważmy szczegółowo 2 przypadki, jedne ze zbiorem 3-elementowym i drugi ze zbiorem 2-elementowym.
- ABC - 3 konie tej samej maści o wdzięcznych imionach A, B i C.
AB, BC, CA - każdy zbiór z osobna to zbiór koni tej samej maści, zatem wszystkie konie razem są tej samej maści, ponieważ każde dwa zbiory mają część wspólną, która zapewnia że wszystkie konie są tej samej maści, nie tylko w ramach zbioru 2-elementowego, ale również jako suma tych zbiorów czyli ABC.
Jeżeli AB są pewnej maści, to C musi też być tej maści ponieważ jest w zbiorze 2-elementowym CA i CB razem z końmi A i B które są tej samej maści.
- AB - 2 tej samej maści
A, B - każdy z osobna jest zbiorem koni tej samej maści, ale niekoniecznie A są tej samej maści co B, ponieważ nie ma części wspólnej.
Łącząc w myśli oba artykuły widzę coś dziwnego. Jednen idzie od n do n+1 czyli indukcja, drugi od n do 0 czyli... rekurencja, próba udownienia że PrawdziwośćTezy(n) = PrawdziwośćTezy(n-1).
Tu mnie tknęło aby zajrzeć do Knutha, do pierwszego rozdziału o rekurencji i czytamy czym jest krok indukcyjny
"Następnie, dowodzimy stwierdzenia dla n > n0 zakładając, że zostało ono już udowodnione dla wszystkich wartości pomiędzy n0 i n-1.".
Czyli w przypadku tych nieszczęsnych koni indukcja jest przeprowadzona prawie poprawnie... :
- dla bazy indukcji, n=0 jest OK
- dla kroku indukcyjnego n do n+1 z założeniem tezy dla n jest OK
Ale to wszystko nic nie znaczy, ponieważ krok indukcyjny można wykonać gdy jesteśmy pewni wyników między n=0 a n-1. A w tym przypadku jest dość ciekawie, ponieważ założenie jest prawdziwe dla wszystkich n między n=0, a n-1, poza
n=1, ponieważ dwa 1-elementowe zbiory koni o tej samej maści w każdym zbiorze nie dają podstaw do myślenia że suma tych zbiorów to wciąż konie o tej samej maści.
Uff, miło było pogimnastykować głowę.
