Binär relation på en mängd

Med en binär relation på en mängd menar vi en binär relation som är definierad mellan två lika mängder.

Exempel

En binär relation på en mängd är en speciell sorts binär relation där båda underliggande mängderna är desamma. En binär relation på en mängd är alltså en relation R sådan att R ⊆ M × M.

Relationen ”större än” är en binär relation på en mängd, eftersom vi arbetar med tal på båda sidor. Det gäller alltså att > ⊆ ℝ × ℝ. Relationen ”pappa — antal barn” är inte en binär relation på en mängd, eftersom papporna väljs ur mängden av alla människor, medan antalet barn väljs ur någon talmängd.

Egenskaper

En binär relation R på en mängd M kan ha några intressanta egenskaper. Vi säger att relationen R är…

• reflexiv, om det för alla a ∈ M gäller att (a, a) ∈ R.
• symmetrisk, om det för alla a, b ∈ M gäller att om (a, b) ∈ R, så även (b, a) ∈ R.
• antisymmetrisk, om det för alla a, b ∈ M gäller att om (a, b) ∈ R och samtidigt (b, a) ∈ R, så är a = b.
• transitiv, om det för alla a, b, c ∈ M gäller att om (a, b) ∈ R och samtidigt (b, c) ∈ R, så ligger även (a, c) i R.

Exempel på reflexivitet

Reflexivitet betyder att ett element står i relation till sig självt. Ett typiskt exempel är likhet. Om vi har definierat likhet på de naturliga talen, så gäller det förstås för varje element a att a = a. Ett annat exempel är delbarhet. Där gäller återigen att talet a är delbart med sig självt, alltså att paret (a, a) ligger i delbarhetsrelationen (sju delar sju).

Relationen mindre än är däremot inte reflexiv, eftersom a < a inte gäller. Det är inte möjligt, sju kan inte vara mindre än sju. På samma sätt med relationen att vara pappa till sitt barn — jag kan inte vara min egen pappa. Sådana relationer är inte reflexiva.

Det viktiga är att reflexiviteten måste gälla för alla element, det räcker inte att hitta några. Ta till exempel relationen ”att gilla någon”. Jag kan gilla någon annan, till exempel en biljettkontrollant, men jag kan också gilla mig själv. Det finns säkert människor som gillar sig själva. Men det finns lika säkert människor som inte gillar sig själva. En sådan relation är då inte reflexiv — alla människor skulle behöva gilla sig själva.

Exempel på symmetri

För en symmetrisk relation gäller att om ett par ligger i relationen, så ligger också det omvända paret i relationen. Ett exempel är relationen att vara syskon. Om Oscar är syskon till Maja, så är Maja också syskon till Oscar. Bland talrelationer kan vi ta relationen ”att vara varandras motsatta tal”. Med det menar jag paren 2 och −2 eller −7 och 7. Det är två tal som har summan noll. En sådan relation är symmetrisk, eftersom ordningen helt enkelt inte spelar någon roll: (2, −2) och (−2, 2) är fortfarande varandras motsatta tal och har summan noll.

En relation som inte är symmetrisk är mindre än (över de reella talen). Den har inte ett enda symmetriskt par, eftersom a < b och b < a aldrig kan gälla samtidigt. Om 5 < 15, så kan inte 15 < 5 gälla. Inte heller är relationen ”att vara pappa till sin son” symmetrisk. Du kan vara pappa till din son, men då kan sonen inte vara pappa till sin pappa.

Även den här egenskapen måste gälla i alla fall. Om relationen ”att gilla någon” (på mängden av alla människor) ska vara symmetrisk, så skulle det, om jag gillar Elsa, samtidigt behöva gälla att Elsa gillar mig. Och eftersom hon inte ens känner mig, kan jag inte säga att hon gillar mig, vilket är synd, och relationen är inte symmetrisk. Vilket också är synd.

Exempel på antisymmetri

Ett klassiskt exempel på en antisymmetrisk relation är mindre än eller lika med. Antisymmetri säger oss att om paren (a, b) och (b, a) båda ligger i relationen, så kan det bara vara när elementen är lika, a = b. Relationen mindre än eller lika med uppfyller detta. När gäller a ≤ b och samtidigt b ≤ a? Bara om a = b. Vi kan prova att sätta in tal: gäller 3 ≤ 5 och samtidigt 5 ≤ 3? Nej. Men 4 ≤ 4 och samtidigt 4 ≤ 4 gäller.

Ett exempel på en relation som inte är antisymmetrisk är par av ord som har lika många bokstäver, till exempel (tisdag, hammar). Relationen är inte antisymmetrisk, eftersom vi hittar ett par av ord som ligger i relationen, vars omvända par också ligger i relationen, och där orden ändå är olika. Alltså paret (tisdag, hammar) och dess omvända par (hammar, tisdag). Båda ligger uppenbarligen i vår relation, men ändå är tisdag ≠ hammar, så relationen är inte antisymmetrisk.

Exempel på transitivitet

Relationen mindre än är transitiv. Transitivitet säger att om 3 < 4 och samtidigt 4 < 5, så måste förstås också 3 < 5 gälla. För många relationer är det en ganska naturlig egenskap. Likadant för exemplet med ord av samma längd. Om (hammar, tisdag) ligger i relationen och (tisdag, blomma) ligger i relationen, så ligger också orden (hammar, blomma) i relationen.

Relationen att vara pappa till är inte transitiv. Om Lucas är pappa till Oscar och Oscar är pappa till William, så är Lucas inte pappa till William, han är farfar. På samma sätt är relationen att gilla någon inte transitiv. Om jag gillar Elsa och Elsa gillar sin man, så betyder det inte att jag också gillar Elsas man.

Transitivitet är också en fråga för vanliga tärningar. Anta att vi har relationen tärning A är bättre än tärning B, om det på tärning A oftare (med större sannolikhet) kommer upp ett högre tal än på tärning B. Är en sådan relation transitiv? Det svarar artikeln icke-transitiva tärningar på.

Ekvivalens och ordning

Några speciella typer av binära relationer har egna namn:

• En ekvivalensrelation är en relation som är reflexiv, symmetrisk och transitiv.
• En ordningsrelation är en relation som är reflexiv, antisymmetrisk och transitiv.