Lezione 7

Operazioni tra cardinalità

Sebbene non abbiamo dato la definizione di cardinalità di un insieme, (abbiamo dato significato al simbolo $\left\vert X\right\vert$ solo nel caso finito), con una serie di esercizi, vediamo come si possano ugualmente definire delle operazioni tra cardinalità.

Esercizio 7.1   Supponiamo che $\left\vert X\right\vert = \left\vert X'\right\vert$ e che $\left\vert Y\right\vert =\left\vert Y'\right\vert$ allora

1. $\left\vert X \times Y\right\vert=\left\vert X'\times Y'\right\vert$
2. $\left\vert X^Y \right\vert=\left\vert{X'}^{Y'}\right\vert$
3. $\left\vert(X\times\{0\})\cup(Y\times\{1\})\right\vert = \left\vert(X'\times\{0\})\cup(Y'\times\{1\})\right\vert$

Soluzione

L'esercizio precedente permette di dare la seguente

Definizione 7.1   Se $X$ e $Y$ sono insiemi, si definiscono

1. $\left\vert X\right\vert + \left\vert Y\right\vert = \left\vert(X\times\{0\})\cup(Y\times\{1\})\right\vert$
2. $\left\vert X\right\vert \left\vert Y\right\vert = \left\vert X\times Y\right\vert$
3. $\left\vert X\right\vert^{\left\vert Y\right\vert}= \left\vert X^Y\right\vert$

Esercizio 7.2   Si provi che le operazioni appena definite, nel caso di insiemi finiti, coincidono con le usuali operazioni tra numeri naturali.
Soluzione

Esercizio 7.3   Si provi che $2^{\left\vert X\right\vert}=\left\vert 2^X\right\vert$.
Soluzione

Lasciamo come esercizio la dimostrazione del fatto che queste operazioni verificano tutte le propruietà delle usuali operazioni tra numeri naturali.

Esercizio 7.4   Si provino le seguenti:

1. $\left\vert X\right\vert + \left\vert Y\right\vert = \left\vert Y\right\vert + \left\vert X\right\vert$
2. $\left\vert X\right\vert \left\vert Y\right\vert = \left\vert Y\right\vert \left\vert X\right\vert$
3. $(\left\vert X\right\vert + \left\vert Y\right\vert)+\left\vert Z\right\vert =\left\vert X\right\vert + (\left\vert Y\right\vert+\left\vert Z\right\vert)$
4. $(\left\vert X\right\vert \left\vert Y\right\vert)\left\vert Z\right\vert =\left\vert X\right\vert (\left\vert Y\right\vert \left\vert Z\right\vert)$
5. $\left\vert X\right\vert (\left\vert Y\right\vert + \left\vert Z\right\vert)= (... ...\vert\left\vert Y\right\vert)+(\left\vert X\right\vert \left\vert Z\right\vert)$
6. $\left\vert X\right\vert ^{\left\vert Y\right\vert +\left\vert Z\right\vert} = ... ...rt ^{\left\vert Y\right\vert} \left\vert X\right\vert^{\left\vert Z\right\vert}$
7. $\big(\left\vert X\right\vert ^{\left\vert Y\right\vert}\big)^{\left\vert Z\rig... ...t} = \left\vert X\right\vert ^{\left\vert Y\right\vert \left\vert Z\right\vert}$

Soluzione

L'assioma di buon ordinamento

Definizione 7.2   Sia $X$ un insieme e sia $\le$ un ordinamento su $X$. Sia $A\subseteq X$, diremo che $z\in A$ è un minimo di $A$ (in simboli $z=\min A$ se per ogni $x\in A$ si ha che $z\le x$.

Definizione 7.3   Un ordinamento totale su un insieme $X$ si dice un buon ordinamento, e in tal caso l'insieme ordinato $(X,\le)$ si dice ben ordinato se ogni sottinsieme non vuoto di $X$ ha minimo.

Teorema 7.4 (buon ordinamento)   L'ordinamento dei numeri naturali è un buon ordinamento.

Dimostrazione.  Supponiamo che l'insieme $A\subseteq \mathbb{N}$ non abbia minimo e proviamo che allora $A=\varnothing$. Chiamiamo $B$ il suo complementare ( $B=\mathbb{N}-A$) e dimostriamo per induzione che

$$\forall n\in\mathbb{N}\quad \{0,1,\dots,n\}\subseteq B$$

$0 \notin A$, altrimenti ne sarebbe il minimo, quindi $0\in B$ e pertanto $\{0\}\subseteq B$.

Supponiamo che $\{0,1,\dots,n\}\subseteq B$, allora $0,1,\dots,n\notin A$ e quindi $n+1 \notin A$, altrimenti ne sarebbe il minimo, ma allora $n+1 \in B$ e pertanto $\{0,1,\dots,n,n+1\}\subseteq B$.

Ma allora $B=\mathbb{N}$ e quindi $A=\varnothing$.     $\square$

Il principio di induzione (seconda forma)

Teorema 7.5 (seconda forma dell'induzione)   Sia $P(n)$ una famiglia di proposizioni indiciate su $\mathbb{N}$ e si supponga che

1. $P(0)$ sia vera
2. per ogni $n>0$ $(P(k)$    vera $\forall k<n)\Rightarrow P(n)$

allora $P(n)$ è vera per ogni $n\in \mathbb{N}$

Dimostrazione.  Sia $A = \{ n \in\mathbb{N}\mid P(n)$ non è vera$\}$, e supponiamo per assurdo che $A\ne\varnothing$. Allora per la proprietà di buon ordinamento $A$ ha minimo $n$. Chiaramente $n\ne 0$ in quanto $P(0)$ è vera. Inoltre se $k<n$ allora $k\notin A$ in quanto $n=\min A$, ma allora dalla (2) segue che $P(n)$ è vera e quindi $n\notin A$, contraddicendo il fatto che $n \in A$.     $\square$

Osservazione 7.6   Si osservi che sia l'enunciato che la dimostrazione precedenti non usano il fatto che si stia parlando di numeri naturali, ma soltanto che si sta lavorando in un insieme bene ordinato. Quindi il principio di induzione in questa forma è applicabile ad ogni insieme bene ordinato.

La divisione euclidea

Nel seguito denoteremo con $\mathbb{Z}$ l'insieme dei numeri interi. Supporremo nota la sua definizione e la definizione delle operazioni tra i suoi elementi. Ci limitiamo a dire che gli interi e le operazioni tra interi possono essere definiti a partire dai naturali e dalle operazioni tra naturali.

Teorema 7.7   Siano $n,m\in\mathbb{Z}$ con $m\ne 0$, allora esistono unici $q,r\in \mathbb{Z}$ tai che

$$\begin{array}{l} n = mq + r \\ 0 \le r < \left\vert m\right\vert \end{array}$$

Dimostrazione. Esistenza. Supponiamo dapprima che $n,m\in \mathbb{N}$, ed usiamo il principio di induzione nella seconda forma su $n$. Se $n=0$ basta prendere $q=0$ e $r=0$. Supponiamo $n>0$ e che la tesi sia vera per ogni $k<n$. Se $n < m$ basta prendere $q=0$ e $r=n$, altrimenti sia $k=n-m$, dato che $m\ne 0$ $0 \le k<n$, quindi per ipotesi di induzione esistono $q,r\in\mathbb{N}$ tali che

$$\begin{array}{l} k = mq + r \\ 0 \le r < m \end{array}$$

ma allora $n= k+m = m q + r + m = (q+1)m + r$.

Supponiamo ora $n<0$ e $m>0$. Allora $-n>0$ e quindi per il caso precedente si ha che esistono $q,r\in \mathbb{Z}$ tali che $-n=mq+r$ e $0\le r<m=\left\vert m\right\vert$. E quindi $n=m(-q)-r$. Se $r=0$ abbiamo finito, se invece $0<r<m$ allora $0<m-r<m=\left\vert m\right\vert$ e $n=m(-q)-r=m(-q)-m+m-r=m(-1-q)+(m-r)$.

Sia infine $m<0$ allora $-m>0$, quindi per i due casi precedenti esistono $q,r\in \mathbb{Z}$ tali che $n=(-m)q+=m(-q)+r$ con $0\le r<-m=\left\vert m\right\vert$.

Unicità. Supponiamo che $n= mq + r$ e $n=mq'+r'$ con $0\le r,r'<m$. Supponiamo che $r'\ge r$, allora $m(q-q')=r'-r$ e quindi passando ai moduli si ha $\left\vert m\right\vert\left\vert q-q'\right\vert=\left\vert r'-r\right\vert=r'-r<\left\vert m\right\vert$,da cui $0\le\left\vert q-q'\right\vert<1$ e quindi $\left\vert q-q'\right\vert=0$ ovvero $q=q'$. Ma allora da $mq+r=mq'+r'$ segue che anche $r=r'$.     $\square$

Osservazione 7.8   Si osservi che la dimostrazione del teorema di esistenza e unicità del quoziente e del resto della divisione euclidea di due numeri naturali, permette di scrivere un algoritmo ricorsivo per il loro calcolo:

$$\hbox{\vrule \vbox{\hrule\kern5pt\hbox{\kern5pt \begin{minipage}{... ... aggiungi $1$ al quoziente. \end{minipage}%% \kern5pt}\kern5pt\hrule }\vrule}$$

che può essere tradotto nella scrittura di un programma ricorsivo per la definizione di una funzione DIVE che calcoli il quoziente e resto della divisione euclidea tra due numeri:

$$\hbox{\vrule\vbox{\hrule\kern5pt\hbox{\kern5pt \begin{minipage}{.... ...n-m,m) END IF }\end{verbatim}\end{minipage}%% \kern5pt}\kern5pt\hrule }\vrule}$$

Esercizio 7.5   Supponendo di avere un linguaggio di programmazione con un'istruzione WHILE, tradurre la definizione della funzione DIVE in una funzione non ricorsiva (induttiva).
Soluzione