Ekvivalenssirelaatio

Ekvivalenssirelaatio on joukon binäärirelaatio, joka on refleksiivinen, symmetrinen ja transitiivinen.

Motivaatio

Ekvivalenssirelaatio on eräänlainen yhtäsuuruusrelaation hienonnus. Voidaan aina päättää, ovatko kaksi joukon alkiota samat, eli onko a = b. Mutta joskus on hyödyllistä selvittää, ovatko kaksi alkiota vain samankaltaiset, ei välttämättä samat. Toisin sanoen – onko niillä sama jokin olennainen ominaisuus. Esimerkiksi kahta kirjaa voidaan pitää samankaltaisina, jos niillä on sama genre – tai ekvivalenssin avulla: kaksi kirjaa on ekvivalentteja, jos niillä on sama genre.

Mitä tällaiselta ekvivalenssilta odotettaisiin? Otetaan toinen esimerkki. Kaksi sanaa on samankaltaisia/ekvivalentteja, jos ne ovat yhtä pitkiä.

Varmaankin odotettaisiin, että jos mitataan kahden samaisen sanan samankaltaisuutta, tulos on, että ne ovat samankaltaisia. Kaikkien sanojen täytyy siis olla samankaltaisia/ekvivalentteja itsensä kanssa. Relaatioiden kielellä: ekvivalenssirelaation täytyy olla refleksiivinen.

Lisäksi jos sana ”puro” on samankaltainen/ekvivalentti sanan ”Aino” kanssa, odotetaan varmasti, että myös sana ”Aino” on ekvivalentti sanan ”puro” kanssa. Toisin sanoen järjestyksellä ei ole väliä. Relaatioiden kielellä: ekvivalenssirelaation täytyy olla symmetrinen.

Ja lopuksi jos sana ”talvi” on samankaltainen/ekvivalentti sanan ”lintu” kanssa ja sana ”lintu” on ekvivalentti sanan ”jalka” kanssa, odotetaan, että myös sanat ”talvi” ja ”jalka” ovat ekvivalentteja. Ekvivalenssirelaation täytyy siis olla myös transitiivinen.

Mitään muuta ekvivalenssilta ei odoteta.

Esimerkkejä

Lisää esimerkkejä ekvivalensseista:

• Asuminen samassa kaupungissa. Eino asuu varmasti samassa kaupungissa kuin Eino (refleksiivisyys). Jos Eino asuu samassa kaupungissa kuin Onni, niin myös Onni asuu samassa kaupungissa kuin Eino (symmetrisyys). Ja jos Onni asuu samassa kaupungissa kuin Väinö, niin myös Eino asuu samassa kaupungissa kuin Väinö (transitiivisuus).
• Kappaleet, joilla on sama säveltäjä. Kappaleella ”Tuulen laulu” on varmasti sama säveltäjä kuin kappaleella ”Tuulen laulu” (refleksiivisyys). Jos kappaleilla ”Tuulen laulu” ja ”Hiljainen joki” on sama säveltäjä, niin myös kappaleilla ”Hiljainen joki” ja ”Tuulen laulu” on sama säveltäjä (symmetrisyys). Ja jos kappaleilla ”Hiljainen joki” ja ”Matka kotiin” on sama säveltäjä, niin myös kappaleilla ”Tuulen laulu” ja ”Matka kotiin” on sama säveltäjä (transitiivisuus).
• (a, b) ∈ R täsmälleen silloin, kun a − b on parillinen luku; a, b ovat kokonaislukuja. Refleksiivisyys: a − a = 0, nolla on parillinen luku. Symmetrisyys: merkitään c = a − b. Silloin b − a = −(a − b) = −c. Jos c on parillinen, myös −c on parillinen. Transitiivisuus: merkitään p = a − b ja q = b − c. Tiedetään, että sekä p että q ovat parillisia lukuja. Nyt pitää osoittaa, että a − c on parillinen luku. Sijoitetaan tähän yhtälöön c:n paikalle c = b − q: a − (b − q), mikä on yhtä suuri kuin a − b + q. Oletuksista tiedetään, että a − b on parillinen luku. Jos parilliseen lukuun lisätään toinen parillinen luku q, saadaan taas parillinen luku.
• Yhtäsuuruus. Yhtäsuuruus on ekvivalenssi, ja se on samalla pienin ekvivalenssi missä tahansa joukossa M.

