Binäärirelaatio joukossa

Binäärirelaatiolla joukossa tarkoitetaan kahden saman joukon välille määriteltyä binäärirelaatiota.

Esimerkkejä

Binäärirelaatio joukossa on erityinen binäärirelaatiotyyppi, jossa molemmat perusjoukot ovat samat. Binäärirelaatio joukossa on siis relaatio R, jolle R ⊆ M × M.

Relaatio ”suurempi kuin” on binäärirelaatio joukossa, koska molemmilla puolilla käsitellään lukuja. Pätee siis > ⊆ ℝ × ℝ. Relaatio ”isä – lasten lukumäärä” ei ole binäärirelaatio joukossa, koska isä valitaan kaikkien ihmisten joukosta, mutta lasten lukumäärä valitaan jostakin lukujoukosta.

Ominaisuudet

Joukon M binäärirelaatiolla R voi olla joitakin mielenkiintoisia ominaisuuksia. Sanotaan, että relaatio R on…

• refleksiivinen, jos kaikille a ∈ M pätee (a, a) ∈ R.
• symmetrinen, jos kaikille a, b ∈ M pätee, että jos (a, b) ∈ R, niin myös (b, a) ∈ R.
• antisymmetrinen, jos kaikille a, b ∈ M pätee, että jos (a, b) ∈ R ja samalla myös (b, a) ∈ R, niin a = b.
• transitiivinen, jos kaikille a, b, c ∈ M pätee, että jos (a, b) ∈ R ja samalla (b, c) ∈ R, niin myös (a, c) kuuluu relaatioon R.

Esimerkkejä refleksiivisyydestä

Refleksiivisyys tarkoittaa, että alkio on relaatiossa itsensä kanssa. Tyypillinen esimerkki on yhtäsuuruus. Jos yhtäsuuruus on määritelty luonnollisilla luvuilla, varmasti pätee, että mille tahansa alkiolle a: a = a. Toinen esimerkki voi olla jaollisuus. Siinäkin luku a on jaollinen itsellään, eli pari (a, a) kuuluu jaollisuusrelaatioon (seitsemän jakaa seitsemän).

Relaatio pienempi kuin ei kuitenkaan ole refleksiivinen, koska ei päde a < a. Se ei ole mahdollista, seitsemän ei voi olla pienempi kuin seitsemän. Samoin relaatio olla lapsensa isä – en voi olla oma isäni. Tällaiset relaatiot eivät ole refleksiivisiä.

Tärkeää on, että refleksiivisyyden täytyy päteä kaikille alkioille, ei riitä löytää vain joitakin. Esimerkiksi relaatio ”pitää jostakusta”. Voin pitää toisaalta jostakusta, vaikkapa lipuntarkastajasta, mutta voin pitää myös itsestäni. Varmasti löytyy ihminen, joka pitää itsestään. Mutta yhtä lailla löytyy ihminen, joka ei pidä itsestään. Tällainen relaatio ei silloin ole refleksiivinen – kaikkien ihmisten pitäisi pitää itsestään.

Esimerkkejä symmetrisyydestä

Symmetrisessä relaatiossa pätee, että jos relaatiossa on jokin pari, siinä on myös käänteinen pari. Esimerkiksi relaatio olla sisarus. Jos Leevi on Ellan sisarus, myös Ella on Leevin sisarus. Lukurelaatioista esimerkiksi voisi olla relaatio ”olla vastaluku”. Tarkoitan lukupareja 2 ja −2 tai −7 ja 7. Ne ovat sellaiset kaksi lukua, joiden summa on nolla. Tällainen relaatio on symmetrinen, koska järjestyksellä ei yksinkertaisesti ole väliä: (2, −2) ja (−2, 2) ovat edelleen toistensa vastalukuja ja summaltaan nolla.

Relaatio, joka ei ole symmetrinen, on pienempi kuin (reaaliluvuilla). Sillä ei ole yhtään symmetristä alkiota, koska ei voi koskaan päteä a < b ja samalla b < a. Jos 5 < 15, ei voi päteä 15 < 5. Lisäksi relaatio ”olla poikansa isä” ei ole symmetrinen. Voit olla poikasi isä, mutta silloin poika ei enää voi olla isänsä isä.

Tämän ominaisuuden täytyy taas päteä kaikissa tapauksissa. Jos relaation ”pitää jostakusta” (kaikkien ihmisten joukossa) pitäisi olla symmetrinen, niin jos minä pidän Ainosta, myös Ainon täytyisi pitää minusta. Ja koska Aino ei edes tunne minua, en voi sanoa, että hän pitää minusta, mikä on harmi, ja relaatio ei ole symmetrinen. Mikä on myös harmi.

Esimerkkejä antisymmetrisyydestä

Klassinen esimerkki antisymmetrisestä relaatiosta on pienempi tai yhtä suuri kuin. Antisymmetrisyys kertoo, että jos parit (a, b) ja (b, a) ovat relaatiossa, niin vain siinä tapauksessa, että alkiot ovat yhtä suuret, a = b. Relaatio pienempi tai yhtä suuri kuin täyttää tämän. Milloin pätee a ≤ b ja samalla b ≤ a? Vain silloin, kun a = b. Sijoitetaan: pätevätkö 3 ≤ 5 ja samalla 5 ≤ 3? Ei. Mutta pätevät 4 ≤ 4 ja samalla 4 ≤ 4.

Esimerkki relaatiosta, joka ei ole antisymmetrinen, voivat olla sanaparit, joilla on sama pituus, esimerkiksi (puisto, kirves). Tällainen relaatio ei ole antisymmetrinen, koska löydetään sanapari, joka on relaatiossa, sen käänteisalkio on myös relaatiossa ja silti molemmat sanat ovat eri sanoja. Eli jo mainittu alkio (puisto, kirves) ja sen käänteinen: (kirves, puisto). Molemmat ovat selvästi tässä relaatiossa, mutta silti puisto ≠ kirves, joten relaatio ei ole antisymmetrinen.

Esimerkki transitiivisuudesta

Transitiivinen on relaatio pienempi kuin. Transitiivisuus kertoo, että jos 3 < 4 ja samalla 4 < 5, niin silloin varmasti pätee myös 3 < 5. Monelle relaatiolle se on melko luonnollinen ominaisuus. Samoin sanojen samaa pituutta koskevassa esimerkissä. Jos relaatiossa on (kirves, puisto) ja relaatiossa on (puisto, lattia), relaatiossa ovat myös sanat (kirves, lattia).

Transitiivinen ei ole relaatio olla pojan isä. Jos Väinö on Onnin isä ja Onni on Einon isä, Väinö ei ole Einon isä, vaan isoisä. Samoin relaatio pitää jostakusta ei ole transitiivinen. Jos pidän Ainosta ja Aino pitää aviomiehestään, se ei tarkoita, että minäkin pidän Ainon aviomiehestä.

Transitiivisuutta pohditaan myös tavallisten pelinoppien yhteydessä. Tarkastellaan relaatiota: noppa A on parempi kuin noppa B, jos nopalla A tulee useammin (suuremmalla todennäköisyydellä) suurempi luku kuin nopalla B. Onko tällainen relaatio transitiivinen? Siihen vastaa artikkeli ei-transitiiviset nopat.

Ekvivalenssi ja järjestys

Joillakin erityisillä binäärirelaatiotyypeillä on omat nimensäkin:

• Ekvivalenssirelaatio on relaatio, joka on refleksiivinen, symmetrinen ja transitiivinen.
• Järjestysrelaatio on relaatio, joka on refleksiivinen, antisymmetrinen ja transitiivinen.