Ekvivalensrelasjon

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

En ekvivalensrelasjon er i matematikk en binær relasjon som er symmetrisk, refleksiv og transitiv. En ekvivalensrelasjon deler mengden inn i en partisjon av ekvivalensklasser. To element i mengden er ekvivalente dersom de tilhører samme ekvivalensklasse. Alle ekvivalente elementer deler et sett av grunnleggende egenskaper, uten å være identiske.

En binær relasjon S på en mengde M definerer en sammenheng mellom to og to elementer i M, slik at for elementene a og b, så er relasjonen enten sann eller usann. For eksempel kan en for mengden av punkt i planet (x,y) definere relasjonen «har første koordinat lik». For to punkt vilkårlige punkt kan denne relasjonen være sann eller usann: (x1,y1) har første koordinat lik (x2,y2). Når relasjonen S er sann for to element a og b, så kan dette skrives aSb.

En ekvivalensrelasjon er en binær relasjon der de følgende egenskapene er oppfylt:

  • Relasjonen er refleksiv, slik at aSa for alle a i mengden M.
  • Relasjonen er symmetrisk, slik at aSb medfører bSa.
  • Relasjonen er transitiv, slik at aSb og bSc medfører aSc.

Relasjonen «har første koordinat lik» er en ekvivalensrelasjon i R2.

En ekvivalensrelasjon er knyttet til en partisjon av mengden M, det vil si en oppdeling av M i ikke-tomme, disjunkte mengder. Disse delmengdene kalles ekvivalensklasser. En ekvivalensklasse kan defineres som

M_a = \lbrace b \in M | bSa \rbrace \,

Et element i M er medlem av én og kun én ekvivalensklasse. To elementer av mengden M er ekvivalente (med hensyn til ekvivalensrelasjonen) hvis og bare hvis de er elementer av samme ekvivalensklasse i partisjonen.

En ekvivalensrelasjon skrives ofte med symbolet ~ istedenfor S, som i uttrykket a ~ b.