Lezione 3 (5 marzo 2001 h. 9.30-10.30)

   
Le operazioni sui naturali

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

Definizione 3.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 3.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 3.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 3.2    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 3.3   Siano $n,m\in\mathbb N$ diremo che $n\le m$ se esiste $k\in \mathbb N$ tale che m=n+k.

Osservazione 3.4   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 3.5   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$

   
Insiemi ordinati

Definizione 3.6   Sia X un insieme e $\cal R$ una relazione binaria su X, $\cal R$ si dice un ordinamento parziale o anche una relazione d'ordine parziale se valgono le seguenti proprietà:

1.

proprietà riflessiva: $\forall x\in X\quad$ $x{\cal R}x$.

2.

proprietà antisimmetrica: $\forall x,y\in X\quad$ $(x{\cal R}y \hbox{\rm { e }} y{\cal R}x )\Rightarrow x=y$

3.

proprietà transitiva: $\forall x,y,z\in X\quad$ $(x{\cal R}y \hbox{\rm { e }} y{\cal R}z )\Rightarrow x{\cal R}z$

Un ordinamento parziale si dice un ordinamento totale se in più vale la

1.

tricotomia: $\forall x,y\in X\quad$ $x{\cal R}y \hbox{\rm { o }} y{\cal R} x$.

Una coppia $(X,{\cal R})$ in cui $\cal R$ è un ordinamento (parziale o totale) si dice un insieme (parzialmente o totalmente) ordinato.

Osservazione 3.7   In genere le relazioni d'ordine si indicano con simboli del tipo $\le$ o $\preceq$, in tal caso quando si scriverà $x \succeq y$ si intenderà $y \preceq x$, e quando si scriverà $x \prec y$ si intenderà il cosiddetto ordinamento stretto ovvero $x\preceq y$ e $x\ne y$. In termini dell'ordinamento stretto la proprietà di tricotomia per l'ordinamento $\preceq$si può rioenunciare dicendo:

• $\forall x,y\in X\quad$ vale una e una sola delle tre seguenti: $X\prec y$, x=y, $y \prec x$.

Osservazione 3.8   In termini di questo nuovo linguaggio $(\mathbb N,\le)$ risulta quindi essere un insieme totalmente ordinato.

L'ordinamento dei naturali e le operazioni

Si possono dimostrare anche le ulteriori proprietche legano l'ordinamento con le operazioni:

Proposizione 3.9   Se n,m,k sono numeri naturali:

1.

$n\le m \Rightarrow n+k \le m+k$

2.

$n\le m \hbox{\rm { e }} k\ge 1 \Rightarrow nk \le mk$

Dimostrazione.  Esercizio per lo studente volenteroso.     $\square$

Esercizio 3.3    A partire dalle proprietà enunciate nella proposizione precedente si provi che se $n,m,k,h\in\mathbb N$ allora

1.

$n\le m \hbox{\rm { e }} k\le h \Rightarrow n+k \le m+h$

2.

$n\le m \hbox{\rm { e }} k\le h \Rightarrow nk \le mh$

Soluzione

   
Insiemi finiti: il Lemma dei cassetti

Dato un numero naturale $n\in\mathbb N$ denotiamo con In l'insieme $I_ n=\{0,1,\dots,n-1\}$.

Definizione 3.10   Diremo che un insieme è finito se esiste $n\in\mathbb N$ tale che $\left\vert X\right\vert=\left\vert I_ n\right\vert$. Un insieme è detto infinito se non è finito

Teorema 3.11 (Lemma dei cassetti)   Siano X e Y due insiemi aventi rispettivamente $\left\vert X\right\vert=\left\vert I_ n\right\vert$ e $\left\vert Y\right\vert=\left\vert I_m\right\vert$ con n<m allora ogni applicazione $f:Y \to X$ non è iniettiva.

Dimostrazione.  Procediamo per induzione su n. Se n=0 allora $X=\varnothing$ e $Y\ne\varnothing$, quindi l'insieme X^Y delle applicazioni $Y\to X$ è vuoto, e quindi non c'è nulla da dimostrare (dal falso segue ogni cosa).

Supponiamo che la tesi sia vera per n e proviamola per n+1. Sia $\left\vert X\right\vert=\left\vert I_{n+1}\right\vert$ e sia, $\left\vert Y\right\vert=\left\vert I_m\right\vert$ con m>n+1 e supponiamo per assurdo che l'applicazione $f:Y \to X$ sia iniettiva. Per definizione esiste una bigezione $g: I_ {n+1} \to X$; poniamo x_n=g(n) e $X'=X-\{x_n\}$. Chiaramente X' è in bigezione con In. Si hanno due casi:

1.

$f^{-1}(x_n)=\varnothing$ (i.e. $\forall y\in Y f(y)\ne x_n$)

2.

$f^{-1}(x_n)\ne\varnothing$ (i.e. $\exists y\in Y : f(y)=x_n$)

Nel primo caso, $f(Y)\subseteq X'$ e quindi $f:Y\to X'$ sarebbe un'applicazione iniettiva da un insieme equipotente a I_m in un insieme equipotente a I_n; dato che m>n+1>n questo è assurdo per ipotesi di induzione.

Nel secondo caso, sia $y\in Y$ tale che f(y)=x_n e sia $Y'=Y-\{y\}$. Dato che f è iniettiva, $f(Y')\subseteq X'$ e quindi, $\setbox \restrictbox=\hbox{$\hbox{$f$ }_{Y'}$ } \setbox 0\hbox{$f$ } {{f}\,\vru... ...th\dp\restrictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{Y'}}:Y'\to X'$è una applicazione iniettiva. Dato che $\left\vert Y'\right\vert = \left\vert I_{m-1}\right\vert$, $\left\vert X'\right\vert=\left\vert I_n\right\vert$ e m-1>n, ciò è assurdo per ipotesi di induzione.     $\square$

Osservazione 3.12   Il nome lemma dei cassetti deriva dal seguente modo naif di enunciare il teorema precedente: se ho un certo numero di oggetti da sistemare in dei cassetti, e il numero di oggetti è superiore a quello dei cassetti, almeno un cassetto conterrà più di un oggetto.