Lezione 2

Equipotenza di insiemi

Definizione 2.1   Siano $X$ e $Y$ due insiemi, diremo che $X$ e $Y$ sono equipotenti se esiste una bigezione $f:X\to Y$. Denoteremo questo fatto con $X\sim Y$, che leggeremo anche $X$ e $Y$ hanno la stessa cardinalità.

Proposizione 2.2   Valgono le seguenti proprietà:

1. $X$ è equipotente a se stesso.
2. se $X$ è equipotente a $Y$ allora $Y$ è equipotente a $X$
3. se $X$ è equipotente a $Y$ e $Y$ è equipotente a $Z$, allora $X$ è equipotente a $Z$.

Dimostrazione.  L'identità è una bigezione; se $f$ è una bigezione, allora $f^{-1}$ è una bigezione; composizione di bigezioni è una bigezione.     $\square$

Osservazione 2.3   Si osservi che non abbiamo dato alcun significato alla parola cardinalità, ossia non abbiamo definito cosa sia la cardinalità di un insieme. In effetti ciò può essere fatto (e sarà fatto eventualmente in corsi successivi), ossia si possono definire una classe di particolari insiemi detti cardinali che godono della seguente proprietà:

• ogni insieme $X$ è equipotente ad uno ed un solo cardinale, tale cardinale è usualmente denotato con $\left\vert X\right\vert$.
• due cardinali diversi non sono equipotenti tra loro.

Questa costruzione generale esula dalle finalità di questo corso, ci limiteremo a farla soltanto per una particolare classe di insiemi: gli insiemi finiti (cfr. 3.5 e 4.1

Supponendo di avere fatto tutto ciò, si può allora provare il seguente

Teorema 2.4   $X\sim Y$ se e solo se $\left\vert X\right\vert = \left\vert Y\right\vert$.

Dimostrazione.  Se $\kappa = \left\vert X\right\vert = \left\vert Y\right\vert$ allora esistono due bigezioni $f:X\to \kappa$ e $g :Y\to\kappa$ ma allora per la proposizione 2.2 si ha che $g^{-1}\circ f : X\to Y$ è una bigezione e quindi $X\sim Y$.

Viceversa sia $X\sim Y$ e sia $f:X\to Y$ una bigezione. Siano $\kappa=\left\vert X\right\vert$ e $\lambda =\left\vert Y\right\vert$, e siano $g:X\to\kappa$ e $h:Y\to\lambda$ delle bigezioni, allora $h^{-1}\circ f \circ g^{-1}:\kappa \to \lambda$ è una bigezione e quindi $\kappa =\lambda$.     $\square$

Esercizio 2.1   Siano $X,Y,X',Y'$ insiemi e siano $f:X\to X'$ e $g:Y\to Y'$ due applicazioni. Si definisca $f\times g:X\times Y\to X'\times Y'$ ponendo

$$f\times g(x,y)=(f(x),g(y)).$$

Si provi che se $X$ e $Y$ sono non vuoti allora

1. $f\times g$ è surgettiva se e solo se $f$ e $g$ sono entrambe surgettive.
2. $f\times g$ è iniettiva se e solo se $f$ e $g$ sono entrambe iniettive.

Cosa resta vero se uno tra $X$ e $Y$ è vuoto?
Soluzione

Esercizio 2.2   Si provi che $\left\vert 2^X\right\vert=\left\vert\{0,1\}^X\right\vert$.
Soluzione

Esercizio 2.3   Si provi che $\left\vert X\times X\right\vert=\left\vert X^{\{0,1\}}\right\vert$.
Soluzione

Esercizio 2.4   Si provi che se $X,Y,Z$ sono insiemi, allora $\left\vert(X^Y)^Z\right\vert=\left\vert X^{Y\times Z}\right\vert$.
Soluzione

Esercizio 2.5   Si provi che se $X,Y,Z$ sono insiemi con $Y\cap Z=\varnothing$, allora $\left\vert X^{Y\cup Z}\right\vert=\left\vert X^Y\times X^Z\right\vert$.
Soluzione

I numeri naturali: gli assiomi di Peano

Ricordiamo gli assiomi (dovuti a Peano) che descrivono la struttura dei numeri naturali.

Assioma 2.5   $0\in \mathbb{N}$

Assioma 2.6   $\mathop{\rm succ}\nolimits :\mathbb{N}\to \mathbb{N}$ è una funzione iniettiva

Assioma 2.7   $\forall n \in\mathbb{N}\quad \mathop{\rm succ}\nolimits (n) \ne 0$

Assioma 2.8 (di induzione)   se $A\subseteq \mathbb{N}$ è un sottinsieme tale che

1. $0\in A$
2. $\forall n \in \mathbb{N}\quad (n\in A \Rightarrow \mathop{\rm succ}\nolimits (n) \in A)$

allora $A=\mathbb{N}$.

Proposizione 2.9   Sia $n\in \mathbb{N}$, $n\ne 0$ allora esiste un unico $m\in \mathbb{N}$ tale che $\mathop{\rm succ}\nolimits (m) = n$. Tale $m$ viene chiamato il predecessore di $m$.

Dimostrazione.  Avendo l'esistenza, l'unicità segue immediatamente dall'iniettività di $\mathop{\rm succ}\nolimits$.

Supponiamo per assurdo che esista un $m\ne 0$ tale che $\mathop{\rm succ}\nolimits (n) \ne m$ per ogni $n$, allora sia $A = \mathbb{N}-\{m\}$. Chiaramente $0\in A$, in quanto $m\ne 0$. Se $n \in A$, allora $succ (n) \ne m$ e quindi $succ (n) \in A$. Ma allora $A=\mathbb{N}$, e questa è una contraddizione.     $\square$

L'assioma di induzione fornisce una potente tecnica di dimostrazione di proposizioni indicizzate sui naturali.

Il principio di induzione (prima forma)

Una conseguenza immediata dell'assioma di induzione è il seguente

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

1. $P(0)$ sia vera
2. per ogni $n\in \mathbb{N}$ $P(n)\Rightarrow P(succ(n))$

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

Dimostrazione.  Sia $A=\{n\mid P(n)$ è vera$\}$, allora $0\in A$ e se $n \in A$ allora vale $P(n)$, quindi vale $P(\mathop{\rm succ}\nolimits (n))$ ossia anche $succ (n) \in A$, quindi per l'assioma di induzione $A=\mathbb{N}$.     $\square$

Il teorema di ricorsione

Al momento i naturali sembrano essere una struttura molto povera, non vi è definita né la somma né il prodotto e nemmeno la relazione d'ordine (poter dire quando due numeri sono uno più grande dell'altro). Per poter dare queste definizioni è necessario dimostrare il seguente

Teorema 2.11 (di ricorsione)   Sia $X$ un insieme, $h:\mathbb{N}\times X\to X$ una funzione e $c\in X$. Esiste una unica funzione $f:\mathbb{N}\to X$ tale che:

$$f(0) = c$$ (1)

$$f(\mathop{\rm succ}\nolimits (n)) = h(n,f(n)) \quad \forall n \in \mathbb{N}$$ (2)

Dimostrazione.  Cominciamo con il provare l'unicità di una tale $f$. Supponiamo che $f$ e $g$ verifichino le due proprietà e proviamo per induzione che $f(n)=g(n)$ per ogni $n$. Usiamo l'induzione. Per $n=0$ la proposizione è vera, infatti dato che sia $f$ che $g$ verificano 1, si ha che $f(0)=c=g(0)$.

Supponiamo che $f(n)=g(n)$. Dalla 2 per $f$ si ha che $f(\mathop{\rm succ}\nolimits (n))=h(n,f(n))$ e la stessa applicata a $g$ dà che $g(\mathop{\rm succ}\nolimits (n))=h(n,g(n))$, dato che $f(n)=g(n)$, allora

$$f(\mathop{\rm succ}\nolimits (n))=h(n,f(n))=h(n,g(n))=g(\mathop{\rm succ}\nolimits (n)).$$

Proviamo ora l'esistenza. Per definizione di funzione quello che si cerca è un insieme $f\subseteq \mathbb{N}\times X$ tale che:

$$\forall n\in\mathbb{N}\quad \exists x \in X : (n,x) \in f$$ (3)

e, traducendo in termini di appartenenza le richieste (1) e (2)

$$(0,c)\in f$$ (4)

$$\forall n\in\mathbb{N}\quad(x,n)\in f \Rightarrow (\mathop{\rm succ}\nolimits (n), h(n,x)) \in f$$ (5)

Sia $\Omega= \{Z\subseteq \mathbb{N}\times X\mid Z$    verifica (1) e (2)$\}$, quello che dobbiamo trovare è un elemento di $\Omega$ che sia una funzione.

Sia $f=\bigcap_{Z\in\Omega}Z$. Dato che $f$ è l'intersezione di tutti gli elementi di $\Omega$, necessariamente

$$\forall Z\in \Omega\quad f\subseteq Z$$ (6)

Provaiamo che $f\in\Omega$. Infatti $(0,c)\in Z$ per ogni $Z\in \Omega$, quindi $(0,c)\in f$. Se $(n,x)\in f$ allora $(n,x)\in Z$ per ogni $Z\in \Omega$, ma allora dato che ogni $Z\in \Omega$ verifica la (5), $(\mathop{\rm succ}\nolimits (n),h(x,n)\in Z$ per ogni $Z\in \Omega$ e quindi $(\mathop{\rm succ}\nolimits (n),h(x,n)\in f$.

Per concludere resta da provare che $f$ verifica la (3). Procediamo per induzione su $n$.

Se $n=0$. Abbiamo già visto che $(0,c)\in f$. Supponiamo per assurdo che esista $(0,d)\in f$ con $d\ne c$, e sia $f'=f-\{(0,d)\}$. Chiaramente $(0,c)\in f'$ e se $(n,x)\in f'\subseteq f$ allora $(\mathop{\rm succ}\nolimits (n),h(n,x))\in f$, ma allora, per il terzo assioma di Peano, $\mathop{\rm succ}\nolimits (n)\ne 0$ per ogni $n\in \mathbb{N}$ e quindi $(\mathop{\rm succ}\nolimits (n),h(n,x))\ne(0,d)$, pertanto $(\mathop{\rm succ}\nolimits (n),h(n,x)\in f'$. Quindi $f'\in\Omega$, ma ciò contraddice la (6) perché $f\not\subseteq f'$.

Supponiamo la tesi vera per $n$. Sia $x$ l'unico elemento tale che $(n,x)\in f$, dato che $f$ verifica la (5), allora $(\mathop{\rm succ}\nolimits (n),h(n,x))\in f$. Supponiamo per assurdo che anche $(\mathop{\rm succ}\nolimits (n),e)\in f$ e si ponga $f'=f-\{(\mathop{\rm succ}\nolimits (n),e)\}$. Proviamo che anche in questo caso $f'\in\Omega$ e si avrà, come prima, un assurdo. Dal terzo assioma di Peano segue che $(0,c)\in f'$. Se $(i,z)\in f'\subseteq f$ allora $(\mathop{\rm succ}\nolimits (i),h(i,z))\in f$. Se $i\ne n$ allora, per l'iniettività di $\mathop{\rm succ}\nolimits$ si ha che $(\mathop{\rm succ}\nolimits (i),h(i,z))\ne (\mathop{\rm succ}\nolimits (n),e)$ e quindi $(\mathop{\rm succ}\nolimits (i),h(i,z))\in f'$. Se invece $i=n$ allora $(n,z)\in f$ implica, per l'unicità di $x$, che $z=x$ e quindi, dato che $h(n,z)\ne e$, $(\mathop{\rm succ}\nolimits (i),h(i,z))=(\mathop{\rm succ}\nolimits (n),h(n,x))\in f'$. Questo conclude la dimostrazione.     $\square$