Next: Lezione 4
Up: Matematica Discreta (II modulo)
Previous: Lezione 2
Subsections
Le operazioni sui naturali
Il teorema di ricorsione permette di definire la somma e il prodotto di numeri
naturali.
Definizione 3.1
Dato
![$ n\in \mathbb{N}$](img214.gif)
si definisce ;la funzione
![$ m\mapsto n+m$](img286.gif)
ricorsivamente nel
seguente modo:
ed analogamente si definisce il prodotto
![$ m\mapsto nm$](img288.gif)
:
Osservazione 3.2
Se si chiamo
![$ 1=succ(0)$](img290.gif)
, allora per ogni
![$ n\in \mathbb{N}$](img214.gif)
si ha che
![$ \mathop{\rm succ}\nolimits (n)=n+1$](img291.gif)
,
infatti dalla definizione di
![$ +$](img292.gif)
si ha che
D'ora in poi non scriveremo più
![$ \mathop{\rm succ}\nolimits (n)$](img294.gif)
ma
![$ n+1$](img295.gif)
.
Esercizio 3.1
Si provi che per ogni
![$ n\in \mathbb{N}$](img214.gif)
si ha
![$ 0+n=n$](img296.gif)
e
![$ 1+n=n+1$](img297.gif)
ossia
![$ 1+n=\mathop{\rm succ}\nolimits (n)$](img298.gif)
.
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.
Osservazione 3.4
Si può vedere
![$ \le$](img303.gif)
come un sottinsieme di
![$ \mathbb{N}\times \mathbb{N}$](img304.gif)
e precisamente
![$ \le = \{(n,m)\in \mathbb{N}\times \mathbb{N}\mid \exists k\in\mathbb{N}:n+k = m\}$](img305.gif)
. E quindi
![$ \le$](img303.gif)
è una
relazione sui
naturali e quello che abbiamo definito come significato di
![$ n\le m$](img300.gif)
è
effettivamente lo stesso che dire
![$ (n,m)\in\le$](img306.gif)
.
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.
Insiemi ordinati
Definizione 3.6
Sia
![$ X$](img28.gif)
un insieme e
![$ \cal R$](img93.gif)
una relazione binaria su
![$ X$](img28.gif)
,
![$ \cal R$](img93.gif)
si dice
un
ordinamento parziale o anche una
relazione d'ordine parziale
se valgono le seguenti proprietà:
- proprietà riflessiva:
.
- proprietà antisimmetrica:
e
- proprietà transitiva:
e
Un ordinamento parziale si dice un
ordinamento totale se in più vale
la
- tricotomia:
o
.
Una coppia
![$ (X,{\cal R})$](img323.gif)
in cui
![$ {\cal R}$](img324.gif)
è 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$](img303.gif)
o
![$ \preceq$](img325.gif)
, in tal caso quando si scriverà
![$ x \succeq y$](img326.gif)
si intenderà
![$ y
\preceq x$](img327.gif)
, e quando si scriverà
![$ x \prec y $](img328.gif)
si intenderà il cosiddetto
ordinamento stretto ovvero
![$ x\preceq y$](img329.gif)
e
![$ x\ne y$](img330.gif)
. In termini
dell'ordinamento stretto la proprietà di tricotomia per l'ordinamento
![$ \preceq$](img325.gif)
si può rioenunciare dicendo:
-
vale una e una sola delle tre seguenti:
,
,
.
Osservazione 3.8
In termini di questo nuovo linguaggio
![$ (\mathbb{N},\le)$](img334.gif)
risulta quindi essere un
insieme totalmente ordinato.
Si possono dimostrare anche le ulteriori proprietche legano l'ordinamento con
le operazioni:
Dimostrazione.
Esercizio per lo studente volenteroso.
Insiemi finiti: il Lemma dei cassetti
Dato un numero naturale
denotiamo con
l'insieme
.
Definizione 3.10
Diremo che un insieme è
finito se esiste
![$ n\in \mathbb{N}$](img214.gif)
tale che
![$ X$](img28.gif)
è
equipotente a
![$ I_ n$](img341.gif)
, in simboli
![$ X \sim I_ n$](img343.gif)
. Un
insieme è detto
infinito se non è finito
Teorema 3.11 (Lemma dei cassetti)
Siano
![$ X$](img28.gif)
e
![$ Y$](img29.gif)
due insiemi aventi rispettivamente
![$ X \sim I_ n$](img343.gif)
e
![$ Y \sim I_m$](img344.gif)
con
![$ n < m$](img345.gif)
allora ogni applicazione
![$ f:Y \to X$](img346.gif)
non è iniettiva.
Dimostrazione.
Procediamo per induzione su
. Se
allora
e
,
quindi l'insieme
delle applicazioni
è vuoto, e quindi non c'è
nulla da dimostrare (dal falso segue ogni cosa).
Supponiamo che la tesi sia vera per
e proviamola per
. Sia
e sia,
con
e supponiamo per assurdo che
l'applicazione
sia iniettiva. Per definizione esiste una bigezione
; poniamo
e
. Chiaramente
è
in bigezione con
. Si hanno due casi:
-
(i.e.
)
-
(i.e.
)
Nel primo caso,
e quindi
sarebbe un'applicazione
iniettiva da un insieme equipotente a
in un insieme equipotente a
;
dato che
questo è assurdo per ipotesi di induzione.
Nel secondo caso, sia
tale che
e sia
. Dato che
è iniettiva,
e quindi,
è una applicazione iniettiva. Dato che
,
e
, ciò è assurdo per ipotesi di induzione.
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.
Next: Lezione 4
Up: Matematica Discreta (II modulo)
Previous: Lezione 2
Domenico Luminati
2004-03-18