Sanna Ranto, LUKUTEORIA JA ALGEBRA
Versio 1, 1.11.2003
LUKUTEORIA
 

Ekvivalenssiluokka

Määritelmä. Olkoon ~ joukon A ekvivalenssirelaatio. Kunkin alkion a  (- A kanssa ekvivalentit alkiot muodostavat joukon A osajoukon. Tätä joukkoa sanotaan alkion a ekvivalenssiluokaksi. Alkion a ekvivalenssiluokasta käytetään merkintää [a] ja se on siis

[a] = {b  (-  A |b ~ a}.

Alkiota a sanotaan ekvivalenssiluokan [a] edustajaksi.

Jokainen ekvivalenssiluokka muodostuu keskenään ekvivalenteista alkioista, toisin sanoen alkiot a ja b kuuluvat samaan ekvivalenssiluokkaan jos ja vain jos a ~ b. Nimittäin, jos a ~ b niin a  (- [b] ja ekvivalenssirelation refleksiivisyyden (E1) perusteella b  (- [b]. Kääntäen, jos a ja b kuuluvat johonkin ekvivalenssiluokkaan [c], niin a ~ c ja b ~ c; ekvivalenssirelaation symmetrisyydestä (E2) ja transitiivisuudesta (E3) seuraa, että a ~ b.

Lause. Jos ~ on joukon A ekvivalenssirelaatio, niin A voidaan esittää erillisten ekvivalenssiluokkien unionina:

      U 
A =     [a]     ([a]  /~\  [a'] =   A  a,a' (-  D, a /= a'),
    a (- D

missä D on joukon A osajoukko, joka sisältää yhden alkion jokaisesta ekvivalenssiluokasta. Joukkoa D sanotaan ekvivalenssiluokkien edustajistoksi.

Todistus. Edellä esitetyn perusteella on selvää, että joukko A voidaan esittää ekvivalenssiluokkien unionina. Vielä pitää osoittaa, että jos a ja a' eivät ole ekvivalentteja, niin ekvivalenssiluokien [a] ja [a'] leikkaus on tyhjä joukko. Tehdään vastaoletus, että leikkaus [a]  /~\ [a'] sisältäisi jonkin alkion b. Silloin b ~ a ja b ~ a'. Ekvivalenssirelaation ominaisuuksien E2 ja E3 perusteella a ~ a'. Koska a ja a' kuuluvat edustajistoon pitää niiden olla yhtä suuret, mutta tämä on ristiriidassa oletuksen kanssa. []

Jos joukko A on erillisten epätyhjien osajoukkojensa unioni, sanotaan, että nämä osajoukot muodostavat joukon A partition (eli osituksen). Tällöin edellinen lause voidaan muotoilla seuraavasti: Jos joukossa A on määritelty ekvivalenssirelaation, niin ekvivalenssiluokat muodostavat joukon A partition.

Kaikkien ekvivalenssiluokkien joukkoa sanotaan joukon A osamäärä- tai tekijäjoukoksi. Sitä merkitään symbolilla A/ ~; siis

A/  ~ = {[a] |a  (-  A}=  {[a] |a  (-  D}.


Linkit:
Ekvivalenssirelaatio