Zasada Indukcji Początkowej

[Pikier]

Zasmuciło mnie że w Kawiarni Szkockiej jest tak mało „nowatorskich idei matematycznych”, więc postanawiam znowu dodać coś mojego. Jest to wprawdzie drobiazg, ale... na bezrybiu i rak ryba:

Niech \(\displaystyle{ n, i, k}\) będą liczbami naturalnymi, a \(\displaystyle{ T}\) tezą o liczbie naturalnej.
Dla każdej \(\displaystyle{ T}\) istnieje takie \(\displaystyle{ k}\) że:
JEŚLI dla każdego \(\displaystyle{ i < k}\) jest \(\displaystyle{ T(i)}\)
TO \(\displaystyle{ T(n}\)) zachodzi dla każdego \(\displaystyle{ n}\)

Mam nadzieję że Władze Forum wybaczą mi że nie użyłem symboli kwantyfikatorów,
ale kierowała mną troska o Czytelników – tutaj tak jest jednak przejrzyściej.

Dowód Zasady jest trywialny, ale wydźwięk dość niespodziewany, co wyjaśnię (głównie Moderatorom) na przykładzie:
Kiedyś Duże Twierdzenie Fermata było udowodnione dla wykładników, powiedzmy do 200. Otóż nie wykluczone, że już z tego wynikało że jest prawdziwe dla wszystkich, a być może z tego nawet że było udowodnione dla mniejszych od 30. Prawda że ta możliwość jest zaskakująca?!
Niestety, Zasada jest niekonstruktywna – nie widać sposobu na wyznaczenie owego dostatecznie dużego k, a tylko wiadomo że istnieje – niemniej sama w sobie jest ciekawa, ze względu na pewne podobieństwo do zwykłej indukcji i walor dydaktyczny.

Przy okazji:
Mój wpis https://www.matematyka.pl/427026.htm został przeniesiony z Kawiarni do Kosza, z tego powodu że nie użyłem Latexa. Gotów więc jestem uzupełnić ten wpis o jedyną formułę matematyczną jakiej użyłem we wskazanym linkiem Dowodzie – oto ona:
\(\displaystyle{ S(x)=(x-x _{1}) ^{2}+(x-x _{2}) ^{2}+...+(x-x _{n}) ^{2}}\)
I niezmiernie mi przykro że nie potrzebowałem formuł więcej (może w przyszłości?)

[leg14]

Niech \(\displaystyle{ T(n) = ( n < -1 )}\). Jakie jest to \(\displaystyle{ k}\) w tym wypadku?


Edit albo nawet \(\displaystyle{ T(n) =}\) n rozkłada się na unikalny z dokładnością do permutacji iloczyn liczb pierwszych. Jkaie teraz jest k?

Możemy się założyć. Jeśli podasz mi dobre k do obu sytuacji (i to udowodnisz), to usuwam konto na forum. W przeciwnym wypadku Ty usuwasz tego posta.

Kiedyś Duże Twierdzenie Fermata było udowodnione dla wykładników, powiedzmy do 200. Otóż nie wykluczone, że już z tego wynikało że jest prawdziwe dla wszystkich, a być może z tego nawet że było udowodnione dla mniejszych od 30. Prawda że ta możliwość jest zaskakująca?!

....


Facet nie chce podać dowodu, bo "jest za łatwy i się ośmieszy".

[Pikier]

Wypada mi objaśnić nieco Zasadę Indukcji Początkowej...

Każdemu uczącemu się matematyki wpaja się od początku zasadę, że sprawdzenie twierdzenia dla iluś tam konkretnych liczb nie jest żadnym dowodem, że należy wykazać że musi ono zachodzić dla wszystkich. Jest to oczywiście słuszne, więc wbija się to tak trwale do głowy że niesposób sobie wyobrazić że może kiedykolwiek być inaczej, a dokładniej - nieco inaczej.
Ja też to miałem tak utrwalone w głowie, że dopiero na starość przyszło mi do głowy sprawdzić, czy aby udowodnienie czegoś dla dostatecznie wielu kolejnych liczb naturalnych nie starczy niekiedy za dowód ogólny. Jakim cudem mogłem pomyśleć o takim wariactwie? – nie wiem, chyba z wrodzonej przekory. Rozpisałem, to na kształt twierdzenia i okazało się że jest... prawdziwe. Zdumiałem się niesłychanie i sądzę że tak samo zdumiałby się każdy matematyk który tego nie widział. Zdumiałem się ponadto tym że nigdy na to się nie natknąłem, a przecież myśl jest nadzwyczaj prosta (chociaż sam zapis tak bardzo prosty nie jest).
Jak człowiek natrafia na coś zdumiewającego, to zazwyczaj chce swoim zdumieniem się podzielić - stąd ten występ w Kawiarni i tej zasady ochrzczenie.
Niestety, ma ona ten mankament że znalezienie owej dostatecznie wielkiej liczby naturalnej (do której wystarczy dojść) wygląda na trudniejsze od dowodu ogólnego dla wszystkich liczb naturalnych. Ale kto wie – może kiedyś komuś w ten właśnie sposób będzie łatwiej? Wszak rzeczy zdumiewające mogą pozwalać sobie na luksus wystąpienia – już za mojego życia odkryto algorytmy o których nigdy bym nie przypuszczał że mogą istnieć.

P.S.
A mojemu Szanownemu Przedpiszcy podaję wartości „k” o które się pyta:
137 – dla tezy pierwszej, 23456 – dla tezy drugiej.
Ale rozpisywać dowodu że są poprawne już nie mam siły.

[Premislav]

Rozpisałem, to na kształt twierdzenia i okazało się że jest... prawdziwe.

A może byłbyś tak uprzejmy i napisał dowód? Jak pewnie wiesz, matematyka nie polega na żonglowaniu liczbami i stwierdzeniami z kapelusza, tylko na przeprowadzaniu dowodów twierdzeń. Stwierdzenie „dowód jest trywialny" (niewątpliwie to subiektywne określenie nierzadko występuje w skryptach i podręcznikach, już wolę dowód pozostawiamy jako ćwiczenie+ opcjonalnie jakaś wskazówka co do metody) nie może posłużyć za dowód.

A mojemu Szanownemu Przedpiszcy podaję wartości „k” o które się pyta:
137 – dla tezy pierwszej, 23456 – dla tezy drugiej.
Ale rozpisywać dowodu że są poprawne już nie mam siły.

Skomentuję to tak: Odkryłem prawdziwie cudowny dowód tego faktu, jednakże ten margines jest zbyt wąski, by go zmieścić. Poza tym moim zdaniem dla pierwszego stwierdzenia dobre jest \(\displaystyle{ 2137}\) (hehe papież), a dla drugiego \(\displaystyle{ 1488}\) (hehe Hitler), ale nie będę tracić czasu na rozpisywanie tego.

Jak na stare lata nie starcza siły, to proponuję bierki. Świetna zabawa!

[AiDi]

A może byłbyś tak uprzejmy i napisał dowód?

Dodam, że jest to warunek konieczny (lecz nie dostateczny), by temat ten został w tym dziale w którym jest.

Ale rozpisywać dowodu że są poprawne już nie mam siły.

Nie nie, to tak nie działa. Przykro mi bardzo, ale na tym forum obowiązują pewne zasady, w szczególności w Kawiarni Szkockiej.

[Pikier]

Tam do licha. Mam podawać dowód czegoś takiego!?
To jest Kawiarnia Szkocka, a nie szkółka dla analfabetów matematycznych.
Odmawiam.

[AiDi]

To jest Kawiarnia Szkocka

Już jest Hyde Park.-- 9 gru 2017, o 11:15 --Jako, że Pikier przeszedł do "merytorycznego" argumentowania swoich matematycznych racji obrażaniem, temat można uznać za wyczerpany.

[krl]

Niestety, Aidi zamknął wątek: 427068.htm#p5520261
zanim udało mi się w nim wypowiedzieć. Dlatego pozwolę sobie otworzyć nowy wątek pod tym samym tytułem i odnieść się do wypowiedzi w starym wątku.

Ze smutkiem stwierdzam, że krytyka wypowiedzi Pikiera w wykonaniu Leg14, Premislava no i Aidi była przynajmniej nieprofesjonalna. Krytykanci zaś po prostu nie mieli w pełni racji.

Leg14 w poście z 6 gru 2017, o 20:16 obiecał, że "Jeśli [Pikier] poda mi dobre k do obu sytuacji (i to udowodni), to usuwam konto na forum". Pikier podał dobre k. Nie podał dowodu (no ale w przypadku dowodów banalnych tradycyjnie można je pomijać). Leg14 ma szczęście, bo gdyby Pikier podał ów prosty dowód, Leg14 byłby zobligowany do zamknięcia swojego konta. Liczby \(\displaystyle{ k}\) podane przez Premislava też są dobre...

Błąd Pikiera nie polegał na tym, że samo twierdzenie przezeń podane:

Niech n, i, k będą liczbami naturalnymi, a T tezą o liczbie naturalnej.
Dla każdej T istnieje takie k że:
JEŚLI dla każdego i < k jest T(i)
TO T(n) zachodzi dla każdego n

jest fałszywe, bo ono jest prawdziwe (czego niestety nie przyznali jego polemiści). Błąd polegał na dalszych sugestiach, że może ono służyć owocnie do dowodzenia twierdzeń.
To, że jakaś implikacja \(\displaystyle{ pRightarrow q}\) jest prawdziwa (gdzie \(\displaystyle{ p}\) i \(\displaystyle{ q}\) są konkretnymi zdaniami), nie oznacza bowiem, że w danym systemie rozumowania zdanie \(\displaystyle{ q}\) wynika ze zdania \(\displaystyle{ p}\).
Ale sugestia Pikiera była obwarowana odpowiednim zastrzeżeniem:

Każdemu uczącemu się matematyki wpaja się od początku zasadę, że sprawdzenie twierdzenia dla iluś tam konkretnych liczb nie jest żadnym dowodem, że należy wykazać że musi ono zachodzić dla wszystkich. Jest to oczywiście słuszne...

Co najwyżej jego zdumienie odkrytym przezeń twierdzeniem jest, powiedzmy, naiwne. Ale to wg mnie nie jest wystarczający powód do niemerytorycznej krytyki, która go spotkała.

Dodam jednak, że fałszywe jest następujące wzmocnienie twierdzenia Pikiera:

Twierdzenie A. Dla każdej tezy \(\displaystyle{ T(x)}\) o liczbach naturalnych istnieje liczba naturalna \(\displaystyle{ k}\) taka, że jeśli teza \(\displaystyle{ T}\) jest prawdziwa dla wszystkich liczb naturalnych \(\displaystyle{ i<k}\), to zdanie \(\displaystyle{ (forall xinmathbb{N})T(x)}\) jest dowodliwe (np. w systemie Arytmetyki Peana).

Ale twierdzenie A wcale nie tak łatwo obalić!

[Premislav]

