Induktiotodistus?

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Tässäpä pientä aivovoimistelua, jonka kuulin kaveriltani:

Jos n naisen joukossa on ainakin yksi vaalea, niin joukon kaikki naiset ovat vaaleita. Väite pätee, kun n = 1. Tehdään induktio-oletus, jonka mukaan väite on tosi arvolla n = k. Olkoon {a1, . . . , ak+1} k+1 naisen joukko, joka sisältää ainakin yhden vaalean. Rajoituksetta voidaan olettaa, että a1 on vaalea. Joukko {a1, . . . , ak} koostuu induktio-oletuksen mukaan vaaleista. Joukko {a2, . . . , ak+1} sisältää tällöin ainakin yhden vaalean, joten sekin koostuu induktio-oletuksen mukaan vaaleista. Näin joukon {a1, . . . , ak+1} kaikki naiset ovat vaaleita, joten väite seuraa induktioperiaatteesta.

Väite ei ole tosi, mutta missä vika?

Kommentit (14)

Vierailija
Olli V
Indukstiotodistelulla on rajansa. Ei sovellu keksimällä keksittyjen ongelmien todeistamiseen.

Ei vika ole siinä, että ongelma olisi "keksitty" (niinhän kaikki ongelmat ovat). Mikäli induktioperiaate on pätevä, täytyy sen soveltua myös tähän tilanteeseen. Siis joko induktioperiaate on epäpätevä tai todistuksessa on virhe.

Itse asiassa todistuksessa on aukko, mutta sitä ei äkkiseltään huomaa.

Cargo
Seuraa 
Viestejä979
Liittynyt27.8.2007

Niinpä niin...

Induktiotahan voidaan käyttää kun on luonnollisia lukuja koskeva ehto (vaikka funktio). Joukko johon lisätään alkioita sieltä täältä ei ole sellainen.

" sähkö (se sähkö, jota tuotetaan mm. voimalaitoksissa) ei ole energiaa "
- Vastaaja_s24fi

“Jos et ole kaksikymppisenä vihreä, sinulla ei ole sydäntä. Mutta jos et ole nelikymppisenä perussuomalainen, sinulla ei ole aivoja.”
- Cargo

Vierailija
kurnimaha
Väite ei ole tosi, mutta missä vika?



Vika on tässä

Joukko {a1, . . . , ak} koostuu induktio-oletuksen mukaan vaaleista. Joukko {a2, . . . , ak+1} sisältää tällöin ainakin yhden vaalean.



mutta jätetään tarkka perustelu jännityksen vuoksi vielä vähän ilmaan.

Cargo
Induktiotahan voidaan käyttää kun on luonnollisia lukuja koskeva ehto (vaikka funktio). Joukko johon lisätään alkioita sieltä täältä ei ole sellainen.

Kyseessähän on juuri luonnollisia lukuja koskeva ehto, koska induktiota tehdään tiettyjen joukkojen alkioiden lukumäärän suhteen (joukon alkioiden lukumäärä = luonnollinen luku). Jos naiset hämäävät, niin väite voidaan "matematisoida" vaikka muotoon: jos n:n kokonaisluvun joukossa on yksi pariton luku, niin jokainen joukon kokonaisluku on pariton.

Tässäpä vastaavanlainen virheellinen induktiotodistus. Osoitetaan induktiolla, että jokainen positiivinen kokonaisluku on yhtäsuuri.

Olkoon x ja y kaksi positiivista kokonaislukua ja olkoon m=max(x,y). Tehdään induktio luvun m suhteen.

Jos m=1, niin väite on selvästi tosi. Tarkastellaan väitettä eräällä m > 1 ja oletetaan, että väite on tosi arvolla m-1. Tällöin max(x-1,y-1) = m-1 eli induktio-oletuksen nojalla x-1 = y-1 ja täten x = y. Siis kaikki positiiviset kokonaisluvut ovat yhtäsuuria.

Vierailija
starless
Vika on tässä
Vikaa on aika monessa paikassa, kun OP ei osaa kirjoittaa induktiotodistusta.
starless
Olkoon x ja y kaksi positiivista kokonaislukua ja olkoon m=max(x,y). Tehdään induktio luvun m suhteen.

Jos m=1, niin väite on selvästi tosi. Tarkastellaan väitettä eräällä m > 1 ja oletetaan, että väite on tosi arvolla m-1. Tällöin max(x-1,y-1) = m-1 eli induktio-oletuksen nojalla x-1 = y-1 ja täten x = y. Siis kaikki positiiviset kokonaisluvut ovat yhtäsuuria.

Öö mitä? Toi sun väite on siis, että m = max (x,y) eli mitä yrität selittää?

Vierailija
kurnimaha
Tässäpä pientä aivovoimistelua, jonka kuulin kaveriltani:

