{"id":6353,"date":"2018-11-09T17:31:13","date_gmt":"2018-11-09T16:31:13","guid":{"rendered":"http:\/\/naukowy.blog.polityka.pl\/?p=6353"},"modified":"2018-11-09T20:02:17","modified_gmt":"2018-11-09T19:02:17","slug":"indukcja-po-wszystkich-koniach","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/naukowy\/2018\/11\/09\/indukcja-po-wszystkich-koniach\/","title":{"rendered":"Indukcja po wszystkich koniach"},"content":{"rendered":"

\"\"Jednym z kluczowych w arytmetyce poj\u0119\u0107 jest indukcja matematyczna<\/strong>. Bez niej w\u0142a\u015bciwie dzisiejsza matematyka nie istnieje.
\n
\nPierwszymi liczbami, o kt\u00f3rych uczy si\u0119 w szkole, s\u0105 liczby naturalne. 0, 1, 2 itd., bez ko\u0144ca, czyli do niesko\u0144czono\u015bci. Matematyka jest nauk\u0105 \u015bcis\u0142\u0105 i sformu\u0142owania typu \u201ei tak dalej\u201d niezbyt lubi. \u017beby ich unikn\u0105\u0107, stosuje si\u0119 pewn\u0105 sztuczk\u0119.<\/p>\n

Dzisiejsza matematyka bazuje na aksjomatach<\/strong>. Ka\u017cdy zapewne pami\u0119ta ze szko\u0142y jakie\u015b twierdzenia: Pitagorasa, Talesa, o trzech ci\u0105gach… Sk\u0105d wiemy, \u017ce twierdzenie jest prawdziwe? Bo zosta\u0142o to dowiedzione. Ale co znaczy \u201edowiedzione\u201d? Znaczy to, \u017ce przedstawiono dow\u00f3d<\/em>. Czyli co w\u0142a\u015bciwie? Wykazanie, \u017ce co\u015b jest prawdziwe? Ale rozumowanie takie opiera\u0107 si\u0119 musi na jakich\u015b przes\u0142ankach. Od czego\u015b trzeba zacz\u0105\u0107. Niekiedy s\u0105 to przes\u0142anki tak podstawowe, \u017ce ich nie zauwa\u017camy. Tak wi\u0119c dow\u00f3d to, najpro\u015bciej m\u00f3wi\u0105c, sko\u0144czony ci\u0105g zda\u0144, pocz\u0105wszy od przes\u0142anek, gdzie ka\u017cde nast\u0119pne po nich wynika z poprzednich zgodnie z pewnymi ustalonymi regu\u0142ami wnioskowania, a\u017c do tego dowodzonego (dowiedzionego<\/em>?).<\/p>\n

Ale sk\u0105d\u015b trzeba te pierwsze przes\u0142anki wzi\u0105\u0107. Tak wi\u0119c wyodr\u0119bnia si\u0119 pewien zbi\u00f3r zda\u0144, z kt\u00f3rych wynika\u0107 maj\u0105 wszystkie inne (wszystkie inne, kt\u00f3re mog\u0105 zosta\u0107 dowiedzione, udowodniono bowiem, \u017ce ka\u017cdy taki sko\u0144czony zestaw przes\u0142anek zawieraj\u0105cy arytmetyk\u0119 nie wystarcza do dowiedzenia wszystkich twierdze\u0144 sformu\u0142owanych w tym samym j\u0119zyku). Przes\u0142anki te nosz\u0105 nazw\u0119 aksjomat\u00f3w<\/em>, czyli pewnik\u00f3w<\/em>. Najs\u0142awniejsze s\u0105 na pewno aksjomaty Euklidesa, stanowi\u0105ce podstaw\u0119 geometrii p\u0142askiej przestrzeni. Zmieniaj\u0105c jeden z tych pewnik\u00f3w, mo\u017cna otrzyma\u0107 inne geometrie \u2013 eliptyczn\u0105 b\u0105d\u017a hiperboliczn\u0105. Aksjomaty arytmetyki sformu\u0142owa\u0142 Giuseppe Peano. Wymy\u015bli\u0142, \u017ce liczby naturalne (dalej tu nie wyjdziemy) mo\u017cna okre\u015bli\u0107, przyjmuj\u0105c istnienie pewnej pocz\u0105tkowej liczby (dzisiaj dwie odr\u0119bne szko\u0142y zaczynaj\u0105 od 0 b\u0105d\u017a od 1, to kwestia umowy), poj\u0119cie nast\u0119pnika (nast\u0119pnej liczby naturalnej, np. po 0 nast\u0119pna jest 1, a po 143 nast\u0119pna jest 144). Dalej przyjmuje si\u0119, \u017ce je\u015bli dwie liczby naturalne maj\u0105 r\u00f3wne nast\u0119pniki, to same te\u017c s\u0105 r\u00f3wne, a wspomniana pocz\u0105tkowa liczba (dajmy na to 0) nie jest nast\u0119pnikiem \u017cadnej innej liczby naturalnej. I tutaj wchodzi aksjomat indukcji<\/strong>.<\/p>\n

We\u017amy zbi\u00f3r o dw\u00f3ch w\u0142asno\u015bciach:
\n\u2022 nale\u017cy do niego 0
\n\u2022 je\u015bli liczba naturalna n<\/em> nale\u017cy do tego zbioru, to i nale\u017cy do niego jej nast\u0119pnik.<\/p>\n

Matematycy lubi\u0105 to zapisywa\u0107 czym\u015b w rodzaju skrzy\u017cowania hieroglif\u00f3w i pisma klinowego, ale my\u015bl\u0119, \u017ce formalizacj\u0119 mo\u017cemy sobie pomin\u0105\u0107. Niezale\u017cnie od zapisu zbi\u00f3r o powy\u017cszych dw\u00f3ch w\u0142asno\u015bciach zawiera wszystkie liczby naturalne<\/em>. To w\u0142a\u015bciwie wszystko, co trzeba poda\u0107, by scharakteryzowa\u0107 liczby naturalne. Oczywi\u015bcie gdyby\u015bmy chcieli co\u015b na nich liczy\u0107 b\u0105d\u017a wprowadza\u0107 relacj\u0119 porz\u0105dku (liczby naturalne ju\u017c tak maj\u0105, \u017ce jak we\u017amiemy dwie, to jedna b\u0119dzie mniejsza lub r\u00f3wna drugiej; nie wszystkie zbiory liczb maj\u0105 tak\u0105 w\u0142a\u015bciwo\u015b\u0107), to trzeba zdefiniowa\u0107 te dzia\u0142ania czy relacje za pomoc\u0105 dodatkowych aksjomat\u00f3w. Dodawanie np. definiuje si\u0119 znowu przez indukcj\u0119; dla dowolnej liczby naturalnej a<\/em>:<\/p>\n

\u2022 a + 0 = a
\n\u2022 a + nast\u0119pnik (b) = nast\u0119pnik (a+b)<\/p>\n

Jak widzimy, 0 jest elementem neutralnym (dodanie go nie zmienia \u017cadnej liczby naturalnej), dodawanie 1 do a<\/em> oznacza wzi\u0119cie nast\u0119pnika a<\/em>, dodawanie 2 oznacza wzi\u0119cie nast\u0119pnika nast\u0119pnika itd., do niesko\u0144czono\u015bci, co mo\u017cna\u00a0sprawdza\u0107 ad mortem defecatam<\/em>, jak to si\u0119 m\u00f3wi w polityce.<\/p>\n

Wiele twierdze\u0144 dowodzi si\u0119, korzystaj\u0105c z indukcji. Dowodzi si\u0119 twierdzenia najpierw dla pocz\u0105tkowej liczby (zwykle 0 b\u0105d\u017a 1), nast\u0119pnie zak\u0142ada si\u0119, \u017ce co\u015b zachodzi dla n<\/em>, i dowodzi dla n+1<\/em>. Je\u015bli zachodzi dla liczby pocz\u0105tkowej i je\u015bli zachodzi dla n<\/em>, to zachodzi dla n+1<\/em>, to z aksjomatu indukcji zachodzi dla wszystkich liczb naturalnych. Przyk\u0142adowo je\u015bli dany zbi\u00f3r ma N<\/em> element\u00f3w, to zbi\u00f3r wszystkich jego podzbior\u00f3w (tzw. zbi\u00f3r pot\u0119gowy<\/em>) ma element\u00f3w 2 do pot\u0119gi N<\/em>.<\/p>\n

\u2022 Je\u015bli zbi\u00f3r ma 0 element\u00f3w (zbi\u00f3r pusty), to ma tylko 1 podzbi\u00f3r: r\u00f3wnie\u017c zbi\u00f3r pusty. Jest 1 taki podzbi\u00f3r, a 2 do pot\u0119gi 0<\/em> wynosi 1. Zgadza si\u0119.
\n\u2022 Za\u0142\u00f3\u017cmy, \u017ce zbi\u00f3r N-elementowy ma 2 do pot\u0119gi N<\/em> podzbior\u00f3w.
\n\u2022 Stw\u00f3rzmy z niego zbi\u00f3r maj\u0105cy N+1<\/em> element\u00f3w, dodaj\u0105c 1 dodatkowy element (mo\u017cemy to zrobi\u0107, bo dwa zbiory zawsze maj\u0105 swoj\u0105 sum\u0119, to akurat jeden z aksjomat\u00f3w teorii mnogo\u015bci). Ile podzbior\u00f3w b\u0119dzie mia\u0142 nowy zbi\u00f3r? Ano po pierwsze zawiera\u0107 b\u0119dzie wszystkie podzbiory, kt\u00f3re mia\u0142 wyj\u015bciowy zbi\u00f3r. Ponadto ka\u017cdemu z tych podzbior\u00f3w odpowiada podzbi\u00f3r r\u00f3\u017cni\u0105cy si\u0119 od nich o tyle tylko, \u017ce zawiera ten jeden element, kt\u00f3ry dodali\u015bmy. B\u0119dzie ich tyle samo, czyli ca\u0142kowita liczna podzbior\u00f3w zwi\u0119kszy si\u0119 dwa razy. Je\u015bli wcze\u015bniej podzbior\u00f3w by\u0142o 2 do N<\/em>, to teraz mamy ich 2*2 do N<\/em>, czyli 2 do pot\u0119gi N+1<\/em>. Zgadza si\u0119. Twierdzenie udowodnione. Matematycy nabazgraliby kwadracik b\u0105d\u017a quod erat demonstrandum<\/em> (co by\u0142o do pokazania<\/em>).<\/p>\n

To teraz we\u017amy inny przyk\u0142ad, tzw. paradoks koni. Spr\u00f3bujemy udowodni\u0107, \u017ce wszystkie konie s\u0105 tej samej barwy.<\/p>\n

\u2022 Aby unikn\u0105\u0107 absurdu zwi\u0105zanego z pustym zbiorem koni (jak nie ma koni, to nie maj\u0105 \u017cadnej barwy), zacznijmy od 1. W zbiorze 1 konia ka\u017cdy ko\u0144 ma t\u0119 sam\u0105 barw\u0119. Dla liczby pocz\u0105tkowej 1 mamy dowiedzione.
\n\u2022 Za\u0142\u00f3\u017cmy, \u017ce zbi\u00f3r n<\/em> koni jest zbiorem koni o tej samej barwie.
\n\u2022 Doprowad\u017amy do tego zbioru kolejnego konia o numerze n+1<\/em>. Nast\u0119pnie usu\u0144my jednego z wcze\u015bniej ju\u017c obecnych koni (o tej samej barwie co pozosta\u0142e z obecnych od pocz\u0105tku w naszym zbiorze). Otrzymujemy w ten spos\u00f3b znowu\u017c zbi\u00f3r n<\/em> koni. Z za\u0142o\u017cenia wszystkie te konie maj\u0105 t\u0119 sam\u0105 barw\u0119, a wi\u0119c nowy ko\u0144 jest tej samej barwy co poprzednie. Doprowad\u017amy teraz konia, kt\u00f3rego\u015bmy wcze\u015bniej usun\u0119li. Ma t\u0119 sam\u0105 barw\u0119 co wszystkie pozosta\u0142e w tym zbiorze. A wi\u0119c zbi\u00f3r n+1<\/em> koni jest zawsze zbiorem koni o tej samej barwie.<\/p>\n

Dowiedli\u015bmy zdanie dla liczby pocz\u0105tkowej 1 i dowiedli\u015bmy, \u017ce je\u017celi zdanie zachodzi dla n<\/em>, to zachodzi dla n+1<\/em>. Zdanie zachodzi wi\u0119c dla ka\u017cdej liczby naturalnej. Ka\u017cdy zbi\u00f3r koni jest zbiorem koni o tej samej barwie. R\u00f3wnie\u017c zbi\u00f3r wszystkich koni. Ergo: wszystkie<\/em> konie s\u0105 tej samej barwy.<\/p>\n

Jak wida\u0107, wniosek jest absurdalny, niezgodny z do\u015bwiadczeniem. Pytanie brzmi: gdzie jest b\u0142\u0105d?<\/strong><\/p>\n

Ilustracja: Ko\u0144 w liczbie 1. Zdj\u0119cie wykonane przez autora.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Jednym z kluczowych w arytmetyce poj\u0119\u0107 jest indukcja matematyczna. Bez niej w\u0142a\u015bciwie dzisiejsza matematyka nie istnieje.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[241,11,4,55,1],"tags":[384,383,387,385,388,382,386],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts\/6353"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/comments?post=6353"}],"version-history":[{"count":5,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts\/6353\/revisions"}],"predecessor-version":[{"id":6424,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts\/6353\/revisions\/6424"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/media?parent=6353"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/categories?post=6353"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/tags?post=6353"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}