Binær relasjon

En binær relasjon, eller en relasjon, er i matematikk en sammenheng mellom objekter i to mengder. For hvert par av objekter vil relasjonen enten være sann eller ikke. Eksempler på relasjoner er «lik», «større enn», «kongruent» og «ortogonal til».

Binære relasjoner er brukt i alle deler av matematikk. En funksjon er definert som en spesiell type binær relasjon.

Formell definisjon

Dersom $M$ og $N$ er vilkårlig mengder, og $S$ er en delmengde av det kartesiske produktet $M\times N$ , så er $S$ en binær relasjon fra $M$ til $N$ .^[1]

For ethvert ordnet par $(a,b)$ i $M\times N$ kan en si at paret er med i $S$ eller ikke. Dette er ekvivalent til å si at relasjonen mellom $a$ og $b$ er oppfylt eller ikke. En relasjon kan generelt skrives på formen $aSb$ eller $S(a,b)$ , men ofte erstattes $S$ med et mer standard symbol, som for eksempel et likhetstegn.

Domenet og rekkevidden (eller kodomenet) til relasjonen er definert ved henholdsvis

{\begin{alignedat}{2}{\mathcal {D}}S&=\lbrace \ a\in M\ |\ (a,b)\in S{\text{ for en }}b\ \in N\ \rbrace \\{\mathcal {R}}S&=\lbrace \ b\in N\ |\ (a,b)\in S{\text{ for en }}a\in M\ \rbrace \end{alignedat}}

Relasjonen er heterogen dersom $M\neq N$ og homogen dersom de to mengdene er like.^{[trenger referanse]} En homogen relasjon kan sies å være en relasjon i mengden der den er definert.

Formelt sett er også den tomme mengden en relasjon, siden denne er en delmengde i $M\times N$ .^[2]

Eksempler

Gitt de to mengdene

{\begin{alignedat}{2}M&=\lbrace 0,1,2,3,4,5,{\text{ ekorn}},{\text{ ulv }}\rbrace \\N&=\lbrace {\text{Partall, Oddetall, Primtall}}\rbrace \end{alignedat}}

I mengden $N$ er Partall en forkortelse for Mengden av partall, og tilsvarende for de andre elementene. Da vil $S=$ (er inneholdt i) være en heterogen relasjon fra $M$ til $N$ . Merk at ikke alle elementene i $M$ er med i relasjonen. Relasjon ternger ikke være entydig, og her er både $(3,{\text{Oddetall}})\in S$ og $(3,{\text{Primtall}})\in S$ .

En funksjon kan defineres som en relasjon som er entydig, det vil si at $(a,b)\in S$ og $(a,c)\in S$ hvis og bare hvis $b=c$ .

Generelle egenskaper

Hvis $S$ og $Q$ er to relasjoner i $M\times N$ , så er både unionen $(S\cup Q)$ , snittet $(S\cap Q)$ og mengdedifferansen $(S-Q)$ relasjoner.^[2] For domenene gjelder

{\begin{alignedat}{2}{\mathcal {D}}(S\cup Q)&={\mathcal {D}}S\cup {\mathcal {D}}Q\\{\mathcal {D}}(S\cap Q)&\subseteq {\mathcal {D}}S\cap {\mathcal {D}}Q\\{\mathcal {D}}S-{\mathcal {D}}Q&\subseteq {\mathcal {D}}(S-Q)\\\end{alignedat}}

For rekkeviddene:

{\begin{alignedat}{2}{\mathcal {R}}(S\cup Q)&={\mathcal {R}}S\cup {\mathcal {R}}Q\\{\mathcal {R}}(S\cap Q)&\subseteq {\mathcal {R}}S\cap {\mathcal {R}}Q\\{\mathcal {R}}S-{\mathcal {R}}Q&\subseteq {\mathcal {R}}(S-Q)\\\end{alignedat}}

Egenskaper til homogene relasjoner

En homogen relasjon kan karakteriseres med følgende egenskaper:^[2]