Jos n naisen joukossa on ainakin yksi vaalea, niin joukon kaikki naiset ovat vaaleita. Väite pätee, kun n = 1. Tehdään induktio-oletus, jonka mukaan väite on tosi arvolla n = k. Olkoon {a1, . . . , ak+1} k+1 naisen joukko, joka sisältää ainakin yhden vaalean. Rajoituksetta voidaan olettaa, että a1 on vaalea. Joukko {a1, . . . , ak} koostuu induktio-oletuksen mukaan vaaleista. Joukko {a2, . . . , ak+1} sisältää tällöin ainakin yhden vaalean, joten sekin koostuu induktio-oletuksen mukaan vaaleista. Näin joukon {a1, . . . , ak+1} kaikki naiset ovat vaaleita, joten väite seuraa induktioperiaatteesta.

Väite ei ole tosi, mutta missä vika?


Tummennettu on väärin.

Väite: Jos joukossa on 1 vaalea, niin koko joukko on vaaleita.
Tod:
Väite pätee, kun n = 1.
Ind.ol: Väite on tosi, kun n=k. Siis joukko {a1, . . . , ak} koostuu vaaleista. Korostan vielä, että varsinainen induktio-oletus on tummennettu.

Pitäisi pystyä induktio-oletuksesta (ja muun matematiikan/logiikan avulla) johtamaan (osoittamaan), että {a1, . . . , ak+1} koostuu vaaleista. Se ei vaan onnistu, joten väitettä ei voi todistaa. Paremminkin sen voi todistaa vääräksi:

Uusi jäsen ak+1 voi olla vaalea taikka sitten ei. Jos ak+1 on vaalea, niin väite pätee. Jos ak+1 ei ole vaalea, niin väite ei pidä. Tässä on ristiriita ja on todistettu, että väite ei pidä paikkaansa.

Vierailija

Minusta varsinainen ongelma on se, että k:n naisen muodostama joukko voi olla myös sellainen, että siinä on vain yksi nainen. Toisin sanoen jos k=1, niin joukkojen {a1,...,ak} ja {a2,...,ak+1} leikkaus on tyhjä. Väite kaatuu tähän.

Vierailija
kurnimaha
Minusta varsinainen ongelma on se, että k:n naisen muodostama joukko voi olla myös sellainen, että siinä on vain yksi nainen. Toisin sanoen jos k=1, niin joukkojen {a1,...,ak} ja {a2,...,ak+1} leikkaus on tyhjä. Väite kaatuu tähän.

k on yleinen positiivinen kokonaisluku jota ei saa ajatella olevan joku tietty luku.

Vierailija
kurnimaha
Minusta varsinainen ongelma on se, että k:n naisen muodostama joukko voi olla myös sellainen, että siinä on vain yksi nainen. Toisin sanoen jos k=1, niin joukkojen {a1,...,ak} ja {a2,...,ak+1} leikkaus on tyhjä. Väite kaatuu tähän.



Totta. Todistuksessahan käytetään induktio-oletusta kahdesti, ensin joukkoon {a_1,...,a_k} ja sitten joukkoon {a_2,...,a_(k+1)}. Tosin induktio-oletuksessa vaaditaan, että joukossa on ainakin yksi vaalea nainen. Jos k > 1, niin tällöinhän ensimmäinen induktio-oletus antaa, että a_k on vaalea ja tällöin joukossa {a_2,...,a_(k+1)} on ainakin yksi vaalea ja induktio-oletusta voidaan käyttää. Mutta jos k=1, niin tällöin meillä ei ole mitään takuita siitä, että joukon {a_2} ainoa nainen olisi vaalea, joten emme voi käyttää induktio-oletusta siihen (tosin jos a_2 olisi vaalea nainen, niin silloin emme edes tarvitsisi induktio-oletusta).

suolaasuolaa
Öö mitä? Toi sun väite on siis, että m = max (x,y) eli mitä yrität selittää?

Ei, vaan väite yritetään todistaa induktiolla luvun m = max(x,y) suhteen.

Vierailija

Jos tarkastellaan joukkoa {a1,...,ak+1}, niin induktio-oletus takaa vain sen, että joukossa alkiot a1,...,ak ovat vaaleita. ak+1 pitää todistaa vaaleaksi (mikä ei tietenkään onnistu).

Vierailija
Kale
Jos tarkastellaan joukkoa {a1,...,ak+1}, niin induktio-oletus takaa vain sen, että joukossa alkiot a1,...,ak ovat vaaleita. ak+1 pitää todistaa vaaleaksi (mikä ei tietenkään onnistu).

