Binær relation

En binær relation er en særlig type relation med aritet to. Typiske binære relationer er for eksempel mindre end, lighed, delelighed, større end osv.

Eksempler

En binær relation er en af de typiske og almindeligt forekommende relationer. Samtidig har den nogle interessante egenskaber, som vi beskriver her.

Et eksempel på en binær relation kan være: forholdet »far — søn«, parret »transportmiddel — antal hjul« eller den mere generelle »objekt — objektets egenskab«. Objektet kan være et dyr og egenskaben antal ben, gennemsnitlig levetid, antal hår på hovedet og lignende.

En binær relation R mellem mængderne M₁ og M₂ kan vi definere således: R ⊆ M₁ × M₂. En binær relation er således en mængde af par, hvor denne mængde er en delmængde af mængdeproduktet af de to mængder, som vi indfører relationen mellem. Relationen »far — søn« kan altså være en relation mellem mængden af alle mennesker, mellem mængden af alle mennesker i Europa eller i København. Vi kan også begrænse mængden i en anden retning, vi kan sige, at vi definerer relationen mellem mængden af alle mænd og ikke mennesker generelt.

For binære relationer bruger vi sædvanligvis en særlig notation. I stedet for at skrive (a, b) ∈ R kan vi skrive aRb. For eksempel kan vi i stedet for (3, 1) ∈ > skrive 3 > 1. På samme måde for andre relationer. Notationen aSb er altså ensbetydende med notationen (a, b) ∈ S.

Invers relation

En invers relation er den omvendte relation til den nuværende relation. (Pas på, den må ikke forveksles med komplementet til en relation.) Hvad er den omvendte relation til relationen mindre end? Større end. Hvis relationen mindre end indeholder elementet (4, 7), altså 4 < 7, så er det inverse element det omvendte: 7 > 4, i den inverse relation vil der være det inverse par (7, 4).

Hvis vi har relationen R ⊆ M₁ × M₂, danner vi den inverse relation R⁻¹ ved at tage alle elementer (a, b) ∈ R og lægge deres inverse ind i R⁻¹. Hvis relationen R altså indeholder elementet (a, b), skal relationen R⁻¹ indeholde elementet (b, a). Det gælder også omvendt: hvis R⁻¹ indeholder elementet (b, a), skal relationen R indeholde elementet (a, b).

Hvis vi skulle definere det, så er relationen R⁻¹ invers til R, netop når der gælder:

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

Der gælder altså, at 6 < 8 netop når 8 > 6. På samme måde for andre par.

Sammensætning af relationer

Binære relationer kan vi sætte sammen med hinanden. Lad os have to relationer, den første, R, bliver »at være far til sin søn«, og den anden, S, »at være bror til sin søster«. Relationen R indeholder altså par (far, søn), den anden relation indeholder par (bror, søster).

Nu prøver vi at sætte relationerne sammen. Der opstår en ny relation, vi kalder den R ∘ S, og denne relation indeholder elementet (a, c) netop når (a, b) ∈ R og samtidig (b, c) ∈ S. Læg mærke til, at b forekommer i begge elementer, én gang på anden plads og så på første plads i parret. Det er et slags forbindelseselement i sammensætningen.

Eksempel: R = {(Torben, Mads), (Peter, Jakob)} og S = {(Mads, Julie), (Mads, Laura), (Jakob, Lise)}. Torben er far til Mads, Peter er far til Jakob. Mads har søstrene Julie og Laura, og Jakob har søsteren Lise.

Nu sætter vi relationerne sammen: R ∘ S. Vi leder efter et par fra R, som på sønnens plads har en, der er opført som bror i relationen S. For eksempel disse to par: (Torben, Mads) og (Mads, Julie). Mads er forbindelseselementet, det har vi ikke brug for længere, og af de resterende navne danner vi et nyt par: (Torben, Julie). Relationen R ∘ S indeholder altså parret (Torben, Julie). Mads har endnu en søster, Laura, hende tilføjer vi også til den sammensatte relation: (Torben, Laura). Til sidst er der sønnen Jakob. Han har søsteren Lise. Så vi har to par: (Peter, Jakob) og (Jakob, Lise). Dermed danner vi endnu et element: (Peter, Lise).

Resultatet er relationen: R ∘ S = {(Torben, Julie), (Torben, Laura), (Peter, Lise)}. Hvad kunne vi kalde denne relation? Sandsynligvis »at være far til sin datter«.

Endnu en gang hele definitionen:

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

Bemærkning: nogle gange bruges den omvendte notation, det vil sige, at man for den samme definition ville bruge S ∘ R i stedet for R ∘ S.