Ekvivalenciaosztály

Ekvivalenciaosztálynak nevezzük egy halmaz azon részhalmazát, amelynek elemei egy megadott ekvivalenciareláció szerint ekvivalensek. Az ekvivalenciaosztályok a halmazt diszjunkt módon osztják fel.

Definíció

Legyen $H$ halmaz, $\rho$ pedig ekvivalenciareláció $H$ felett. Ekkor $y\in H$ szerinti ekvivalenciaosztálynak nevezzük a következő halmazt:

$K:=\left\{x|x\in H\land x\rho y\right\}.$

Tulajdonságok

Diszjunkt halmazok

Az ekvivalenciaosztályok diszjunkt halmazok:

$K\cap K'=\emptyset$

Bizonyítás

Indirekt módon bizonyítunk: tegyük fel, hogy van olyan elem, amely mindkét osztálynak eleme. Ekkor mindkét osztály minden eleme ekvivalens ezzel az elemmel, és az ekvivalencia definíciója alapján egymással is, tehát a két halmaz kölcsönösen részhalmaza egymásnak, azaz egyenlő.

$K\cap K'={x}$

$\forall k\in K:k\rho x$

$\forall k'\in K':k'\rho x$

Az ekvivalencia tranzitivitása alapján

$\forall k\in K,\forall k'\in K':k\rho k'$

Az ekvivalenciaosztály definíciója szerint pedig

$\forall k\in K:k\in K'\Rightarrow K\subseteq K'$

$\forall k'\in K':k'\in K\Rightarrow K'\subseteq K$

$K\subseteq K'\land K'\subseteq K\Rightarrow K=K'$

QED

Faktorizálás

Ha $\rho$ ekvivalencia a $H$ halmaz felett, akkor minden eleme benne van valamelyik ekvivalenciaosztályban. A $H$ feletti ekvivalenciaosztályok halmazát $H$ faktorhalmazának nevezzük. Jelölése: $H_{/\rho }$.