volledige inductie - wat gaat hier mis?

[Anton_v_U]

Misschien haal ik oude koeien uit de sloot, maar ik vond 'm wel leuk.

Waar gaat de onderstaande redenering mis?

Stelling: alle mensen zijn even oud.

Bewijs (met volledige inductie):

Formuleer de stelling als:

Voor elke k geldt: in elke groep van k mensen zijn alle mensen even oud

Het is triviaal dat de stelling waar is voor k=1

Te bewijzen: als de stelling waar is voor n=k dat hij dan waar is voor k+1.

Inductieveronderstelling: de stelling is waar voor n=k.

In een kamer is een groep van k mensen aanwezig. Op grond van de inductieveronderstelling zijn al deze mensen even oud.Zet nu een van de mensen op de gang. De overgebleven k-1 mensen in de kamer zijn even oud. Laat een willekeurig persoon de kamer betreden. Er is nu weer een groep van k mensen, dus ze zijn even oud. Roep nu de weggestuurde persoon terug in de kamer. Alle (k+1) mensen in de kamer zijn dan even oud.

Aangetoond is dat als je een willekeurig persoon toevoegt aan een groep van k mensen, alle personen in de groep van k+1 mensen even oud zijn.

Hiermee is bewezen dat alle mensen even oud zijn.

[tempelier]

Het gaat al fout bij de overgang van k=1 naar k=2

[Drieske]

Je argumentatie is ten eerste wat warrig neergeschreven. Volgens mij bedoel je zoiets:

++++++++++++++++++

Stel dat de bewering klopt voor elke groep van k mensen, we willen dat ze dan ook klopt voor k+1 mensen. Neem dus een groep van k+1 mensen. Neem een willekeurig persoon en zet deze op de gang. Je hebt nu een groep van k mensen en per inductiehypothese is nu iedereen even oud. Roep nu de persoon op de gang terug en zet iemand anders op de gang. We hebben nu weer een groep van k personen en dus is iedereen even oud. Dus alle k+1 mensen zijn even oud.

++++++++++++++++++

Wat tempelier zegt, is effectief de verklaring, maar het is wat kort uitgelegd. Wat er misgaat, is de veronderstelling dat twee zo'n deelverzamelingen steeds een gemeenschappelijk element bevatten. Maar dat is zeker niet zo. Kijk maar naar n=2.

Het is overigens een klassieker met veel varianten: http://en.wikipedia.org/wiki/All_horses_are_the_same_color

[tempelier]

Iets uitgebreider dan:

Het kijken naar k=2 (n=2) helpt niet dacht ik.

Het zit hem in k=1.

Is k=1 dan is het waar en hebben alle personen de leeftijd p

Wordt nu een persoon verwijderd dan gebeurt er iets dat voor de k>1 niet geldt.

De groep is nu leeg

Wordt er een willekeurig persoon in de groep gezet dan is de bewering weer waar,

maar deze persoon kan de leeftijd q hebben.

Wordt de eerste nu weer terug gezet dan zijn er dus twee personen:

eentje met de leeftijd p de andere met de leeftijd q.

Er is geen rede waarvoor perse zou moeten gelden p=q

Derhalve volgt niet uit:het is waar voor ""k=1"" het ook waar is voor ""k=2"".

Het moet echter waar zijn voor alle k wil het inductie bewijs werken.

Daarom kan de bewering niet perse waar zijn.

[Drieske]

Het bewijs in de openingspost is zeer vreemd. Je begint met een groep van k personen, doet er eentje weg, eentje bij en roept dan een miraculeuze extra persoon. Klopt niet veel van. Als je het wilt bewijzen voor k+1 is er geen reden om te kijken naar k-1.

Kijken naar n=2 helpt wel degelijk. Daar zit de contradictie. Zeker niet in n=1. Uiteraard wel in het bewijs zoals ik het opschreef. Maar goed, we bedoelen we hetzelfde denk ik: het probleem zit in de overgang van 1 naar 2 personen. Zie ook de link in mijn vorige post.