Domenico Luminati
Ricordiamo gli assiomi (dovuti a Peano) che descrivono la struttura dei numeri naturali.
Dimostrazione. Avendo l'esistenza, l'unicità segue immediatamente dall'iniettività di
.
Supponiamo per assurdo che esista un
tale che
per
ogni n, allora sia
.
Chiaramente
,
in quanto
.
Se
,
allora
e quindi
.
Ma allora
,
e questa è una contraddizione.
L'assioma di induzione fornisce una potente tecnica di dimostrazione di proposizioni indicizzate sui naturali.
Dimostrazione. Sia
,
allora
e se
allora
vale P(n), quindi vale
ossia anche
,
quindi per l'assioma di induzione
.
Al momento i naturali sembrano essere una struttura molto povera, non vi è definita né la somma né il prodotto e nemmeno la relazione d'ordine (poter dire quando due numeri sono uno più grande dell'altro). Per poter dare queste definizioni è necessario dimostrare il seguente
Dimostrazione. Cominciamo con il provare l'unicità di una tale f. Supponiamo che f e gverifichino le due proprietà e proviamo che allora f(n)=g(n) per ogni
.
Usiamo l'induzione. Per n=0 la proposizione è vera, infatti dato
che sia f che g verificano 1, si ha che
f(0)=c=g(0).
Supponiamo che f(n)=g(n). f verifica la (2) e quindi
,
ma anche g verifica la (2) quindi
.
Dato che, per ipotesi di induzione, f(n)=g(n), allora
Proviamo ora l'esistenza. Per definizione di funzione, quello che si cerca è
un insieme
tale che:
Sia
,
quello che dobbiamo trovare è un elemento di
che sia una funzione.
Sia
.
Dato che f è l'intersezione di tutti gli
elementi di
,
necessariamente
f verifica la proprietà (5).
Se
allora
per ogni
,
ma allora dato che
ogni
verifica la (5),
per ogni
e quindi
.
Per concludere resta da provare che f verifica la (3). Procediamo
per induzione su n. Sia n=0. Abbiamo già visto che
.
Supponiamo per assurdo che esista
con
,
e sia
.
Chiaramente
e se
allora
,
ma allora, per il terzo assioma di
Peano,
per ogni
e quindi
,
pertanto
.
Quindi
,
ma ciò contraddice la (6) perché
.
Supponiamo la tesi vera per n. Sia x l'unico elemento tale che
,
dato che f verifica la (5), allora
.
Supponiamo per assurdo che anche
con
e si
ponga
.
Proviamo che anche in questo caso
e si avrà, come prima, un assurdo. Dal terzo assioma di Peano segue che
e quindi, dato che
allora
.
Se
allora
.
Si hanno due casi:
oppure i=n. Se
allora, per l'iniettività di
si ha che
e
quindi
.
Se invece i=n allora
e quindi, per ipotesi di induzione,
l'unicità di x implica che z=x. Dato che
,
Il teorema di ricorsione permette di definire la somma il prodotto di numeri naturali.
Si può dimostrare la seguente
Dimostrazione. La dimostrazione è lasciata per esercizio agli studenti volonterosi. I punti
che richiedono maggiore attenzione sono il secondo e il quarto.
Proviamo la seconda. Per induzione su n. Per definizione
.
Supponiamo che
,
allora
Soluzione dell'esercizio 4.2 Proviamo la prima. Procediamo per induzione su n. Se n=0 allora dalla
definizione si ha che
.
Supponiamo che
allora
Proviamo la seconda. Che
segue dal fatto che
Soluzione dell'esercizio 4.3 Proviamo soltanto l'associatività della somma. Dobbiamo provare che per ogni
si ha che
(n+m)+k=n+(m+k).
Procediamo per induzione su k. Se k=0 dalla definizione si ha
(n+m)+ 0
=n+m e anche
n+(m+0)=n+(m)=n+m. Supponiamo la tesi vera per k e proviamola
per
.