Lezione 1

Insiemi e operazioni tra insiemi

Non intendiamo qui dare un'assiomatica della teoria degli insiemi (cosa che esula dalle finalità di questo corso e demandata ad altri eventuali corsi successivi), ma soltanto elencare alcune delle proprietà e delle costruzioni che permettono di confrontare insiemi e costruire nuovi insiemi a partire da altri, facendo eventualmente notare la necessità di assiomatizzare tali cosatruzioni.

Per noi un insieme sarà soltanto una collezione di oggetti detti i suoi elementi. La proprietà fondamentale che si richiede 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 ovvia 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.

Il criterio per stabilire quando due insiemi sono uguali, è fornito dal 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)$$

Definizione 1.2 (vuoto)   Si denota con $\varnothing$ l'insieme vuoto, ovvero l'insieme caratterizzato dalla proprietà di non avere elementi, in altri termini l'insieme tale che per ogni $x$ $x\not\in\varnothing$.

Osservazione 1.3   L'assioma di estensionalità garantisce evidentemente che se l'insieme vuoto esiste esso è anche unico. In effetti la sua esistenza va presa come assioma.

Osservazione 1.4   Se $P(x)$ è una qualsiasi proprietà attribuibile a $x$, (ad esempio "$x$ ha gli occhi azzurri") allora l'asserzione

$$\forall x\quad x\in\varnothing \Rightarrow P(x)$$

è vera. Ricordiamo infatti che un'implicazione $Q \Rightarrow P$ altro non è che un modo diverso per scrivere

$$P$$    o $$($$non $$Q)$$

ossia o vale la tesi o non vale l'ipotesi. Quindi se l'ipotesi $Q$ è sempre falsa, l'implicazione risulta vero (gli antichi dicevano ex falso quodlibet, dal falso segue qualsiasi cosa).

Nel nostro caso, per definizione di vuoto, la premessa $x\in\varnothing$ è sempre falsa, per qualsiasi $x$, quindi l'implicazione è vera. Possiamo pertanto asserire che gli elementi dell'insieme vuoto hanno gli occhi azzurri.

Definizione 1.5   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$.

Un modo di definire degli insiemi è quello di usare una ``proprietà'' che ne caratterizzi gli elementi. Ossia se $P$ è una, formula della teoria degli insiemi, per intenderci una proprietà esprimibile in termini del simbolo di appartenenza e di uguaglianza, dei quantificatori e dei connettivi logici, (e, o, $\Rightarrow$, non) allora con $\{x\mid P(x)\}$, si intende la collezzione di tutti gli $x$ che soddisfano la proprietà $P$. Il paradosso di Russel mostra che in generale un tale oggetto può non essere un insieme. Si dà però il seguente

Assioma 1.6 (separazione)   Se $X$ è un insieme e $P$ è una proprietà esprimibile in termini del linguaggio della teoria degli insiemi, allora la collezione

$$\{x\mid x\in X$$    e $$P(x)\}$$

è un insieme. Si userà spesso anche la notazione $\{x\in X\mid P(x)\}$, per indicare questo insieme.

Definizione 1.7   Se $X$ e $Y$ sono insiemi si costruiscono altri insiemi:

• intersezione $X \cap Y = \{x\mid x\in X$    e $x\in Y\}$
• differenza $X \setminus Y = \{x\mid x\in X$    e $x\notin Y\}$.

  Quando $Y\subseteq X$ la differenza $X \setminus 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à

• unione $X \cup Y = \{x\mid x\in X$    o $x\in Y\}$
• differenza simmetrica $X \bigtriangleup Y = (X \setminus Y)\cup (Y \setminus X)$
• prodotto $X \times Y =\{(x,y)\mid x\in X$    e $y\in Y\}$
• potenza $2^X=\{ x \mid x\subseteq X\}$

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\}$$

