L\'uso indiscriminato dell\'induzione e\' male

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
MindFlyer

Messaggio da MindFlyer » 01 gen 1970, 01:33

Ripropongo degli esempi di induzione usata in modi sbagliati: alcuni molto famosi, altri meno. Siete invitati a dire, per ognuno, qual e\' l\'errore e come andrebbe corretto (quando possibile). Se avete altri esempi, proponeteli!
<BR>
<BR>1) <!-- BBCode Start --><B>Dimostrare che ogni sottoinsieme non vuoto di N ha un elemento minimo.</B><!-- BBCode End --> Induzione sul numero n degli elementi dell\'insieme: per n=1 ovviamente funziona; poi, supposto che funzioni per tutti gli insiemi di n elementi, possiamo costruire ogni insieme di n+1 elementi aggiungendo un elemento ad un opportuno insieme di n elementi. Se questo nuovo elemento e\' minore del minimo, diventa il nuovo minimo, altrimenti il minimo rimane quello di prima. Ergo, il teorema e\' dimostrato per sottoinsiemi di N di qualunque numero di elementi.
<BR><!-- BBCode Start --><I>Se siete convinti che vada tutto bene, notate che esattamente nello stesso modo si puo\' \"dimostrare\" che ogni sottoinsieme di N ha un elemento massimo, cosa chiaramente falsa!</I><!-- BBCode End -->
<BR>
<BR>2) <!-- BBCode Start --><B>Dimostrare che tutti gli interi da 1 a 101 hanno la stessa parita\'.</B><!-- BBCode End --> Dimostriamo che gli n elementi di un qualunque sottoinsieme degli interi da 1 a 101 hanno la stessa parita\', per induzione su n. Per n=1 e\' ovvio, mentre se e\' vero per ogni sottoinsieme di n elementi, allora preso un qualunque sottoinsieme di n+1 elementi possiamo fissare un suo elemento a che avra\' una certa parita\' P(a). Tutti gli altri n elementi avranno, per ipotesi induttiva la stessa parita\'. Tra questi scegliamo b e c, con parita\' P(b)=P(c), e di nuovo gli n elementi diversi da b avranno la stessa parita\'. Ma siccome a e c sono inclusi tra questi elementi, allora deve necessariamente valere P(a)=P(c)=P(b), e dunque tutti gli n+1 elementi hanno la stessa parita\', concludendo la dimostrazione.
<BR><!-- BBCode Start --><I>Ora, 1 e\' dispari e 2 e\' pari... come si spiega?</I><!-- BBCode End -->
<BR>
<BR>3) <!-- BBCode Start --><B>Nel piano sono presi n>=3 punti, in modo che ogni retta passante per 2 di essi, passa anche per un terzo punto. Dimostrare che tutti gli n punti stanno su una stessa retta.</B><!-- BBCode End --> Per induzione su n: per n=3 e\' ovvio. Supponiamo ora che sia vero per n, ed aggiungiamo un n+1 esimo punto. Per ipotesi induttiva i primi n punti stanno su una retta: ma anche l\'n+1 esimo deve stare su quella retta, perche\' altrimenti ogni retta passante per quel punto ed uno qualunque dei rimantenti n, non passerebbe per alcun altro punto. Quindi la tesi e\' dimostrata per induzione.
<BR><!-- BBCode Start --><I>Beh, effettivamente l\'enunciato e\' vero, ma la dimostrazione contiene un errore micidiale!</I><!-- BBCode End -->
<BR>
<BR>4) <!-- BBCode Start --><B>Sono dati n interi positivi tali che i 2<sup>n</sup> possibili loro sottoinsiemi hanno somme tutte distinte tra loro. Dimostrare che il piu\' grande tra gli n numeri e\' maggiore della somma degli altri n-1 (per convenzione, l\'insieme vuoto ha somma 0).</B><!-- BBCode End --> Se n=1 o n=2 e\' ovvio. Ora, supponiamo di avere n>=3 numeri, e sia a il piu\' grande, b il piu\' grande dopo a, e S>0 la somma dei numeri rimanenti. Siccome anche gli n-1 numeri fino a b devono avere 2<sup>n-1</sup> somme distinte, si puo\' applicare l\'ipotesi induttiva, concludendo che necessariamente b>S. Questo significa che tutte le 2<sup>n-2</sup> somme dei sottoinsiemi dei primi n-2 numeri vengono ripetute \"traslate in avanti\" di b, in modo che l\'inizio della seconda \"ripetizione\" cominci dopo la fine della prima. In caso contrario, sicuramente le due \"ripetizioni\" si intersecherebbero. Se adesso fosse b<=a<=S+b, allora per lo stesso motivo la \"ripetizione\" traslata di a dovrebbe intersecare quella traslata di b. Quindi a>S+b, e questo conclude la dimostrazione per induzione.
<BR><!-- BBCode Start --><I>Anche qui, l\'enunciato e\' addirittura falso. Dov\'e\' l\'errore?</I><!-- BBCode End --><font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: MindFlyer il 21-06-2004 17:28 ]

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-06-21 04:49, MindFlyer wrote:
<BR>2) <!-- BBCode Start --><B>Dimostrare che tutti gli interi da 1 a 101 hanno la stessa parita\'.</B><!-- BBCode End --> Dimostriamo che gli n elementi di un qualunque sottoinsieme degli interi da 1 a 101 hanno la stessa parita\', per induzione su n. Per n=1 e\' ovvio, mentre se e\' vero per ogni sottoinsieme di n elementi, allora preso un qualunque sottoinsieme di n+1 elementi possiamo fissare un suo elemento a che avra\' una certa parita\' P(a). Tutti gli altri n elementi avranno, per ipotesi induttiva la stessa parita\'. Tra questi scegliamo b e c, con parita\' P(b)=P(c), e di nuovo gli n elementi diversi da b avranno la stessa parita\'. Ma siccome a e c sono inclusi tra questi elementi, allora deve necessariamente valere P(a)=P(c)=P(b), e dunque tutti gli n+1 elementi hanno la stessa parita\', concludendo la dimostrazione.
<BR><!-- BBCode Start --><I>Ora, 1 e\' dispari e 2 e\' pari... come si spiega?</I><!-- BBCode End -->
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>non so se e\' questo, ma credo l\'errore stia nel dire che si possano sempre prendere b e c perche\' se partiamo dall\'insime che ha 1 elemento, l\'insime successivo ne ha 2 e qui esiste un solo altro elemento oltre al primo. ovviamente, trattandosi di induzione, se non vale un passaggio, crolla tutto. (spero!)

Avatar utente
XT
Messaggi: 695
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da XT » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-06-21 12:03, matthewtrager wrote:
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-06-21 04:49, MindFlyer wrote:
<BR>2) <!-- BBCode Start --><B>Dimostrare che tutti gli interi da 1 a 101 hanno la stessa parita\'.</B><!-- BBCode End --> Dimostriamo che gli n elementi di un qualunque sottoinsieme degli interi da 1 a 101 hanno la stessa parita\', per induzione su n. Per n=1 e\' ovvio, mentre se e\' vero per ogni sottoinsieme di n elementi, allora preso un qualunque sottoinsieme di n+1 elementi possiamo fissare un suo elemento a che avra\' una certa parita\' P(a). Tutti gli altri n elementi avranno, per ipotesi induttiva la stessa parita\'. Tra questi scegliamo b e c, con parita\' P(b)=P(c), e di nuovo gli n elementi diversi da b avranno la stessa parita\'. Ma siccome a e c sono inclusi tra questi elementi, allora deve necessariamente valere P(a)=P(c)=P(b), e dunque tutti gli n+1 elementi hanno la stessa parita\', concludendo la dimostrazione.
<BR><!-- BBCode Start --><I>Ora, 1 e\' dispari e 2 e\' pari... come si spiega?</I><!-- BBCode End -->
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>non so se e\' questo, ma credo l\'errore stia nel dire che si possano sempre prendere b e c perche\' se partiamo dall\'insime che ha 1 elemento, l\'insime successivo ne ha 2 e qui esiste un solo altro elemento oltre al primo. ovviamente, trattandosi di induzione, se non vale un passaggio, crolla tutto. (spero!)
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>la stessa storia delle bionde!
"Signore, (a+b^n)/n=x, dunque Dio esiste!" (L.Euler)

MindFlyer

Messaggio da MindFlyer » 01 gen 1970, 01:33

Si\', esatto, questo era famoso... ma si puo\' anche formulare in modi in cui l\'errore non e\' cosi\' ovvio!
<BR>Gli altri due?
<BR>
<BR>EDIT: ho aggiunto un quarto esempio, veramente satanico.<BR><BR>[ Questo Messaggio è stato Modificato da: MindFlyer il 21-06-2004 17:28 ]

edony
Messaggi: 204
Iscritto il: 01 gen 1970, 01:00
Località: Salerno

Messaggio da edony » 01 gen 1970, 01:33

Per il primo direi,ma non ne sono proprio sicurissimo, che con quel procedimento si dimostra il principio per sottoinsiemi finiti, e per questi vale sia col massimo che col minimo,non si dimostra però la tesi per i sottoinsiemi infiniti,che non hanno cardinalità,sulla quale dunque non si può applicare il PI.
<BR>
<BR>P.s. non sono sicuro che gli insiemi infiniti non abbiano effettivamente cardinalità, però il concetto è quello...non si può esprimere il numero degli elementi in pratica.

BlaisorBlade
Messaggi: 113
Iscritto il: 01 gen 1970, 01:00
Località: Catania

Messaggio da BlaisorBlade » 01 gen 1970, 01:33

Appunto: l\'unico errore nel primo è che non viene specificato che il sottoinsieme dato deve essere finito; l\'induzione non vale su insiemi infiniti. Tuttavia gli insiemi infiniti hanno una cardinalità, edony! E si possono anche \"contare\" i loro elementi, dato che l\'unica definizione seria di \"contare\" è mettere in corrispondenza biunivoca con un altro insieme. E si scoprono varie cose, per esempio che i razionali sono quanti gli interi, ma che i reali sono di più, e i reali in [0,1] sono quanti i punti nello spazio....
<BR>
<BR>Per il 2, in effetti, nella dimostrazione più diffusa non si prendono 2 elementi diversi da a, ma si piglia solo un b=/=a. Ti riferisci a questo, Mind, con
<BR>
<BR>\"Si\', esatto, questo era famoso... ma si puo\' anche formulare in modi in cui l\'errore non e\' cosi\' ovvio!\" ?
<BR>
<BR>Per il 3): l\'ipotesi induttiva è per tutti gli insiemi di n punti, ma un insieme di n+1 punti può non contenere insiemi di n punti che soddisfano l\'ipotesi. Questo è sull\'Engel, e un matematico professionista aveva scritto anche una soluzione molto complicata (ce n\'è anche una di 5 righe col principio del minimo intero, ma per ora non la posto, e non è banale).

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-06-21 21:18, BlaisorBlade wrote:
<BR>Per il 3): l\'ipotesi induttiva è per tutti gli insiemi di n punti, ma un insieme di n+1 punti può non contenere insiemi di n punti che soddisfano l\'ipotesi.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>beh, se l\'insieme ha n punti per ipotesi induttiva soddisfa la cosa, no? <IMG SRC="images/forum/icons/icon_cool.gif">
<BR>in effetti in quello c\'è qualcosa che mi sfugge..
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]

MindFlyer

