Volledige inductie

quote:

Op vrijdag 11 november 2005 06:20 schreef Doderok het volgende:
Misschien is een voorbeeld duidelijker:

S_i=1+2+3+4+.. +i

Te Bewijzen: S_i=i(i+1)/2

Bewijs:

het geldt voor i=1
1=1.(1+1)/2

als het voor een waarde i=k geldt, geldt het dan ook voor i=k+1 ?
Dat moet dus aangetoond worden, dat veronderstellen we niet zomaar.
Dus, gegeven dat voor een waarde k geldt S_k=k(k+1)/2
Eveneens gegeven n=k+1
Te bewijzen:
S_n=n(n+1)/2

Uit de definitie van S_k
S_k=1+2+..+k
S_n=S_k+1=1+2+ .. +k+(k+1)
volgt: S_n=S_k+n
formule voor S_k invullen
=(k.(k+1)/2)+n
substitutie k=n-1
=((n-1).n/2)+n
=((n-1).n + 2n)/2
=(n.n + n)/2
=n.(n+1)/2
wat moest bewezen worden.

Het geldt voor k=1, dus ook voor k=2 etc..

Het werken met 3 indices i, k, n maakt het niet duidelijker. Eerder onduidelijker.
Zeker als 2 indices volstaan.

quote:

Op vrijdag 11 november 2005 07:16 schreef Yosomite het volgende:

[..]

Het werken met 3 indices i, k, n maakt het niet duidelijker. Eerder onduidelijker.
Zeker als 2 indices volstaan.

Toch duidelijker dan blauwe grassprietjes

quote:

Op vrijdag 11 november 2005 05:31 schreef Aslama het volgende:
De kernvraag was: hoe heb je bewezen dat al de grassprieten in de verzameling blauw zijn?
Stel:

Jje hebt grassprieten die op een rij staan. Je kunt ze niet zien. Je pakt de eerste en kijkt: blauw. Vervolgens pakt je een willekeurige grasspriet van de rij en kijkt: ook blauw. Daarna pakt je alle grassprieten die na de willekeurige grasspriet in de rij staan en kijk ze zijn allemaal blauw.

Heb je bewezen dat alle grassprieten in de rij blauw zijn ? Als je de willekeurige grasspriet pakte die meteen na de eerste graspriet staat wel. Maar dat is niet zeker omdat het een willekeurige is. Het voorbeeld is niet helemaal volledige inductie maar laat zien dat je hebt niet bewezen dat de uitspraak voor n<k geldt.

Nee, dan heb je het niet bewezen. Maar dit is ook niet de methode van volledige inductie. Deze gaat zo:

Je hebt grassprieten die op een rij staan. Je kunt ze niet zien. Je pakt de eerste en kijkt: blauw.
Vervolgens bewijs je, op wat voor manier dan ook, dat als je een willekeurige grasspriet pakt, en hij is toevallig blauw, degene die erna staat ook blauw is.

Dit bovenstaande moet voor ELKE willekeurige grasspriet gelden, niet voor zomaar een willekeurige. Eigenlijk bewijs je dus: ALS een grassprietje blauw is, DAN is zijn opvolger ook blauw.

En daarna laat je VI het werk doen. De eerste is blauw, dus is de tweede ook blauw, dus is de derde ook blauw, enzovoorts.


Duidelijk is het dominovoorbeeld:
Omvallende dominostenen op een rijtje voldoen aan twee voorwaarden:
1. De eerste dominosteen wordt door iemand omgeduwd.
2. Als een willekeurige dominosteen omvalt, valt hij tegen de volgende aan, en die valt dan ook. Dit geldt voor ELKE willekeurige dominosteen.

Nu bewijs je hiermee dat ze allemaal omvallen. De eerste valt om, daarom de tweede, enzovoorts.

quote:

Op vrijdag 11 november 2005 05:31 schreef Aslama het volgende:

[..]

De kernvraag was: hoe heb je bewezen dat al de grassprieten in de verzameling blauw zijn?
Stel:

