Ekvivalensrelasjon

Ein **ekvivalensrelasjon** er ein binær relasjon som fangar eigenskapen *likeverd* (ekvivalens) mellom objekt. Ekvivalensrelasjonar er kjenneteikna som dei relasjonane som er refleksive, symmetriske og transitive.

## Formell definisjon

Lat *R* vere ein homogen, binær relasjon over ei mengd *A*. Altså er *R* ei delmengd av *A*2. *R* er ein ekvivalensrelasjon dersom
* eitkvart element *a* er likeverdig med seg sjølv (*R* er *refleksiv*),
* viss *a* er likeverdig med *b*, så er og *b* likeverdig med *a* (*R* er *symmetrisk*),
* og viss *a* er likeverdig med *b*, som er likeverdig med *c*, så må *a* òg vere likeverdig med *c* (*R* er *transitiv*).

## Døme

### Likskap

Det enklaste dømet på ein ekvivalensrelasjon er *likskapsrelasjonen* *R*=, der to element er likeverdige viss og berre viss dei er like. Dette er den minimale refleksive relasjonen over ei mengd, og er både symmetrisk og antisymmetrisk.

### Modulær kongruens

Eit anna mykje brukt døme på ekvivalensrelasjonar kjem frå modulær aritmetikk. Gjeve eit heiltal *a* og eit positivt heiltal *m*, så er a\mod m resten du får når du deler *a* på *m*. Til dømes er 7\mod 3 = 1, fordi 7/3 er 2, med 1 i rest, medan 9\mod 3 = 0, fordi 9 går opp i 3. Resten er alltid eit heiltal mellom 0 og m-1. To heiltal *a* og *b* er *kongruente modulo* *m* viss dei gjev den same resten. Dette vert notert som a \equiv b\mod m.

For kvart positivt heiltal *m* er då kongruens modulo *m* ein ekvivalensrelasjon over heiltala. Det er enkelt å sjå at dei ulike eigenskapane til relasjonen held.

### Parallelle liner

To uendeleg lange, rette liner i planet er parallelle dersom dei anten er den same lina, eller aldri kryssar einannan. Parallellitet er ein ekvivalensrelasjon på mengda av uendelege rette liner i planet. Det er enkelt å sjå at relasjonen er refleksiv og symmetrisk, men for å sjå at den er transitiv må me nytte oss av følgjande setning:
* To liner er parallelle viss og berre viss ei anna, ikkje-parallell line kryssar båe linene i same vinkelen.
Altså, viss ein har tre liner *r*, *s*og *t*, og *r* og *s* er parallelle, vil ei anna line *p* krysse båe i same vinkelen. Og viss *s* og *t* er parallelle, kryssar *p* båe desse i same vinkelen òg. Så *p* kryssar *r* og *t* i same vinkelen, som tyder at *r* og *t* er parallelle.

## Ekvivalensklasser

Ein viktig eigenskap med kvar ein ekvivalensrelasjon *R* er at han deler mengda si *A* inn i *ekvivalensklasser* av ekvivalente element. Mengda av ekvivalensklasser vert notert som *A / R*, og er ein partisjon av *A*. Altså ligg kvart element *a* ∈ *A* i éi og berre éi ekvivalensklasse. Den ekvivalensklassa som inneheld *a* kan noterast som [*a*]*R*, eller berre [*a*] viss det ikkje er tvil om kva for ein relasjon ein snakkar om.

I likskapsrelasjonen *R*= ligg kvart element i si eiga ekvivalensklasse: A /R_= = \{\{a\}: a\in A\}.

I kongruensrelasjonen modulo *m* er ekvivalensklassene dei same som *restklassene* modulo *m*: A /\equiv_m = \{\{a: a\equiv r \mod m\}: 0\leq r\leq m-1\}

I parallell-relasjonen består kvar ekvivalensklasse av alle liner som går i same retning i planet. Det er uendeleg mange ekvivalensklasser i dette dømet, sidan det finst uendeleg mange retningar ei line kan liggje i.

## Kjelder
*