1.4 Az ekvivalencia reláció
Ekvivalenciarelációnak nevezzük egy relációt, ha az a reflexív, szimmetrikus és tranzitív. Jelölése: a ~ b.
Példa:
Legyen H egy város azon lakóinak a halmaza. Az a ρ b jelentse azt, hogy „a ugyanabban az utcában lakik, mint b".
Világos, hogy ez a reláció
- reflexív, mert a ρ a.
- szimmetrikus, mert ha a ρ b , akkor b ρ a.
- tranzitív, hiszen a ρ b és b ρ c , akkor a ρ c.
További példák a matematika köréből:
- A pozitív természetes számok halmazán: a kisebb b-vel.
- A tér valamennyi síkjának a halmazán: a párhuzamos b-vel.
- A részhalmaza B-nek (A
B).
Ekvivalensnek nevezünk két elemet, ha azok relációban állnak egymással, és a reláció ekvivalencia reláció.
Legyen ρ a T halmazon
értelmezett ekvivalencia reláció, és legyen a ∈ T. Az a ekvivalencia osztályának nevezzük T-nek
az a-val ekvivalens elemeinek halmazát, azaz az a-val relációban
lévő elemek halmazát. Jelölése: T(a). (T(a) T
).
Tétel 1.1: Legyen a,b ∈ T, és a ≠ b. Ha T(a)-nak és T(b)-nek van nem üres metszete, akkor a két ekvivalencia osztály megegyezik.
Bizonyítás.
Tegyük fel, hogy a T(a) és T(b) ekvivalencia osztályoknak
van közös eleme. Legyen ez x. Mivel x ∈ T(a) és x ∈ T(b),
ezért x ~ a és x ~ b egyidejűleg. Így a
tranzitivitás miatt a ~ b, ezért a ∈
T(b), ami miatt T(a) T(b). Hasonlóan
megmutatható, hogy T(b)
T(a).
Így T(a) = T(b).
Következmény.
Két különböző ekvivalancia osztály metszete üres halmaz. Egy ekvivalencia osztályt bármely eleme meghatározza.
Ha T az alaphalmaz, akkor T* jelöli a T halmazhoz tartozó ekvivalencia osztályok halmazát.