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

Relazioni d'equivalenza: definizione e prime proprietà

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

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

Osservazione 7.2   Per ogni n la congruenza modulo n è una relazione d'equivalenza.

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.

Osservazione 7.5   La proiezione a quoziente è evidentemente surgettiva.

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

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

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

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:

$$\left[x_1\right]=\left[x_2\right]\iff x_1\stackrel{f}{\sim}x_2\iff f(x_1)=f(x_2)$$ (1)

e quindi la definizione è ben posta.

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$