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 (AB).

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 aT. 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,bT, és ab. 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 xT(a) és xT(b), ezért x ~ a és x ~ b egyidejűleg. Így a tranzitivitás miatt a ~ b, ezért aT(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.