Lezione 7 (15 marzo 1999 h. 9.30-10.30)

Definizione 7.1 Sia X un insieme una relazione su X è un sottoinsieme di $X\times X$ . Se ${\cal R}$ è una relazione su X si scriverà $x{\cal R}x$ piuttosto che $(x_1,x_2)\in{\cal R}$ Diremo che ${\cal R}$ è una relazione d'equivalenza se verifica le seguenti proprietà:

1.: (proprietà riflessiva) $x{\cal R}x$ per ogni $x\in X$ ;
2.: (proprietà simmetrica) $x_1{\cal R}x_2\Rightarrow x_2{\cal R}x_1$ per ogni $x_1,x_2\in X$ ;
3.: (proprietà transitiva) $x_1{\cal R}x_2$ e $x_2{\cal R}x_3\Rightarrow x_1{\cal R}x_3$ per ogni $x_1,x_2,x_3\in X$ .

Se ${\cal R}$ è una relazione d'equivalenza su X e $x\in X$ si chiama classe d'equivalenza di x l'insieme

$\begin{displaymath}\left[x\right]_{\cal R}=\{y\in X\mid y{\cal R}x\}. \end{displaymath}$

Proposizione 7.3 Se ${\cal R}$ è una relazione d'equivalenza su X allora:

1.: per ogni $x\in X$ $x\in\left[x\right]_{\cal R}$ .
2.: per ogni $x_1,x_2\in X$ $\left[x_1\right]_{{\cal R}}=\left[x_2\right]_{{\cal R}}$ se e solo se $x_1{\cal R}x_2$
3.: per ogni $x_1,x_2\in X$ $\left[x_1\right]_{\cal R}\cap\left[x_2\right]_{\cal R}\ne\varnothing\Rightarrow \left[x_1\right]_{\cal R}=\left[x_2\right]_{\cal R}$ .

Dim. Si osservi che nella dimostrazione della proposizione 6.5 non si è usato il fatto che si stesse parlando di congruenze, ma soltanto il fatto che la relazione di congruenza verifica le proprietà riflessiva, simmetrica e transitiva; basta allora ripetere parola per parola quella dimostrazione. $\square$

Partizioni e insieme quoziente

Definizione 7.4 Sia X un insieme e ${\cal R}$ una relazione d'equivalenza su X, l'insieme delle classi d'equivalenza di X si chiama insieme quoziente di X modulo ${\cal R}$ e si denota con $X\big/\mathchoice {{}_{\!\displaystyle {}{\cal R}}} {{}_{\!\textstyle {}{\cal R}}} {{}_{\!\scriptstyle {}{\cal R}}} {{}_{\!\scriptscriptstyle {}{\cal R}}}$ . È definita l'applicazione

$\begin{eqnarray*}\pi_{\cal R}&:& X\longrightarrow{}X\big/\mathchoice {{}_{\!\di... ...l R}}} \\ \pi_{\cal R}&:& x\longmapsto\left[x\right]_{\cal R} \end{eqnarray*}$

che ad ogni elemento associa la sua classe d'equivalenza e che si chiama proiezione a quoziente.

Definizione 7.6 Sia X un'insieme. Un sottoinsieme ${\cal P}$ delle parti di X si dice una partizione di X se:

1.: $\bigcup_{A\in{\cal P}} A=X$ ;
2.: $A\cap B=\varnothing$ per ogni $A,B\in {\cal P}$ con $a\ne B$ .

Osservazione 7.7 Alla luce di queste due definizioni i punti 1 e 3 della proposizione precedente possono essere riassunti dicendo che l'insieme quoziente $X\big/\mathchoice {{}_{\!\displaystyle {}{\cal R}}} {{}_{\!\textstyle {}{\cal R}}} {{}_{\!\scriptstyle {}{\cal R}}} {{}_{\!\scriptscriptstyle {}{\cal R}}}$ è una partizione di X.

Esercizio 7.1 Sia X un insieme. Si dimostri che gli insiemi

$R=\{{\cal R}\mid{\cal R}\hbox{\rm { \\lq e una relazione d'equivalenza su }}X\}$
$P=\{{\cal P}\mid{\cal P}\hbox{\rm { \\lq e una partizione di }}X\}$

sono in bigezione.
Soluzione

Il teorema di omomorfismo per insiemi

Esercizio 7.2 Siano X e Y insiemi e sia $f:X\to Y$ un'applicazione. Si definisca la relazione su X

$\begin{displaymath}x_1\stackrel{f}{\sim}x_2\iff f(x_1)=f(x_2). \end{displaymath}$

Si provi che $\stackrel{f}{\sim}$ è una relazione d'equivalenza su X. La relazione $\stackrel{f}{\sim}$ si chiama relazione indotta da f.
Soluzione

Teorema 7.8 Siano X,Y insiemi e $f:X\to Y$ un'applicazione. Esiste una unica applicazione $\widetilde{f{}}:X\big/\mathchoice {{}_{\!\displaystyle {}\stackrel{f}{\sim}}} ... ...e {}\stackrel{f}{\sim}}} {{}_{\!\scriptscriptstyle {}\stackrel{f}{\sim}}}\to Y$ tale che $\widetilde{f{}}\circ\pi=f$ .

$\begin{displaymath}\begin{picture} (96,57)(-11,-7) \put(0,40){\makebox(0,0){$G$ ... ...0){\vector(1,0){60}} \put(10,5){\vector(2,1){60}} \end{picture}\end{displaymath}$

Si ha inoltre che:

1.: $\widetilde{f{}}$ è iniettiva;
2.: $\widetilde{f{}}$ è surgettiva se e solo se f è surgettiva.

Dim. Definiamo $\widetilde{f{}}$ . Sia $\left[x\right]\in X\big/\mathchoice {{}_{\!\displaystyle {}\stackrel f \sim}} ... ...criptstyle {}\stackrel f \sim}} {{}_{\!\scriptscriptstyle {}\stackrel f \sim}}$ allora affinché $\widetilde{f{}}\circ\pi=f$ , dovrà risultare che $\widetilde{f{}}(\left[x\right])=\widetilde{f{}}(\pi(x))=f(x)$ . Quindi se $\widetilde{f{}}$ esiste è necessariamente unica e definita da $\widetilde{f{}}(\left[x\right])=f(x)$ .

Dimostriamo che questa è una buona definizione, ossia che la definizione non dipende dal rappresentante della classe, ossia che se $\left[x_1\right]=\left[x_2\right]$ allora $\widetilde{f{}}(\left[x_1\right])=\widetilde f(\left[x_2\right])$ . Ma:

La catena di equivalenze in (1) mostra anche che $\widetilde{f{}}$ è iniettiva.

Supponiamo ora che f sia surgettiva, allora dato $y\in Y$ esiste $x\in X$ tale che f(x)=y ma allora $\widetilde{f{}}(\left[x\right])=f(x)=y$ . Viceversa se $\widetilde{f{}}$ è surgettiva, allora dato $y\in Y$ esiste $\left[x\right]\in X\big/\mathchoice {{}_{\!\displaystyle {}\stackrel f \sim}} ... ...criptstyle {}\stackrel f \sim}} {{}_{\!\scriptscriptstyle {}\stackrel f \sim}}$ tale che $\widetilde{f{}}(\left[x\right])=y$ . Ma allora $f(x)=\widetilde{f{}}(\left[x\right])=y$ , ossia f è surgettiva. $\square$

Lezione 7 (15 marzo 1999 h. 9.30-10.30)

Relazioni d'equivalenza: definizione e prime proprietà

Partizioni e insieme quoziente

Il teorema di omomorfismo per insiemi