Jje hebt grassprieten die op een rij staan. Je kunt ze niet zien. Je pakt de eerste en kijkt: blauw. Vervolgens pakt je een willekeurige grasspriet van de rij en kijkt: ook blauw. Daarna pakt je alle grassprieten die na de willekeurige grasspriet in de rij staan en kijk ze zijn allemaal blauw.

Heb je bewezen dat alle grassprieten in de rij blauw zijn ? Als je de willekeurige grasspriet pakte die meteen na de eerste graspriet staat wel. Maar dat is niet zeker omdat het een willekeurige is. Het voorbeeld is niet helemaal volledige inductie maar laat zien dat je hebt niet bewezen dat de uitspraak voor n<k geldt.

Als je ziet dat de eerste graspriet blauw is, en je kunt aantonen dat voor elke willekeurige n geld dat als graspriet_n-1 blauw is, dat dan graspriet_n ook blauw is, dan moet je conclusie zijn dat alle grasprieten blauw zijn. De eerste is namelijk blauw, dus is de tweede ook blauw, dus is de derde ook blauw, dus is de vierde ook blauw, enzovoort...

Edit: oh, was al gezegd

quote:

Op vrijdag 11 november 2005 03:58 schreef Aslama het volgende:

[..]

De vette zin is een aanname dus de gehele bewering is een aanname. Stel je voor dat de vette zin onwaar is (een aanname kan onwaar zijn), wat voor conclusie kan je trekken voor n+1 ?
[..]

Als je deze inductiestap niet kunt maken, dan klopt je veronderstelling niet. Simpel.

Het mooie van inductie is, dat je een afleiding kunt gaan gokken, en dan kunt checken met volledige inductie of je gok ook klopt. Maar als je met de aanname "waar voor n"niet kunt aantonen "waar voor n+1", dan houdt het op; dan was je gokje kennelijk niet goed.
( en natuurlijk moet de aanname gelden voor een kleinste n, bijvoorbeeld 1, 2, 3, etc. ) Je kunt zo gemakkelijk bv de ongelijkheid van Bernoulli bewijzen, da's een aardige oefening

quote:

Op vrijdag 11 november 2005 12:31 schreef Haushofer het volgende:

[..]

Als je deze inductiestap niet kunt maken, dan klopt je veronderstelling niet. Simpel.

Dat is niet het antwoord op mijn vraag. Je hebt de inductie stap gemaakt, maar de vette zin blijkt onwaar te zijn. Dat kan, want de vette zin is een aanname. Wat voor conclusie kan je trekken voor n+1 ?

quote:

Het mooie van inductie is, dat je een afleiding kunt gaan gokken, en dan kunt checken met volledige inductie of je gok ook klopt. Maar als je met de aanname "waar voor n"niet kunt aantonen "waar voor n+1", dan houdt het op; dan was je gokje kennelijk niet goed.
( en natuurlijk moet de aanname gelden voor een kleinste n, bijvoorbeeld 1, 2, 3, etc. ) Je kunt zo gemakkelijk bv de ongelijkheid van Bernoulli bewijzen, da's een aardige oefening

quote:

Op vrijdag 11 november 2005 06:20 schreef Doderok het volgende:
Misschien is een voorbeeld duidelijker:

S_i=1+2+3+4+.. +i

Te Bewijzen: S_i=i(i+1)/2

Bewijs:

het geldt voor i=1
1=1.(1+1)/2

(a) als het voor een waarde i=k geldt, geldt het dan ook voor i=k+1 ?
Dat moet dus aangetoond worden, dat veronderstellen we niet zomaar.
(b) Dus, gegeven dat voor een waarde k geldt S_k=k(k+1)/2

(a) is een voorwaarde die nog getoetst (bewezen) moet worden, in (b) is die voorwaarde plotseling als een bewezen feit behandeld. Dat noem ik een omtovering, geen bewijs. Zie je dat ?

quote:

Eveneens gegeven n=k+1
Te bewijzen:
S_n=n(n+1)/2 ..........(d)

Uit de definitie van S_k
S_k=1+2+..+k
S_n=S_k+1=1+2+ .. +k+(k+1)
volgt: S_n=S_k+n
formule voor S_k invullen
=(k.(k+1)/2)+n ...(c)
substitutie k=n-1
=((n-1).n/2)+n
=((n-1).n + 2n)/2
=(n.n + n)/2
=n.(n+1)/2
wat moest bewezen worden.

