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:=\{x|x\in H\wedge x\rho y\}.$

Tulajdonságok

Diszjunkt halmazok

Az ekvivalenciaosztályok diszjunkt halmazok:

$K\cap K^{\prime }=\mathrm{\varnothing }$

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^{\prime }=x$

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

$\mathrm{\forall }{k}^{\prime }\in K^{\prime }:k^{\prime }\rho x$

Az ekvivalencia tranzitivitása alapján

$\mathrm{\forall }k\in K,\mathrm{\forall }{k}^{\prime }\in K^{\prime }:k\rho k^{\prime }$

Az ekvivalenciaosztály definíciója szerint pedig

$\mathrm{\forall }k\in K:k\in K^{\prime }\Rightarrow K\subseteq K^{\prime }$

$\mathrm{\forall }{k}^{\prime }\in K^{\prime }:k^{\prime }\in K\Rightarrow K^{\prime }\subseteq K$

$K\subseteq K^{\prime }\wedge K^{\prime }\subseteq K\Rightarrow K=K^{\prime }$

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$.

További információk

• Alice és Bob - 13. rész: Alice és Bob eladósodik
• Alice és Bob - 18. rész: Alice és Bob felcsavarja a számegyenest

Források

• I. N. Bronstejn, K. A. Szemengyajev, G. Musiol, H. Mühlig: Matematika kézikönyv Sablon:ISBN