Finden Sie die kleinste Äquivalenzrelation R auf M mit R1 ⊆ R.

Question

Aufgabe:

Es sei M = {1, 2, 3, 4, 5, 6} und R1 = {(3, 3), (1, 2), (5, 2), (3, 6)}.

(a) Finden Sie die kleinste Äquivalenzrelation R auf M mit R1 ⊆ R.

(b) Geben Sie die Quotientenmenge M/R durch Aufzählung ihrer Elemente an! In der Aufzählung
soll jedes Element der Quotientenmenge nur einmal vorkommen

Leider weiß ich nicht wie ich am besten bei dieser Aufgabe anfangen soll.

Vielleicht kann mir jemand von euch helfen! :)

Answer 1

Zu (a):

1. Da \(R\) reflexiv sein muss, füge zu \(R_1\) alle \((x,x)\) mit \(x\in M\)

hinzu, die in \(R_1\) fehlen, die nun reflexive Relation heiße \(R_2\).

2. Da \(R\) symmetrisch sein muss, füge zu jedem \((x,y)\in R_2\)

\((y,x)\) hinzu, wenn es noch fehlt, die nun reflexive und

symmetrische Relation heiße \(R_3\).

3. "Transitive Hülle":

Da \(R\) transitiv sein muss, füge zu jedem Paar \((x,y),(y,z)\in R_3\)

\((x,z)\) hinzu, wenn es noch fehlt.

Die daraus entstandene Relation heiße wieder \(R_3\).

Fahre auf diese Weise solange fort, bis \(R_3\) transitiv ist.

Nun ist \(R=R_3\) die gesuchte Äquivalenzrelation.

Die Symmetrie von \(R\) muss nicht mehr überprüft werden,

weil die transitive Hülle einer symmetrischen Relation automatisch

wieder symmetrisch ist.