Het geldt voor k=1, dus ook voor k=2 etc..

In (c) zie je hoe de nog te toetsen voorwaarde als een feit wordt behandeld om de stelling te bewijzen. Dus volledige inductie is gebasseerd op een aanname, staat ook in de beschrijving van VI, en die aanname wordt in de VI niet bewezen.

[ Bericht 0% gewijzigd door Aslama op 12-11-2005 10:13:49 ]

quote:

Op vrijdag 11 november 2005 09:04 schreef Pie.er het volgende:

[..]

Nee, dan heb je het niet bewezen. Maar dit is ook niet de methode van volledige inductie.

Klopt dat schreef ik ook.

quote:

Deze gaat zo:

Je hebt grassprieten die op een rij staan. Je kunt ze niet zien. Je pakt de eerste en kijkt: blauw.
Vervolgens bewijs je, op wat voor manier dan ook, dat als je een willekeurige grasspriet pakt, en hij is toevallig blauw, degene die erna staat ook blauw is.

Oke je hebt bewezen dat als je een willekeurige grasspriet pakt, en hij is toevallig blauw, degene die erna staat ook blauw is. Dus deze bewering is waar (bewezen):

Als je een willekeurige grasspriet pakt, en hij is toevallig blauw, degene die erna staat ook blauw is.

Het probleem is, er wordt in VI helemaal geen willekeurige grasspriet daadwerkelijk gepakt, het is: als gepakt en blauw, dan pas de volgende blauw.
Dus met VI kan je in feite niets zeggen of die erna staat ook blauw is.

quote:

Dit bovenstaande moet voor ELKE willekeurige grasspriet gelden, niet voor zomaar een willekeurige. Eigenlijk bewijs je dus: ALS een grassprietje blauw is, DAN is zijn opvolger ook blauw.

Dat het aan deze voorwaarde voldoet wordt inderdaad in VI aangenomen. Aangenomen dat een grassprietje blauw is, dan is zijn opvolger ook blauw. Er wordt niet bewezen dat een grassprietje blauw is en dus geen uitspraken over de opvolger.

quote:

En daarna laat je VI het werk doen. De eerste is blauw, dus is de tweede ook blauw, dus is de derde ook blauw, enzovoorts.


Duidelijk is het dominovoorbeeld:
Omvallende dominostenen op een rijtje voldoen aan twee voorwaarden:
1. De eerste dominosteen wordt door iemand omgeduwd.
2. Als een willekeurige dominosteen omvalt, valt hij tegen de volgende aan, en die valt dan ook. Dit geldt voor ELKE willekeurige dominosteen.

Nu bewijs je hiermee dat ze allemaal omvallen. De eerste valt om, daarom de tweede, enzovoorts.

[ Bericht 0% gewijzigd door Aslama op 11-11-2005 17:36:14 ]

Tip: lees een cursus wiskundige logica, er zal een wereld voor je opengaan
Je maakt het allemaal veel moeilijker dan het is.

quote:

Op vrijdag 11 november 2005 17:29 schreef placebeau het volgende:
Tip: lees een cursus wiskundige logica, er zal een wereld voor je opengaan
Je maakt het allemaal veel moeilijker dan het is.

Het heeft meer zin als je kan aantonen waar de logica fout is.

http://www.math.ru.nl/wis(...)wiskundigdenken4.pdf

enneeuh nog een voorbeeld.

Uit onderzoek weten we:
Ik bezit het genoom L.
iedereen die het genoom L bezit geeft dat door aan zijn kinderen.

simpele conclusie:
Heel mijn nageslacht zal het genoom L bezitten.

Ok Aslama, ik zal het stap voor stap proberen.

Stel we hebben een stelling P op de natuurlijke getallen die we willen bewijzen met behulp van VI. Dat gaan we dan doen:

(1) We bewijzen dat P geldt voor de basiselementen van de verzameling. Omdat het de natuurlijke getallen betreft, is het basiselement 1. Nu bewijzen we P(1).
[ a ] P(1) is bewezen.

