Definizione

$R \subseteq S \times S$ è di equivalenza se:

• Riflessiva: $\forall x \in S, xRx$
• Simmetrica: $\forall x, y \in S, xRy \Rightarrow yRx$
• Transitiva: $\forall x,y,x \in S, xRy,yRz \Rightarrow xRz$

Partizione

Una partizione di un insieme $S$ è un insieme $A \subseteq P(S)$ tale che:

• gli insiemi sono non vuoti: $\forall X \in A, X \neq \emptyset$
• a due a due disgiunti: $\forall X,Y \in A, X \cap Y = \emptyset$
• la loro unione è tutto S: $\bigcup_{X \in A} X = S$

Classe di equivalenza, insieme quoziente

Sia $R \subseteq S \times S$ relazione di equivalenza

La classe di equivalenza di $x \in S$ modulo $R$ è l’insieme: $[x]_R = \{ y \in S|yRx \} \subseteq S$

L’insieme quoziente di $S$ modulo $R$ è l’insieme di tutte le classi di equivalenza degli elementi di $S$: $S\backslash R = \{ [x]_R|x \in S \}$

Proposizione

$S$ insieme, $R \subseteq S \times S$ relazione d’equivalenza. Allora valgono le seguenti affermazioni:

• $x \in [x]_R$ $\forall x \in S$ ($[x]_R \neq \emptyset$)
• se $xRy \Rightarrow [x]_R = [y]_R$
• se $x \cancel{R} y \Rightarrow [x]_R \cap [y]_R = \emptyset$