Induzione paradossale

E' abbastanza classico, ma non lo ho mai visto postato e quindi lo faccio io per chi non lo conoscesse.

Trovare l'errore in questa dimostrazione per inbduzione.

Dimostriamo che tutte le ragazze sono bionde.
Procediamo per induzione du un insieme di n ragazze.
Se n=0 l'asserzione e' vera a vuoto;
se n=1 c'e' una sola ragazza e quindi non ci sono problemi (se vi state chiedendo perche' questaragazza deve per forza essere bionda, vi faccio notare che la cosa non ha importanza: se fosse bruna allora vuol dire che stiamo dimostrando che tutte le ragazze sono brune)
Consideriamo un insieme di n+1 ragazze; ne togliamo una e abbiamo un insieme di n ragazze che per ipotesi induttiva sono tutte bionde. Ora rimettiamo la ragazza che avevamo tolto e al posto di quella ne togliamo un altra: anche in questo caso abbiamo n ragazze bione. Ma allora l'insieme considerato contiene n+1 ragazze bione.
Per induzione si conclude allora che tutte le ragazze sono bione.

E le brune?!??!

Platone

Conoscevo una versione con le palle da biliardo...

Ma allora l'insieme considerato contiene n+1 ragazze bione.
Per induzione si conclude allora che tutte le ragazze sono bione.

E le brune?!??!

Platone

hai ragione platone ..per induzione si può concludere che tutte le ragazze sono BONE!!!!..anke le more

Ciao Platone... allora ce lo dici dove sta l'errore???


Fabio

Aiutino: allo stesso (sostituendo "ragazze bionde" con "dispari primi") si puo' dimostrare che tutti i numeri dispari sono primi...

Platone

nessuno mi dice che quando prendi la n+1-esima ragazza essa e' bionda!!!

Te lo dice (a torto) il fatto che se prendi due sottinsiemi (distinti) di n elementi ciascuno, ed in ogniuno le n ragazze sono tutte bionde allora necessariamente l'insieme cin n+1 ragazze che stavamo considerando ha solo ragazze bionde e quindi anche la n+1 esima e' bionda.
Il baco del ragionamento sta nel fatto che il principio di induzione e' assiomatizzato su un insieme dotato di funzione successore, cioe' su un insieme nel quale dato l'n esimo elemento si possa determinare univocamente l'n+1 esimo.
Supposto vero che la n essima ragazza sia bionda, chi e' la n+1 esima su cui applicare il principio di induzione?

Platone

E' abbastanza classico, ma non lo ho mai visto postato e quindi lo faccio io per chi non lo conoscesse.

Trovare l'errore in questa dimostrazione per inbduzione.

Dimostriamo che tutte le ragazze sono bionde.
Procediamo per induzione du un insieme di n ragazze.
Se n=0 l'asserzione e' vera a vuoto;
se n=1 c'e' una sola ragazza e quindi non ci sono problemi (se vi state chiedendo perche' questaragazza deve per forza essere bionda, vi faccio notare che la cosa non ha importanza: se fosse bruna allora vuol dire che stiamo dimostrando che tutte le ragazze sono brune)
Consideriamo un insieme di n+1 ragazze; ne togliamo una e abbiamo un insieme di n ragazze che per ipotesi induttiva sono tutte bionde. Ora rimettiamo la ragazza che avevamo tolto e al posto di quella ne togliamo un altra: anche in questo caso abbiamo n ragazze bione. Ma allora l'insieme considerato contiene n+1 ragazze bione.
Per induzione si conclude allora che tutte le ragazze sono bione.

E le brune?!??!

Platone

Non mi convince per nulla l'inizio («...se fosse bruna allora vuol dire che stiamo dimostrando che tutte le ragazze sono brune...»), anche perché poi lo usi nella tua ipotesi induttiva...
io lo conoscevo in una forma che mi pare decisamente più convincente:

«Dimostriamo che
"se in un inseme di ragazze almeno una è bionda, allora tutte le ragazze sono bionde".
Procediamo per induzione du un insieme di n ragazze.
Se n=0 l'asserzione e' oviamente vera.
Non ce ne è bisogno, ma per maggior chiarezza si dimosta anche per n=1 (altrettanto ovvio).
Consideriamo un insieme di n+1 ragazze dove ce ne è almeno 1 bionda; se tutte sono bionde abbiamo finito, altrimenti ne togliamo una non bionda e abbiamo un insieme di n ragazze con almeno 1 bionda, quindi, per ipotesi induttiva, sono tutte bionde.
Ora rimettiamo la ragazza che avevamo tolto e al posto di quella ne togliamo un'altra (necessariamente bionda): anche in questo caso abbiamo che le n ragazze sono tutte bionde. Ma allora le ragazze dell'insieme considerato sono tutte bionde.
Per induzione si conclude allora che
se in un inseme di ragazze almeno una è bionda, allora tutte le ragazze sono bionde,
e da questo, considerando l'insieme di tutte le ragazze del mondo, che tutte le ragazze sono bionde.»


Come è possibile?


In un clima di Olimpiadi della Matematica mi viene da proporre:

A) Effettivamente tutte le ragazze sono bionde.
B) Effettivamente tutte le ragazze sono bionde quando sono in un inseme con almeno 1 bionda.
C) Il teorema è vero perché non ci sono ragazze bionde (sono tutte tinte).
D) La dimostrazione, anche se sembra eccezionalmente convincente, ha un errore.
E) L'assurdo si ha nel considerare che abbia senso parlare di "bionde", dal momento che è un concetto non è definibile (si possono avere più capelli, sia biondi, sia non biondi; c'è tutta una gradazione di toni di "castano" che vanno dal quasi bianchissimo al quasi nerissimo, il colore dei capelli varia con le stagioni, con l'età, con le ore del giorno, con lo stato di salute, ecc.).


Chi sceglie la "D" è invitato a dire anche dove è l'errore.

L'errore è che l'assunto è dimostrato per n=1, ma non per n=0 (il colore di capelli di "nessuna ragazza" non è biondo è "nessun colore", e comunque in tale insieme non c'è "una" bionda), né per n=2.
Per poter partire con una dimostrazione per induzione manca quindi il "carburante" di startup (ovvero nel caso specifico che essa sia dimostrata per due casi consecutivi all'inizio della serie)

In particolare, il ragionamento proposto

Consideriamo un insieme di n+1 ragazze dove ce ne è almeno 1 bionda; se tutte sono bionde abbiamo finito, altrimenti ne togliamo una non bionda e abbiamo un insieme di n ragazze con almeno 1 bionda, quindi, per ipotesi induttiva, sono tutte bionde.
Ora rimettiamo la ragazza che avevamo tolto e al posto di quella ne togliamo un'altra (necessariamente bionda): anche in questo caso abbiamo che le n ragazze sono tutte bionde. Ma allora le ragazze dell'insieme considerato sono tutte bionde.

non funziona per n+1=2, poiché togliendo la seconda ragazza (necessariamente bionda) non ho motivi di credere che tra le n (=1) ragazze rimaste ci sia necessariamente almeno una bionda.

Volete generalizzare lo zero considerando bionda "a vuoto" l'insieme di zero ragazze? Il risultato non cambia, salta l'ipotesi che togliendo la seconda ragazza (necessariamente bionda) non ho certezza che tra le n (=1) ragazze rimaste ci sia necessariamente almeno una bionda nel gruppo rimasto, visto che la bionda rimasta potrebbe essere la bionda "a vuoto" numero zero, che non corrisponde alle condizioni per applicare il ragionamento induttivo (che parlava di almeno una bionda).