Ekvivalensrelasjon

From Wikipedia, the free encyclopedia

Remove ads

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 A2. 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 resten du får når du deler am. Til dømes er , fordi 7/3 er 2, med 1 i rest, medan , fordi 9 går opp i 3. Resten er alltid eit heiltal mellom 0 og . To heiltal a og b er kongruente modulo m viss dei gjev den same resten. Dette vert notert som .

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, sog 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.

Remove ads

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 aA 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: .

I kongruensrelasjonen modulo m er ekvivalensklassene dei same som restklassene modulo m:

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


Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads