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

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!
 
 1) Dimostrare che ogni sottoinsieme non vuoto di N ha un elemento minimo. 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.
 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!
 
 2) Dimostrare che tutti gli interi da 1 a 101 hanno la stessa parita\'. 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.
 Ora, 1 e\' dispari e 2 e\' pari... come si spiega?
 
 3) 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. 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.
 Beh, effettivamente l\'enunciato e\' vero, ma la dimostrazione contiene un errore micidiale!
 
 4) Sono dati n interi positivi tali che i 2n 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). 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 2n-1 somme distinte, si puo\' applicare l\'ipotesi induttiva, concludendo che necessariamente b>S. Questo significa che tutte le 2n-2 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.
 Anche qui, l\'enunciato e\' addirittura falso. Dov\'e\' l\'errore? [ Questo Messaggio è stato Modificato da: MindFlyer il 21-06-2004 17:28 ]

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-06-21 04:49, MindFlyer wrote:
 2) Dimostrare che tutti gli interi da 1 a 101 hanno la stessa parita\'. 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.
 Ora, 1 e\' dispari e 2 e\' pari... come si spiega?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 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!)

XT · Messaggio da XT » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-06-21 12:03, matthewtrager wrote:
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-06-21 04:49, MindFlyer wrote:
 2) Dimostrare che tutti gli interi da 1 a 101 hanno la stessa parita\'. 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.
 Ora, 1 e\' dispari e 2 e\' pari... come si spiega?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 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!)
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 la stessa storia delle bionde!

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!
 Gli altri due?
 
 EDIT: ho aggiunto un quarto esempio, veramente satanico. [ Questo Messaggio è stato Modificato da: MindFlyer il 21-06-2004 17:28 ]

edony · 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.
 
 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 · 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....
 
 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!\" ?
 
 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).

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-06-21 21:18, BlaisorBlade wrote:
 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.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 beh, se l\'insieme ha n punti per ipotesi induttiva soddisfa la cosa, no? <IMG SRC="images/forum/icons/icon_cool.gif">
 in effetti in quello c\'è qualcosa che mi sfugge..

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-06-21 21:18, BlaisorBlade wrote:
 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!\" ?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 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.
 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.
 
 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...
 
 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.
 
 EDIT: Non sapevo che il 3) fosse sull\'Engel. Riesci a dirmi anche la pagina, plz? [ Questo Messaggio è stato Modificato da: MindFlyer il 22-06-2004 03:55 ]

BlaisorBlade · 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).
 
 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.
 
 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 · 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).
 
 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. [ Questo Messaggio è stato Modificato da: MindFlyer il 23-06-2004 01:23 ]