Bináris reláció halmazon

Halmazon értelmezett bináris relációnak azt a bináris relációt nevezzük, amelyet két azonos halmaz között definiálunk.

Példák

A halmazon értelmezett bináris reláció a bináris reláció speciális esete, amikor mindkét alaphalmaz ugyanaz. A halmazon értelmezett bináris reláció tehát olyan R reláció, amelyre R ⊆ M × M.

A „nagyobb, mint” reláció halmazon értelmezett bináris reláció, mert mindkét oldalon számokkal dolgozunk. Vagyis > ⊆ ℝ × ℝ. Az „apa – gyerekek száma” reláció nem halmazon értelmezett bináris reláció, mert az apát az összes ember halmazából választjuk, a gyerekek számát viszont valamilyen számhalmazból.

Tulajdonságok

Az M halmazon értelmezett R bináris relációnak lehetnek érdekes tulajdonságai. Azt mondjuk, hogy az R reláció…

• reflexív, ha minden a ∈ M esetén (a; a) ∈ R.
• szimmetrikus, ha minden a, b ∈ M esetén, ha (a; b) ∈ R, akkor (b; a) ∈ R is.
• antiszimmetrikus, ha minden a, b ∈ M esetén, ha (a; b) ∈ R és egyszerre (b; a) ∈ R is teljesül, akkor a = b.
• tranzitív, ha minden a, b, c ∈ M esetén, ha (a; b) ∈ R és egyszerre (b; c) ∈ R, akkor (a; c) is benne van R-ben.

Példák a reflexivitásra

A reflexivitás azt jelenti, hogy az elem önmagával relációban áll. Tipikus példa az egyenlőség. Ha a természetes számokon értelmezzük az egyenlőséget, akkor bármelyik a elemre biztosan igaz, hogy a = a. Másik példa az oszthatóság. Itt is igaz, hogy az a szám osztható önmagával, vagyis az (a; a) pár benne van az oszthatósági relációban (a hetes osztja a hetest).

A „kisebb, mint” reláció viszont már nem reflexív, mert nem igaz, hogy a < a. Ez nem lehetséges, a hetes nem lehet kisebb a hetesnél. Hasonlóan a „valakinek az apja” reláció: nem lehetek a saját apám. Az ilyen relációk nem reflexívek.

Fontos, hogy a reflexivitásnak minden elemre teljesülnie kell, nem elég néhányat találni. Vegyük például a „valakit kedvel” relációt. Kedvelhetek valakit, például a kalauzt, de kedvelhetem magamat is. Biztosan van olyan ember, aki kedveli saját magát. De ugyanígy van olyan is, aki saját magát nem kedveli. Az ilyen reláció tehát nem reflexív – minden embernek kedvelnie kellene önmagát.

Példák a szimmetriára

A szimmetrikus relációban, ha egy pár benne van a relációban, akkor az inverz pár is benne van. Ilyen például a testvérség. Ha Gergő testvére Annának, akkor Anna is testvére Gergőnek. A számrelációk közül ilyen lehet az „ellentettje” reláció. Ezen például a 2 és −2, vagy a −7 és 7 párokat értem. Ezek olyan számok, amelyek összege nulla. Ez a reláció szimmetrikus, mert a sorrend egyszerűen nem számít: (2; −2) és (−2; 2) is egymás ellentettjei, és összegük nulla.

Nem szimmetrikus a „kisebb, mint” reláció (a valós számokon). Ennek egyetlen eleme sem szimmetrikus, mert sosem teljesülhet egyszerre a < b és b < a. Ha 5 < 15, akkor nem lehet 15 < 5. Nem szimmetrikus a „valakinek az apja” reláció sem. Lehetsz a fiad apja, de akkor a fiad már nem lehet az apjának az apja.

Ennek a tulajdonságnak szintén minden esetben teljesülnie kell. Ha a „valakit kedvel” relációnak (az összes ember halmazán) szimmetrikusnak kellene lennie, akkor ha én kedvelem Kingát, akkor Kingának is kedvelnie kellene engem. És mivel engem nem is ismer, nem mondhatom, hogy kedvel, ami kár, és a reláció nem szimmetrikus. Ami szintén kár.

Példák az antiszimmetriára

Az antiszimmetrikus reláció klasszikus példája a „kisebb vagy egyenlő”. Az antiszimmetria azt mondja, hogy ha az (a; b) és a (b; a) elem is benne van a relációban, akkor csak úgy lehet, ha egyenlők, a = b. A „kisebb vagy egyenlő” reláció ezt teljesíti. Mikor igaz egyszerre a ≤ b és b ≤ a? Csak akkor, ha a = b. Helyettesítsünk be: igaz-e, hogy 3 ≤ 5 és egyszerre 5 ≤ 3? Nem. De igaz, hogy 4 ≤ 4 és egyszerre 4 ≤ 4.

Olyan reláció, amely nem antiszimmetrikus, lehet az azonos hosszúságú szavak párja, például (hétfő; balta). Ez a reláció azért nem antiszimmetrikus, mert találunk olyan szópárt, amely benne van a relációban, az inverz eleme is benne van, a két szó mégis különböző. Ott van az említett (hétfő; balta) elem és az inverze: (balta; hétfő). Mindkettő nyilván benne van a relációnkban, de hétfő ≠ balta, tehát a reláció nem antiszimmetrikus.

Példa a tranzitivitásra

Tranzitív a „kisebb, mint” reláció. A tranzitivitás azt mondja, hogy ha 3 < 4 és egyszerre 4 < 5, akkor biztosan igaz, hogy 3 < 5 is. Sok relációnál ez egészen természetes tulajdonság. Hasonlóan az azonos hosszúságú szavak példájánál. Ha relációban áll a (balta; hétfő) és relációban áll a (hétfő; hasáb), akkor a (balta; hasáb) szópár is relációban áll.

Nem tranzitív a „valakinek az apja” reláció. Ha Tamás Ferenc apja, Ferenc pedig Miklós apja, akkor Tamás nem apja Miklósnak, hanem a nagyapja. Hasonlóan nem tranzitív a „valakit kedvel” reláció. Ha kedvelem Kingát, Kinga pedig kedveli a férjét, ez nem jelenti azt, hogy én is kedvelem Kinga férjét.

A tranzitivitással a klasszikus dobókockáknál is foglalkoznak. Tegyük fel, hogy az A kocka jobb, mint a B kocka, ha az A kockán gyakrabban (nagyobb valószínűséggel) esik nagyobb szám, mint a B kockán. Tranzitív-e ez a reláció? Erre válaszol a nemtranzitív kockákról szóló cikk.

Ekvivalencia és rendezés

Néhány speciális bináris relációnak saját neve is van:

• Az ekvivalencia olyan reláció, amely reflexív, szimmetrikus és tranzitív.
• A rendezés olyan reláció, amely reflexív, antiszimmetrikus és tranzitív.