Matematička indukcija -- pogreška pri formuliranju pretpostavke

Ok, idemo redom.

Da, i mene je fenomen začudio. Činjenica je da je math-dokazivanje jedna prilično osjetljiva stvar, i sva poanta i snaga dokaza je u logičkom odmaku završne konkluzije od početnih premisâ. Kod indukcije je to naročito izraženo: iz tvrdnje da nešto vrijedi za samo jedan prirodni broj, i jedne univerzalne implikacije, ja mogu zaključiti univerzalnu tvrdnju da nešto vrijedi za svaki prirodan broj. Moćno, zar ne?

Samo treba tu univerzalnu implikaciju dokazati kako treba, i iz ispravnih premisâ. Ona ima oblik (Ak@|N)(P(k)=>P(k+1)). Nažalost, ovo je jedno od mjestâ gdje kvantifikatori nisu distributivni prema logičkim veznicima, te gornji zapis nije ekvivalentan zapisu (Ak@|N)P(k)=>(Ak@|N)P(k+1). A to je, nažalost, ono što je jaako puno studenata, i to dobrih studenata, napravilo. U pretpostavci indukcije, napisali su "Pretpostavimo da P vrijedi za svaki k@|N". :-(

E sad, zašto je to tako strašno? Kao što rekoh gore, sva bit math-dokaza je u, da tako kažem, "udaljenosti" između premisa i konkluzije. Ako sam dokazao nešto što je prilično daleko i na puno većoj "visini" od premisâ, dokaz je moćan.
Nažalost, vrijedi i dualno: ako sam dokazao neku od svojih pretpostavki, dokaz je bezvrijedan. Mislim da ćemo se složiti da iz P dokazati P (bar neformalno:) stvarno nije neko umijeće. :-/

A to je upravo ono što ispada kad čovjek čita gore skiciran "dokaz" indukcijom. Prvo se dokaže baza, a onda se iz pretpostavke koja je potpuno jednaka onom što treba dokazati dokaže to isto (zapravo slabije: dokaže se da tvrdnja vrijedi za svaki prirodni broj od 2 nadalje. Tek s bazom to postaje ekvivalentno pretpostavci). Dokaz na taj način ima oblik dokaza P=>P, i zaista se tu ne dokazuje zapravo ništa.

E sad, činjenica je da su ti ljudi uglavnom bar bazu riješili kako treba, i obično je praksa da se za bazu dade koji bod. No kao što napisah gore, baza tek pretvara taj napisan dokaz u dokaz oblika P=>P. Dakle, čak i uz nju dokaz zapravo nema logičke vrijednosti. Nema svrhe dokazati P(1), ako već u sljedećem koraku pretpostavim puuno snažniju stvar (Ak@|N)P(k).

Možda postoji i argument za suprotnu tezu ovdje, a to je princip "nema negativnih bodova". Odnosno, ako je netko napisao samo bazu, dobio je (ja mislim 1 ) bod. Može se argumentirati da ako je netko napisao više od toga, kakvu god glupost napisao, nije fer kazniti ga oduzimanjem tog boda koji je već zaradio. To sad ovisi o asistentu Pažaninu, koji je ispravljao taj zadatak, i bit će na žalbama u utorak. Ja sam pričao s njim o tom problemu, i rekao mi je da je ionako davao samo jedan bod za sâmu bazu, te da smatra da ljudi valjda neće za jedan bod ići na žalbe. Možda vas je potcijenio... u svakom slučaju, osim baze koja može biti diskutabilna (iako sam prezentirao gore argument da ni ona ništa ne vrijedi u ovom kontekstu), smatram da nemate pravo na bodove.

Samo još jednu stvar da napomenem, za ljude koji ovo gledaju "izvana". Brucoši još nemaju dovoljno fluentno math-izražavanje (treba samo vidjeti što sve ja moram čitati na 1. zadatku :-o), i često im se tu debelo gleda kroz prste. No ovo je specifičan slučaj. Na vježbama je posvećeno nekoliko minuta nabrajanju (i možda pokazivanju primjerâ) najčešćih grešaka kod dokazivanja math-indukcijom, i ova je zasigurno bila spomenuta kao najozbiljnija. Dakle, bili ste upozoreni. Matematičkoj strogosti se morate naučiti prije ili kasnije. Ako vam netko eksplicitno kaže da je neko argumentiranje pogrešno, očekuje se da ga ne koristite. :-/

---

Nesi:

ok, call me blind/stupid/votevr
no koliko mene moj mozak sluzi, ovo je forma indukcije koju su meni uviejk tupili...... ovo u zagradama se kao podrazumijeva, a sad mi se cini da se cijelo vrijeme podrazumijevalo nesto sasvim krivo.....

(*)baza n=1 (recimo)
pretp: n=n (da li ovo zapravo znaci da pretp. da nesto vrijedi za neki, pa onda dokazavsi da vrijedi i za n+1 to povlaci da vrijedi za sve?!!?)
korak... n=n+1 (dokazujemo za n+1)
blabla

jerbo..... prva verzija koju napisah je bila n=n (pretp da vrijedi za svaki n)
a obzirom na raspravu...... [b]a i na razum kojeg upravo ukljucih[/b].... nesto mi tu smrdi.....

dakle, u konacnici pitanje: ovo moje sto napisah(*) je ok?

Ok, idemo još jednom. Pun zapis aksioma matematičke indukcije glasi
P(1) & (Ak@|N)(P(k)=>P(k+1)) => (An@|N)P(n)
, gdje je P nešto dosta komplicirano za definirati, ali neformalno recimo "neko svojstvo prirodnih brojeva" (P(ž) znači da prirodni broj ž ima to svojstvo).

Dakle, indukcija (kao i većina teorema u mathu) ima oblik implikacije. Da bi se ona mogla iskoristiti (konzultiramo tablicu istinitosti), treba dokazati njenu pretpostavku, dakle
P(1) & (Ak@|N)(P(k)=>P(k+1))
, i onda možemo izvući kao zaključak njenu posljedicu,
(An@|N)P(n)
, što je u većini slučajeva upravo ono što nam treba.

Dakle, treba dokazati P(1) & (Ak@|N)(P(k)=>P(k+1)),
i to ima oblik konjunkcije. Opet konzultiramo tablicu istinitosti, i vidimo da treba dokazati oba njena dijela:
P(1)
i
(Ak@|N)(P(k)=>P(k+1)
, da bismo mogli zaključiti da ona vrijedi.

Ovo prvo se obično lako dokaže, i zove se baza. Ovo drugo se obično malo teže dokaže, i zove se korak. Bacimo se na to.
Ta izjava ima oblik univerzalne kvantifikacije po k@|N. Sad nažalost ne možemo konzultirati tablicu istinitosti (to bi bila kao fol konjunkcija beskonačno mnogo implikacijâ tipa (P(1)=>P(2))&(P(2)=>P(3))&....), pa moramo primijeniti neku drugu taktiku.

Razmišljamo ovako: ja moram, in effect, dokazati P(52)=>P(53). No to moram napraviti tako da se u tom dokazu broj 52 može zamijeniti bilo kojim prirodnim brojem (zovem ga k) (a broj 53 njegovim sljedbenikom). Na prvi pogled, to je stvarno dobro napraviti metodom "sve muhe jednim udarcem", odnosno pretpostaviti P(k) univerzalno. Ali gledajmo korak dalje... ako smo stvarno pretpostavili P(k) univerzalno, čemu dovvaga dokazivati P(53) (i to, ironično, koristeći od naše univerzalne pretpostavke samo totalno loše odabran komad P(52):-])? To je onda stvarno samo specijalni slučaj naše pretpostavke, i nije ga nikakav problem dokazati. Pitamo se zašto je to tako? Ofcourse -- zato što smo, silly us, kompletno pretpostavili upravo ono što smo trebali dokazati.

Dakle, treba nam nešto drugo. Intuitivno, trebamo dokazati P(52)=>P(53), ali zapravo ne pretpostavljajući P(52). Zašto to ne moramo pretpostavljati? Zato što će slijediti iz implikacije P(51)=>P(52) koju smo hopefully dokazali, jednom kad imamo P(51). To će također slijediti iz P(50), po implikaciji P(50)=>P(51) koju smo također već dokazali, i tako dalje... odnosno, preciznije, i tako bliže jedinici. :-)

Dakle, na neformalnoj razini, imamo nešto poput beskonačne varijante onog što se obično zove BSOMP. Sjetimo se što je BSOMP... kad jednom shvatimo da se dokaz od točke na koju smo došli račva u dvije grane, koje su međusobno izomorfne ("jednakog oblika", prelaze jedna u drugu jednostavnom zamjenom nekih slovâ nekim drugim slovima, pri čemu zadatak ostaje isti pri toj zamjeni), možemo dokazati samo jednu od njih (svejedno koju), i iz toga će asistent znati zaključiti da smo znali dokazati i drugu.:-) Da umjesto dvije grane imamo njih 20, koje su također izomorfne, dovoljno bi bilo dokazati samo jednu od njih (napisavši na početak nešto poput "BSOMP da vrijedi prvi slučaj od njih 20"). Ta jedna bi onda poslužila kao template pomoću kojeg bi se mogle dokazati i ostalih 19, samo trivijalnim zamjenama slova ili uvrštavanjima specijalnih slučajeva. Da ih umjesto 20 imamo beskonačno, po jednu za svaki prirodni n, dovoljno bi bilo dokazati da za neku granu od njih, za neki n@|N, dokaz prolazi.

I zato korak indukcije ima takav oblik. Pretpostavi se da za neki n@|N (koji se onda obično označi s k, da se izbjegne konfuzija s čudnom notacijom n=n+1:) vrijedi P(k) , i iz toga se dokaže P(k+1). Na taj način dokazana je implikacija P(k)=>P(k+1), koja je zaista template za sve implikacije u gornjoj beskonačnoj konjunkciji: P(1)=>P(2), P(2)=>P(3), itd. Dakle, dokazano je (Ak@|N)(P(k)=>P(k+1)), i to bez pretpostavke (Ak@|N)P(k) (koja je naravno samo drugo ime za (An@|N)P(n), što trebamo dokazati). A to je upravo ono što smo tražili.