(2) Nu P(1) bewezen is, nemen we k, een natuurlijk getal ongelijk aan het basiselement 1.
- We nemen aan (we weten dus niet of het klopt!) dat P geldt voor alle natuurlijke getallen < k.
- Met deze aanname, waarvan we niet weten of hij klopt, proberen we te bewijzen dat P geldt voor k. Als P niet geldt voor k met deze aanname kunnen we de stelling niet bewijzen. Maar goed, we bewijzen dus P(k) en kunnen dan concluderen:

[ b ] P(k) is bewezen voor alle natuurlijke k waarvoor geldt dat P geldt voor alle natuurlijke getallen < k. (Let op: we weten dus nog steeds niet of deze aanname klopt, maar we weten nu WEL dat als deze aanname klopt, dat P(k) ook klopt!!)

(3) Nu gaan we de dominostenen laten vallen . We weten dat P(1) klopt: [ a ].
- Klopt P(2)? Ja, zie [ b ]: omdat P(1) klopt geldt P voor alle natuurlijke getallen < 2, wat onze voorwaarde was, dan klopt P(2) ook.
- Klopt P(3)? Ja, zie [ b ]: omdat P(1) klopt en P(2) klopt geldt P voor alle natuurlijk getallen < 3, wat onze voorwaarde was, en zo kunnen we concluderen dat P(3) klopt.
- Klopt P(4)? Ja, zie [ b ]: omdat P(1), P(2) en P(3) klopt geldt P voor alle natuurlijke getallen < 4, wat onze voorwaarde was, en zo kunnen we concluderen dat P(4) klopt.
enz.
enz.

wat klopt er niet?

quote:

Op vrijdag 11 november 2005 17:33 schreef Aslama het volgende:

[..]

Het heeft meer zin als je kan aantonen waar de logica fout is.

Mja, ik wil niet lullig doen, maar ik snap werkelijk waar niet wat je probleem is Dat bewijs wat ik je gegeven heb is zonneklaar naar mijn idee. Heb je daar al es goed naar gekeken?

quote:

Op vrijdag 11 november 2005 17:52 schreef placebeau het volgende:
http://www.math.ru.nl/wis(...)wiskundigdenken4.pdf

Bedankt voor de link. Ik ga lezen als ik tijd heb. Bewezen is als ik tijd heb ga ik lezen. Maar ik heb geen tijd Kan je zeggen dat ik ga lezen?Het is wel bewezen dat als ik tijd heb ik ga lezen .

quote:

enneeuh nog een voorbeeld.

Uit onderzoek weten we:
Ik bezit het genoom L.
iedereen die het genoom L bezit geeft dat door aan zijn kinderen.

simpele conclusie:
Heel mijn nageslacht zal het genoom L bezitten.

Dit is interessant. Als je duidelijk kan maken dat de natuurlijke getallen op die manier werkt dan vind ik VI waterdicht.

Hij heeft problemen met de aanname. Maar die is toch zonneklaar dacht ik

1. bewijs dat de eerste dominosteen omvalt
2. als alle dominostenen < k zijn omgevallen, bewijs dat dan k ook omvalt.
3. omdat dominosteen 1 om is gevallen, zijn alle dominostenen < 2 omgevallen, waardoor 2 ook omvalt.
4. omdat dominosteen 1 en 2 zijn omgevallen, zijn alle dominostenen < 3 omgevallen, waardoor 3 ook omvalt.
5. etc. etc. etc.

quote:

Op vrijdag 11 november 2005 18:12 schreef Haushofer het volgende:

[..]

Mja, ik wil niet lullig doen, maar ik snap werkelijk waar niet wat je probleem is Dat bewijs wat ik je gegeven heb is zonneklaar naar mijn idee. Heb je daar al es goed naar gekeken?

Ik wil ook niet lullig doen. Tuurlijk heb ik goed gelezen en er zelfs inhoudelijk op gereageerd. Heb je zelf wel goed begrepen wat ik bedoel ?
Trouwens begrijp je mijn vraag niet? welke conclusie kan je trekken voor n=k+1 als blijkt dat de aanname niet klopt (deze vraag is geldig)

quote:

Op vrijdag 11 november 2005 18:28 schreef Aslama het volgende:

