En ekvivalensrelation ∼ är en relation, som uppfyller villkoren
Givet en ekvivalensalgebra. Då finns följande algoritm, för att skapa en indelning av M i delmängder Mi.
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