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. 

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{alignat}{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{alignat}


Relasjonen er *heterogen* dersom M \neq  N og *homogen* dersom de to mengdene er like. 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.

## Eksempler

Gitt de to mengdene

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


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.  For domenene gjelder

:
\begin{alignat}{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{alignat}


For rekkeviddene:

:
\begin{alignat}{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{alignat}


## Egenskaper til homogene relasjoner
En homogen relasjon kan karakteriseres med følgende egenskaper:  

* 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 (\textstyle{}2 , men \textstyle{} 3 \not
* 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 (