Next: Lezione 4 (7 marzo
Up: Matematica Discreta (II modulo)
Previous: Lezione 2 (28 febbraio
Subsections
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$](img110.gif)
si definisce ;la funzione
![$m\mapsto n+m$](img171.gif)
ricorsivamente nel
seguente modo:
ed analogamente si definisce il prodotto
![$m\mapsto nm$](img173.gif)
:
Osservazione 3.2
Se si chiamo 1=
succ(0), allora per ogni
![$n\in\mathbb N$](img110.gif)
si ha che
![$\mathop{\rm succ}\nolimits(n)=n+1$](img175.gif)
,
infatti dalla definizione di + si ha che
D'ora in poi non scriveremo più
![$\mathop{\rm succ}\nolimits(n)$](img177.gif)
ma
n+1.
Esercizio 3.1
Si provi che per ogni
![$n\in\mathbb N$](img110.gif)
si ha 0+
n=
n e 1+
n=
n+1 ossia
![$1+n=\mathop{\rm succ}\nolimits(n)$](img178.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$](img182.gif)
come un sottinsieme di
![$\mathbb N\times \mathbb N$](img183.gif)
e precisamente
![$\le = \{(n,m)\in \mathbb N\times \mathbb N\mid \exists k\in\mathbb N:n+k = m\}$](img184.gif)
.
E quindi
![$\le$](img182.gif)
è una
relazione sui
naturali e quello che abbiamo definito come significato di
![$n\le m$](img180.gif)
è
effettivamente lo stesso che dire
![$(n,m)\in\le$](img185.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 un insieme e
![$\cal R$](img47.gif)
una relazione binaria su
X,
![$\cal R$](img47.gif)
si dice
un
ordinamento parziale o anche una
relazione d'ordine parziale
se valgono le seguenti proprietà:
- 1.
- proprietà riflessiva:
.
- 2.
- proprietà antisimmetrica:
- 3.
- proprietà transitiva:
![$(x{\cal R}y \hbox{\rm { e }} y{\cal R}z )\Rightarrow x{\cal R}z$](img198.gif)
Un ordinamento parziale si dice un
ordinamento totale se in più vale
la
- 1.
- tricotomia:
.
Una coppia
![$(X,{\cal R})$](img200.gif)
in cui
![$\cal R$](img47.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$](img182.gif)
o
![$\preceq$](img201.gif)
,
in tal caso quando si scriverà
![$x \succeq y$](img202.gif)
si intenderà
![$y
\preceq x$](img203.gif)
,
e quando si scriverà
![$x \prec y $](img204.gif)
si intenderà il cosiddetto
ordinamento stretto ovvero
![$x\preceq y$](img205.gif)
e
![$x\ne y$](img206.gif)
.
In termini
dell'ordinamento stretto la proprietà di tricotomia per l'ordinamento
![$\preceq$](img201.gif)
si può rioenunciare dicendo:
-
vale una e una sola delle tre seguenti:
,
x=y,
.
Osservazione 3.8
In termini di questo nuovo linguaggio
![$(\mathbb N,\le)$](img209.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 In l'insieme
.
Definizione 3.10
Diremo che un insieme è
finito se esiste
![$n\in\mathbb N$](img110.gif)
tale che
![$\left\vert X\right\vert=\left\vert I_ n\right\vert$](img216.gif)
.
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$](img216.gif)
e
![$\left\vert Y\right\vert=\left\vert I_m\right\vert$](img217.gif)
con
n<
m allora ogni applicazione
![$f:Y \to X$](img218.gif)
non è
iniettiva.
Dimostrazione.
Procediamo per induzione su n. Se n=0 allora
e
,
quindi l'insieme XY delle applicazioni
è 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
e sia,
con m>n+1 e supponiamo per
assurdo che l'applicazione
sia iniettiva. Per definizione esiste una
bigezione
;
poniamo xn=g(n) e
.
Chiaramente
X' è in bigezione con In. Si hanno due casi:
- 1.
-
(i.e.
)
- 2.
-
(i.e.
)
Nel primo caso,
e quindi
sarebbe un'applicazione
iniettiva da un insieme equipotente a Im in un insieme equipotente a In;
dato che m>n+1>n questo è assurdo per ipotesi di induzione.
Nel secondo caso, sia
tale che f(y)=xn e sia
.
Dato che
f è iniettiva,
e quindi,
è una applicazione iniettiva. Dato che
,
e m-1>n, 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 (7 marzo
Up: Matematica Discreta (II modulo)
Previous: Lezione 2 (28 febbraio
Domenico Luminati
2001-06-18