Ma l'induzione non fallisce?
Salve a tutti.
Perdonatemi se vi pongo una domanda idiota, ma avendo discusso altre volte su questo forum di esempi di prove per induzione che sembrano funzionare ma poi non funzionano, torno per porre una domanda sulla seguente dimostrazione. La faccio perché l'ho trovata su una dispensa dell'università, quindi per il principio di autorità credo di essere io in errore.
Oggetto: dimostrare la seguente proposizione
[tex]\text{ Se } a,b,d \text{ sono tre qualunque elementi di } \mathbb{N} \text{ allora } a+b=a+d \implies b=d[/tex]
Dimostrazione
[tex]\text{Fissati } b, d \text{ l'implicazione da provare è vera se } a=0. \text{ Ammettiamola vera per } a \text{ e supponiamo }\\ (a+1)+b=(a+1)+d \text{ o, ciò che è lo stesso, } (a+b)+1=(a+d)+1. \text{ Ma questo, per l'iniettività della }\\ \text{ funzione successore, implica } b=d.[/tex]
E' evidente che si usa il principio di induzione, ma io mi domando: questo non è uno dei casi dove l'induzione fallisce? Voglio dire: qui l'ipotesi induttiva è una implicazione, che essa sia vera per [tex]a[/tex] non ci assicura che sia vero l'antecedente di questa implicazione (i.e. (*) [tex]a+b=a+d[/tex]); inoltre perché assume che sia vero (**) [tex](a+1)+b=(a+1)+d[/tex]? Mi son risposto: perché vuole provare che l'implicazione è vera per [tex]a+1[/tex] e se supponesse falsa la (**) l'implicazione sarebbe vera per falsità dell'antecendente, ma ammesso e non concesso che questo sia lecito, poi quando sfrutta l'iniettività del successore su [tex](a+b)+1=(a+d)+1[/tex] non sta usando (*) senza sapere se è vera?
Non è forse forse sono in errore? Se lo sono, perché lo sono?
P.S.
L'ho messa qui perché le dispense di cui in oggetto sono dispense di un corso di Analsi.
Perdonatemi se vi pongo una domanda idiota, ma avendo discusso altre volte su questo forum di esempi di prove per induzione che sembrano funzionare ma poi non funzionano, torno per porre una domanda sulla seguente dimostrazione. La faccio perché l'ho trovata su una dispensa dell'università, quindi per il principio di autorità credo di essere io in errore.
Oggetto: dimostrare la seguente proposizione
[tex]\text{ Se } a,b,d \text{ sono tre qualunque elementi di } \mathbb{N} \text{ allora } a+b=a+d \implies b=d[/tex]
Dimostrazione
[tex]\text{Fissati } b, d \text{ l'implicazione da provare è vera se } a=0. \text{ Ammettiamola vera per } a \text{ e supponiamo }\\ (a+1)+b=(a+1)+d \text{ o, ciò che è lo stesso, } (a+b)+1=(a+d)+1. \text{ Ma questo, per l'iniettività della }\\ \text{ funzione successore, implica } b=d.[/tex]
E' evidente che si usa il principio di induzione, ma io mi domando: questo non è uno dei casi dove l'induzione fallisce? Voglio dire: qui l'ipotesi induttiva è una implicazione, che essa sia vera per [tex]a[/tex] non ci assicura che sia vero l'antecedente di questa implicazione (i.e. (*) [tex]a+b=a+d[/tex]); inoltre perché assume che sia vero (**) [tex](a+1)+b=(a+1)+d[/tex]? Mi son risposto: perché vuole provare che l'implicazione è vera per [tex]a+1[/tex] e se supponesse falsa la (**) l'implicazione sarebbe vera per falsità dell'antecendente, ma ammesso e non concesso che questo sia lecito, poi quando sfrutta l'iniettività del successore su [tex](a+b)+1=(a+d)+1[/tex] non sta usando (*) senza sapere se è vera?
Non è forse forse sono in errore? Se lo sono, perché lo sono?
P.S.
L'ho messa qui perché le dispense di cui in oggetto sono dispense di un corso di Analsi.
Risposte
Penso di essere effettivamente in errore.
Si vuole provare per induzione che [tex]\forall a,b,d \in \mathbb{N}, a+b=a+d \implies b=d[/tex].
Per [tex]a=0[/tex] si ha [tex]0+b=b=d=0+d \implies b=d[/tex] che è banalmente vera.
Occorre poi provare che [tex](a+b=a+d \implies b=d) \implies ((a+1)+b=(a+1)+d \implies b=d)[/tex]: supposto dunque vero che (1) [tex]a+b=a+d\implies b=d[/tex] si vuole provare che è vero (2) [tex](a+1)+b=(a+1)+d\implies b=d[/tex]; ebbene se [tex](a+1)+b\neq(a+1)+d[/tex] allora (2) è vera perché ex falso quodlibet, sicché supponiamo [tex](a+1)+b=(a+1)+d[/tex]: risulta, per associatività e commutatività, [tex](a+b)+1=(a+d)+1[/tex], ma questa è l'uguaglianza tra i successivi di [tex]a+b[/tex] ed [tex]a+d[/tex], quindi per l'iniettività della funzione successore e non per l'antecendete della (1), si ha [tex]a+b=a+d[/tex]; quindi poiché è vera la (1) per ipotesi induttiva, si ha [tex]b=d[/tex], sicché, finalmente, [tex](a+1)+b=(a+1)+d \implies b=d[/tex] è vera.
Dico bene o no?
Si vuole provare per induzione che [tex]\forall a,b,d \in \mathbb{N}, a+b=a+d \implies b=d[/tex].
Per [tex]a=0[/tex] si ha [tex]0+b=b=d=0+d \implies b=d[/tex] che è banalmente vera.
Occorre poi provare che [tex](a+b=a+d \implies b=d) \implies ((a+1)+b=(a+1)+d \implies b=d)[/tex]: supposto dunque vero che (1) [tex]a+b=a+d\implies b=d[/tex] si vuole provare che è vero (2) [tex](a+1)+b=(a+1)+d\implies b=d[/tex]; ebbene se [tex](a+1)+b\neq(a+1)+d[/tex] allora (2) è vera perché ex falso quodlibet, sicché supponiamo [tex](a+1)+b=(a+1)+d[/tex]: risulta, per associatività e commutatività, [tex](a+b)+1=(a+d)+1[/tex], ma questa è l'uguaglianza tra i successivi di [tex]a+b[/tex] ed [tex]a+d[/tex], quindi per l'iniettività della funzione successore e non per l'antecendete della (1), si ha [tex]a+b=a+d[/tex]; quindi poiché è vera la (1) per ipotesi induttiva, si ha [tex]b=d[/tex], sicché, finalmente, [tex](a+1)+b=(a+1)+d \implies b=d[/tex] è vera.
Dico bene o no?
"WiZaRd":
[tex]\text{Fissati } b, d \text{ l'implicazione da provare è vera se } a=0. \text{ Ammettiamola vera per } a \text{ e supponiamo }\\ (a+1)+b=(a+1)+d \text{ o, ciò che è lo stesso, } (a+b)+1=(a+d)+1. \text{ Ma questo, per l'iniettività della }\\ \text{ funzione successore, implica } b=d.[/tex]
Manca un piccolo passaggio, forse... Direi:
"Ma questo, per l'iniettività della funzione successore, implica [tex]a+b=a+d[/tex] e, per ipotesi induttiva, [tex]b=d[/tex]."
*** EDIT: vedo, con piacere, che avevi risolto!
Per quanto riguarda la seconda questione, cioè la (**), direi questo: innanzitutto hai [tex](a+1)+m=(a+m)+1[/tex] per ogni [tex]m\in \mathbb{N}[/tex] (viene, se ben ricordo, dalle proprietà che definiscono induttivamente la somma); quindi se [tex](a+1)+b=(a+1)+d[/tex] hai [tex](a+b)+1=(a+1)+b=(a+1)+d=(a+d)+1[/tex].
WiZ, domani ti consiglio vivamente di passare a MSA: ci sono le lauree e se sei a corrente di quanto è successo il mese scorso...
"Gugo82":
*** EDIT: vedo, con piacere, che avevi risolto!
Confortato da quanto scrivi, direi di sì. Thanks
"Gugo82":
WiZ, domani ti consiglio vivamente di passare a MSA: ci sono le lauree e se sei a corrente di quanto è successo il mese scorso...
Perché cosa è successo il mese scorso? Il mese scorso MSA l'ho frequentato ma non so niente...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo