Lezione 1 (28 febbraio 2000 h. 9-11)

   
Insiemi e operazioni tra insiemi

Non intendiamo qui dare un'assiomatica della teoria degli insiemi, per noi un insieme sarà soltanto una collezione di oggetti detti i suoi elementi. La proprietà fondamentale che si richied affinché un oggetto sia un insieme è che si possa sempre stabilire senza ambiguità se qualche cosa è un suo elemento oppure no. In simboli, se A è un insieme allora per ogni x si ha che $x\in A$ (x appartiene ad A) oppure $x\notin A$ (x non appartiene ad A). Questa che può sembrare una richiesta vuota in realtà non lo è. Si consideri l'oggetto definito da:

$$A=\{x \mid x\notin x\}$$

e si provi a stabilire se $A\in A$ oppure no.

1.

Se $A\in A$, allora, dalla definizione di A segue che $A \notin A$

2.

Se $A \notin A$ allora, per definizione di A, $A\in A$

Quindi A non può essere un insieme, in quanto non possiamo decidere se $A\in A$ oppure no. Questo esempio è noto come il paradosso di Russel.

L'altra proprietà fondamentale degli insiemi, e che fornisce un criterio per stabilire quando due insiemi sono uguali, è la seguente

Assioma 1.1 (estensionalità)   Due insiemi sono uguali se e solo se hanno gli stessi elementi. In simboli

$$A=B \iff (\forall x\, x \in A \iff x\in B)$$

Ricordiamo alcune definizioni.

Definizione 1.2   Siano X e Y due insiemi, si dice che X è contenuto in Y (o anche X è sottinsieme di Y), e si denota con $X \subseteq Y$ se ogni elemento di X è elemento di Y, in simboli, $\forall x\,(x\in X \Rightarrow x\in Y)$. Si dice che X è contenuto strettamente in Y (o anche che è un sottinsieme proprio di Y) e si denota con $X\subsetneq Y$, se $X \subseteq Y$ e $X\ne Y$.

Se X e Y sono insiemi si costruiscono altri insiemi:

• intersezione $X \cap Y = \{x\mid x\in X \hbox{\rm { e }} x\in Y\}$
• unione $X \cup Y = \{x\mid x\in X \hbox{\rm { o }} x\in Y\}$
• differenza $X - Y = \{x\mid x\in X \hbox{\rm { e }} x\notin Y\}$.

  Quando $Y\subseteq X$ la differenza X-Y viene chiamata il complemento di Y in X e viene denotata anche con $\complement_XY$ o semplicemente con $\complement Y$ o con Y' quando non ci sia ambiguità

• differenza simmetrica $X \bigtriangleup Y = (X-Y)\cup (Y-X)$
• prodotto $X \times Y =\{(x,y)\mid x\in X \hbox{\rm { e }} y\in Y\}$
• potenza $2^X=\{ x \mid x\subseteq X\}$
• $X^Y=\{ f \subseteq X\times Y \mid f \hbox{\rm { \\lq e una funzione totale }}X\to Y\}$

Se I è un insieme e per ogni $i\in I$ è dato un insieme X_i, si definiscono

• intersezione $$\bigcap_{i\in I} X_i = \{ x \mid \forall\,i\ x \in X_i\}$$
• unione $$\bigcup_{i\in I} X_i = \{ x \mid \exists\,i\ x \in X_i\}$$

Esercizio 1.1    Si provi che valgono le seguenti:

1.

$\forall X\,X\subseteq X$

2.

$\forall X,Y,Z\,X\subseteq Y$ e $Y\subseteq Z$ allora $X\subseteq Z$.

3.

$\forall X,Y\,X\subseteq Y$ e $Y\subseteq X$ se e solo se X=Y

Soluzione

Esercizio 1.2    Siano X e Y insiemi, si provi che $X\subseteq Y \iff X\cap Y = X \iff X\cup Y = Y$.
Soluzione

Esercizio 1.3    Siano X, Y, Z insiemi, si provino le seguenti:

1.

proprietà associativa dell'intersezione e dell'unione

$$\begin{eqnarray*}X\cap (Y \cap Z) & = & (X \cap Y)\cap Z \\ X\cup (Y \cup Z) & = & (X \cup Y)\cup Z \end{eqnarray*}$$

2.

proprietà commutativa

$$\begin{eqnarray*}X \cap Y & = & Y \cap X \\ X \cup Y & = & Y \cup X \end{eqnarray*}$$

3.

proprietà di assorbimento

$$\begin{eqnarray*}X \cup (X \cap Y) & = & X \\ X \cap (X \cup Y) & = & X \end{eqnarray*}$$

4.

proprietà distributiva dell'intersezione rispetto all'unione e dell'unione rispetto all'intersezione

$$\begin{eqnarray*}X \cap (Y \cup Z) & = & (X \cap Y) \cup (X \cap Z) \\ X \cup (Y \cap Z) & = & (X \cup Y) \cap (X \cup Z) \end{eqnarray*}$$

5.

leggi di de Morgan

$$\begin{eqnarray*}X - (Y \cup Z) & = & (X - Y) \cap (X - Z) \\ X - (Y \cap Z) & = & (X - Y) \cup (X - Z) \end{eqnarray*}$$

6.

$X - ( X - Y ) = X \cap Y$

7.

se $Y\subseteq X$ allora $\complement_X\complement_X Y = Y$.

Soluzione

Esercizio 1.4    Siano X, Y, Z insiemi, si provino le seguenti:

1.

$X\bigtriangleup(Y \bigtriangleup Z ) = (X \bigtriangleup Y)\bigtriangleup Z$

2.

$X\cap(Y \bigtriangleup Z) = (X\cap Y)\bigtriangleup(X\cap Z)$

Soluzione

   
Equipotenza di insiemi

Definizione 1.3   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 $\left\vert X\right\vert=\left\vert Y\right\vert$, che leggeremo anche X e Y hanno la stessa cardinalità.

Osservazione 1.4   Si osservi che non stiamo dando alcun significato al simbolo $\left\vert X\right\vert$, ossia non stiamo definendo cosa sia la cardinalità di un insieme. In effetti ciò può essere fatto (e sarà fatto in corsi successivi), ossia si possono definire una classe di particolari insiemi detti cardinali che godono della seguente proprietà:

ogni insieme è equipotente ad uno ed un solo cardinale.

Quando questo sarà fatto, quello che per noi è una definizione, ossia $\left\vert X\right\vert=\left\vert Y\right\vert$ se e solo se esiste una bigezione tra X e Y, sarà un teorema.

Proposizione 1.5   Valgono le seguenti proprietà:

1.

X è equipotente a se stesso.

2.

se X è equipotente a Y allora X è 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$

Esercizio 1.5      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

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.

Soluzione

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

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

Esercizio 1.8    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 1.9    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

   
Insiemi finiti: il Lemma dei cassetti

Dato un numero naturale $n\in\mathbb N$ denotiamo con In l'insieme $I_ n=\{0,1,\dots,n-1\}$.

