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... ...limits {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 $I_ n$ 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 $I_ n$. 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'}$}\setbox0\hbox{$f$} {{f} \vrule wid... ...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.