Question

Wieviele Äquivalenzrelationen gibt es auf der 3-elementigen Menge A={a,b,c} ?

Answer 1

Jede Relation ist eine Teilmenge von M x M.

Diese hat 9 Elemente.   Sei M = {a,b,c}

Wenn es eine Äquivalenzrelation ist, müssen   (a,a), (b,b) , (c,c) enthalten sein.

Diese drei allein genügen auch schon.

Also 1. Relation ist  R1= {   (a,a), (b,b) , (c,c) }

 Nimmt man ein Paar hinzu , etwa (a,b) dann muss auch (b,a) mit dabei sein

wegen der Symmetrie. Das genügt dann auch schon für die Transitivität., also

R2={   (a,a), (b,b) , (c,c), (a,b) , (b,a)   }   entsprechend mit (a,c) bzw. (b,c)

entstehen R3 und R4.

Nimmt man allerdings zwei weitere Paare (nicht symmetrische) hinzu, etwa

(a,b) und (a,c) dann wegen Symmetrie wie (b,a) und (c,a) und dann wegen der

Transitivität also auch (b,c), und damit hat man dann alle.

Es gibt also 5 verschiedene Äquivalenzrelationen.

Answer 2

Eine Äquivalenzrelation teilt die Grundmenge in sogenannte Äquivalenzklassen ein. Äquivalenzklassen sind nicht-leere Teilmengen der Grundmenge, so dass jedes Element in genau einer Äquivalenzklasse ist.

Zähle, wieviele Möglichkeiten es gibt, A in Äquivalenzklassen einzuteilen.

Es gibt eine Möglichkeit, dass es eine Äquivalenzklasse gibt. Diese ist dann {a,b,c}. Das entspricht der Äquivalenzrelation, in der jedes Element von A äquivalent zu jedem Element von A ist.

Es gibt eine Möglichkeit, dass es drei Äquivalenzklassen gibt. Diese sind dann {a}, {b} und {c}. Das entspricht der Äquivalenzrelation, in der jedes Element von A nur äquivalent zu sich selbst ist.

Es gibt mehrere Möglichkeiten, dass es zwei Äquivalenzklassen gibt. Eine davon ist zum Beispiel {a,b} und {c}. Das entspricht der Äquivalenzrelation, in der a äquivalent zu a und zu b ist, und c nur äquivalent zu sich selbst ist.

Finde heraus, wie viele weitere Möglichkeiten es gibt, A in zwei Äquivalenzklassen einzuteilen.