Kurnimaha ei kyllä missään vaiheessa kirjoittanut induktio-oletusta eksplisiittisesti auki, mutta se mitä hän todistuksessa käyttää on seuraava:
"jos k:n naisen joukossa on ainakin yksi vaalea nainen, niin kaikki naiset ovat vaaleita". Täten jos tarkastellaan k+1:n naisen joukkoa, jossa on yksi vaalea (rajoituksetta valitaan, että se on a_1), niin tällöin induktio-oletusta voidaan soveltaa joukkoon {a_1, ... , ak} (koska se on k:n naisen joukko, jossa on ainakin yksi vaalea). Lisäksi induktio-oletusta voidaan soveltaa joukkoon {a_2, ... , a_(k+1)}, mikäli joukossa on ainakin yksi vaalea nainen, koska se on myös k:n naisen joukko. Mikäli k > 1, niin a_k on ensimmäisen induktio-oletuksen nojalla vaalea nainen ja induktio-oletusta voi käyttää myös jälkimmäiseen joukkoon. Mutta jos k=1, niin joukot ovat alkiovieraita ja induktio-askelta ei saa vietyä läpi.

Vierailija
Kale
k on yleinen positiivinen kokonaisluku jota ei saa ajatella olevan joku tietty luku.

Näinhän se on, jos väitteen haluaa osoittaa oikeaksi. Nyt tarkoituksena ei kuitenkaan ollut todistaa sitä oikeaksi vaan löytää vastaesimerkki, joka ei toteuta väitettä.

Vierailija
Kale
k on yleinen positiivinen kokonaisluku jota ei saa ajatella olevan joku tietty luku.

No ei nyt ihan niinkään. Induktio-askeleen todistus on pystyttävä viemään läpi jokaisella kokonaisluvulla, joka on perusaskeleen lukua suurempi, mutta teknisistä syistä tarkastelu voidaan joutua jakamaan tilanteisiin, joissa luku k saa tiettyjä arvoja. Esimerkiksi joissakin äärellisiä graafeja koskevissa induktiotodistustuksissa voidaan joutua todistus jakamaan tapauksiin, joissa k on ensin parillinen ja sitten pariton. Joskus jopa k:lle pitää valita jopa konkreettisia lukuja arvoiksi, että kaikki vaihtoehdot saadaan käytyä läpi. Teknisistä syistä tällöin todistus yleensä tehdään hyvinjärjestys-periaatteen avulla, mutta koska hyvinjärjestys-periaate on ekvivalentti induktioperiaatteen kanssa, niin todistus voitaisiin muotoilla myös perinteiseksi induktiotodistukseksi. Tuosta tulikin mieleen, että jos tämä naisten vaaleutta käsittelevä todistus siirrettäisiin hyvinjärjestys-periaatteen nojalla tehtäväksi, niin virhe on helpompi löytää.

Tarkoituksena on siis osoittaa, että jos n naista sisältävässä joukossa on 1 vaalea nainen, niin kaikki n naista ovat vaaleita. Oletetaan väite vääräksi ja olkoon k pienin lukumäärä, jolla väite rikkoituu. Olkoon a_1, a_2, ... , a_k nyt k naista, joista ainakin yksi on vaalea ja yksi ei ole vaalea (eli tämä kokoelma on eräs pienimmistä vastaesimerkeistä). Olkoon ei-vaalea nainen a_k ja vaalea nainen a_1. Tarkastellaan nyt joukkoa {a_1, a_k}. Mikäli k > 3, niin luvun k valinnan nojalla joukko {a_1, a_k} sisältää vain vaaleita naisia, siis ristiriita naisen a_k ei-vaaleuden kanssa. Mikäli k=2, niin joukko {a_1, a_k} on alkuperäinen joukkomme ja tästä nyt ei saa ristiriitaa mitenkään. Tästä voimme sitten tulla täysin selvään johtopäätökseen, että mikäli alkuperäiselle väitteellemme on olemassa pienin vasta-esimerkki, niin se saadan valitsemalla joukkoon kaksi naista (yhden vaalean ja yhden ei-vaalean, doh...).

Vierailija
starless
Kale
k on yleinen positiivinen kokonaisluku jota ei saa ajatella olevan joku tietty luku.



No ei nyt ihan niinkään. Induktio-askeleen todistus on pystyttävä viemään läpi jokaisella kokonaisluvulla, joka on perusaskeleen lukua suurempi, mutta teknisistä syistä tarkastelu voidaan joutua jakamaan tilanteisiin, joissa luku k saa tiettyjä arvoja. Esimerkiksi joissakin äärellisiä graafeja koskevissa induktiotodistustuksissa voidaan joutua todistus jakamaan tapauksiin, joissa k on ensin parillinen ja sitten pariton. Joskus jopa k:lle pitää valita jopa konkreettisia lukuja arvoiksi, että kaikki vaihtoehdot saadaan käytyä läpi.

No joo jos ihan pilkulleen tarkkoja ollaan (niin kuin matematiikassa kyllä pitäisikin olla), mutta tiedät mitä tarkoitin.

Uusimmat

Suosituimmat