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 ${\displaystyle H}$ halmaz, ${\displaystyle \rho }$ pedig ekvivalenciareláció ${\displaystyle H}$ felett. Ekkor ${\displaystyle y\in H}$ szerinti ekvivalenciaosztálynak nevezzük a következő halmazt:

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

Tulajdonságok

Diszjunkt halmazok

Az ekvivalenciaosztályok diszjunkt halmazok:

${\displaystyle 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ő.

${\displaystyle K\cap K'={x}}$

${\displaystyle \forall k\in K:k\rho x}$

${\displaystyle \forall k'\in K':k'\rho x}$

Az ekvivalencia tranzitivitása alapján

${\displaystyle \forall k\in K,\forall k'\in K':k\rho k'}$

Az ekvivalenciaosztály definíciója szerint pedig

${\displaystyle \forall k\in K:k\in K'\Rightarrow K\subseteq K'}$

${\displaystyle \forall k'\in K':k'\in K\Rightarrow K'\subseteq K}$

${\displaystyle K\subseteq K'\land K'\subseteq K\Rightarrow K=K'}$

QED

Faktorizálás

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