Definizione 1.6   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 1.7 (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 In. 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'}$ } \setbox 0\hbox{$f$ } {{f}\,\vru... ...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$

Corollario 1.8   Se $n,m\in\mathbb N$ sono due naturali diversi X e Y sono insiemi finiti con $\left\vert X\right\vert=\left\vert I_ n\right\vert$ e $\left\vert Y\right\vert=\left\vert I_m\right\vert$, allora X e Y non sono equipotenti. In particolare, se $\left\vert X\right\vert=\left\vert I_ n\right\vert$ e $\left\vert X\right\vert = \left\vert I_m\right\vert$ allora n=m.

Si osservi che questo corollario fa sì che si possa definire la cardinalità degli insiemi finiti.

Definizione 1.9   Sia X un insieme finito, si dice cardinalità di X l'unico numero naturale n tale che $\left\vert X\right\vert=\left\vert I_ n\right\vert$.

Osservazione 1.10   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.

Proposizione 1.11   Sia X un insieme finito e $Y\subseteq X$ allora anche Y è finito e $\left\vert Y\right\vert\le \left\vert X\right\vert$. Se Y è un sottoinsieme proprio di X allora $\left\vert Y\right\vert < \left\vert X\right\vert$.

Dimostrazione. Procediamo per induzione su $n=\left\vert X\right\vert$. Se n=0 allora $X=\varnothing$ e quindi anche $Y=\varnothing$, da cui si conclude. Supponiamo la tesi vera per n e sia dato X con $\left\vert X\right\vert = n+1$. Sia $f:I_n\to X$ una bigezione e sia, poniamo x_n=f(n) e $X'=X-\{x_n\}$. Chiaramente $\left\vert X'\right\vert=n$. Si hanno due casi $x_n\not\in Y$ e $x_n\in Y$. Nel primo caso $Y\subseteq X'$, quindi, per ipotesi di induzione, $\left\vert Y\right\vert\le\left\vert X'\right\vert=n<n+1=\left\vert X\right\vert$. Nel secondo caso, detto $Y'=Y-\{x_n\}$ si ha che $Y'\subseteq X'$ e quindi $\left\vert Y'\right\vert\le\left\vert X'\right\vert$ e quindi $\left\vert Y\right\vert=\left\vert Y'\right\vert+1\le\left\vert X'\right\vert+1=\left\vert X\right\vert$. Si osservi che in quest'ultimo caso, se $Y\ne X$ allora anche $Y'\ne X'$ e quindi, per ipotesi di induzione si ha che $\left\vert Y'\right\vert<\left\vert X'\right\vert$ da cui $\left\vert Y\right\vert < \left\vert X\right\vert$.     $\square$

Come conseguenza si ha il seguente

Corollario 1.12   Un insieme finito non è equipotente ad alcun suo sottoinsieme proprio.

Esempio 1.13   L'insieme $\mathbb N$ non è finito, si consideri ad esempio l'applicazione $\mathbb N\to\mathbb N$ definita da $n \mapsto2n$, questa è una bigezione tra $\mathbb N$ ed il sottinsieme proprio dei numeri pari.

Esercizio 1.10      Siano X e Y insiemi finiti. Si provi che

1.

se $X\cap Y=\varnothing$ allora $\left\vert X\cup Y\right\vert=\left\vert X\right\vert+\left\vert Y\right\vert$.

2.

in generale $\left\vert X\cup Y\right\vert=\left\vert X\right\vert+\left\vert Y\right\vert-\left\vert X\cap Y\right\vert$

Soluzione

Esercizio 1.11      Siano $X_1,\dots, X_n$ insiemi finiti a due a due disgiunti si provi che $\bigcup_{i=1}^nX_i$ è finito e che

$$\left\vert\bigcup_{i=1}^n X_i\right\vert=\sum_{i+1}^n\left\vert X_i\right\vert.$$

Soluzione

Esercizio 1.12      Se X e Y sono insiemi finiti, si provi che

1.

$\left\vert X\times Y\right\vert=\left\vert X\right\vert\left\vert Y\right\vert$.

2.

$\left\vert X^Y\right\vert=\left\vert X\right\vert^{\left\vert Y\right\vert}$

3.

$\left\vert 2^X\right\vert=2^{\left\vert X\right\vert}$.

Soluzione

Esercizio 1.13    Siano X e Y insiemi finiti entrambi di cardinalità n. Si provi che ogni funzione iniettiva $X\to Y$ è anche surgettiva.
Soluzione

Esercizio 1.14    Sia X un insieme finito di cardinalità n. Si determini il numero delle applicazioni biunivoche di X in sé.
Soluzione