Ekvivalensrelation

En ekvivalensrelation är en relation, som uppfyller villkoren

  1. a a    (reflexiv)
  2. a b b a    (symmetrisk)
  3. a b och b c a c    (transitiv)
En ekvivalensalgebra är en algebra <M, >, där M är mängden av element, som algebran 'handlar om', och där relationen skall vara definierad för alla par av element ur M, och där, är en ekvivalensrelation.

Givet en ekvivalensalgebra. Då finns följande algoritm, för att skapa en indelning av M i delmängder Mi.

  1. Tag ett godtyckligt outnyttjat element, a, i M.
  2. Öka i med 1, och låt Mi vara mängden av alla element, x, i M som uppfyller x a.
  3. Om det finns några outnyttjade element kvar i M, gå till 1.
Det här kallas en ekvivalensklassindelning av M och de olika Mi kallas ekvivalensklasser eller bara klasser. Mängden av klasser kallas class~ (M).

En ekvivalensklassindelning blir en partitionering av M, dvs alla Mi täcker tillsammans hela M, och inga Mi går om lott.

Annorlunda uttryckt: varje element x i M tillhör exakt en ekvivalensklass. Reflexiviteten innebär att ett element åtminstone tillhör en ekvivalensklass, nämligen klassen av sig själv. Transitiviteten och symmetrin innebär att om x skulle tillhöra två klasser, så måste element i vardera klassen också vara ekvivalenta med varandra, och då måste de båda klasserna vara samma klass.

Ekvivalensklassindelningen ger upphov till två funktioner, varav den ena måste konstrueras.

Projektionen π är en mycket allmän representation av vad vi i dagligt tal kallar en 'projektion'. Den är bara i sällsynta fall en isomorfism. Givet en ekvivalensalgebra tillsammans med en operation <M, ~,+>. En intressant fråga är då om projektionen 'respekterar' operationen +. så att följande diagram kommuterar:

I så fall kan man göra alla beräkningar av + med hjälp av ○ i den nedre delen av diagrammet. Den operationen bör vara enklare, eftersom man har mycket färre element där (nämligen antalet klasser i M) än i den övre delen av diagrammet. Man kan dock inte komma tillbaka exakt till resultatet x+y utan bara till en representant repr(π(x)○ π(y)) för den klass som x+y tillhör.

Om <M,+> är en grupp och projektionen π respekterar +, så är algebran < π~(M), ○> en grupp, som kallas kvotgruppen M/~

Givet en partitionering, så genererar den omvänt en relation, som är en ekvivalensrelation, nämligen relationen:

tillhör samma klass som

Relationer som saknar villkoret på transitivitet kallas toleransrelationer. För toleransrelationer finns ingen möjlighet att göra ekvivalensklassindelningar, och därmed finns heller inga ekvivalensklassgränser. Toleransrelationer uppträder därför ofta, när man säger att man har "gränsdragningsproblem".

till innehåll