Principio d'induzione matematica
salve, vorrei chiedervi se vi va di spiegarmi un pò il principio di induzione in modo semplice (perchè su wikipedia, altri siti o sul Courant e Robbins non capisco molto), se è troppo lungo e complicato vi chiedo se conosciate qualche sito dove venga spiegato, semplicemente, tale principio.
grazie dell'attenzione
grazie dell'attenzione
Risposte
Secondo la definizione di Peano non è vero che $n$ ed $n+1$ rapresentano tutto $NN$.
Il Principio di Induzione è il quinto assioma di Peano, il quale assioma recita così:
5° Assioma di Peano
Sia $S$ una parte (o sottoinsieme) dell'insieme $NN$ dei numeri naturali. Soddisfi $S$ le due seguenti condizioni:
1) $0 \in S$ (*)
2) $bar{n} \in S => bar{n} + 1 \in S$
Allora $S=NN$.
Questo è il quinto assioma di Peano per la presentazione assiomatica di $NN$ (la ragiona di una presentazione assiomatica di $NN$ sta nel fatto che $NN$ è unico a meno di isomorfismi: applicazioni biiettive di $NN$ in un altro modello di numeri naturali tali da lasciare inalterate le strutture algebriche e d'ordine definite). Tale assioma è noto con il nome di Principio di Induzione.
Come suggerisce il nome, questo è un principio, un assioma e, in quanto tale, non si discute (**). La sostanza del principio è questa: se consideri una parte $S$ di $NN$ e a questa parte $S$ appartiene $0$ e ogniqualvolta $\bar{n}$ è in $S$ succede che anche $bar{n}+1$ (cioè il successivo di $\bar{n}$) è in $S$, allora si può affermare che $S=NN$.
Il principio di induzione nudo e crudo non dimostra niente. Sta la per i fatti suoi e "caratterizza" $NN$.
Noi, che siamo furbi, lo usiamo (nel senso letterale del termine) per fare le dimostrazioni.
Supponiamo di volere dimostrare una proprietà dei numeri naturali. Supponiamo che $A$ sia la parte di $NN$ per la quale vale la proprietà in questione. Se riusciamo a provare che la proprietà è vera per $0$ allora $0 \in A$ e in questo modo cadiamo nell'ipotesi 1) del quinto assioma di Peano. Se riusciamo a provare che supponendo vero che $\bar{n}$ verifica la proprietà si ha che la propeità è vera per $\bar{n}+1$ allora cadiamo nella ipotesi 2) del quinto assioma, perché abbiamo che, supponendo vero che $\bar{n} \in A$, allora anche $\bar{n} + 1 \in A$; a ciò alcune precisazioni: l'ipotesi 2) dell'assioma richiede necessariamente che si supponga vero $\bar{n} \in NN$, se infatti non fosse necessario supporre ciò allora $S$ mancherebbe di $bar{n}$ e quindi ci giochiamo la tesi $S=N$ (***)
In questo modo che succede? Succede che $A$ verifica le 2) ipotesi del 5° assioma e, duqnue, in virtù dello stesso $A=NN$. Ma $A$ è quella parte di $NN$ per la quale vale la proprietà che stiamo discutendo e se $A=NN$ allora la propeità che stiamo discutendo è vera in $NN$, cioè vale per ogni numero naturale.
Note
(*) Anzicché $0 \in NN$ può aversi $1 \in NN$: nulla di strano, dipende da ome si vuol fare iniziare $NN$.
(**) In realtà il principio di induzione è dimostrabile con il Principio del Minimo Intero, anche se questa affermazione non è delle più felici.
(***) Notare che sto dicendo che dobbiamo supporre.
P.S.
Spero di non avere detto sciocchezze (e qui mi rivolgo ai miei superiori di grado nel forum) e di non aver generato confusione nel nostro amico pippo93.
Il Principio di Induzione è il quinto assioma di Peano, il quale assioma recita così:
5° Assioma di Peano
Sia $S$ una parte (o sottoinsieme) dell'insieme $NN$ dei numeri naturali. Soddisfi $S$ le due seguenti condizioni:
1) $0 \in S$ (*)
2) $bar{n} \in S => bar{n} + 1 \in S$
Allora $S=NN$.
Questo è il quinto assioma di Peano per la presentazione assiomatica di $NN$ (la ragiona di una presentazione assiomatica di $NN$ sta nel fatto che $NN$ è unico a meno di isomorfismi: applicazioni biiettive di $NN$ in un altro modello di numeri naturali tali da lasciare inalterate le strutture algebriche e d'ordine definite). Tale assioma è noto con il nome di Principio di Induzione.
Come suggerisce il nome, questo è un principio, un assioma e, in quanto tale, non si discute (**). La sostanza del principio è questa: se consideri una parte $S$ di $NN$ e a questa parte $S$ appartiene $0$ e ogniqualvolta $\bar{n}$ è in $S$ succede che anche $bar{n}+1$ (cioè il successivo di $\bar{n}$) è in $S$, allora si può affermare che $S=NN$.
Il principio di induzione nudo e crudo non dimostra niente. Sta la per i fatti suoi e "caratterizza" $NN$.
Noi, che siamo furbi, lo usiamo (nel senso letterale del termine) per fare le dimostrazioni.
Supponiamo di volere dimostrare una proprietà dei numeri naturali. Supponiamo che $A$ sia la parte di $NN$ per la quale vale la proprietà in questione. Se riusciamo a provare che la proprietà è vera per $0$ allora $0 \in A$ e in questo modo cadiamo nell'ipotesi 1) del quinto assioma di Peano. Se riusciamo a provare che supponendo vero che $\bar{n}$ verifica la proprietà si ha che la propeità è vera per $\bar{n}+1$ allora cadiamo nella ipotesi 2) del quinto assioma, perché abbiamo che, supponendo vero che $\bar{n} \in A$, allora anche $\bar{n} + 1 \in A$; a ciò alcune precisazioni: l'ipotesi 2) dell'assioma richiede necessariamente che si supponga vero $\bar{n} \in NN$, se infatti non fosse necessario supporre ciò allora $S$ mancherebbe di $bar{n}$ e quindi ci giochiamo la tesi $S=N$ (***)
In questo modo che succede? Succede che $A$ verifica le 2) ipotesi del 5° assioma e, duqnue, in virtù dello stesso $A=NN$. Ma $A$ è quella parte di $NN$ per la quale vale la proprietà che stiamo discutendo e se $A=NN$ allora la propeità che stiamo discutendo è vera in $NN$, cioè vale per ogni numero naturale.
Note
(*) Anzicché $0 \in NN$ può aversi $1 \in NN$: nulla di strano, dipende da ome si vuol fare iniziare $NN$.
(**) In realtà il principio di induzione è dimostrabile con il Principio del Minimo Intero, anche se questa affermazione non è delle più felici.
(***) Notare che sto dicendo che dobbiamo supporre.
P.S.
Spero di non avere detto sciocchezze (e qui mi rivolgo ai miei superiori di grado nel forum) e di non aver generato confusione nel nostro amico pippo93.
"alvinlee88":
[quote="pippo93"]dunque... vediamo se ho capito bene...allora noi dimostriamo che una affermazione è vera per un n qualsiasi e per il suo successivo :n+1, ora, dato che l'insieme dei naturali , come mi ha ricordato Sergio, è formato da numeri che abbiano un successore, sappiamo che se l'affermazione è vera per n e per n+1 allora è vera per tutti i numeri naturali (perchè n e n+1 rappresentano, secondo la definizione di Peano, tutti i numeri naturali). Giusto?
No.
Noi non dimostriamo che una affermazione è vera per un n qualsiasi e per n+1 (non dimostreremmo un bel nulla), ma dimostriamo che l'affermazione è vera per $1$ ( o per $0$, dipende dalla cosa da dimostrare) e dimostriamo che il fatto che sia vera per $n$ qualsiasi implica che sia vera anche per $n+1$.[/quote]
ah, forse ho capito: non serve a niente dimostrare un'affermazione per 4 e per 5 perchè sarebbe "dimostrata" solo per tali numeri, bisogna dimostrare che se A è vera per n deve essere per forza vera per n+1, sottolineando che n+1 è il successivo di un numero arbitrario e quindi ha in se il concetto di infinito (riaguardo ai naturali). Così è corretto, giusto?
Non so bene cosa intendi quando dici che "$n+1$ ha in sè il concetto di infinito riguardo ai naturali", però credo tu stia afferrando il concetto. In ogni caso, leggiti bene il post di wizard: il fatto che sia un principio vuol dire che ,di per sè, è indimostrabile (anche se può essere dimostrato a partire dall'assioma di buon ordinamento e viceversa- uno dei 2 lo devi prendere buono come assioma indimostrabile-), ma devi capire perchè è così utile: ci permette di dimostrare con relativa facilità proposizioni relative a infiniti numeri, formalizza rigorosamente il "e così via".
Comunque ho letto anch'io su wikipedia e magari per iniziare non è proprio chiarissimo, con le varie forme, ma spero che fra tutti siamo riusciti a chiarirti un pò le idee..
Comunque ho letto anch'io su wikipedia e magari per iniziare non è proprio chiarissimo, con le varie forme, ma spero che fra tutti siamo riusciti a chiarirti un pò le idee..
"alvinlee88":
Non so bene cosa intendi quando dici che "$n+1$ ha in sè il concetto di infinito riguardo ai naturali", però credo tu stia afferrando il concetto. In ogni caso, leggiti bene il post di wizard: il fatto che sia un principio vuol dire che ,di per sè, è indimostrabile (anche se può essere dimostrato a partire dall'assioma di buon ordinamento e viceversa- uno dei 2 lo devi prendere buono come assioma indimostrabile-), ma devi capire perchè è così utile: ci permette di dimostrare con relativa facilità proposizioni relative a infiniti numeri, formalizza rigorosamente il "e così via".
Comunque ho letto anch'io su wikipedia e magari per iniziare non è proprio chiarissimo, con le varie forme, ma spero che fra tutti siamo riusciti a chiarirti un pò le idee..
dicendo che n+1 ha in sè il concetto di infinito intendo che riassume il fatto che dopo ogni numero arbitrario ce ne sia un altro e che logicamente non esista una fine
ho trovato questo esercizio sull'induzione nel libro "che cos'è la matematica?":
dimostrare che $1^3+2^3+...n^3=[(n(n+1))/2]^2$ io l'ho eseguito così (vi ringrazio se avrete la pazienza di correggermi):
si dimostra per $1$, quindi $1^3=[(1(1+1))/2]^2=1$ e questo è ovvio.
Ora, se è vera $1^3+2^3+...n^3=[(n(n+1))/2]^2$ allora deve essere vera $1^3+2^3+...n^3+(n+1)^3=[(n(n+1))/2]^2+(n+1)^3$ quindi eseguendo le moltiplicazioni e prod notevoli ottengo :
$1^3+2^3+...n^3+(n+1)^3=[(n(n+1))/2]^2+(n+1)^3=(n^4+6n^3+13n^2+12n+4)/4$ e dato che $(n^4+6n^3+13n^2+12n+4)/4=(((n+1)(n+2))/2)^2$ e il secondo membro non è altro che il secondo membro dell'uguaglianza poco fa supposta vera. Quindi dimostrato che $1^3+2^3+...n^3=[(n(n+1))/2]^2$ è vera per $1$, e il fatto che sia vera per $n$ implica il fatto che sia vera per $n+1$, allora è vera per qualsiasi $n in NN$
dimostrare che $1^3+2^3+...n^3=[(n(n+1))/2]^2$ io l'ho eseguito così (vi ringrazio se avrete la pazienza di correggermi):
si dimostra per $1$, quindi $1^3=[(1(1+1))/2]^2=1$ e questo è ovvio.
Ora, se è vera $1^3+2^3+...n^3=[(n(n+1))/2]^2$ allora deve essere vera $1^3+2^3+...n^3+(n+1)^3=[(n(n+1))/2]^2+(n+1)^3$ quindi eseguendo le moltiplicazioni e prod notevoli ottengo :
$1^3+2^3+...n^3+(n+1)^3=[(n(n+1))/2]^2+(n+1)^3=(n^4+6n^3+13n^2+12n+4)/4$ e dato che $(n^4+6n^3+13n^2+12n+4)/4=(((n+1)(n+2))/2)^2$ e il secondo membro non è altro che il secondo membro dell'uguaglianza poco fa supposta vera. Quindi dimostrato che $1^3+2^3+...n^3=[(n(n+1))/2]^2$ è vera per $1$, e il fatto che sia vera per $n$ implica il fatto che sia vera per $n+1$, allora è vera per qualsiasi $n in NN$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo