Numeri naturali e principio di induzione

[jarod1981®]

Il primo insieme non banale che potrebbe essere costruito direttamente a partire dalla teoria assiomatica degli insiemi è l'insieme dei numeri naturali, ovvero dei numeri 0, 1, 2, 3, ... In questa sede si darà un'impostazione assiomatica alla definizione dell'insieme ℕ, seguendo l'idea del matematico italiano G. Peano. Peano introdusse cinque assiomi, che oggi portano il suo nome, e che costituiscono una definizione assiomatica rigorosa di insieme dei numeri naturali.

Gli assiomi di Peano

I numeri naturali si susseguono in ordine uno dopo l'altro a partire dal numero zero, denotato con 0; come primo assioma va quindi chiesto che 0 sia un numero naturale:
Assioma 1: 0∈ℕ.

Va a questo punto detto che dal numero 0 si passa ai numeri successivi:

Assioma 2: Per ogni numero naturale n esiste un unico numero naturale s(n) detto successivo di n.

Vanno poi chiarite le proprietà fondamentali che questa operazione di successivo possiede; anzitutto il numero 0 è il primo della lista, per cui non è successivo di nessun numero:

Assioma 3: Per ogni n∈ℕ si ha s(n)≠0.

Inoltre, ogni numero naturale che non sia 0 proviene da un solo numero naturale mediante l'operazione di successivo; per cui va chiesto che:

Assioma 4: Se n,m∈ℕ con s(n)=s(m), allora si ha n=m.

Infine vi è l'ultimo assioma che chiude la definizione; non è infatti chiaro, sulla base degli assiomi precedente, se questa operazione di successivo iterata fornisca o no tutti i numeri naturali o se ne rimanga qualcuno escluso. Il quinto ed ultimo assioma dà una risposta a questa domanda e afferma proprio che iterando, a partire dallo 0, l'operazione di successivo, si ottengono tutti i numeri naturali:

Assioma 5: Supponiamo che A⊆ℕe che si abbia 0∈A e n∈A⇒s(n)∈A; allora risulta A=ℕ.

I cinque assiomi di Peano costituiscono una possibile definizione rigorosa dei numeri naturali, che quindi rimangono oggetti non definiti; sono però definite le loro proprietà, e questo, il più delle volte, basta per la matematica.

Il principio di induzione
Il Teorema più importante della teoria di base dell'insieme dei numeri naturali è anche noto con il nome di principio di induzione, che è una conseguenza immediata del quinto assioma di Peano. Il Principio di induzione fornisce uno strumento molto utile che permette di dimostrare che una certa proprietà P(n)che dipende dai numeri naturali è vera. L'idea su cui si basa il principio è la seguente: dimostrare che è vera P(0) e che è vera l'implicazione P(n)⇒P(s(n)); in altre parole va controllata la verità della proprietà P per il numero 0, ed in un secondo momento va dimostrata l'implicazione P(n)⇒P(s(n)), ovvero va dimostrato che supponendo P(n) vera si ottiene che anche P(s(n)) è vera. In tal modo si ha la seguente catena: P(0) vera, allora P(1) vera, allora P(2) vera, allora P(3) vera, ecc. e, in linea di principio, continuando all'infinito si ha la verità di P per ogni numero naturale.

Teorema (Principio di induzione): Sia P(n) una proprietà dipendente da n∈ℕ. Si supponga che P(0) sia vera e che P(n)⇒P(s(n)) per ogni n naturale; allora si ha che P(n) è vera per ogni n∈ℕ.

Dimostrazione. Sia A={n∈ℕ:P(n)}. Allora A⊆ℕ e 0∈A, per ipotesi; inoltre si ha, sempre per ipotesi, n∈A⇒s(n)∈A. Per il quinto assioma di Peano si ha A=ℕ, per cui la proprietà P è vera per ogni n naturale.

Operazioni tra numeri naturali
Attraverso la nozione di successivo è possibile introdurre le prime operazioni definite sull'insieme ℕ, che sono somma e prodotto, ben definite per ricorsione nel seguente modo: n+0=n, n+s(m)=s(n+m) e n·1=n, n·(m+1)=n·m+n, dove 1=s(0). Le operazioni tra numeri naturali godono di varie proprietà, probabilmente già note al lettore:

n+m=m+n, n·m=m·n (proprietà commutativa)
n+(m+p)=(n+m)+p, n·(m·p)=(n·m)·p (proprietà associativa)
n·(m+p)=n·m+n·p, (proprietà distributiva).

Esempio 1: Dimostrare per induzione la proprietà commutativa della somma.
Dim. E' da dimostrare che per ogni n,m naturali si ha n+m=m+n. La dimostrazione procederà per induzione su m. Per prima cosa va dimostrato quindi che per ogni n naturale si ha n+0=0+n. A sua volta questa proprietà va dimostrata per induzione su n; per n=0 si ha 0+0=0+0 che è vera, inoltre per definizione di somma si ha anche 1+0=0+1, quindi supponendo n+0=0+n si ha

(n+1)+0=n+(1+0)=n+(0+1)=(n+0)+1=(0+n)+1=0+(n+1).

che conclude la verifica. Con ciò è stato dimostrato che per ogni n naturale vale n+0=0+n, che è la proprietà commutativa per m=0. Come ultimo passo va quindi supposto ora che n+m=m+n per ogni n,m naturali, e va dimostrato che
n+(m+1)=(m+1)+n.
Si ha n+(m+1)=(n+m)+1=(m+n)+1=m(n+1)=m+(1+n)=(m+1)+n che conclude l'intera dimostrazione.

Esempio 2: Dimostrare per induzione su N che

∑n=0Nn=N(N+1)2.

Dim. Procedendo come al solito si ha

∑n=00n=0=0(0+1)2

per cui la formula data è vera per N=0; supponendo che

∑n=0Nn=N(N+1)2
si ha
∑n=0N+1n=∑n=0Nn+(N+1)=N(N+1)2+(N+1)=(N+1)(N+2 )2

che conclude la dimostrazione.

Ordinamento
Accanto alle operazioni principali definite su ℕ vi è un'altra importante proprietà strutturale dell'insieme dei numeri naturali: l' ordinamento totale.
I numeri naturali sono ordinati tra loro, si ha, per definizione di ordine totale,

0≤1≤2≤3≤4≤....

In altre parole per ogni n naturale si ha n≤s(n). Tale ordinamento è compatibile con le operazioni di somma e prodotto, nel senso che si ha
n≤m⇒n+p≤m+p, n≤m⇒n·p≤m·p .




[Solo gli utenti registrati possono visualizzare tutti i links]