Primijetimo podvučenu riječ "intuitivno" gore. To pretpostavlja da univerzalna kvantifikacija ima oblik "beskonačne konjunkcije", što baš i nije logički definabilno u istom frameworku (tzv. logika prvog reda) unutar koje se obično radi gorespomenuta indukcija. Postoji i strogo logičko objašnjenje za to, no bojim se da je pomalo izvan opsega ove diskusije. Zato bih samo napisao jedan jednostavniji slučaj, koji dobro pokazuje zbog čega tu univerzalna kvantifikacija prelazi u egzistencijalnu.

To će biti za slučaj da P(k+1) zamijenimo tvrdnjom koja ne ovisi o k. Dakle, recimo da je to neka tvrdnja Q. To jest bitno pojednostavljivanje, ali će, vjerujem, pokazati što se događa.
Dakle, imamo (Ak@|N)(P(k)=>Q). Pogledajmo tablicu istinitosti, i vidjet ćemo da je formula P=>Q ekvivalentna formuli (!P)vQ (i inutitivno, math-implikacija da P povlači Q upravo znači da P ne vrijedi, ili pak Q vrijedi).

So, imamo (Ak@|N)(!P(k)vQ) . Dakle, za svaki prirodan broj k, imamo dvije mogućnosti: u prvoj, !P(k) , a u drugoj, Q. No druga ne ovisi o k , pa ako vrijedi Q (neovisno o k), ne mora uopće vrijediti nijedan !P(k). S druge strane, ako Q ne vrijedi, druga mogućnost otpada za svaki k, pa uvijek vrijedi !P(k). Sve u svemu, univerzalno imamo dva slučaja: u prvom Q , a u drugom (Ak@|N)!P(k). Odnosno, imamo tvrdnju ((Ak@|N)!P(k))vQ. Ako je hoćemo napisati u obliku implikacije (da izvučemo tu implikaciju van), pogledajmo gore, moramo je dovesti u oblik !P'vQ', odnosno prvi disjunkt mora biti negacija.

To možemo, ako se sjetimo formule za negiranje kvantifikatora -- negacija egzistencijalnog je univerzalni. Odnosno, naš prvi disjunkt, (Ak@|N)!P(k) je zapravo !(Ek@|N)P(k) . So, naša tvrdnja ima oblik
(!(Ek@|N)P(k))vQ , pa je možemo zapisati kao implikaciju
(Ek@|N)P(k)=>Q.

Sjetimo se od čega smo krenuli, i vidimo da je
(Ak@|N)(P(k)=>Q)
ekvivalentno s
((Ek@|N)P(k))=>Q.

Dakle, da za svaki k tvrdnja P(k) povlači Q, ekvivalentno je tome da tvrdnja "za neki k vrijedi P(k)" povlači Q . Naravno, kao što rekoh gore, kad Q ovisi također o k, stvari su kompliciranije jer se scopeovi zapetljavaju, ali u osnovi se događa ista stvar -- u pretpostavci, univerzalna kvantifikacija prelazi u egzistencijalnu. "Pretpostavimo da vrijedi za neki k."

i drugo, zasto se prije nije RIJECIMA govorilo? i ZAPISALO na plocu RIJECIMA?

Da bih napisao ovo gore, trebalo mi je vremena kao za jedne prosječne vježbe ( 2 sata). Ok, s pripremom bi možda bilo malo manje. Ali definitivno, takve stvari se pri ovom programu i tempu _ne stignu_ napraviti.

Sad jasno zašto želim logiku i teoriju skupova na prvoj (zapravo nultoj) godini? Ne da mučim studente... već da im omogućim da govore konzistentno, i da ih ne razumijemo mi , već i oni sami sebe.

Gore je boldano tvoje "a i na razum kojeg upravo ukljucih"... koliko si dosad dokaza indukcijom napravila? Neću reći da su svi bili potpuno bezvrijedni, ali definitivno bi imalo više smisla da ti je ovo gore netko prije rekao, zar ne?

a ne samo napisati n=n ili k=n ili neku inkarnaciju istog..... i smatrati da se podrazumijeva ovo 'neki n', kao sto rekoh, moj prvi impuls je bio reci 'za svaki'

Da, i ovo "n=n" isto vidjeh, i apsoštrumfno mi nije jasno kako netko može takvo nešto napisati. Što je onda korak, "n=n+1"?? :-/ "Za n=n+1" vrijedi sve, jer to ne zadovoljava nijedan n@|N.

Ako se već želi labelirati etape dokaza bez puno razmišljanja, standardne labele su "n=1","n=k"&"n=k+1".

---

Nesi:

zapravo sam mislila na sljedece:
ne pisati [latex]\forall k \in N[/latex] vec pisati [b]za neki [/b][latex]k \in N[/latex]

na ploci nisam (I believe) NIKADA vidjela da pise 'pretpostavimo da za neki k iz N vrijedi'

Pa iskreno se nadam da nisi ni vidjela da piše [latex]\forall k\in\bf N[/latex] (u pretpostavci indukcije po k).

to su mozda rekli - ali to ispari...... :roll:

Hm... pa da ti i piše u bilježnici iz kolegija koji si slušala prije dvije godine, jednako bi dosad isparilo kao i iz glave... ne li?

a jedino pisano bi bilo 'n=k' ili 'n=n' bez icega vise, uz, kao sto rekoh [u]mozda[/u] receno, ali cisto sumnjam.....

Mi smo to rekli. Bar se nadam, svi. Jer u vježbama po kojima svi radimo (krckovim), bilo je eksplicitno naglašeno kao česta greška. A što se tiče pisanja, čitaj dolje...

a cini se da je upravo tu big problem - prvih par puta bi bas rijecima trebalo zapisati 'pretp. da za NEKI k iz N vrijedi....' 'idemo provjeriti da li vrijedi za k+1'....<blabla dalje>

a tako necega se ne sjecam.....

The problem is, ljudima se previše na prvoj godini tupi s izomorfizmom intuitivnog shvaćanja i strogo logičkog kvantificiranja. I zato (IMO) ljudi imaju toliko problema sa shvaćanjem implikacije, zato mnogi ne kuže poantu dokaza metodom kontradikcije, prazan skup im predstavlja konceptualne probleme, i hrpa drugih stvari.

