Reklama
Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2
niedowiary - blog (szalonych) naukowców niedowiary - blog (szalonych) naukowców niedowiary - blog (szalonych) naukowców

9.11.2018
piątek

Indukcja po wszystkich koniach

9 listopada 2018, piątek,

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.

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 26

Dodaj komentarz »
  1. To się sypie już dla n=2. Usuwamy konia numer 1. Zostaje nowy koń numer 2.
    Mamy więc dwa rozłączne zbiory o rozmiarze n=1 każdy. Każdy składa się z koni o tej samej barwie w liczbie 1, ale zbiory są rozłączne. Nie możemy niczego wywnioskować dla n=2.

  2. „Załóżmy, że zbiór n koni jest zbiorem koni o tej samej barwie”.
    „Z założenia wszystkie te konie mają tę samą barwę”…

    Drugie zdanie nie jest zgodne z założeniem (mimo, że samo o sobie tak twierdzi – kłamie), więc nie można z niego nic wnioskować o zbiorze z założenia.

  3. Dodam jeszcze że „dowód” w tekście nie jest przedstawiony poprawnie, nie możemy tak po prostu przyprowadzić usuniętego konia, bo wcale nie wiemy czy on jest tego samego koloru co pozostałe n (może konie zmieniają kolor w różnych grupach). I jeszcze nie udowodniliśmy że (n+1) jest tego samego koloru (circular proof?).

    W dowodzie polegamy na tym że dwa zbiory o rozmiarach n składające się z koni (1,..,n) i (2,…,n+1) spełniają założenie i nie są rozłączne. W związku z tym wszystkie (1,…,n+1) konie są tego samego koloru. Co oczywiście nie jest prawdą dla n=2.

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. Pan Marcin, znowu zrobil nam podpuche gleboko-filozoficzna. Spryciarz! 🙂

  6. Niezłe! Rozumowanie jest prawidłowe i wniosek jest poprawny. Indukcyjnie teza została udowodniona. Problem jest w założeniu: „Jeżeli dla dowolnego n wszystkie n koni ma ten sam kolor”. I to założenie jest nieprawdziwe. A jak wiadomo z nieprawdziwego założenia można poprawnie wyciągnąć dowolne, w tym i niezgodne z doświadczeniem wnioski.
    Gdyby założenie „dla dowolnego n wszystkie konie mają ten sam kolor” było prawdziwe doświadczalnie to i wynik indukcji byłby prawdziwy doświadczalnie.

  7. @izabella
    Na pewno sypie się dla n=2? Wtedy mamy zbiór 2 koni powiedzmy K1 i K2. Wywalamy K1. Doprowadzamy konia K3. Oba zbiory nie są rozłączne, mają niepusty iloczyn {K2}. Bardzo słuszne rozumowanie, ale chyba nie dla n=2?

  8. @xswedc
    Tzn. na czym polega ta sprzeczność z założeniem?

  9. Marcin Nowak
    10 listopada o godz. 19:04

    Bardzo słuszna uwaga, powinnam była napisać dla n+1=2, czyli dla n=1 🙂

  10. @ZWO
    Nie jest, półtora godziny kiedyś nad tym myślałem, zanim mnie olśniło 🙂

  11. ZWO
    10 listopada o godz. 17:46
    Gdyby założenie „dla dowolnego n wszystkie konie mają ten sam kolor” było prawdziwe doświadczalnie to i wynik indukcji byłby prawdziwy doświadczalnie.

    Gdybyśmy stosowali indukcję tylko wiedząc z góry że założenie jest prawdziwe dla dowolnego n, to nie byłoby po co jej stosować.

  12. Ja i bez indukcji wiem, że w nocy wszystkie konie są czarne. Może zresztą nie chodziło o konie?

  13. Pomyślę.
    Na razie podobne rozumowanie: Ja znam polski. Załóżmy, że n ludzi zna polski. Ponadto Pan Nowak (n+1) także zna polski. Czyli wszyscy ludzie na świecie znają polski. I tak z resztą świata. Ten sam błąd, ale jaki.

  14. A czy da się udowodnić że wszystkie konie mają tyle samo nóg? Albo głów?

    Błąd już chyba wyjaśniony. Najciekawsze w dowodzie jest to, że gdyby twierdzenie było prawdą dla dwóch koni, to byłoby i dla trzech, czterech, …, i nieskończoności. Tylko dla tych dwóch nie da się wykazać. A to feler …

    Bardzo sympatyczny problemik, dziękuję.

  15. @izabella
    Otóż istotnie, jeśli każde 2 konie są tego samego koloru (mówią po polsku itd.), wszystkie konie są tego samego koloru (mówią po polsku itd.).

    Zwróćcie Państwo uwagę na jeszcze jedną rzecz. Indukcja polega na dowiedzeniu zdania Z(1) i implikacji Z(n) => Z(n+1). Tymczasem w podanym przykładzie zdania dowiedzione dla 1 i użyte w implikacji nie są takie same.

  16. I mnie to przyszło w nocy do głowy. Niezależnie od implikacji Z(n) => Z(n+1) należy udowodnić własność dla Z(1). I tego się tutaj zrobić nie da.

  17. Po zastanowieniu.
    Cały dowcip polega tutaj na tym, że Z(1) = Z(2) bo nie istnieje zgodność kolorów dla 1 konia. Czyli udowodnienie, że dla „każdej pary” to wykazanie, że dana własność obowiązuje dla pierwszego elementu ciągu. Do udowodnienia nie jest „kolor” tylko „zgodniść”. Przypadek języka polskiego jest czymś innym.

  18. @ZWO
    „Ten sam błąd, ale jaki.”

    Elementarny, dear ZWO! Autor bloga pozwala sobie najpierw podać niekompletną definicję procedury, aby potem, stosując ją, dowodzić po uważaniu, co bądź. To jest nagminnie stosowane w polityce (i w Polityce) oraz – do pewnego stopnia, ale w sposób cywilizowany – w naukach przyrodniczych (tzw. indukcja przyrodnicza). Konkretnie, w definicji brakuje kwantyfikatora (i to na dodatek wielkiego!).
    Wynikanie prawdziwości P_n+1 z P_n ma zachodzić DLA KAZDEGO n. I to trzeba udowodnić! Na dodatek n to nie prosty desygnat liczebności zbioru, ale również – kolejności. Szcześciem, autor bloga nie zajął się indukcją elektromagnetyczna – bylibyśmy porażeni!

  19. @rang
    Cały dowcip polega na tym, że gdyby dowodzić porządnie, to by takiej absurdalnej konkluzji udowodnić nie można. Natomiast kwantyfikator duży był w domyśle 🙂

  20. @ZWO
    Niekoniecznie Z(1) = Z(2), ale raczej dowodzimy Z'(1) i następnie dla każdego n: Z”(n) => Z”(n+1). Zdanie Z”, żeby miało sens, musi dotyczyć n należącego do zbioru liczb naturalnych i równego przynajmniej 2 (nowy koń ma taki sam kolor, jak pozostałe – muszą istnieć jakieś pozostałe). Gdyby zrobić to, jak mnie uczono w liceum, od czego należy zaczynać rozumowanie w matematyce, czyli określenia dziedziny, nie byłoby i paradoksu 🙂

  21. @Marcin Nowak

    „Natomiast kwantyfikator duży był w domyśle”
    Ja raczej odnosilem sie do przykladu ZWO o jezyku polskim.
    Natomiast, co do koni to sztuczka jest raczej prestigitatorska, aczkolwiek ‚domyslne’ ukryte zalożenia też tam są i dotyczą sposobu przeprowadzenia samego ‚eksperymentu’. Autor zakłada, że albo każdy koń wybrany na chybił trafił dodany do zbioru koni czarnych w jakiś mistyczny sposób staje się czarny (co na to koń?!), albo że a priori wybiera się konia czarnego. To drugie kłoci się z zawartym w twierdzeniu kwantyfikatorem (sic!) ‚wszystkie konie (w domysle (sic!) we wszechświecie) są czarne’ – czarne są tylko te wybrane. W najlepszym razie autor udowadnia więc twierdzenie, że wszystkie konie z owego zbioru są czarne (lub uczernione). Ewentualnie czyni założenie, że wszystkie w ogóle są czarne, ale wtedy dowodzone twierdzenie zawarte jest w założeniu. A zresztą, koń jaki jest, każdy widzi.

  22. No to zaczynamy „dyskusję”. Następne 150 wpisów będzie nie o problemie tylko o tym, kto miał rację w poprzednim wpisie. Jak zwykle. Czy zacząć od udowadniania, że to ja miałem, mam i będę miał rację, czy jednak jakiś mały żarcik? Czekam na propozycje, pewnie typu „spadaj”, „od… się”. Też jak zwykle.
    Albo może jednak: Wychodząc od błędnych założeń można bezbłędnie udowodnić nieprawdę. Jak zwykle!

  23. Na świecie zyje ok. 58 mln koni o tgrzech podstawowych barwach: najbardziej popularne są kasztanowate i stanowią ok 40% wszystkich.

    Tak więc założenie jest nieprawdziwe dla n=58mln *0,4 +1 = 23 200 001 koni.

    Prowadzimy indukcję na fałszywych założeniach.

  24. A czy matematyka w ogole istnieje poza ludzkim umyslem? Oto jest pytanie.

    Pamietam, ze ostrzegano nas na filozofi, ze matematyka do nauk przyrodniczych nie nalezy. Na podpore dawano przyklad wlasnie o indukcji i czarnym labedziu.

    Temat axiomatow w naukach przyrodniczych jest ciekawy sam w sobie, ale ludzie madrzy w temacie mowia, ze nauki przyrodnicze nie wynikaja z samej logiki.

    O takie zero przykladowo. Bez zera w matematyce/logice ani rusz.
    A zera w przyrodzie nie ma! Nawet nie ma zera absolutnego w skali temperatur.

  25. Tylko, że te składniki nauk przyrodniczych, które nie wynikają z logiki też podlegają własnej logice, a jeśli przypadkowi – to statystyce.

  26. R.S.
    13 listopada o godz. 21:01
    Pamietam, ze ostrzegano nas na filozofii, ze matematyka do nauk przyrodniczych nie należy.

    Gdyby w biologii nie obowiązywały prawa matematyczne, to nie istniałaby biologia obliczeniowa, biostatystyka, czy nawet bioinformatyka. Bardzo wiele zjawisk biologicznych da się opisać przy pomocy równań różniczkowych, zwykłych lub stochastycznych, na przykład zmiany populacji drapieżników i ich ofiar (wspomniany niedawno Lotka), zachowanie ryb w ławicy, czy wyładowanie pojedynczego neuronu. A przypadkowość też się rządzi swoimi prawami.

    Że też filozofowie mogli coś takiego powiedzieć. Może oni byli teologiczni.

  27. W czasie studiow, przeladowani programem, filozofia bardzo ciezko nam doskwierala. Ale po latach po glebszym zastanowieniu coraz czesciej odnajduje w niej sporo intrugujacych tematow.

    Zacznijmy od podzialu nauk na trzy podstawowe galezie:

    Formal sciences: the study of mathematics and logic, which use an a priori, as opposed to factual, methodology.

    Natural sciences: the study of natural phenomena (including cosmological, geological, chemical, and biological factors of the universe)

    Social sciences: the study of human behavior and societies.

    Oczywiscie, ze jest przenikanie i wzajemne inspiracje, ale podstawowe pytanie wciaz wymaga odpowiedzi. Dlaczego matematyka odnosi takie sukcesy wsrod pozostalych galezi naukowych mimo, ze nie nalezy do nauk przyrodniczych?

    Czy cos nam sie wymyka w poznaniu, bazujac na naukach formalnych?

    SETI wysylal w przestrzen miedzygwiezna liczby pierwsze, a czy one czasem nie sa eliptycznym brzeczeniem much? A my ludzkosc bedac wlasnie tymi muchami zakladamy ze odkrylismy uniwersalny sposob komunikacji.

    Polecam film Arrival, w ktorym inne miedzygwiezdne stwory porozumiewaly sie po fraktalnemu 🙂

    Natrafilem ostatnio na krytyke przekazu zawartego w zlotej plycie sondy Pionier. Jeden z wygrawerowanych rysunkow pokazuje oscylogram sygnalu wizyjnego.
    I tak sobie pomyslalem:
    Good luck trying to play it on modern digital TV.
    Nie wiem, czy jeszcze, nowa generacja inzynierow wie jak dziala lampa elektronowa. A juz zrobic taka lampe, toz to zapomniana sztuka starozytnych.

    Stad moj wpis na poczatku:
    Pan Marcin, znowu zrobil nam podpuche gleboko-filozoficzna. Spryciarz!

css.php