Äquivalenzrelationen auf kleinen Mengen aufzählen

Question

Aufgabe:

Die Fachschaft hat einen Überraschungsfilmabend organisiert. Die Getränkeversorgung ist gut, aber leider stellt sich heraus, dass der Film "101 Äquivalenzrelationen " entsetzlich langweilig ist. In nicht mehr ganz nüchternem Zustand fängt der Fachschaftsrat an,
sich darüber zu unterhalten, ob Sie eigentlich alle Äquivalenzrelationen auf kleinen Mengen aufzählen können, angeblich gäbe es auf der Menge {1, 2} nur 2 mögliche Äquivalenzrelationen, auf der Menge {1, 2, 3} fünf. Stimmt das? Welche Anzahlen wird die Fachschaft für {1, 2, 3, 4} und {1,2, 3, 4,5} finden?

Problem:

Ich denke diese Aufgabe ist nicht schwer. Nur leider bin ich etwas zu blöd zu verstehen wie man schon für {1,2} nur 2 mögliche Äquivalenzrelationen bekommen könnte. Wären es nicht {(1,1),(1,2),(2,2),(2,1)} also 4 ???

Falls jemand sieht was die meinen oder ich falsch verstehe bitte/gerne melden.

Comments

Das was da steht ist EINE Äquivalenzrelation.

Eine Äquivalenzrelation auf M ist eine Teilmenge R vom kartesischen Produkt M x M die eben der Reflexivität, Symmetrie und Transitivität genügt

Also:

(m,m) liegt in R für alle m aus M

Wenn (m,n) in R liegt, dann auch (n,m)

Wenn (m,n) und (n,p) in R liegen, dann auch (m,p)

Die zweite Äquivalenzrelation auf {1,2} ist

{(1,1), (2,2)}

Für die Aufgabe ist es eventuell nützlich die Korrespondenz zwischen den Äquivalenzrelationen auf M und den Partitionen von M zu nutzen.

---

Ich blick leider noch nicht ganz so durch. Also {(1,2),(2,1)} wäre die erste Äqui-R. und die zweite wäre {(1,1),(2,2)} oder wie? :(

Wärst du so nett und könntest noch das Beispiel mit {1,2,3} erläutern.

---

{(1,1),(2,2)}

Das ist eine

{(1,1),(1,2),(2,2),(2,1)}

Ist die zweite

Für {1,2,3} hast du 5 Stück:

{{1,1), (2,2), (3,3)}

{(1,1), (1,2), (2,1), (2,2), (3,3)}

{(1,1), (2,2), (2,3) ,(3,2), (3,3)}

{(1,1), (2,2), (3,3), (1,3), (3,1)}

{(1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3), (1,3), (3,1)}

---

Ich hätte für die anderen Beiden 9 und 14. Was hältst du davon ?

---

Es sollten 15 und 52 sein. (Bellsche Zahlen)

Answer 1

Die Äquivalenzklassen einer Äquivalenzrelation liefern eine
Partition der Grundmenge und jede Partition der Grundmenge
liefert eine Äquivalenzrelation, indem man zwei Elemente äquivalent nennt,
wenn sie in derselben Teilmenge liegen, die die Partition bilden.

Diese Zuordnung Äquivalenzrelation → Partition ist bijektiv.
Damit gibt es genauso viele Äquivalenzrelationen auf einer
endlichen Menge M wie es Partitionen von M gibt.