Somma dei naturali principio d'induzione
Qualcuno può spiegarmi la somma dei primi numeri naturali applicando il principio di induzione?
Risposte
Per prima cosa bisogna tenere presenti gli assiomi di peano che caratterizzano un insieme non vuoto $NN$.
Assioma 1): $1inNN$
Assioma 2): per ogni $ninNN$ esiste uno ed un solo $f(n)inNN$, chiamato successore di $NN$.
Assioma 3): per ogni $ninNN$, risulta $f(n)!=1$.
Assioma 4): Se $m,n inNN$, e $f(m)=f(n)$ allora questo implica $m=n$.
Assioma 5): Ogni sottoinsieme $K$ di $NN$ con le seguenti proprietà:
a) $1inK$
b) se $kinK$ allora $f(k)inK$
Coincide con $NN$.
In sostanza a posto dell'usuale asterisco per comodità ho usato $f$ come funzione successore, l'assioma 5) non è altro che il più usuale principio del minimo(ogni sottoinsieme non vuoto di $NN$ ha minimo).
Andiamo adesso a definire la somma in $NN$ con le seguenti condizioni:
i) $(n+1)=f(n)$ per ogni $ninNN$.
ii) se $(n+m)$ è definito, $n+f(m)=f(n+m)$.
Possiamo adesso mostrare che la somma ha le seguenti proprietà:
Se $m,n,t inNN$
Chiusura $n+m$$inNN$
Commutatività $n+m=m+n$
Associatività $m+(n+t)=(m+n)+t$
Cancellazione Se $m+t=n+t$, allora $m=n$.
Per esempio dimostriamo la proprietà di chiusura;
Dobbiamo in sostanza dimostrare che $n+m$ è per tutti gli $m,ninNN$, un numero naturale, come conseguenza delle condizioni i) ed ii) e degli assiomi.
Supponiamo che $n$ sia un naturale fissato e consideriamo la seguente proposizione:
$(n+m)inNN$ per ogni $m$$inNN$
adesso la proposizione per $m=1$ è vera essendo $n+1=f(n)inNN$ vera per la condizione i) e per l'assioma 2).
Sia $m=k$ per un qualche $kinNN$ e supponiamo che sia $(n+k)inNN$ vera, allora segue che anche $n+f(k)$$inNN$ cioè è vera , infatti $n+f(k)=f(n+k)$ per la condizione ii) e $f(n+k)inNN$ dato che $(n+k)inNN$ per l'assioma 2).
Essendo che la proposizione è vera per $m=1$ (base dell'induzione), ed che se supposta vera per qualche $m=kinNN$ allora è vera per $m=k+1$, possiamo concludere che è vera per tutti gli $m$$inNN$.
Le rimanenti proprietà si possono dimostrare similmente utilizzando le condizioni i),ii), e gli assiomi (prova!).
Spero che non abbia commesso errori nell'esposizione, in ogni caso apprezza lo sforzo!
Assioma 1): $1inNN$
Assioma 2): per ogni $ninNN$ esiste uno ed un solo $f(n)inNN$, chiamato successore di $NN$.
Assioma 3): per ogni $ninNN$, risulta $f(n)!=1$.
Assioma 4): Se $m,n inNN$, e $f(m)=f(n)$ allora questo implica $m=n$.
Assioma 5): Ogni sottoinsieme $K$ di $NN$ con le seguenti proprietà:
a) $1inK$
b) se $kinK$ allora $f(k)inK$
Coincide con $NN$.
In sostanza a posto dell'usuale asterisco per comodità ho usato $f$ come funzione successore, l'assioma 5) non è altro che il più usuale principio del minimo(ogni sottoinsieme non vuoto di $NN$ ha minimo).
Andiamo adesso a definire la somma in $NN$ con le seguenti condizioni:
i) $(n+1)=f(n)$ per ogni $ninNN$.
ii) se $(n+m)$ è definito, $n+f(m)=f(n+m)$.
Possiamo adesso mostrare che la somma ha le seguenti proprietà:
Se $m,n,t inNN$
Chiusura $n+m$$inNN$
Commutatività $n+m=m+n$
Associatività $m+(n+t)=(m+n)+t$
Cancellazione Se $m+t=n+t$, allora $m=n$.
Per esempio dimostriamo la proprietà di chiusura;
Dobbiamo in sostanza dimostrare che $n+m$ è per tutti gli $m,ninNN$, un numero naturale, come conseguenza delle condizioni i) ed ii) e degli assiomi.
Supponiamo che $n$ sia un naturale fissato e consideriamo la seguente proposizione:
$(n+m)inNN$ per ogni $m$$inNN$
adesso la proposizione per $m=1$ è vera essendo $n+1=f(n)inNN$ vera per la condizione i) e per l'assioma 2).
Sia $m=k$ per un qualche $kinNN$ e supponiamo che sia $(n+k)inNN$ vera, allora segue che anche $n+f(k)$$inNN$ cioè è vera , infatti $n+f(k)=f(n+k)$ per la condizione ii) e $f(n+k)inNN$ dato che $(n+k)inNN$ per l'assioma 2).
Essendo che la proposizione è vera per $m=1$ (base dell'induzione), ed che se supposta vera per qualche $m=kinNN$ allora è vera per $m=k+1$, possiamo concludere che è vera per tutti gli $m$$inNN$.
Le rimanenti proprietà si possono dimostrare similmente utilizzando le condizioni i),ii), e gli assiomi (prova!).
Spero che non abbia commesso errori nell'esposizione, in ogni caso apprezza lo sforzo!
@francicko: Gli assiomi sono corretti, ma credo che gaten intendesse che qualcuno gli spiegasse la nota formula:
\[
\sum_{n=1}^N n = \frac{N(N+1)}{2}
\]
usando il Principio d'Induzione.
Inoltre, noto che il tuo assioma 5 è il Principcio d'Induzione, e non il Principio del Buon Ordinamento come da te affermato. Va bene che i due principi sono equivalenti, ma gli enunciati sono diversi e qui cerchiamo di non confondere le idee agli utenti meno esperti.
@gaten: Di questo argomento si è parlato millemila volte all'interno del forum.
Ti invito caldamente ad usare la funzione CERCA ed a non far perdere tempo agli altri utenti la prossima volta.
[xdom="gugo"]Chiudo.[/xdom]
\[
\sum_{n=1}^N n = \frac{N(N+1)}{2}
\]
usando il Principio d'Induzione.
Inoltre, noto che il tuo assioma 5 è il Principcio d'Induzione, e non il Principio del Buon Ordinamento come da te affermato. Va bene che i due principi sono equivalenti, ma gli enunciati sono diversi e qui cerchiamo di non confondere le idee agli utenti meno esperti.
@gaten: Di questo argomento si è parlato millemila volte all'interno del forum.
Ti invito caldamente ad usare la funzione CERCA ed a non far perdere tempo agli altri utenti la prossima volta.
[xdom="gugo"]Chiudo.[/xdom]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo