Binäärirelaatio

Binäärirelaatio on erityinen relaatiotyyppi, jonka aariteetti on kaksi. Tyypillisiä binäärirelaatioita ovat esimerkiksi pienempi kuin, yhtäsuuruus, jaollisuus, suurempi kuin jne.

Esimerkkejä

Binäärirelaatio on yksi tyypillisistä ja yleisesti esiintyvistä relaatioista. Samalla sillä on joitakin mielenkiintoisia ominaisuuksia, jotka kuvataan tässä.

Esimerkki binäärirelaatiosta voi olla suhde ”isä – poika”, pari ”kulkuneuvo – pyörien lukumäärä” tai yleisempi ”olio – olion ominaisuus”. Olio voi olla eläin ja ominaisuus jalkojen lukumäärä, keskimääräinen elinikä, päässä olevien hiusten lukumäärä ja niin edelleen.

Joukkojen M₁ ja M₂ välisen binäärirelaation R voi määritellä näin: R ⊆ M₁ × M₂. Binäärirelaatio on siis parien joukko, ja tämä joukko on niiden kahden joukon karteesisen tulon osajoukko, joiden välille relaatio määritellään. Relaatio ”isä – poika” voi siis olla relaatio kaikkien ihmisten joukossa, kaikkien Euroopan tai Helsingin ihmisten joukossa. Joukkoa voi rajata myös toiseen suuntaan: voidaan sanoa, että relaatio määritellään kaikkien miesten joukossa, ei ihmisten yleensä.

Binäärirelaatioille käytetään yleensä erityistä merkintää. Sen sijaan, että kirjoitettaisiin (a, b) ∈ R, voidaan kirjoittaa aRb. Esimerkiksi merkinnän (3, 1) ∈ > sijaan voidaan kirjoittaa 3 > 1. Samoin muille relaatioille. Merkintä aSb on siis yhtäpitävä merkinnän (a, b) ∈ S kanssa.

Käänteisrelaatio

Käänteisrelaatio on annetulle relaatiolle vastakkainen relaatio. (Huomaa, ettei sitä saa sekoittaa relaation komplementtiin.) Mikä on relaation pienempi kuin vastakkainen relaatio? Suurempi kuin. Jos relaatio pienempi kuin sisältää alkion (4, 7), eli 4 < 7, käänteinen alkio on päinvastainen: 7 > 4, käänteisrelaatiossa on käänteinen pari (7, 4).

Jos R ⊆ M₁ × M₂ on relaatio, käänteisrelaatio R⁻¹ muodostetaan ottamalla kaikki alkiot (a, b) ∈ R ja lisäämällä relaatioon R⁻¹ niiden käänteiset. Jos siis relaatio R sisältää alkion (a, b), relaation R⁻¹ täytyy sisältää alkio (b, a). Se pätee myös toisin päin: jos R⁻¹ sisältää alkion (b, a), relaation R täytyy sisältää alkio (a, b).

Määriteltynä relaatio R⁻¹ on relaation R käänteisrelaatio täsmälleen silloin, kun pätee:

$$\mathrm{\forall }a\in M_1\mathrm{\forall }b\in M_2:(a,b)\in R\iff (b,a)\in R^{-1}$$

Pätee siis 6 < 8 täsmälleen silloin, kun 8 > 6. Samoin muille pareille.

Relaatioiden yhdistäminen

Binäärirelaatioita voi yhdistää keskenään. Olkoot kaksi relaatiota, ensimmäinen, R, ”olla poikansa isä” ja toinen, S, ”olla sisarensa veli”. Relaatio R sisältää siis parit (isä, poika) ja toinen relaatio parit (veli, sisko).

Yritetään nyt yhdistää relaatiot. Syntyy uusi relaatio, merkitään sitä R ∘ S, ja tämä relaatio sisältää alkion (a, c) täsmälleen silloin, kun (a, b) ∈ R ja samalla (b, c) ∈ S. Huomaa, että b esiintyy molemmissa alkioissa, kerran parin toisella paikalla ja sitten parin ensimmäisellä paikalla. Se on yhdistämisen eräänlainen liitosalkio.

Esimerkki: R = {(Väinö, Onni), (Eino, Leevi)} ja S = {(Onni, Aino), (Onni, Helmi), (Leevi, Emma)}. Väinö on Onnin isä, Eino on Leevin isä. Onnilla on sisaret Aino ja Helmi ja Leevillä on sisko Emma.

Nyt yhdistetään relaatiot: R ∘ S. Etsitään sellainen pari relaatiosta R, jonka poikapaikalla on joku, joka on veljenä relaatiossa S. Esimerkiksi nämä kaksi paria: (Väinö, Onni) ja (Onni, Aino). Onni on liitosalkio, sitä ei enää tarvita, ja jäljelle jääneistä nimistä muodostetaan uusi pari: (Väinö, Aino). Relaatio R ∘ S sisältää siis parin (Väinö, Aino). Onnilla on vielä yksi sisko, Helmi, hänetkin lisätään yhdistettyyn relaatioon: (Väinö, Helmi). Lopuksi jää poika Leevi. Hänellä on sisko Emma. Saadaan siis kaksi paria: (Eino, Leevi) ja (Leevi, Emma). Niistä syntyy toinen alkio: (Eino, Emma).

Tuloksena on relaatio: R ∘ S = {(Väinö, Aino), (Väinö, Helmi), (Eino, Emma)}. Miten tämän relaation voisi nimetä? Todennäköisesti ”olla tyttärensä isä”.

Vielä kerran koko määritelmä:

$$(a,c)\in (R\circ S)\iff \mathrm{\exists }b(a,b)\in R\wedge (b,c)\in S$$

Huomautus: joskus käytetään päinvastaista merkintää, eli samalle määritelmälle käytettäisiin merkinnän R ∘ S sijaan merkintää S ∘ R.