Osservazione 1.8   Quelle che abbiamo appena dato come definizioni, sono solo in parte tali. Se infatti gli insiemi intersezione, differenza e complemento sono effettivamente definibili a usando l'assioma di separazione, per gli altri tale assioma non è più sufficiente (non si separano degli elementi da un insieme, ma si costruiscono, insiemi ``più grandi'') e quindi tali costruzioni devono essere opportunamente assiomatizzate, cosa che però noi non facciamo.

Esercizio 1.1   Si provi che valgono le seguenti:

1. $\forall X\quad \varnothing \subseteq X$
2. $\forall X\quad X\subseteq X$
3. $\forall X,Y,Z\quad X\subseteq Y$ e $Y\subseteq Z$ allora $X\subseteq Z$.
4. $\forall X,Y\quad 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
   

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

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

   
   

2. proprietà commutativa
   

   $$X \cap Y = Y \cap X$$

   $$X \cup Y = Y \cup X$$

   
   

3. proprietà di assorbimento
   

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

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

   
   

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

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

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

   
   

5. leggi di de Morgan
   

   $$X \setminus (Y \cup Z) = (X \setminus Y) \cap (X \setminus Z)$$

   $$X \setminus (Y \cap Z) = (X \setminus Y) \cup (X \setminus Z)$$

   
   