Relasjonen er refleksiv dersom aSa for alle a i mengden M.
- Relasjonen er irrefleksiv dersom det ikke finnes noen a i M slik at aSa
Relasjonen er symmetrisk dersom aSb medfoører bSa.
- Relasjonen er asymmetrisk dersom aSb medfører ikke bSa.
Relasjonen er antisymmetrisk dersom aSb og bSa medfører at a = b.
Relasjonen er transitiv dersom aSb og bSc medfører aSc.

Relasjonen «større eller lik» er refleksiv, mens relasjonen «større enn» ikke er det. Relasjonen «lik» er symmetrisk, mens relasjonen «større eller lik» er antisymmetrisk. En relasjon som er både refleksiv, symmetrisk og transitiv kalles en ekvivalensrelasjon. En relasjon som er refleksiv, antisymmetrisk og transitiv kalles en partiell ordning.

Refleksivitet

En relasjon S er refleksiv dersom ethvert element i en gitt mengde er relatert til seg selv.

Eksempler på refleksive relasjoner:

Likhet (=) på tall
Større eller lik (≤) på tall
Delmengde-relasjonen ( $\textstyle {}\subseteq$ )

Irrefleksivitet

En relasjon S er irrefleksiv dersom ingen objekter i en mengde er relatert til seg selv.

Eksempler på irrefleksive relasjoner:

Ekte større (<) på tall
Er ikke lik (≠) på tall

Symmetri

En relasjon S er symmetrisk dersom en relasjon er slik at dersom x er relatert til y, så er y også relatert til x. Merk at symmetri er ikke det motsatte av antisymmetri.

Eksempler på symmetriske relasjoner:

Likhet (=) på tall
«Søsken-relasjonen»

Asymmetri

En relasjon er asymmetrisk den har egenskapen hvis x er relatert til y, så er det ikke slik at y er relatert til x.

Eksempler på asymmetriske relasjoner:

Mindre enn (<) på tall: $\textstyle {}2<3$ , men $\textstyle {}3\not <2$
Delmengde-relasjonen $\textstyle {}\subseteq$

Antisymmetri

En relasjon er antisymmetrisk dersom den er slik at hvis to objekter er relatert med hverandre, så må de være samme objekt. Merk at antisymmetri ikke er det motsatte av symmetri.

Eksempler på antisymmetriske relasjoner:

Mindre eller lik (≤) på tall, hvis x≤y og y≤x, så er x=y
Likhet på tall, hvis x=y og y=x, så er x=y
Ekte mindre (<) på tall, det finnes ingen tilfeller slik at x < y og y < x, så det blir en tom sannhet.

Transitivitet

En relasjon er transitiv dersom den er slik at hvis x er relatert til y og y er relatert til z, så er x relatert til z.

Likhet (=) på tall
Mindre eller lik (≤) på tall

Generalisering

En binær relasjon er definert mellom to mengder, men det er også mulig å definere relasjoner som involverer flere mengder. En ternær relasjon kan for eksempel defineres som en delmengde av et kartesisk produkt av tre mengder. Gitt mengden {Adam, Eva, Kain, Abel, Ola, Per}, så kan en lage en ternær relasjon a og b er foreldre til c i denne mengden.

Det vil alltid være mulig å omformulere slike høyre-ordens relasjoner til et sett av binære relasjoner, så i praksis er det binære relasjoner som studeres. Derfor utelates ofte ordet binær, og en relasjon er underforstått en binær relasjon.^[2]

Se også

Relasjonsalgebra

Referanser

^ Paul R. Halmos (2025). Naive set theory. New York: Dover Publications. s. 26-29. ISBN 0-486-81487-4.
^ ^a ^b ^c ^d Patrick Suppes (1972). Axiomatic set theory. New York: Dover Publications. s. 57-67. ISBN 0-486-61630-4.

[PRH-1] Paul R. Halmos (2025). Naive set theory. New York: Dover Publications. s. 26-29. ISBN 0-486-81487-4.

[PS-2] Patrick Suppes (1972). Axiomatic set theory. New York: Dover Publications. s. 57-67. ISBN 0-486-61630-4.

[1]

[2]