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

Soluzione