Lezione 1 (26 febbraio 2001 h. 9.30-10.30)

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   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.3 (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 \hbox{\rm { e }} P(x)\}$$

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

Definizione 1.4   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\}$
• 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à

• unione $X \cup Y = \{x\mid x\in X \hbox{\rm { o }} x\in Y\}$
• 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\}$

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.5   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 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

Relazioni, funzioni parziali e funzioni totali

Definizione 1.6   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.7   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 \hbox{\rm { 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 $X^Y\{ f:X\to Y\}$.

Osservazione 1.8   Una funzione parziale può essere pensata come ``una legge'' 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, dà senso proprio all'uguale contenuto nella scrittura $y=f(x)$. In questa accezione (legge che associa ad un elemento un altro elemento) verranno generalmente usate le funzioni.

Esempio 1.9   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$.

Definizione 1.10   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) \hbox{\rm { e }} z=g(y)\}$$

Proposizione 1.11   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.12   Con l'interpretazione data nell'osservazione 1.8 si ha allora che $g\circ f(x)=g(f(x))$.

Definizione 1.13   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.14   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.15   Sia $f:X\to Y$ una bigezione, allora esiste una 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.16   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.5   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.6   Perché se $X$ e $Y$ sono insiemi allora anche $Y^X$ è un insieme?
Soluzione

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

Esercizio 1.8   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.9   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) ... ...ad f^{-1}(\bigcup_{i\in I} A_i)=\bigcup_{i\in I} f^{-1}(A_i)$$

Soluzione