Lezione 1 (22 febbraio 1999 h. 9.30-10.30)

L'assioma di buon ordinamento dei numeri naturali

Assioma 1.1 (di buon ordinamento)   Se $S\subset\mathbb N$ è un sottoinsieme non vuoto allora S ha minimo, ossia esiste $m\in S$ tale che per ogni $s\in S$ si ha $m\le s$.

Principio di induzione: prima forma

Teorema 1.2 (prima forma dell'induzione)   Sia P(n) una successione di proposizioni indicizzate sui naturali. Si supponga che

1.

P(0) sia vera.

2.

$\forall n\in\mathbb N$ $P(n)\Rightarrow P(n+1)$

allora P(n) è vera per ogni n.

Dim.  Sia $S=\{n\in\mathbb N\mid P(n) \hbox{\rm { non \\lq e vera}}\}$, se per assurdo $S\ne\varnothing$, per l'assioma di buon ordinamento esiste m il minimo di S. m>0dato che P(0) è vera per l'ipotesi 1, mentre P(m) è falsa in quanto $m\in S$. Ma allora $m-1\in\mathbb N$ e, dato che m-1<m e m è il minimo di S, $m-1\notin S$ ossia P(m-1) è vera. Ma allora, per l'ipotesi 2 si ha che P(m-1+1)=P(m) è vera, ossia $m\notin S$, che è assurdo. Quindi $S=\varnothing$ ossia P(n) è vera per ogni $n\in\mathbb N$.     $\square$

Principio di induzione: seconda forma

Teorema 1.3 (seconda forma dell'induzione)   Sia P(n) una successione di proposizioni indicizzate sui naturali. Si supponga che

1.

P(0) sia vera.

2.

$\forall n>0$ se P(k) è vera per ogni k<n allora anche P(n) è vera

allora P(n) è vera per ogni n.

Dim.  Come nella dimostrazione precedente sia $S=\{n\in\mathbb N\mid P(n) \hbox{\rm { non \\lq e vera}}\}$, e come prima supponiamo per assurdo $S\ne\varnothing$, e sia m il minimo di S. m>0 dato che P(0)è vera per l'ipotesi 1, mentre P(m) non è vera in quanto $m\in S$. Inoltre, dato che m è il minimo di S, se k<m allora $k\notin S$ e quindi P(k) è vera. Ma allora, per l'ipotesi 2 si ha che P(m) è vera, ossia $m\notin S$, che è assurdo. Quindi $S=\varnothing$ ossia P(n) è vera per ogni $n\in\mathbb N$.     $\square$

Divisione euclidea tra naturali

Proposizione 1.4   Siano $n,m\in\mathbb N$, $m\ne0$ allora esistono $q,r\in\mathbb N$ tali che

$$n=mq+r\quad\hbox{\rm {con}}\quad 0\le r<m.$$

Dim.  Usiamo il principio di induzione nella seconda forma applicato alla successione di proposizioni

$$P(n):= \forall\,m>0\ \exists\,q,r\in\mathbb N\hbox{\rm { tali che }}n=mq+r \hbox{\rm { e }}0\le r<m$$

Se n=0 basta prendere q=r=0. Sia ora n>0 e supponiamo che P(k)sia vera per ogni k<n. Osserviamo che se m> n basta prendere q=0 e r=n. Se invece $m\le n$, consideriamo k=n-m. Dato che $0<m\le n$ si ha $0\le k<n$ e quindi, per ipotesi di induzione P(k)è vera. Ossia esistono $q,r\in\mathbb N$ tali che $0\le r<m$ e k=mq+r. Ma allora n=k+m=mq+m+r=m(q+1)+r.     $\square$