Messaggio da MindFlyer » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-06-21 21:18, BlaisorBlade wrote:
<BR>Per il 2, in effetti, nella dimostrazione più diffusa non si prendono 2 elementi diversi da a, ma si piglia solo un b=/=a. Ti riferisci a questo, Mind, con \"Si\', esatto, questo era famoso... ma si puo\' anche formulare in modi in cui l\'errore non e\' cosi\' ovvio!\" ?
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Quella di prendere solo un b=/=a non e\' una sostanziale differenza, perche\' mi sembra che in realta\' anche la versione piu\' classica prenda implicitamente un c oltre ad a e b, ma non lo dica al solo scopo di mascherare meglio l\'inganno.
<BR>Intendevo dire che puo\' non essere cosi\' ovvia la necessita\' della dimostrazione diretta di piu\' di un caso base per poter far partire l\'induzione. Inoltre, non sempre l\'enunciato che si va a dimostrare e\' falso, o comunque non lo e\' in modo cosi\' palese, ed e\' quindi meno immediato accorgersi dell\'errore.
<BR>
<BR>Ok per i punti 1) e 3). Solamente, per il 3) la dimostrazione giusta e corta non fa uso del principio del minimo intero, ma del fatto che un insieme finito di numeri reali (ovvero le distanze tra i vari punti) ha minimo. Era solo una puntualizzazione senza troppa importanza...
<BR>
<BR>Che mi dite invece del 4)? Forse l\'ho scritto in modo incomprensibile, ma l\'errore di fondo e\' sottile quanto devastante! Se non capite quello che ho scritto, chiedete e vi sara\' chiarito.
<BR>
<BR>EDIT: Non sapevo che il 3) fosse sull\'Engel. Riesci a dirmi anche la pagina, plz?<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: MindFlyer il 22-06-2004 03:55 ]

BlaisorBlade
Messaggi: 113
Iscritto il: 01 gen 1970, 01:00
Località: Catania

Messaggio da BlaisorBlade » 01 gen 1970, 01:33

Per Talpuz: se l\'insieme di n+1 punti l\'ho costruito a partire da uno di n, quello di n soddisfa l\'ipotesi, ovviamente. Ma siamo proprio sicuri che a partire da tutti gli insiemi di n punti possiamo costruire quelli di n+1? Non ne siamo sicuri (poi è così dato che la tesi è vera, ma solo alla fine). Mi pare che si fosse parlato di questo a Pisa, per combinatoria (forse accennato).
<BR>
<BR>Pensa a un\'insieme di 3 punti su una retta e di altri 3 su un\'altra retta. In realtà, non soddisfa le ipotesi del problema (e non posso trovare un controesempio a un teorema), ma lo fa finché ti limiti a finché pigli 2 punti sulla stessa retta; se però gli togli un punto qualunque, non vale più neanche questa assunzione.
<BR>
<BR>Per MindFlyer: non ho il libro a portata, ma è un esempio del capitolo sull\'Extremal Principle, mi pare il 3: si tratta del Sylvester Problem, se non erro.

BlaisorBlade
Messaggi: 113
Iscritto il: 01 gen 1970, 01:00
Località: Catania

Messaggio da BlaisorBlade » 01 gen 1970, 01:33

Per il 4): scusa, ma che problema c\'è se si due ripetizioni si intersecano? Se in una ripetizione vi sono 3 e 5, e lo shift è 1 (si possono aumentare i coefficienti per avere una situazione effettivamente possibile in quel contesto), si ottengono 4 e 6. In realtà, le due ripetizioni non si intersecano perché le somme degli n-2 numeri sono tutte minori di b, quindi se aggiungo numeri non vi sono intersezioni (quel discorsetto per assurdo sembra fatto proprio per confondere).
<BR>
<BR>In particolare, se S+b > a, metti che S+b è 5, e a è < 5, dove sta l\'assurdo? Sembra implicito (ma falso) che le somme coprano a sufficenza gli interi (ad esempio comprendano tutti i numeri di un intervallo opportuno).

MindFlyer

Messaggio da MindFlyer » 01 gen 1970, 01:33

Ok Blaisor, ma tu sai anche che se togli a, togli b ed al suo posto metti un numero minore di S, per l\'ipotesi induttiva hai un\'intersezione. Percio\', rimettendo b hai una situazione esattamente identica tra b e S+b, ma solo traslata di b: insomma, anche qui a non puo\' stare prima di S+b.<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: MindFlyer il 23-06-2004 01:23 ]

Bloccato