Dubbio su dimostrazione per induzione
Ciao a tutta la sezione.
Vorrei chiedere a voi un aiuto riguardo l'intuizione della dimostrazione per induzione. Studiandola con i postulati di Peano mi ci trovo mostrando come l'insieme l'insieme X=N tramite l'ultimo postulato renda vera una P(n) per ogni $n in X$. Cioè la proposizione vera per un certo n in X e per tutti i successivi (funzione successore) diventa vera per ogni naturale N essendo N=X dall'ultimo postulato.
Quello che non riesco però a vedere è intuitivamente come funzioni una dimostrazione per induzione.
Di base mostro che:
- vale la base dell'induzione per un certo n=0 (o comnque un primo n del mio insieme es. anche n=1)
- passo induttivo: esso si compone dell'ipotesi induttiva dove suppongo vera P(n) per qualche n e tramite cui andrò a mostrare che P(n)=>P(n+1) e questa implicazione mostra che l'assunto P varrà per ogni n.
Ora, il punto in cui mi incastro è questo: io suppongo vera P(n), ma per quanto ne so potrebbe essere falsa (non ho infatti dimostrato P(n) ma solo supposto P(n) VERA). Quindi quando vado a verificare P(n)=>P(n+1) in realtà sto studiano una implicazione che di base potrebbe avere l'antecedente FALSO, nessuno garantisce che P(n) fosse di per sé vero.
Ma dal falso consegue qualunque cosa. Quindi non sto viziando la mia dimostrazione in tal modo? Partendo dal falso infatti se mostro che sfruttado P(n) è vero per P(n+1) dimostro che quella cosa falsa potrebe essere vera per ogni n
. Non ci siamo, qualcosa mi sfugge.
Non riesco proprio a sbrogliarmi da questo punto in cui mi aggroviglio.
Grazie per l'aiuto.
Vorrei chiedere a voi un aiuto riguardo l'intuizione della dimostrazione per induzione. Studiandola con i postulati di Peano mi ci trovo mostrando come l'insieme l'insieme X=N tramite l'ultimo postulato renda vera una P(n) per ogni $n in X$. Cioè la proposizione vera per un certo n in X e per tutti i successivi (funzione successore) diventa vera per ogni naturale N essendo N=X dall'ultimo postulato.
Quello che non riesco però a vedere è intuitivamente come funzioni una dimostrazione per induzione.
Di base mostro che:
- vale la base dell'induzione per un certo n=0 (o comnque un primo n del mio insieme es. anche n=1)
- passo induttivo: esso si compone dell'ipotesi induttiva dove suppongo vera P(n) per qualche n e tramite cui andrò a mostrare che P(n)=>P(n+1) e questa implicazione mostra che l'assunto P varrà per ogni n.
Ora, il punto in cui mi incastro è questo: io suppongo vera P(n), ma per quanto ne so potrebbe essere falsa (non ho infatti dimostrato P(n) ma solo supposto P(n) VERA). Quindi quando vado a verificare P(n)=>P(n+1) in realtà sto studiano una implicazione che di base potrebbe avere l'antecedente FALSO, nessuno garantisce che P(n) fosse di per sé vero.
Ma dal falso consegue qualunque cosa. Quindi non sto viziando la mia dimostrazione in tal modo? Partendo dal falso infatti se mostro che sfruttado P(n) è vero per P(n+1) dimostro che quella cosa falsa potrebe essere vera per ogni n
. Non ci siamo, qualcosa mi sfugge.Non riesco proprio a sbrogliarmi da questo punto in cui mi aggroviglio.
Grazie per l'aiuto.
Risposte
Se tu dimostri che $P(n+1)$ è vera quando $P(n)$ è vera, sei a posto perché hai già dimostrato che $P(x)$ è vera per il PRIMO della lista e quindi ne consegue (dal passo induttivo che hai appunto dimostrato vero) che è vera per il SECONDO della lista, da cui ne consegue che è vera per il TERZO della lista, ecc.
Cordialmente, Alex
Cordialmente, Alex
Ah ok quindi il senso è che parto comunque dal primo. Perché avevo inteso "il suppongo vera per P(n)" come una ipotesi su un n-esimo superiore al primo e mi dicevo "si ok, ma è solo SUPPOSTO vero" che diamine me ne faccio di una implicazione che potrebbe avere antecedente falso.
Invece è proprio la base dell'induzione che garantisce che qualunque antecedente P(n) sia vero, perché raggiungo un qualunque P(n) per passi induttivi e risulta vero.
Invece è proprio la base dell'induzione che garantisce che qualunque antecedente P(n) sia vero, perché raggiungo un qualunque P(n) per passi induttivi e risulta vero.
"smartword":
Ah ok quindi il senso è che parto comunque dal primo.
Eh, beh, se il principio di induzione si basa sue "due passi" un motivo ci sarà
Thx
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo