Ekvivalenssirelaatio

Joukon ${\displaystyle M}$ alkioiden välillä määritelty relaatio ${\displaystyle \operatorname {R} }$ on ekvivalenssirelaatio, jos se toteuttaa seuraavat kolme ehtoa:

1. ${\displaystyle a\operatorname {R} a}$.
2. Jos ${\displaystyle a\operatorname {R} b}$, niin myös ${\displaystyle b\operatorname {R} a}$.
3. Jos ${\displaystyle a\operatorname {R} b}$ ja ${\displaystyle b\operatorname {R} c}$, niin ${\displaystyle a\operatorname {R} c}$.^[1]

Ensimmäistä ominaisuutta sanotaan refleksiivisyydeksi, toista symmetrisyydeksi ja kolmatta transitiivisuudeksi. Jokin yksittäinen määritelty relaatio eli suhde joukon alkioiden välillä on ekvivalenssi, jos se on refleksiivinen, symmetrinen ja transitiivinen.

Esimerkiksi yhtäsuuruus reaalilukujen joukossa on selvästikin ekvivalenssirelaatio, koska se toteuttaa varmasti kaikki kolme ekvivalenttisuuden ehtoa.

Toinen esimerkki: Määritellään relaatio ${\displaystyle |}$ reaalilukujen välillä siten että ${\displaystyle a|b}$ jos ${\displaystyle a-b}$ on kokonaisluku. ${\displaystyle |}$ on refleksiivinen, koska ${\displaystyle a-a=0}$ on kokonaisluku. Jos ${\displaystyle a|b}$ eli ${\displaystyle a-b}$ on kokonaisluku, niin myös ${\displaystyle b-a}$ on kokonaisluku eli ${\displaystyle b|a}$, joten ${\displaystyle |}$ on symmetrinen. Myös jos ${\displaystyle a|b}$ ja ${\displaystyle b|c}$, niin ${\displaystyle a-b}$ ja ${\displaystyle b-c}$ ovat kokonaislukuja eli myös ${\displaystyle a-c}$ on kokonaisluku. Tällöin ${\displaystyle a|c}$ ja ${\displaystyle |}$ on transitiivinen. Kaikki kolme ehtoa ovat ${\displaystyle |}$:lle voimassa, joten ${\displaystyle |}$ on ekvivalenssirelaatio.

Kolmas esimerkki: Oppilaat a, b ja c kuuluvat samalle koululuokalle (relaatio ${\displaystyle R}$ on täten "kuuluu samalle luokalle"). Tällöin kukin oppilas on itsensä kanssa samalla luokalla (refleksiivisyys), jos henkilö a on b:n kanssa samalla luokalla, myös b on a:n kanssa samalla luokalla (symmetrisyys) ja kolmanneksi, jos a on b:n kanssa samalla luokalla, ja b c:n kanssa, pätee transitiivinen riippuvuus, eli myös a on c:n kanssa samalla luokalla.

Ekvivalenssirelaatio muodostaa joukon alkioista ekvivalenssiluokkia, joissa kaikki keskenään ekvivalentit alkiot kuuluvat samaan luokkaan. Esimerkiksi luvun ${\displaystyle 5/7}$ muodostaman luokan kaikki jäsenet ovat muotoa ${\displaystyle 5/7+n}$, missä n on kokonaisluku.

Ekvivalenssiluokat voidaan myös esittää edustajien avulla. Esimerkiksi edellä määritellyssä relaatiolla ${\displaystyle |}$ jokainen luokka voidaan valita edustettavaksi luvulla puoliavoimelta väliltä [0,1). Kaikki reaaliluvut ovat tällöin ekvivalentteja jonkin tämän välin luvun kanssa.

Ekvivalenssirelaatiota joukossa X vastaa aina tietty joukon X ositus (jako erillisiin osajoukkoihin). Vastaavasti, jos X:ssä on annettu ositus, sen avulla voidaan määrittää ekvivalenssirelaatio. Tätä keskeistä yhteyttä kutsutaan ekvivalenssirelaatioiden peruslauseeksi.

• Merikoski, Jorma; Virtanen, Ari; Koivisto, Pertti: Diskreetti matematiikka I. Tampere: Tampereen yliopisto, 2001 (1993). ISBN 951-44-3604-0
• Lipschutz, Seymour: Set Theory and Related Topics. McGraw-Hill, 1964. ISBN 0070379866