Äquivalenzrelation in der Menge {a,b,c,d}, definiert mit a+d = b+c

Question

Eigentlich habe ich gerade eine relativ einfache Aufgabe vor mir:

Es ist eine Relation R definiert durch (a,b)R(c,d) in der Menge {a,b,c,d}. Die Frage ist wie viele Äquivalenzklassen es jetzt gibt. Ich komme nach einigem überlegen auf 13 verschiedene Klassen.

Kann mir jemand sagen, ob das die richtige Lösung ist und wie ich das formal begründe?

Answer 1

Lies mal hier:

https://de.wikipedia.org/wiki/Partition_%28Mengenlehre%29#cite_note-1

insbesondere den Abschnitt: "Partitionen und Äquivalenzrelationen".

Daraus ergibt sich, das die Anzahl der Äquivalenzrelationen, die auf einer Menge M mit n Elementen definiert werden können, gleich der Anzahl der Partitionen ist, in die M zerlegt werden kann. Diese Anzahl wiederum wird durch die Bellsche Zahl B_n beschrieben und für eine Menge mit  n=4 Elementen gilt:

B₄ = 15

Du musst also noch ein bisschen nachdenken, dann fallen dir die beiden fehlenden Äquivalenzrelationen sicher noch ein :-)

Comments

Zunächst:

Die Relation gilt ja in Menge A = {a,b,c,d), also AxA:

(a,a)      (b,a)      (c,a)      (d,a)

(a,b)      (b,b)      (c,b)      (d,b)

(a,c)      (b,c)       (c,c)      (d,c)

(a,d)      (b,d)      (c,d)      (d,d)

Wenn die Relation durch a+d=b+c gilt, dann müssten sich die Paare (a,d), (b,c) als erste Klasse ergeben. Da a+d = d+a ist, gehört das Paar (d,a) dieser Klasse genau so an wie (c,b).

Da ich aber nur 4*4 Elemente habe und alleine 4 davon in einer Klasse sind, können doch nur noch 4*3 Elemente übrig bleiben. Also 12 + eine Klasse sind 13?

Vielleicht würdest du mir deine konkrete Lösung nennen?