I numeri naturali ed il teorema di ricorsione

Domenico Luminati

   
I numeri naturali: gli assiomi di Peano

Ricordiamo gli assiomi (dovuti a Peano) che descrivono la struttura dei numeri naturali.

Assioma 1.1   $0\in \mathbb N$

Assioma 1.2   $\mathop{\rm succ}\nolimits:\mathbb N\to \mathbb N$ è una funzione iniettiva

Assioma 1.3   $\forall n \in\mathbb N\quad \mathop{\rm succ}\nolimits(n) \ne 0$

Assioma 1.4 (di induzione)   se $A\subseteq \mathbb N$ è un sottinsieme tale che

1.

$0\in A$

2.

$\forall n \in \mathbb N\quad (n\in A \Rightarrow\mathop{\rm succ}\nolimits(n) \in A)$

allora $A=\mathbb N$.

Proposizione 1.5   Sia $n\in \mathbb N$, $n\ne 0$ allora esiste un unico $m\in \mathbb N$ tale che $\mathop{\rm succ}\nolimits(m) = n$. Tale m viene chiamato il predecessore di m.

Dimostrazione. Avendo l'esistenza, l'unicità segue immediatamente dall'iniettività di $\mathop{\rm succ}\nolimits$.

Supponiamo per assurdo che esista un $m\ne 0$ tale che $\mathop{\rm succ}\nolimits(n) \ne m$ per ogni n, allora sia $A = \mathbb N-\{m\}$. Chiaramente $0\in A$, in quanto $m\ne 0$. Se $n \in A$, allora $succ (n) \ne m$ e quindi $succ (n) \in A$. Ma allora $A=\mathbb N$, e questa è una contraddizione.     $\square$

L'assioma di induzione fornisce una potente tecnica di dimostrazione di proposizioni indicizzate sui naturali.

   
Il principio di induzione (prima forma)