Triviaali ekvivalenssi

Olkoon M epätyhjä joukko. Mikä on joukon M pienin mahdollinen ekvivalenssi R? Karteesisen tulon M × M pienin mahdollinen osajoukko on tyhjä joukko ∅. Toteuttaako tyhjä joukko ekvivalenssin ehdot?

Se on varmasti symmetrinen, sillä relaatiolla R ei ole yhtään alkiota, joten symmetrisyysehto toteutuu automaattisesti ja triviaalisti. Samoin transitiivisuus. Ongelma on refleksiivisyys. Määritelmän mukaan kaikille joukon M alkioille x pätee (x, x) ∈ R. Toteutuuko tämä? Joukko M on epätyhjä, joten se sisältää jonkin alkion, vaikkapa q. Onko pari (q, q) relaatiossa R? Ei ole. Relaatio R ei siis ole refleksiivinen.

Mikä on pienin refleksiivisyyden toteuttava relaatio? Yhtäsuuruusrelaatio. Relaation R täytyy sisältää vähintään parit (x, x) kaikille joukon M alkioille. Se on juuri identtinen relaatio. Onko tällainen relaatio symmetrinen? Sen näkee helposti, että on. Samoin on helppo nähdä, että se on myös transitiivinen. Joukon M pienin ekvivalenssirelaatio on siis identtinen relaatio, jota merkitään id_M ja joka sisältää parit (x, x) kaikille x ∈ M.

Mikä on joukon M suurin mahdollinen ekvivalenssi? Suurin osajoukko on koko joukko M × M. Toteuttaako se ekvivalenssin ehdot? Sen näkee kai triviaalisti, että toteuttaa.

Ekvivalenssiluokka

Jokainen ekvivalenssi jakaa joukon M erillisten joukkojen perheeksi, joita kutsutaan ekvivalenssiluokiksi.

Olkoon M kaikkien sanojen joukko ja ekvivalenssi R ”yhtä pitkät sanat”. Siis (a, b) ∈ R täsmälleen silloin, kun sanoilla a ja b on sama pituus. Tämä ekvivalenssi jakaa sanojen joukon useaan pienempään joukkoon, jotka sisältävät aina samanpituisia sanoja. Yksittäiset ekvivalenssiluokat voidaan erottaa alaindeksillä, joka erottaa samalla sanojen pituuden kyseisessä joukossa:

• M₂ = {ja, on, ei, se, …}
• M₃ = {ovi, kuu, tie, sää, …}
• M₄ = {talo, kala, koti, tuli, …}
• …

Huomaa kaksi asiaa: 1) yksittäiset joukot ovat keskenään erillisiä, niillä ei ole yhteistä alkiota. 2) kaikki yksittäisen joukon alkiot ovat keskenään ekvivalentteja. Kaikki joukon M₃ sanat ovat keskenään ekvivalentteja, koska kaikkien sanojen pituus on kolme, siis sama pituus, mikä on ekvivalenssin ehto.

Jokainen alkio määrää samalla yksiselitteisesti oman ekvivalenssiluokkansa. Sitä merkitään yleensä merkinnällä M[x], missä x ∈ M. Jos kirjoitettaisiin M[ovi], määritettäisiin yksiselitteisesti ekvivalenssiluokka, jota jo merkittiin M₃.

Miten ekvivalenssiluokka sitten löydetään, jos tunnetaan jokin x ∈ M? Käydään läpi kaikki joukon M alkiot ja selvitetään, mitkä niistä ovat ekvivalentteja alkion x kanssa. Ne ovat kaikki alkiot, jotka kuuluvat ekvivalenssiluokkaan M[x].

Luokan M[ovi] löytämiseksi käytäisiin läpi kaikki joukon M sanat ja säilytettäisiin joukossa M₃ ne sanat, joiden pituus on kolme.

Ekvivalenssiluokan määritelmä ja ominaisuudet

Ekvivalenssiluokka voitaisiin määritellä näin. Olkoon M joukko ja R siinä määritelty ekvivalenssi. Silloin osituksen luokalla, joka sisältää alkion x ∈ M, tarkoitetaan:

$$M[x]=\{y\in M\mid (x,y)\in R\}$$

Määritelmä sanoo, että ne ovat kaikki y, jotka ovat ekvivalentteja annetun alkion x kanssa. Koska ekvivalenssirelaatio on refleksiivinen, mukaan tulee tällä tavalla myös alkio x itse – koska x on ekvivalentti itsensä kanssa.