Kakve to veze ima s ovim? Kod mnogo njih, pogotovo ovih naprednijih studenata (koji su češće i napravili tu grešku), kvantifikatori su samo nešto što se onako "ofrlje" doda na izjavu, čisto kao neko pojašnjenje. I u tom mindsetu, [latex]\forall[/latex] znači "razmišljam univerzalno" (ono što engleski jezik označava članom "a"), dok [latex]\exists[/latex] znači "razmišljam partikularno" (ono što se u engleskom označava s "the"). A to u mnogim primjerima dovodi do gadnih miskoncepcijâ. Nemogućnost shvaćanja da za sve elemente praznog skupa vrijedi bilo što, je jedna od njih. Ovo o čemu ovdje pričamo je druga.

Jer stvarno, u tom mindsetu, čovjek samo želi reći "ovo što tu pišem, moći će se pretpostaviti, i iz toga dokazati što već treba, što god k bio. Razmišljam univerzalno". Da smo napisali na ploču "za neki", i to podvukli/istakli/whatever, dogodilo bi se nešto još gore /iako bi se možda za to dobilo više bodova:/. Čovjek bi rekao "aha, razmišljam partikularno", dokazao da recimo P(1)=>P(2), i gotova stvar. Suptilne stvari poput dosega pojedinih pretpostavki, i ostali detalji koji su bolno detaljno raspisani u gornjem postu, ostaju zauvijek skriveni.

Zato ja jednostavno eksplicitno upozorim ljude da ne smiju napisati "za svaki", i objasnim im zašto (otprilike kao ono što napisah gore, samo kraće:), ali ne pišem ni "neki", jer bih to vjerojatno prije ili kasnije napisao kao "[latex]\exists[/latex]", a iz gore opisanih razlogâ, mislim da bi ih to zbunilo još više. Jednostavno objasnim šprancu, dam intuitivno objašnjenje zašto ona radi, i nakon toga koristim labele "n=1","n=k"&"n=k+1" , uz napomenu da će o striktnim scopeovima pojedinih varijablî ovdje naučiti tek nešto kasnije.

(Osim toga, kad se piše strogo simbolički, nesporazum nestaje. Samo treba zatvoriti zagradu na pravom mjestu.
"(.za svaki k.)(pretpostavimo da vrijedi P(k) ...i iz toga dokažimo P(k+1)...)" je sasvim ok. No ljudi onda pišu polusimbolički, jednostavno ne stave zagrade, i u prvom retku ostane samo
za svaki k, pretpostavimo da vrijedi P(k).
Još se to onda "prevede" na klasični Analiza-dijalekt, koji stavlja kvantifikatore na kraj, i dobiješ
pretpostavimo da vrijedi P(k) za svaki k,
dakle, katastrofu.)

tuzno je da tek na trecoj godini postanem svjesna sto indukcija zbilja jest, a za nju mi pile vec 7 godina.... ali taj famozni 'neki' mi prije (u srednjoj) nije bas nesto posebno znacio
a na faxu su ga zaboravili propisno istaknuti.....

Da ti pravo kažem, nemam blagog pojma gdje bi ljudi ovo (što gore napisah) trebali čuti. Pravo mjesto bi bila neka nulta godina, gdje se uči jezik i samo jezik. (Pa zaBoga, ne učiš npr. norveški tako da te netko baci u Norvešku i pusti te da učiš metodom pokušaja i pogrešaka... prvo imaš bar neku probnu simulaciju.) Ovako, stvarno to ostavljam "za poslije", kao i hrpu stvari, misleći "a valjda će to naučiti na logici/teoriji_skupova/...", no nekako više nisam siguran da je to dobra taktika. Anyhow, uvijek postoji hr.sci.matematika, gdje se mogu raspisati koliko želim. ;-)

meni su to uglavnom bile samo labele.......
cinimise da mi je tek sad jasno zasto mi nikad nije sve stimalo s indukcijom...... uvijek mi je nes fallio i nikad mi nije 'legla'
do sada :g:

Meni se čini da je tako sa svim math-nerazumijevanjima. Glavni problem je što se uči obrnutim redom. Skoro svaku stvar prvo naučiš kao glupu mehaničku metodu, a tek onda, često i desetak godina kasnije, naučiš _zašto_, dovvaga. :-/