Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Induzione matematica, esempi di abbagli cercasi
220 views
Skip to first unread message
tip&tap
Mar 29, 2015, 5:08:36 PM3/29/15
to
Ogni tanto capita di leggere qualche esempio di dimostrazione
"sbagliata", cioè valida ad una prima occhiata da un punto di vista
meramente formale, ma inficiata da un qualche elemento da scovare
osservando attentamente il significato dei vari passaggi.
Per quanto riguarda l'induzione matematica non ho trovato granché a
riguardo, eppure è uno strumento estremamente potente e credo, proprio
in virtù di questo, che di abbagli possano prendersene eccome.
Mi potreste indirizzare su qualche controesempio, che illustri cioè come
a prima vista il metodo sembri applicato correttamente, ma contenga
invece degli errori di fondo? Mi piacerebbe farmi un'idea di quelle che
sono le cattive pratiche nell'applicazione del metodo induttivo.
Grazie
"sbagliata", cioè valida ad una prima occhiata da un punto di vista
meramente formale, ma inficiata da un qualche elemento da scovare
osservando attentamente il significato dei vari passaggi.
Per quanto riguarda l'induzione matematica non ho trovato granché a
riguardo, eppure è uno strumento estremamente potente e credo, proprio
in virtù di questo, che di abbagli possano prendersene eccome.
Mi potreste indirizzare su qualche controesempio, che illustri cioè come
a prima vista il metodo sembri applicato correttamente, ma contenga
invece degli errori di fondo? Mi piacerebbe farmi un'idea di quelle che
sono le cattive pratiche nell'applicazione del metodo induttivo.
Grazie
JTS
Mar 29, 2015, 5:54:32 PM3/29/15
to
in cui ce ne sia almeno uno bianco tutti e' costituito intieramente da
cavalli bianchi. Si "dimostra" per induzione nel seguente modo.
Primo passo: osserviamo che la proprieta' vale per gruppi di un cavallo.
Quindi per n = 1 la proprieta' vale.
Ora dimostriamo che se la proprieta' e' vera per gruppi composti da n
cavalli, e' vera anche per gruppi composti da n+1 cavalli.
Sia un gruppo di n+1 cavalli in cui ce n'e' uno bianco. Identifichiamo
questo cavallo bianco. Ora togliamo dal gruppo un altro cavallo, diverso
da quello bianco che abbiamo identificato; otteniamo un gruppo di n
cavalli, in cui ce n'e' uno bianco (perche' abbiamo avuto cura di
lasciarlo). Per l'ipotesi induttiva che tutti i cavalli del gruppo che
abbiamo ottenuto sono bianchi.
Ora possiamo prendere uno qualunque di questi cavalli bianchi e
eliminarlo dal gruppo di n, facendo rientrare il cavallo che avevamo
escluso (del quale non conosciamo ancora il colore). Abbiamo di nuovo un
gruppo di n cavalli di cui ce n'e' almeno uno bianco (sono tutti bianchi
meno quello che abbiamo appena aggiunto). Applicando di nuovo l'ipotesi
induttiva, concludiamo che anche l'ultimo cavallo e' bianco.
Abbiamo quindi dimostrato che se il teorema e' vero per n, e' vero anche
per n+1. Combinando con il fatto che e' vero per n = 1, otteniamo che il
teorema e' vero: se in un gruppo di cavalli ce n'e' uno bianco, sono
tutti bianchi.
Per il momento non scrivo dov'e' il problema. Credo che sia istruttivo
capire dove e', cioe' si capisca una piccola cosa in piu' sul principio
di induzione.
---
Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft.
http://www.avast.com
Giorgio Bibbiani
Mar 30, 2015, 1:00:09 AM3/30/15
to
JTS ha scritto:
nel caso di n = 1, dato un gruppo di n+1 cavalli formato da un
cavallo bianco e uno nero, {B, N}.
> Identifichiamo
> questo cavallo bianco. Ora togliamo dal gruppo un altro cavallo,
> diverso da quello bianco che abbiamo identificato; otteniamo un
> gruppo di n cavalli, in cui ce n'e' uno bianco (perche' abbiamo avuto
> cura di lasciarlo).
Adesso il gruppo e' {B}.
> Per l'ipotesi induttiva che tutti i cavalli del
> gruppo che abbiamo ottenuto sono bianchi.
>
> Ora possiamo prendere uno qualunque di questi cavalli bianchi e
> eliminarlo dal gruppo di n, facendo rientrare il cavallo che avevamo
> escluso (del quale non conosciamo ancora il colore)
Adesso il gruppo e' {N}.
> Abbiamo di nuovo
> un gruppo di n cavalli di cui ce n'e' almeno uno bianco (sono tutti
> bianchi meno quello che abbiamo appena aggiunto).
L'affermazione sopra e' sbagliata, perche' non e' detto che nel
gruppo ci siano cavalli bianchi, e cio' conclude la "dimostrazione".
> Applicando di nuovo
> l'ipotesi induttiva, concludiamo che anche l'ultimo cavallo e' bianco.
>
> Abbiamo quindi dimostrato che se il teorema e' vero per n, e' vero
> anche per n+1. Combinando con il fatto che e' vero per n = 1,
> otteniamo che il teorema e' vero: se in un gruppo di cavalli ce n'e'
> uno bianco, sono tutti bianchi.
Bella "dimostrazione", non la conoscevo :-).
Ciao
--
Giorgio Bibbiani
> Una che era piaciuta a me e' la dimostrazione che un gruppo di cavalli
> in cui ce ne sia almeno uno bianco tutti e' costituito intieramente da
> cavalli bianchi. Si "dimostra" per induzione nel seguente modo.
>
> Primo passo: osserviamo che la proprieta' vale per gruppi di un
> cavallo. Quindi per n = 1 la proprieta' vale.
>
> Ora dimostriamo che se la proprieta' e' vera per gruppi composti da n
> cavalli, e' vera anche per gruppi composti da n+1 cavalli.
> Sia un gruppo di n+1 cavalli in cui ce n'e' uno bianco.
Per capire dov'e' l'inghippo provo ad applicare la "dimostrazione"
> in cui ce ne sia almeno uno bianco tutti e' costituito intieramente da
> cavalli bianchi. Si "dimostra" per induzione nel seguente modo.
>
> Primo passo: osserviamo che la proprieta' vale per gruppi di un
> cavallo. Quindi per n = 1 la proprieta' vale.
>
> Ora dimostriamo che se la proprieta' e' vera per gruppi composti da n
> cavalli, e' vera anche per gruppi composti da n+1 cavalli.
> Sia un gruppo di n+1 cavalli in cui ce n'e' uno bianco.
nel caso di n = 1, dato un gruppo di n+1 cavalli formato da un
cavallo bianco e uno nero, {B, N}.
> Identifichiamo
> questo cavallo bianco. Ora togliamo dal gruppo un altro cavallo,
> diverso da quello bianco che abbiamo identificato; otteniamo un
> gruppo di n cavalli, in cui ce n'e' uno bianco (perche' abbiamo avuto
> cura di lasciarlo).
> Per l'ipotesi induttiva che tutti i cavalli del
> gruppo che abbiamo ottenuto sono bianchi.
>
> Ora possiamo prendere uno qualunque di questi cavalli bianchi e
> eliminarlo dal gruppo di n, facendo rientrare il cavallo che avevamo
> escluso (del quale non conosciamo ancora il colore)
> Abbiamo di nuovo
> un gruppo di n cavalli di cui ce n'e' almeno uno bianco (sono tutti
> bianchi meno quello che abbiamo appena aggiunto).
gruppo ci siano cavalli bianchi, e cio' conclude la "dimostrazione".
> Applicando di nuovo
> l'ipotesi induttiva, concludiamo che anche l'ultimo cavallo e' bianco.
>
> Abbiamo quindi dimostrato che se il teorema e' vero per n, e' vero
> anche per n+1. Combinando con il fatto che e' vero per n = 1,
> otteniamo che il teorema e' vero: se in un gruppo di cavalli ce n'e'
> uno bianco, sono tutti bianchi.
Ciao
--
Giorgio Bibbiani
radica...@gmail.com
Mar 30, 2015, 4:27:46 AM3/30/15
to
Il giorno domenica 29 marzo 2015 23:54:32 UTC+2, JTS ha scritto:
> Am 29.03.2015 um 23:08 schrieb tip&tap:
> > Ogni tanto capita di leggere qualche esempio di dimostrazione
> > "sbagliata", cioè valida ad una prima occhiata da un punto di vista
> > meramente formale, ma inficiata da un qualche elemento da scovare
> > osservando attentamente il significato dei vari passaggi.
> >
> > Per quanto riguarda l'induzione matematica non ho trovato granché a
> > riguardo, eppure è uno strumento estremamente potente e credo, proprio
> > in virtù di questo, che di abbagli possano prendersene eccome.
> >
> > Mi potreste indirizzare su qualche controesempio, che illustri cioè come
> > a prima vista il metodo sembri applicato correttamente, ma contenga
> > invece degli errori di fondo? Mi piacerebbe farmi un'idea di quelle che
> > sono le cattive pratiche nell'applicazione del metodo induttivo.
> >
> > Grazie
>
>
> Una che era piaciuta a me e' la dimostrazione che un gruppo di cavalli
> in cui ce ne sia almeno uno bianco tutti e' costituito intieramente da
> cavalli bianchi. Si "dimostra" per induzione nel seguente modo.
>
> Primo passo: osserviamo che la proprieta' vale per gruppi di un cavallo.
> Quindi per n = 1 la proprieta' vale.
Dovrebbe valere per ogni gruppo di un cavallo pero' : ossia qui hai
> Am 29.03.2015 um 23:08 schrieb tip&tap:
> > Ogni tanto capita di leggere qualche esempio di dimostrazione
> > "sbagliata", cioè valida ad una prima occhiata da un punto di vista
> > meramente formale, ma inficiata da un qualche elemento da scovare
> > osservando attentamente il significato dei vari passaggi.
> >
> > Per quanto riguarda l'induzione matematica non ho trovato granché a
> > riguardo, eppure è uno strumento estremamente potente e credo, proprio
> > in virtù di questo, che di abbagli possano prendersene eccome.
> >
> > Mi potreste indirizzare su qualche controesempio, che illustri cioè come
> > a prima vista il metodo sembri applicato correttamente, ma contenga
> > invece degli errori di fondo? Mi piacerebbe farmi un'idea di quelle che
> > sono le cattive pratiche nell'applicazione del metodo induttivo.
> >
> > Grazie
>
>
> Una che era piaciuta a me e' la dimostrazione che un gruppo di cavalli
> in cui ce ne sia almeno uno bianco tutti e' costituito intieramente da
> cavalli bianchi. Si "dimostra" per induzione nel seguente modo.
>
> Primo passo: osserviamo che la proprieta' vale per gruppi di un cavallo.
> Quindi per n = 1 la proprieta' vale.
gia' assunto quello che vuoi dimostrare.
radica...@gmail.com
Mar 30, 2015, 4:30:32 AM3/30/15
to
Paolo Emilio
Mar 30, 2015, 8:19:01 AM3/30/15
to
allora a=b".
Corollario: "Tutti i naturali sono nulli, in particolare 1=0".
Dimostrazione per induzione, partendo da n=0.
Sia: P(n) = "a,b naturali, max(a,b)=n".
1) P(0) e' vera: se a,b sono naturali & max(a,b)=0, allora a=b=0.
2) Se P(n) e' vera, allora:
P(n+1): max(a,b)=n+1 ==> max(a-1,b-1)=n & a-1=b-1 ==> a=b, c.v.d.
--
Ciao Paolo
radica...@gmail.com
Mar 30, 2015, 8:36:41 AM3/30/15
to
contorte. La ragione e' ovvia.
tip&tap
Mar 30, 2015, 2:11:11 PM3/30/15
to
> L'affermazione sopra e' sbagliata, perche' non e' detto che nel
> gruppo ci siano cavalli bianchi, e cio' conclude la "dimostrazione".
Se non ho capito male l'inghippo è che l'insieme sul quale si cerca di
> gruppo ci siano cavalli bianchi, e cio' conclude la "dimostrazione".
applicare la regola nelle varie fasi non è lo stesso, ma viene
modificato a convenienza. Quindi questo approccio di togliere un
elemento e poi rimetterlo e generalmente sbagliato?
Mi ricorda tanto il gioco delle tre carte :-)
Giorgio Bibbiani
Mar 30, 2015, 2:19:40 PM3/30/15
to
tip&tap ha scritto:
tolti e rimessi "senza barare".
In questa "dimostrazione" si e' barato passando dall'affermazione
corretta:
"sono tutti bianchi meno quello che abbiamo appena aggiunto",
alla deduzione sbagliata:
"ce n'e' almeno uno bianco",
infatti i cavalli tutti bianchi avrebbero potuto essere in numero di 0.
> Mi ricorda tanto il gioco delle tre carte :-)
Infatti, e' un gioco da bari...;-)
Ciao
--
Giorgio Bibbiani
> Se non ho capito male l'inghippo è che l'insieme sul quale si cerca di
> applicare la regola nelle varie fasi non è lo stesso, ma viene
> modificato a convenienza. Quindi questo approccio di togliere un
> elemento e poi rimetterlo e generalmente sbagliato?
Non direi che sia generalmente sbagliato, se gli elementi vengono
> applicare la regola nelle varie fasi non è lo stesso, ma viene
> modificato a convenienza. Quindi questo approccio di togliere un
> elemento e poi rimetterlo e generalmente sbagliato?
tolti e rimessi "senza barare".
In questa "dimostrazione" si e' barato passando dall'affermazione
corretta:
"sono tutti bianchi meno quello che abbiamo appena aggiunto",
alla deduzione sbagliata:
"ce n'e' almeno uno bianco",
infatti i cavalli tutti bianchi avrebbero potuto essere in numero di 0.
> Mi ricorda tanto il gioco delle tre carte :-)
Ciao
--
Giorgio Bibbiani
tip&tap
Mar 30, 2015, 2:24:02 PM3/30/15
to
> Teorema: "Dati a,b naturali (0 incluso) e se max(a,b) e' il loro massimo,
> allora a=b".
> Corollario: "Tutti i naturali sono nulli, in particolare 1=0".
> Dimostrazione per induzione, partendo da n=0.
> Sia: P(n) = "a,b naturali, max(a,b)=n".
> 1) P(0) e' vera: se a,b sono naturali & max(a,b)=0, allora a=b=0.
> 2) Se P(n) e' vera, allora:
> P(n+1): max(a,b)=n+1 ==> max(a-1,b-1)=n & a-1=b-1 ==> a=b, c.v.d.
Uhm, vediamo. Se a,b sono due naturali qualsiasi allora
> allora a=b".
> Corollario: "Tutti i naturali sono nulli, in particolare 1=0".
> Dimostrazione per induzione, partendo da n=0.
> Sia: P(n) = "a,b naturali, max(a,b)=n".
> 1) P(0) e' vera: se a,b sono naturali & max(a,b)=0, allora a=b=0.
> 2) Se P(n) e' vera, allora:
> P(n+1): max(a,b)=n+1 ==> max(a-1,b-1)=n & a-1=b-1 ==> a=b, c.v.d.
max(1,2) = 2 => max(1-1,2-1) = 1 ma 1-1 <> 2-1 quindi è falsa.
Ciao
pire...@gmail.com
Mar 30, 2015, 4:06:13 PM3/30/15
to
Secondo me l'inghippo sia in questo caso che in quello del gruppo dei cavalli e' il seguente: quando si mostra che data vera la proposizione per n, segue la proposizione per n+1, bisogna dimostrare che il passo si possa fare per qualunque n. Sia in questo caso che nel caso dei cavalli non si puo' fare il passaggio per un particolare n (da 1 a 2 per il caso dei cavalli, da 0 ad 1 in questo caso), quindi si rompe la catena induttiva.
Paolo Emilio
Mar 30, 2015, 5:04:09 PM3/30/15
to
Il 30 marzo 2015, pire...@gmail.com ha scritto:
>Am Montag, 30. März 2015 14:19:01 UTC+2 schrieb Paolo Emilio:
>> Teorema: "Dati a,b naturali (0 incluso) e se max(a,b) e' il loro massimo,
>> allora a=b".
>> Corollario: "Tutti i naturali sono nulli, in particolare 1=0".
>> Dimostrazione per induzione, partendo da n=0.
>> Sia: P(n) = "a,b naturali, max(a,b)=n".
>> 1) P(0) e' vera: se a,b sono naturali & max(a,b)=0, allora a=b=0.
>> 2) Se P(n) e' vera, allora:
>> P(n+1): max(a,b)=n+1 ==> max(a-1,b-1)=n & a-1=b-1 ==> a=b, c.v.d.
>Am Montag, 30. März 2015 14:19:01 UTC+2 schrieb Paolo Emilio:
>> Teorema: "Dati a,b naturali (0 incluso) e se max(a,b) e' il loro massimo,
>> allora a=b".
>> Corollario: "Tutti i naturali sono nulli, in particolare 1=0".
>> Dimostrazione per induzione, partendo da n=0.
>> Sia: P(n) = "a,b naturali, max(a,b)=n".
>> 1) P(0) e' vera: se a,b sono naturali & max(a,b)=0, allora a=b=0.
>> 2) Se P(n) e' vera, allora:
>> P(n+1): max(a,b)=n+1 ==> max(a-1,b-1)=n & a-1=b-1 ==> a=b, c.v.d.
>L'inghippo secondo me e' questo: prendiamo n+1 = 1; non possiamo
>concludere che sia a-1 che b-1 siano entrambi numeri naturali, in quanto
>uno dei due potrebbe essere uguale a -1. Non possiamo quindi usare il
>fatto che P(0) e' vera.
Si' infatti le regole sono che la 2) deve valere per ogni n>=0.
>concludere che sia a-1 che b-1 siano entrambi numeri naturali, in quanto
>uno dei due potrebbe essere uguale a -1. Non possiamo quindi usare il
>fatto che P(0) e' vera.
>Secondo me l'inghippo sia in questo caso che in quello del gruppo dei
>cavalli e' il seguente: quando si mostra che data vera la proposizione
>per n, segue la proposizione per n+1, bisogna dimostrare che il passo si
>possa fare per qualunque n. Sia in questo caso che nel caso dei cavalli
>non si puo' fare il passaggio per un particolare n (da 1 a 2 per il caso
>dei cavalli, da 0 ad 1 in questo caso), quindi si rompe la catena
>induttiva.
fortissimo) ma tu scambi le ragazze bionde con gli occhi azzurri per
cavalli bianchi. Comunque forse non mi sembra la soluzione giusta.
--
Ciao Paolo
0 new messages