Ekvivalenssin ositukseksi kutsutaan sitten kaikkien ekvivalenssiluokkien joukkoa. Kaikkien sanojen joukon ositus olisi siis joukko {M₂, M₃, M₄, …}.

Ekvivalenssiluokkien perusominaisuudet:

• (a, b) ∈ R täsmälleen silloin, kun M[a] = M[b]. Jos kaksi alkiota a, b ovat ekvivalentteja, niiden ekvivalenssiluokkien täytyy olla yhtä suuret.
• Kääntäen, jos ei päde (a, b) ∈ R, niin myös M[a] ≠ M[b], tarkemmin M[a] ∩ M[b] = ∅. Jos kaksi alkiota eivät ole ekvivalentteja, niiden osituksen luokat ovat erillisiä.
• Kaikkien ekvivalenssiluokkien yhdisteen täytyy antaa alkuperäinen joukko M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Edellinen merkintä on vain äärelliselle määrälle ekvivalenssiluokkia, mutta yleisesti niitä voi olla äärettömän monta.)

Esimerkkejä ekvivalenssin osituksista

Ensimmäinen esimerkki, parittomat ja parilliset luvut:

Olkoon yksinkertainen ekvivalenssi R määritelty positiivisten kokonaislukujen joukossa ℤ⁺. (a, b) ∈ R täsmälleen silloin, kun sekä a että b on pariton tai sekä a että b on parillinen. Esimerkkialkioita: (1, 7), (13, 9), (4, 6), (8, 136). Määritetään nyt tämän ekvivalenssin ositus ekvivalenssiluokkiin.

Edetään vaihe vaiheelta. Mikä on luokka ℤ⁺[1]? Täytyy löytää kaikki luvut, jotka ovat ekvivalentteja luvun yksi kanssa. Ekvivalenssin ehdon mukaan ne ovat kaikki parittomat luvut, joten ℤ⁺[1] = {1, 3, 5, 7, 9, …}.

Mikä on luokka ℤ⁺[2]? Etsitään kaikki luvut, jotka ovat ekvivalentteja kakkosen kanssa. Ne ovat kaikki parilliset luvut: ℤ⁺[2] = {2, 4, 6, 8, 10, …}.

Nyt ℤ⁺[3]. Mitkä luvut ovat ekvivalentteja kolmosen kanssa? Kaikki parittomat luvut. Mutta näin saadaan joukko ℤ⁺[1], joka laskettiin toissa kappaleessa. Samoin luokalle ℤ⁺[4], siinä saadaan taas parillisten lukujen joukko.

Nähdään, että tästä eteenpäin samat joukot toistuisivat. Sen näkee myös siitä, että valitaanpa mikä tahansa muu positiivinen kokonaisluku n, pätee jo n ∈ ℤ⁺[1] tai n ∈ ℤ⁺[2]. Muita positiivisia kokonaislukuja kuin parittomat ja parilliset ei ole, joten nämä kaksi joukkoa muodostavat ekvivalenssin osituksen.

Se on samanlaista kuin jos kuviteltaisiin ekvivalenssi ihmisten joukossa: sekä a että b on mies tai sekä a että b on nainen. Silloin ositukseksi saataisiin naisten joukko ja miesten joukko.

Toinen esimerkki, itseisarvo:

Olkoon ekvivalenssi R kokonaislukujen joukossa Z määritelty näin: (a, b) ∈ R täsmälleen silloin, kun |a| = |b|. (Pystyviivat tarkoittavat itseisarvoa.) Edetään taas vaihe vaiheelta:

• Z[0] = {0}. Nolla on relaatiossa vain nollan kanssa.
• Z[1] = {−1, 1}. Yksi on relaatiossa ykkösen ja miinus ykkösen kanssa, koska |1| = |−1|.
• Z[2] = {−2, 2}. Kaksi on relaatiossa kakkosen ja miinus kakkosen kanssa.
• Z[3] = {−3, 3}.
• …

Lienee selvää, miten tämä jatkuu. Koko ositus olisi siis luokkien joukko:

$$\{\{a,-a\}\mid a\in {\mathbb{Z}}_0^{+}\}$$

(Siis kaikki parit a, −a, joissa a on epänegatiivinen kokonaisluku.) Näet, että luokkia on äärettömän monta.