Binær relation på en mængde

Ved en binær relation på en mængde forstår vi en binær relation defineret mellem to ens mængder.

Eksempler

En binær relation på en mængde er en særlig type binær relation, hvor begge underliggende mængder er ens. En binær relation på en mængde er altså en relation R, så R ⊆ M × M.

Relationen »større end« er en binær relation på en mængde, fordi vi på begge sider arbejder med tal. Der gælder altså, at > ⊆ ℝ × ℝ. Relationen »far — antal børn« er ikke en binær relation på en mængde, fordi vi udvælger faren fra mængden af alle mennesker, mens vi udvælger antallet af børn fra en talmængde.

Egenskaber

En binær relation R på en mængde M kan have nogle interessante egenskaber. Vi siger, at relationen R er…

• refleksiv, hvis der for alle a ∈ M gælder, at (a, a) ∈ R.
• symmetrisk, hvis der for alle a, b ∈ M gælder, at hvis (a, b) ∈ R, så er også (b, a) ∈ R.
• antisymmetrisk, hvis der for alle a, b ∈ M gælder, at hvis (a, b) ∈ R og samtidig også (b, a) ∈ R, så er a = b.
• transitiv, hvis der for alle a, b, c ∈ M gælder, at hvis (a, b) ∈ R og samtidig (b, c) ∈ R, så er også (a, c) i R.

Eksempler på refleksivitet

Refleksivitet betyder, at et element er i relation med sig selv. Et typisk eksempel er lighed. Hvis vi har defineret lighed på de naturlige tal, så gælder det helt sikkert, at a = a for ethvert element a. Et andet eksempel kan være delelighed. Her gælder det igen, at tallet a er deleligt med sig selv, altså er parret (a, a) i delelighedsrelationen (syv går op i syv).

Relationen mindre end er derimod ikke refleksiv, fordi det ikke gælder, at a < a. Det er ikke muligt, syv kan ikke være mindre end syv. På samme måde relationen at være far til sit barn — jeg kan ikke være min egen far. Sådanne relationer er ikke refleksive.

Det er vigtigt, at refleksivitet skal gælde for alle elementer, det er ikke nok at finde nogle få. For eksempel relationen »at kunne lide nogen«. Jeg kan dels kunne lide en anden, for eksempel en kontrollør, men jeg kan også kunne lide mig selv. Der findes helt sikkert et menneske, som kan lide sig selv. Men der findes lige så vel et menneske, som ikke kan lide sig selv. En sådan relation er så ikke refleksiv — alle mennesker skulle kunne lide sig selv.

Eksempler på symmetri

For en symmetrisk relation gælder, at hvis et par er i relationen, så er det inverse par også i relationen. For eksempel relationen at være søskende. Hvis Oscar er søskende til Ida, så er Ida også søskende til Oscar. Af talrelationer kunne det være relationen »at være det modsatte tal«. Med det mener jeg parrene 2 og −2 eller −7 og 7. Det er sådanne to tal, der giver nul som sum. En sådan relation er symmetrisk, fordi rækkefølgen simpelthen er ligegyldig: (2, −2) og (−2, 2) er stadig hinandens modsatte tal og giver nul som sum.

En relation, som ikke er symmetrisk, er mindre end (over de reelle tal). Den har ikke et eneste symmetrisk element, fordi a < b og samtidig b < a aldrig kan gælde. Hvis 5 < 15, så kan 15 < 5 ikke gælde. Desuden er relationen »at være far til sin søn« ikke symmetrisk. Du kan være far til din søn, men så kan sønnen ikke være far til sin far.

Denne egenskab skal igen gælde i alle tilfælde. Hvis relationen »at kunne lide nogen« (på mængden af alle mennesker) skal være symmetrisk, så skulle Sofie Madsen, hvis jeg kan lide hende, samtidig kunne lide mig. Og fordi hun ikke engang kender mig, kan jeg ikke sige, at hun kan lide mig, hvilket er ærgerligt, og relationen er ikke symmetrisk. Hvilket også er ærgerligt.

Eksempler på antisymmetri

Et klassisk eksempel på en antisymmetrisk relation er mindre end eller lig med. Antisymmetri fortæller os, at hvis elementerne (a, b) og (b, a) er i relationen, så må de være ens, a = b. Relationen mindre end eller lig med opfylder det. Hvornår gælder a ≤ b og samtidig b ≤ a? Kun hvis a = b. Når vi sætter ind: gælder 3 ≤ 5 og samtidig 5 ≤ 3? Nej. Men 4 ≤ 4 og samtidig 4 ≤ 4 gælder.

Et eksempel på en relation, der ikke er antisymmetrisk, kan være par af ord, der har samme længde, for eksempel (lørdag, hammer). En sådan relation er ikke antisymmetrisk, fordi vi finder et par af ord, som er i relationen, deres inverse element er også i relationen, og alligevel er de to ord forskellige. Altså det nævnte element (lørdag, hammer) og dets inverse: (hammer, lørdag). Begge er åbenbart i vores relation, men alligevel er lørdag ≠ hammer, så relationen er ikke antisymmetrisk.

Eksempel på transitivitet

Relationen mindre end er transitiv. Transitivitet fortæller os, at hvis 3 < 4 og samtidig 4 < 5, så skal 3 < 5 helt sikkert også gælde. For mange relationer er det en forholdsvis naturlig egenskab. På samme måde for eksemplet med ord af samme længde. Hvis (hammer, lørdag) er i relationen, og (lørdag, brænde) er i relationen, så er også ordene (hammer, brænde) i relationen.

Relationen at være far til en søn er ikke transitiv. Hvis Torben er far til Frederik, og Frederik er far til Mikkel, så er Torben ikke far til Mikkel, han er hans farfar. På samme måde er relationen at kunne lide nogen ikke transitiv. Hvis jeg kan lide Sofie, og Sofie kan lide sin mand, betyder det ikke, at jeg også kan lide Sofies mand.

Transitivitet beskæftiger man sig også med ved klassiske terninger. Lad os antage relationen terning A er bedre end terning B, hvis der på terning A oftere (med større sandsynlighed) slås et højere tal end på terning B. Er en sådan relation transitiv? Det svarer artiklen ikke-transitive terninger på.

Ækvivalens og ordning

Nogle særlige typer binære relationer har også deres egne navne:

• En ækvivalensrelation er en relation, som er refleksiv, symmetrisk og transitiv.
• En ordningsrelation er en relation, som er refleksiv, antisymmetrisk og transitiv.