Bináris reláció

A bináris reláció olyan speciális reláció, amelynek aritása kettő. Tipikus bináris relációk például a „kisebb, mint”, az egyenlőség, az oszthatóság, a „nagyobb, mint” és hasonlók.

Példák

A bináris reláció a tipikus, gyakran előforduló relációk egyike. Van néhány érdekes tulajdonsága, ezeket most bemutatjuk.

Bináris reláció például az „apa – fia” kapcsolat, a „közlekedési eszköz – kerekek száma” páros, vagy az általánosabb „objektum – az objektum tulajdonsága”. Az objektum lehet egy állat, a tulajdonság pedig a lábak száma, az átlagos élettartam, a fején lévő szőrszálak száma és így tovább.

Az R bináris relációt az M₁ és M₂ halmaz között így definiálhatjuk: R ⊆ M₁ × M₂. A bináris reláció tehát párok halmaza, mégpedig a két halmaz Descartes-szorzatának részhalmaza, amely halmazok között a relációt bevezetjük. Az „apa – fia” reláció így lehet reláció az összes ember halmaza között, az összes európai ember halmaza között, vagy akár a budapestiek között. A halmazt más irányban is szűkíthetjük: mondhatjuk, hogy a relációt az összes férfi halmaza között értelmezzük, nem az emberek között általában.

A bináris relációkhoz általában külön jelölést használunk. Ahelyett, hogy (a; b) ∈ R-t írnánk, írhatjuk, hogy aRb. Például (3; 1) ∈ > helyett írhatjuk, hogy 3 > 1. Hasonlóan a többi relációnál. Az aSb felírás tehát egyenértékű az (a; b) ∈ S felírással.

Inverz reláció

Az inverz reláció az adott relációval ellentétes reláció. (Vigyázat, ne keverd össze a reláció komplementerével.) Mi a „kisebb, mint” reláció ellentéte? A „nagyobb, mint”. Ha a „kisebb, mint” reláció tartalmazza a (4; 7) elemet, azaz 4 < 7, akkor az inverz elem az ellentétes lesz: 7 > 4, az inverz relációban tehát az inverz pár a (7; 4).

Ha adott az R ⊆ M₁ × M₂ reláció, az R⁻¹ inverz relációt úgy kapjuk, hogy vesszük az összes (a; b) ∈ R elemet, és az R⁻¹-be az inverzüket tesszük. Ha tehát az R reláció tartalmazza az (a; b) elemet, akkor az R⁻¹ reláció tartalmazza a (b; a) elemet. Ez fordítva is igaz: ha R⁻¹ tartalmazza a (b; a) elemet, akkor az R relációnak tartalmaznia kell az (a; b) elemet.

Definícióval megfogalmazva: az R⁻¹ reláció akkor és csak akkor inverze az R-nek, ha teljesül:

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

Eszerint 6 < 8 akkor és csak akkor, ha 8 > 6. Hasonlóan a többi párra.

Relációk összetétele

A bináris relációkat összetehetjük egymással. Legyen két reláció: az első, R, legyen „valakinek az apja”, a második, S pedig „fiútestvére valakinek”. Az R reláció tehát (apa; fiú) párokat tartalmaz, a második reláció (fiútestvér; lánytestvér) párokat.

Most próbáljuk meg összetenni a két relációt. Új relációt kapunk, jelöljük R ∘ S-sel, és ez az (a; c) elemet pontosan akkor tartalmazza, ha (a; b) ∈ R és egyszerre (b; c) ∈ S. Figyeld meg, hogy mindkét elemben szerepel b, egyszer a pár második, egyszer az első helyén. Ez az összetétel összekötő eleme.

Példa: R = {(Tamás; Márk), (Péter; Zoltán)} és S = {(Márk; Anna), (Márk; Lilla), (Zoltán; Luca)}. Tamás Márk apja, Péter Zoltán apja. Márknak két lánytestvére van, Anna és Lilla, Zoltánnak pedig egy, Luca.

Most összetesszük a relációkat: R ∘ S. Olyan párt keresünk R-ből, amelynek a fiú helyén olyasvalaki áll, aki S-ben fiútestvérként szerepel. Például ez a két pár: (Tamás; Márk) és (Márk; Anna). Márk az összekötő elem, ezt tovább nem használjuk, a megmaradt nevekből pedig új párt készítünk: (Tamás; Anna). Az R ∘ S reláció tehát tartalmazza a (Tamás; Anna) párt. Márknak van még egy lánytestvére, Lilla, őt is hozzáadjuk az összetett relációhoz: (Tamás; Lilla). Végül marad a fiú, Zoltán. Neki van egy lánytestvére, Luca. Két párunk van tehát: (Péter; Zoltán) és (Zoltán; Luca). Ezekből újabb elem lesz: (Péter; Luca).

Az eredmény a reláció: R ∘ S = {(Tamás; Anna), (Tamás; Lilla), (Péter; Luca)}. Hogyan nevezhetnénk el ezt a relációt? Valószínűleg „apja a lányának”.

Még egyszer a teljes definíció:

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

Megjegyzés: néha fordított jelölést használnak, vagyis ugyanarra a definícióra R ∘ S helyett S ∘ R-t írnak.