Wie viele Äquivalenzrelationen gibt es auf der Menge n = {1;2;;n} für n∈{2;3,4}?

Question

Sei M eine Menge. Eine Relation R von M nach M (oder kurz: eine Relation R auf M ) heißt Äquivalenzrelation, wenn sie reflexiv, symmetrisch und transitiv ist. Wie viele Äquivalenzrelationen gibt es auf der Menge n = {1;2;…;n} für n∈{2;3,4}?

Ich hab folgende Fragen zu der Aufgabe bekommen

1. Es gibt insgesamt wie viele  Äquivalenzrelationen auf der Menge {1;2}.

2. Es gibt insgesamt wie viele Relationen auf der Menge {1;2;3}. Davon sind wie viele   Äquivalenzrelationen auf der Menge {1;2;3}.

3. Es gibt insgesamt wie viele Relationen auf der Menge {1;2;3;4}. Davon sind wie viele Äquivalenzrelationen auf der Menge {1;2;3;4}.

Meine Idee:

Bei 1 eine Äquivalenzrelation

Bei 2 512 Relationen 5 Äquivalenzrelationen

Bei 3 65536 also 2^16 bei der Anzahl an Äquivalenzrelationen weiß ich hier nicht weiter. Kann mir wer helfen

Ich verstehe nicht was mit (2,3,4) gemeint ist

Answer 1

1. Eine Relation auf M ist ja immer eine Teilmenge von MxM.

Hier ist MxM={(1;1),(1;2),(2,1),(2,2)}

Eine Äquivalenzrelation ist doch {(1;1),(2,2)} denn die ist reflexiv, symmetrisch

und transitiv.

Außerdem MxM selbst ist auch eine. Also gibt es hier 2 Äquivalenzrelationen.

Für 2 ist vielleicht hilfreich:

https://www.mathelounge.de/997416/wie-viele-aquivalenzrelationen-gibt-es-auf-der-menge

Comments

Stimmen denn die Anzahlen der Relationen und wie ist das bei 3