[..]

Ik wil ook niet lullig doen. Tuurlijk heb ik goed gelezen en er zelfs inhoudelijk op gereageerd. Heb je zelf wel goed begrepen wat ik bedoel ?
Trouwens begrijp je mijn vraag niet? welke conclusie kan je trekken voor n=k+1 als blijkt dat de aanname niet klopt (deze vraag is geldig)

Je kunt nog steeds dezelfde conclusie trekken: ALS de aanname klopt, dan klopt de conclusie ook. Als blijkt dat de aanname niet klopt, klopt deze stelling nog steeds

[ Bericht 100% gewijzigd door Maethor op 11-11-2005 19:00:53 (Klopt niet helemaal - zie mijn volgende post) ]

quote:

Op vrijdag 11 november 2005 18:29 schreef DionysuZ het volgende:

[..]

Je kunt nog steeds dezelfde conclusie trekken: ALS de aanname klopt, dan klopt de conclusie ook. Als blijkt dat de aanname niet klopt, klopt deze stelling nog steeds

a => b
a is waar dan b is waar.
a is niet waar dan geen uitspraak over b. Dat heeft mijn oma toen verteld.

nou en?

quote:

Op vrijdag 11 november 2005 18:37 schreef Aslama het volgende:

[..]

a => b
a is waar dan b is waar.
a is niet waar dan geen uitspraak over b. Dat heeft mijn oma toen verteld.

truth table:

Zoals je ziet is het alleen belangrijk om te weten wat b doet als a waar is. Als b waar is als a waar is, dan is a => b waar.

quote:

Op vrijdag 11 november 2005 18:35 schreef Maethor het volgende:
Iedereen die genoom L heeft geeft dit door aan zijn kinderen.

Dit begrijp ik ja en bewezen.

quote:

Als X geldt voor een willekeurige n, dan ook voor n+1

Dit moet dus bewezen worden.

quote:

Ik bezit het genoom L
X geldt voor n=1

Dus mijn zoon bezit genoom L
X geldt voor n=2

Dus mijn kleinzoon bezit genoom L, etc etc
X geldt voor n=3,4,5,...

Dus mijn hele nageslacht bezit genoom L
X geldt voor n>=1

_____
Wat je moet bewijzen is dus dat
- Als X geldt voor een willekeurige n, dan ook voor n+1, én
- X geldt voor n=a.
en dan volgt
- X geldt voor n>=a.

In het voorbeeld namen we a=1. X is een stelling / eigenschap.

quote:

Op vrijdag 11 november 2005 18:46 schreef Aslama het volgende:
[..]
Dit begrijp ik ja en bewezen.
[..]
Dit moet dus bewezen worden.
[..]

...?

quote:

Op vrijdag 11 november 2005 18:45 schreef DionysuZ het volgende:

[..]

truth table:
[ code verwijderd ]

Zoals je ziet is het alleen belangrijk om te weten wat b doet als a waar is. Als b waar is als a waar is, dan is a => b waar.

a => b is bewezen dus true. je moet nu alleen kijken naar 2, 4 en 5 in de truth table. Je ziet als a false is, kan b zowel fals en true zijn.

quote:

Op vrijdag 11 november 2005 18:35 schreef Maethor het volgende:
Iedereen die genoom L heeft geeft dit door aan zijn kinderen.

Iedereen weet genoom op die manier werkt.

quote:

Als X geldt voor een willekeurige n, dan ook voor n+1

Dit is de stelling die eerste dmv VI bewezen moet worden. Mijn punt is dat VI gebruik maakt van een aanname.

quote:

Ik bezit het genoom L
X geldt voor n=1

Dus mijn zoon bezit genoom L
X geldt voor n=2

Dus mijn kleinzoon bezit genoom L, etc etc
X geldt voor n=3,4,5,...

Dus mijn hele nageslacht bezit genoom L
X geldt voor n>=1

_____
Wat je moet bewijzen is dus dat
- Als X geldt voor een willekeurige n, dan ook voor n+1, én
- X geldt voor n=a.
en dan volgt
- X geldt voor n>=a.

In het voorbeeld namen we a=1. X is een stelling / eigenschap.