Teorema 2.1 (prima forma dell'induzione)   Sia P(n) una famiglia di proposizioni indicizzate su $\mathbb N$ e si supponga che

1.

P(0) sia vera

2.

per ogni $n\in \mathbb N$ $P(n)\Rightarrow P(succ(n))$

allora P(n) è vera per ogni $n\in \mathbb N$

Dimostrazione. Sia $A=\{n\mid P(n)\hbox{\rm { \\lq e vera}}\}$, allora $0\in A$ e se $n \in A$ allora vale P(n), quindi vale $P(\mathop{\rm succ}\nolimits(n))$ ossia anche $succ (n) \in A$, quindi per l'assioma di induzione $A=\mathbb N$.     $\square$

   
Il teorema di ricorsione

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

Teorema 3.1 (di ricorsione)   Sia X un insieme, $h:\mathbb N\times X\to X$ una funzione e $c\in X$. Esiste una unica funzione $f:\mathbb N\to X$ tale che:

  

f(0) = c (1)

$$f(\mathop{\rm succ}\nolimits(n)) h(n,f(n)) \quad \forall n \in \mathbb N$$ = (2)

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 $n\in \mathbb N$. 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 $f(\mathop{\rm succ}\nolimits(n))=h(n,f(n))$, ma anche g verifica la (2) quindi $g(\mathop{\rm succ}\nolimits(n))=h(n,g(n))$. Dato che, per ipotesi di induzione, f(n)=g(n), allora

$$f(\mathop{\rm succ}\nolimits(n))=h(n,f(n))=h(n,g(n)=g(\mathop{\rm succ}\nolimits(n)).$$

Proviamo ora l'esistenza. Per definizione di funzione, quello che si cerca è un insieme $f\subseteq \mathbb N\times X$ tale che:

$$\forall n\in\mathbb N\quad \exists \hbox{\rm { unico }} x \in X : (n,x) \in f$$ (3)

e, traducendo in termini di appartenenza le richieste (1) e (2)

  

$$(0,c)\in f$$ (4)

$$\forall n\in\mathbb N\quad(x,n)\in f \Rightarrow(\mathop{\rm succ}\nolimits(n), h(n,x)) \in f$$ (5)

Sia $\Omega= \{Z\subseteq \mathbb N\times X\mid Z \hbox{\rm { verifica (\ref{eq:ricop}) e (\ref{eq:ricnp})}}\}$, quello che dobbiamo trovare è un elemento di $\Omega$che sia una funzione.

Sia $f=\bigcap_{Z\in\Omega}Z$. Dato che f è l'intersezione di tutti gli elementi di $\Omega$, necessariamente

$$\forall Z\in \Omega\quad f\subseteq Z$$ (6)

Proviamo ora che $f\in\Omega$. f verifica la proprietà (4). Infatti $(0,c)\in Z$per ogni $Z\in \Omega$, quindi $(0,c)\in \bigcap_{Z\in\Omega}Z = f$.

f verifica la proprietà (5). Se $(n,x)\in f$ allora $(n,x)\in Z$ per ogni $Z\in \Omega$, ma allora dato che ogni $Z\in \Omega$ verifica la (5), $(\mathop{\rm succ}\nolimits(n),h(x,n))\in Z$ per ogni $Z\in \Omega$ e quindi $(\mathop{\rm succ}\nolimits(n),h(x,n))\in \bigcap_{Z\in\Omega}Z = f$.

Per concludere resta da provare che f verifica la (3). Procediamo per induzione su n. Sia n=0. Abbiamo già visto che $(0,c)\in f$. Supponiamo per assurdo che esista $(0,d)\in f$ con $d\ne c$, e sia $f'=f-\{(0,d)\}$. Chiaramente $(0,c)\in f'$ e se $(n,x)\in f'\subseteq f$ allora $(\mathop{\rm succ}\nolimits(n),h(n,x))\in f$, ma allora, per il terzo assioma di Peano, $\mathop{\rm succ}\nolimits(n)\ne 0$ per ogni $n\in \mathbb N$ e quindi $(\mathop{\rm succ}\nolimits(n),h(n,x))\ne(0,d)$, pertanto $(\mathop{\rm succ}\nolimits(n),h(n,x))\in f'$. Quindi $f'\in\Omega$, ma ciò contraddice la (6) perché $f\not\subseteq f'$.

Supponiamo la tesi vera per n. Sia x l'unico elemento tale che $(n,x)\in f$, dato che f verifica la (5), allora $(\mathop{\rm succ}\nolimits(n),h(n,x))\in f$. Supponiamo per assurdo che anche $(\mathop{\rm succ}\nolimits(n),e)\in f$ con $e\ne h(n,x)$ e si ponga $f'=f-\{(\mathop{\rm succ}\nolimits(n),e)\}$. Proviamo che anche in questo caso $f'\in\Omega$e si avrà, come prima, un assurdo. Dal terzo assioma di Peano segue che $(0,c)\ne(\mathop{\rm succ}\nolimits(n),e)$ e quindi, dato che $(0,c)\in f$ allora $(0,c)\in f'$. Se $(i,z)\in f'\subseteq f$ allora $(\mathop{\rm succ}\nolimits(i),h(i,z))\in f$. Si hanno due casi: $i\ne n$ oppure i=n. Se $i\ne n$ allora, per l'iniettività di $\mathop{\rm succ}\nolimits$ si ha che $(\mathop{\rm succ}\nolimits(i),h(i,z))\ne (\mathop{\rm succ}\nolimits(n),e)$ e quindi $(\mathop{\rm succ}\nolimits(i),h(i,z))\in f'$. Se invece i=n allora $(i,z)=(n,z)\in f$e quindi, per ipotesi di induzione, l'unicità di x implica che z=x. Dato che $h(n,x)\ne e$,

$$(\mathop{\rm succ}\nolimits(i),h(i,z))=(\mathop{\rm succ}\nolimits(n),h(n,x))\in f'.$$

Questo conclude la dimostrazione.     $\square$

   
Le operazioni sui naturali

Il teorema di ricorsione permette di definire la somma il prodotto di numeri naturali.

Definizione 4.1   Dato $n\in \mathbb N$ si definisce ;la funzione $m\mapsto n+m$ ricorsivamente nel seguente modo:

$$\begin{array}{rcl} n + 0 & = & n \\ n + \mathop{\rm succ}\nolimits{m} & = & \mathop{\rm succ}\nolimits{n+m} \end{array}$$

ed analogamente si definisce il prodotto $m\mapsto nm$:

$$\begin{array}{rcl} n 0 & = & 0 \\ n (m+1) & = & nm + n \end{array}$$

Osservazione 4.2   Se si chiamo 1=succ(0), allora per ogni $n\in \mathbb N$ si ha che $\mathop{\rm succ}\nolimits(n)=n+1$, infatti dalla definizione di + si ha che

$$n+1 = n+\mathop{\rm succ}\nolimits(0)= \mathop{\rm succ}\nolimits(n+0) = \mathop{\rm succ}\nolimits(n)$$

D'ora in poi non scriveremo più $\mathop{\rm succ}\nolimits(n)$ ma n+1.

Esercizio 4.1    Si provi che per ogni $n\in \mathbb N$ si ha 0+n=n e 1+n=n+1 ossia $1+n=\mathop{\rm succ}\nolimits(n)$.
Soluzione

Esercizio 4.2    Si provi che per ogni $n\in \mathbb N$ si ha $0\cdot n=0$ e $1\cdot n=n\cdot 1= n$..
Soluzione

Esercizio 4.3    Si provino le usuali proprietà (i.e. associativa, commutativa, distributiva) della somma e del prodotto di numeri naturali.
Soluzione

   
L'ordinamento dei naturali

Con la somma si può definire la nozione di ordinamento dei numeri naturali.

Definizione 5.1   Siano $n,m\in \mathbb N$ diremo che $n\le m$ se esiste $k\in\mathbb N$ tale che m=n+k.

Osservazione 5.2   Si può vedere $\le$ come un sottinsieme di $\mathbb N\times \mathbb N$ e precisamente $\le = \{(n,m)\in \mathbb N\times \mathbb N\mid \exists k\in\mathbb N:n+k = m\}$. E quindi $\le$ è una relazione sui naturali e quello che abbiamo definito come significato di $n\le m$ è effettivamente lo stesso che dire $(n,m)\in\le$.

Si può dimostrare la seguente

Proposizione 5.3   Valgono le seguenti proprietà:

1.

$\forall n\in \mathbb N\quad$ $n\le n$.

2.

$\forall n,m\in \mathbb N\quad$ $(n\le m \hbox{\rm { e }} m\le n \Rightarrow n=m$

3.

$\forall n,m,k\in \mathbb N\quad$ $(n\le m \hbox{\rm { e }} m\le k \Rightarrow n\le k$

4.

$\forall n,m\in \mathbb N\quad$ $n\le m \hbox{\rm { o }} m\le n$.

Dimostrazione. La dimostrazione è lasciata per esercizio agli studenti volonterosi. I punti che richiedono maggiore attenzione sono il secondo e il quarto.     $\square$

Soluzioni proposte

Soluzione dell'esercizio 4.1  Proviamo la prima. Procediamo per induzione su n. Se n=0 allora dalla definizione si ha che 0+0=0. Supponiamo che 0+n=n allora

$$0+\mathop{\rm succ}\nolimits(n) = \mathop{\rm succ}\nolimits(0 +n ) = \mathop{\rm succ}\nolimits(n).$$

Proviamo la seconda. Per induzione su n. Per definizione $1+0=1=\mathop{\rm succ}\nolimits(0)$. Supponiamo che $1+n=\mathop{\rm succ}\nolimits(n)$, allora

$$1+\mathop{\rm succ}\nolimits(n) = \mathop{\rm succ}\nolimits(1+n) = \mathop{\rm succ}\nolimits( \mathop{\rm succ}\nolimits(n))$$

e quindi anche in questo caso, si ha la tesi.     

Soluzione dell'esercizio 4.2  Proviamo la prima. Procediamo per induzione su n. Se n=0 allora dalla definizione si ha che $0\cdot 0=0$. Supponiamo che $0\cdot n=0$ allora

$$0\cdot\mathop{\rm succ}\nolimits(n) = (0 \cdot n ) + 0 = 0 + 0 = 0.$$

Proviamo la seconda. Che $n\cdot 1 = n$ segue dal fatto che

$$n \cdot 1 = n \cdot 0 + n = 0 + n = n$$

L'altra uguaglianza la proviamo per induzione su n. Per definizione $1\cdot0$. Supponiamo che $1\cdot n = n$, allora

$$1\cdot \mathop{\rm succ}\nolimits(n) = 1 \cdot n + 1 = n + 1 = \mathop{\rm succ}\nolimits(n).$$

e quindi anche in questo caso, si ha la tesi.     

Soluzione dell'esercizio 4.3  Proviamo soltanto l'associatività della somma. Dobbiamo provare che per ogni $n,m,k\in\mathbb N$ 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 $\mathop{\rm succ}\nolimits(k)$.

$$\begin{eqnarray*}(m+n)+\mathop{\rm succ}\nolimits(k) & = & \mathop{\rm succ}\nol... ...thop{\rm succ}\nolimits(n+k)=m+(n+\mathop{\rm succ}\nolimits(k)) \end{eqnarray*}$$