6. $X \setminus ( X \setminus 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

Relazioni, funzioni parziali e funzioni totali

Definizione 1.9   Siano $X$ e $Y$ insiemi si dice relazione tra $X$ e $Y$, un sottinsieme ${\cal R}\subseteq X\times Y$. Se $\cal R$ è una relazione si scriverà anche $x{\cal R}y$ come sinonimo di $(x,y)\in {\cal R}$.

Una relazione tra $X$ e se stesso, si dirà anche una relazione binaria su $X$.

Definizione 1.10   Una relazione $f\subseteq X\times Y$ si dice una funzione parziale se per ogni $x\in X$ esiste al più un $y\in Y$ tale che $(x,y)\in f$. In simboli:

$$\forall x\in X ((x,y)\in f$$    e $$(x,y')\in f ) \Rightarrow y=y'$$

Si scriverà $f:X\rightharpoonup Y$ per dire che $f$ è una funzione parziale da $X$ a $Y$ e in tal caso si scriverà anche $y=f(x)$ come sinonimo di $(x,y)\in f$.

L'insieme $\{x\in X\mid \exists y\in Y:y=f(x)\}$ è detto il dominio di $f$ e si denota con $\mathop{\rm dom}\nolimits (f)$.

L'insieme $\{y\in Y\mid \exists x\in \mathop{\rm dom}\nolimits (f):y=f(x)\}$ è detto l'immagine di $f$ e si denota con $\mathop{\rm im}\nolimits (f)$.

Una funzione parziale $f:X\rightharpoonup Y$ si dice funzione totale o semplicemente funzione se $\mathop{\rm dom}\nolimits (f)=X$, in tal caso si scrive $f:X\to Y$.

Si denota $Y^X$ l'insieme di tutte le funzioni (totali) da $X$ a $Y$, ossia $Y^X=\{ f:X\to Y\}$.

Osservazione 1.11   Una funzione parziale può essere pensata come ``una legge ben definita'' che ad ogni elemento $x\in\mathop{\rm dom}\nolimits (f)$ associa l'unico elemento $y\in Y$ tale che $(x,y)\in f$, questo elemento si denota con $f(x)$. Con questa interpretazione, si dà senso proprio all'uguale contenuto nella scrittura $y=f(x)$, scrittura che quindi è equivalente a $(x,y)\in f$. In questa accezione (legge che associa ad un elemento un altro elemento) verranno generalmente usate le funzioni.

Esercizio 1.5   Siano $f,g \in Y^X$ due funzioni da $X$ in $Y$. Si provi che $f=g$ se e solo se $f(x)=g(x)$ per ogni $x\in X$.
Soluzione

Esempio 1.12   Se $X$ è un insieme ${\rm id}_X=\{(x_1,x_2)\in X\times X\mid x_1=x_2\}$ è una funzione, che viene chiamata l'identità di $X$. In altri termini ${\rm id}_X(x)=x$ per ogni $x\in X$.

Esempio 1.13   Se $f:X\to Y$ è una funzione e $A\subseteq X$, allora $f\cap (A \times Y)$ è anch'essa una funzione, che si denota con $\setbox\restrictbox=\hbox{$\hbox{$f$}_{A}$}\setbox0\hbox{$f$} {{f} \vrule wid... ...ictbox depth\dp\restrictbox \hbox{\vrule depth\dp0 height \ht0 width0pt}_{A}}$ e viene chiamata restrizione di $f$ ad $A$.

Esempio 1.14   Se $f:A \to Y$ e $g:B\to Y$ sono funzioni, non è detto che l'unione $f \cup g \subseteq (A\cup B) \times Y$, sia ancora una funzione. In effetti, dato che $((A\setminus B) \times Y) \cap g =\varnothing$, se $x\in A\setminus B$ allora esiste un unico $y\in Y$ tale $(x,y)\in f\cup g$ e precisamente quello tale che $(x,y)\in f$. Analogamente se $x\in B\setminus A$. Se invece $x\in A\cap B$ potrebbero esisterne un unico $y_1$ tale che $(x,y_1(\in f$ ed esiste un unico $y_2$ tale che $(x,y_2)\in g$, quindi affinché $f\cup g$ sia una funzione è necessario che per ogni $x\in A\cap B$ questi due elementi coincidano, in altre parole è necessario che $\restriction{f}{a\cap B}=\restriction{g}{a\cap B}$.

Esercizio 1.6   Se $X$ è un insieme, come sono fatti $X^\varnothing$ e $\varnothing ^X$?
Soluzione

Definizione 1.15   Siano $f:X\rightharpoonup Y$ e $g:Y\rightharpoonup Z$ si chiama composizione di $f$ e $g$ la relazione tra $X$ e $Z$ definita da

$$g\circ f = \{(x,z)\mid \exists y\in Y : y=f(x)$$    e $$z=g(y)\}$$

Proposizione 1.16   Se $f:X\rightharpoonup Y$ e $g:Y\rightharpoonup Z$ allora $g\circ f:X\rightharpoonup Z$. Se $f:X\to Y$ e $g:Y\to Z$ allora $g\circ f:X\to Z$.

Dimostrazione. Per provare il primo punto, dobbiamo mostrare che se $(x,z),(x,z')\in g\circ f$ allora $z=z'$. Per definizione di $g\circ f$ esiste $y\in Y$ tale che $y=f(x)$ e $z=g(y)$ ed esiste un $y'\in Y$ tale che $y'=f(x)$ e $z=g(y')$. Ma allora, dato che $f$ è una funzione parziali, $y=y'$, e quindi, dato che anche $g$ è una funzione parziale $z=z')$.

Se $f$ e $g$ sono funzioni totali, sono in particolare delle funzioni parziali e quindi, per quanto appena mostrato, $g\circ f$ è una funzione parziale. Dobbiamo provare che per ogni $x\in X$ esiste uno $z\in Z$ tale che $z=g\circ f(x)$. Sia $x\in X$, dato che $f$ `e una funzione totale, esiste $y\in Y$ tale che $y=f(x)$, dato che anche $g$ è totale esiste allora $z\in Z$ tale che $z=g(y)$, ma questo significa che $(x,z)\in g\circ f$, ovvero $z=g\circ f(x)$.     $\square$

Osservazione 1.17   Con l'interpretazione data nell'osservazione 1.11 si ha allora che $g\circ f(x)=g(f(x))$.

Definizione 1.18   Sia $f:X\to Y$ ed $A\subseteq X$, si chiamo immagine di $A$ tramite $f$ l'insieme:

$$f(A)=\{ y \in Y\mid \exists x\in A : y=f(x)\}=\{ f(x)\mid x\in A \}.$$

Definizione 1.19   Sia $f:X\to Y$ ed $A\subseteq Y$, si chiamo immagine inversa di $A$ tramite $f$ l'insieme:

$$f^{-1}(A)=\{ x \in X\mid f(x)\in A\}.$$

Definizione 1.20   Una funzione $f:X\to Y$ si dice:

• iniettiva se per ogni $x_1,x_2\in X$ $x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2)$
• surgettiva se per ogni $y\in Y$ esiste $x\in X$ tale che $f(x)=y$
• bigettiva se è iniettiva e bigettiva

Proposizione 1.21   Sia $f:X\to Y$ una bigezione, allora esiste un'unica funzione $g:Y\to X$ tale che $f\circ g= {\rm id}_Y$ e $g\circ f= {\rm id}_X$. Tale funzione si chiama inversa di $f$ e si denota con $f^{-1}$.

Dimostrazione. Dato $y\in Y$ esiste un unico $x\in X$ tale che $f(x)=y$ (esiste perché $f$ è surgettiva, è unico perché è iniettiva); chiamiamo $g(y)$ tale elemento. È allora evidente che $f(g(y))=y$ per ogni $y\in Y$. D'altra parte $f(g(f(x)))=f(x)$ per ogni $x\in X$ (applico la relazione precedente con $x=f(x)$), e quindi per l'iniettività di $f$ si ha che $g(f(x))=x$. È chiaro che tale funzione è l'unica possibile con le proprietà richieste.     $\square$

Osservazione 1.22   Si osservi che rispetto alla notazione insiemistica di funzione si ha che $f^{-1}=\{(y,x)\in Y\times X\mid (x,y)\in f\}$.

Il seguente esercizio inverte il risultato della proposizione precedente.

Esercizio 1.7   Sia $f:X\to Y$ e si supponga che esista una funzione $g:Y\to X$ tale che $g\circ f= {\rm id}_X$ e $f\circ g= {\rm id}_Y$. Si provi che allora $f$ è bigettiva.
Soluzione

Esercizio 1.8   Perché se $X$ e $Y$ sono insiemi allora anche $Y^X$ è un insieme?
Soluzione

Esercizio 1.9   Siano $f:X\rightharpoonup Y$ e $g:Y\rightharpoonup Z$, si determini $\mathop{\rm dom}\nolimits (g\circ f)$.
Soluzione

Esercizio 1.10   Siano $f:X\to Y$ e $g:Y\to Z$ si provi che:

• se $f$ e $g$ sono iniettive allora $g\circ f$ è iniettiva
• se $f$ e $g$ sono surgettive allora $g\circ f$ è surgettiva
• se $f$ e $g$ sono bigettive allora $g\circ f$ è bigettiva

Soluzione

Esercizio 1.11   Siano $X,Y,I$ insiemi, $f:X\to Y$ e $A_i\subseteq Y$ per ogni $i\in I$. Si provi che

$$f^{-1}(\bigcap_{i\in I} A_i)=\bigcap_{i\in I} f^{-1}(A_i) \qquad\qquad f^{-1}(\bigcup_{i\in I} A_i)=\bigcup_{i\in I} f^{-1}(A_i)$$

Soluzione

Esercizio 1.12   Siano $X,Y,I$ insiemi, $f:X\to Y$ e $A_i\subseteq X$ per ogni $i\in I$. Si provi che

$$f(\bigcap_{i\in I} A_i)=\bigcap_{i\in I} f(A_i) \qquad\qquad f(\bigcup_{i\in I} A_i)\subseteq \bigcup_{i\in I} f(A_i)$$

Si provi che in generale nella seconda delle due non può valere l'uguaglianza.
Soluzione