To, że implikacja jest prawdziwa, nie znaczy, że twierdzenie jest prawdziwe (ani że w ogóle mamy do czynienia z twierdzeniem - chyba że dość swobodnie operuje Pan odcieniami znaczeniowymi, raz mając na myśli twierdzenie matematyczne, a raz twierdzenie typu „pani Józia twierdzi, że kiedyś to były czasy"), dość osobliwe, że z jednej strony sam Pan pisze o różnicy między implikacją a wynikaniem, zaś z drugiej nazywa Pan to, co napisał użytkownik Pikier twierdzeniem. Moim zdaniem coś takiego:
jeśli suma miar kątów wewnętrznych w trójkącie wynosi \(\displaystyle{ \pi}\) radianów, to hipoteza Goldbacha jest prawdziwa
w obrębie powszechnie przyjętej aksjomatyki nie jest żadnym twierdzeniem, choć możemy rozpatrywać wartość logiczną takiego zdania (oczywiście istnieją bardziej prozaiczne przykłady, ale już raz Pańska specyfika spowodowała niezrozumienie mojego porównania, więc postarałem się dostosować).

Może wzbudzono we mnie błędne przekonanie, ale formułując twierdzenia matematyczne, chcemy zazwyczaj by z założeń wynikała teza. U Pikiera tego nie widzę (prawdziwość implikacji, jak sam Pan przecież pisze, nie jest tożsama z wynikaniem). A raczej celem działu Kawiarnia Szkocka są twierdzenia matematyczne i ich dowody (oraz dyskusja nad takowymi).

Poza tym AiDi napisał tylko jakie są zasady obowiązujące w dziale Kawiarnia Szkocka, a więc być może to trochę przesada oskarżać go o krytykanctwo, choć z drugiej strony nie dziwi mnie zaistnienie tej przesady.

[leg14]

Skoro już zostałem wywołany do tablicy, to dodam, że moja pierwsza odpowiedź do Pikiera nie mogła żadną miarą być uznana za agresywną bądź nieprofesjonalną. Jej forma ewoluowała w miarę wymiany prywatnej korespondencji z nim .

Tak myślałem, że chodzi o logiczne mambo jambo ( z przymrużeniem oka bierzcie tę uwagę), dlatego czekałem na dowód, zwłaszcza, że uwaga Pikeira o WTF raczej sugerowała

następujące wzmocnienie twierdzenia Pikiera:

. Stąd liczyłem na jakieś wyklarowanie sytuacji z jego strony. Nawiasem mówiąc skoro takie, rzeczy uznajemy za stwierdzenia, to czemu by tego nie wzmocnić? Mozliwości są nieograniczone - po co działać tylko na liczbach naturalnych? Na forum pojawia się masa undergroundowych matematyków, jeśli Pikier nie chce dyskutować i bronić swoich racji, to czemu mam z radością przyjmować jego zaśmiecanie kawiarni ( która zdechła lata temu, gdy mnie na forum jeszcze nie było, a teraz zostały nam tylko takie kwiatki(nie licząc np. postów Guraka, ale kontent jego postów też raczej nie należy do KS), zwłaszcza, że to nie był pierwszy taki post Pikiera ?

[AiDi]

Ze smutkiem stwierdzam, że krytyka wypowiedzi Pikiera w wykonaniu [...]Aidi była przynajmniej nieprofesjonalna. Krytykanci zaś po prostu nie mieli w pełni racji.

Słucham? Powtórzę - na tym forum panują pewne zasady. Poprosiłem o coś, odmówiono, temat przeniosłem. Potem zaczęło się wyzywanie moderacji od idiotów. Reagowanie na to jest nieprofesjonalne? Temat odblokowuję bo widzę, że jest szansa podnieść jego poziom merytoryczny.

[krl]

Rzeczywiście, trochę przesadziłem, bo Aidi nie krytykował. Tylko przeniósł temat do Hyde Parku, a następnie go zamknął. Nie zmienia to faktu, że twierdzenie Pikiera jest poprawnym i prawdziwym twierdzeniem o liczbach naturalnych, co było niesłusznie kwestionowane. Dowód jest banalny, ale nie wszystkie twierdzenia mają trudne dowody. Dlatego mogę zrozumieć emocjonalną reakcję Pikiera.
Podobne idee są wyrażone w innych twierdzeniach i konstrukcjach matematycznych, np. w teorii mnogości. Mam tu na myśli np. twierdzenie o refleksji czy też liczby Hanfa.
"Undergroundowi matematycy": ja podchodzę do nich z sympatią. Czasami ich posty pobudzają wyobraźnię...
@Premislav: poglądy na naturę matematyki i jej twierdzeń zmieniały się w czasie. Początkowo matematyka dotyczyła tylko liczb i geometrii. Później poszerzono ją o analizę itd. Współcześnie mamy ramy logiczne, w których uprawiamy matematykę. Dopiero w tych ramach można wysłowić twierdzenia Goedla! I z grubsza, twierdzenie teorii (w wersji sformalizowanej) to dowolna formuła języka teorii, dowodliwa w tej teorii. Zaś twierdzenie matematyczne to w praktyce takie twierdzenie, które można sformalizować w ramach określonej teorii. Twierdzenie Pikiera spełnia to kryterium (i nie jest istotne, że jest banalne).

[Premislav]

No to przegrałem. Przepraszam w takim razie za zawracanie głowy. Uwierają mnie takie zasady, ale takie najwyraźniej są.
Szkoda, że nie mogę pstryknąć palcami i wrócić z miejsca do mojej ukochanej (niegdyś) historii, bo w matematyce zawsze tylko się myliłem.

[leg14]

Ja też to miałem tak utrwalone w głowie, że dopiero na starość przyszło mi do głowy sprawdzić, czy aby udowodnienie czegoś dla dostatecznie wielu kolejnych liczb naturalnych nie starczy niekiedy za dowód ogólny. Jakim cudem mogłem pomyśleć o takim wariactwie? – nie wiem, chyba z wrodzonej przekory. Rozpisałem, to na kształt twierdzenia i okazało się że jest... prawdziwe.

To nie jest prawdą i nawet papież mnie nie przekona, że jest inaczej.

[krl]

Ja też to miałem tak utrwalone w głowie, że dopiero na starość przyszło mi do głowy sprawdzić, czy aby udowodnienie czegoś dla dostatecznie wielu kolejnych liczb naturalnych nie starczy niekiedy za dowód ogólny. Jakim cudem mogłem pomyśleć o takim wariactwie? – nie wiem, chyba z wrodzonej przekory. Rozpisałem, to na kształt twierdzenia i okazało się że jest... prawdziwe.

To nie jest prawdą i nawet papież mnie nie przekona, że jest inaczej.

Oczywiście. To, co cytujesz, to z grubsza Twierdzenie A (w moim poście), które jest fałszywe (ale które jednak niełatwo obalić...). Pikier sformalizował je niedokładnie, w formie Twierdzenia Pikiera, które jest prawdziwe. Po prostu Pikier nie odróżnił prawdziwości zdania \(\displaystyle{ Z}\) o liczbach naturalnych od jego dowodliwości (w jakimś systemie rozumowania, np. Arytmetyce Peana). To nie to samo. Może być zdanie prawdziwe, którego jednak nie można udowodnić.
Gdybyśmy natomiast potrafili określić, dla dowolnej tezy \(\displaystyle{ T(x)}\) o liczbach naturalnych, oszacowanie \(\displaystyle{ f(T)\in\mathbb{N}}\) na ewentualny kontrprzykład \(\displaystyle{ x\in\mathbb{N}}\) dla tezy \(\displaystyle{ \forall x T(x)}\), przy pomocy funkcji obliczalnej \(\displaystyle{ f}\), to dawałoby to nam metodę rozstrzygania prawdziwości zdań o liczbach naturalnych (Jak rozumiem, to miał na myśli Pikier). Ogólnie tego typu oszacowanie nie może istnieć...
Ale takie rozważania prowadzą np. do metody rezolucji, która jest podstawą do automatycznego dowodzenia twierdzeń w informatyce.
@Premislav: napisałem: To, że jakaś implikacja \(\displaystyle{ p\Rightarrow q}\) jest prawdziwa (gdzie \(\displaystyle{ p}\) i \(\displaystyle{ q}\) są konkretnymi zdaniami), nie oznacza bowiem, że w danym systemie rozumowania zdanie \(\displaystyle{ q}\) wynika ze zdania \(\displaystyle{ p}\).
Miałem na myśli coś takiego: załóżmy, że mamy zdanie \(\displaystyle{ (\forall x\in\mathbb{N})T(x)}\), o którym skądinąd wiemy, że jest prawdziwe. W tym przypadku dla każdego \(\displaystyle{ k\in\mathbb{N}}\) prawdziwa jest implikacja \(\displaystyle{ A}\): \(\displaystyle{ (\forall i<k)T(i)\Rightarrow(\forall x\in\mathbb{N})T(x)}\). Niekoniecznie mamy jednak jej dowód.
Teraz, jeśli weźmiemy nawet bardzo duże \(\displaystyle{ k}\) i dla wszystkich \(\displaystyle{ i<k}\) osobno napiszemy sobie dowody zdań \(\displaystyle{ T(i)}\), to bez dowodu zdania \(\displaystyle{ A}\) nie da to nam dowodu zdania \(\displaystyle{ \forall x T(x)}\).