Wie viele Äquivalenzrelationen gibt es bei einer Menge mit 4 Elementen

14.06.2018, 13:26

Ahnungslos123

Wie viele Äquivalenzrelationen gibt es bei einer Menge mit 4 Elementen

Meine Frage:
Guten Tag liebes Matheforum, da morgen unsere Matheklausur ansteht und wir Probleme mit den Eigenschaften von Relationen haben, haben wir folgende Fragen:
Wie viele Äquivalenzrelationen gibt es bei einer Menge M = {a,b,c,d}? Wir gehen davon aus, dass es 15 Stück sind, gemäß Summe der Partitionen.
Und wann ist eine Relation transitiv? Die allgemeine Regel, welche besagt, (x,y) und (y,z) --> (x,z) , ist uns bekannt. Jedoch verwirren uns folgende Beispiele:
M = {1,2,3,4}
R1 = {(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(3,2)}
R2 = {(1,1),(2,2),(3,3),(4,4),(2,1),(1,3),(2,3)}
R3 = {(1,1),(2,2),(3,3),(4,4),(2,1),(1,3),(3,2)}
R4 = {(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,3)}
Laut der Definition wären also R1-R3 nicht transitiv, R4 jedoch schon. Stimmt dies? Oder sind auch R1-R3 transitiv?
Und würde dies anders aussehen, wenn es sich um Die Menge K = {a,b,c,d} handeln würde?
Denn im obigen Beispiel vermuten wir ja (falls es auch stimmt), dass (1,2),(1,3),(2,3) transitiv ist, da 1 kleiner gleich 2 ist, 2 kleiner gleich 3 ist --> dadurch muss auch 1 kleiner gleich 3 sein. Dementsprechend wäre dies bei (2,1),(1,3),(2,3) nicht der Fall.
Jedoch kann man ja Buchstaben nicht in eine kleiner gleich Beziehung stellen, sondern nur in eine Istgleich Beziehung?!

Wie Ihr seht, sind wir alle sehr verwirrt. Es wäre uns wirklich sehr geholfen, wenn Ihr uns zumindest weitere Denkanstöße geben könntet :-)

Meine Ideen:
Ideen in Fragestellung inbegriffen.

14.06.2018, 13:40

HAL 9000

Auf diesen Beitrag antworten »

RE: Wie viele Äquivalenzrelationen gibt es bei einer Menge mit 4 Elementen

Zitat:

Original von Ahnungslos123
Wir gehen davon aus, dass es 15 Stück sind, gemäß Summe der Partitionen.

Ja, dürfte stimmen.

Zitat:

Original von Ahnungslos123
Laut der Definition wären also R1-R3 nicht transitiv

Wieso sollen $\begin{eqnarray*} R_1,R_2 \end{eqnarray*}$ nicht transitiv sein? Dann müsstest du ja leicht Beispiele $\begin{eqnarray*} (x,y),(y,z)\in R_i \end{eqnarray*}$ anbringen können, für die $\begin{eqnarray*} (x,z)\not\in R_i \end{eqnarray*}$ gilt - welche sind das? verwirrt

Bei $\begin{eqnarray*} R_3 \end{eqnarray*}$ gibt es in der Tat so ein Gegenbeispiel: Es ist $\begin{eqnarray*} (2,1),(1,3)\in R_3 \end{eqnarray*}$ , aber $\begin{eqnarray*} (2,3)\not\in R_3 \end{eqnarray*}$ .

14.06.2018, 14:34

Ahnungslos123

Auf diesen Beitrag antworten »

RE: Wie viele Äquivalenzrelationen gibt es bei einer Menge mit 4 Elementen
Zunächst mal vielen Dank für deine Antwort :-)
Ich glaube es verstanden zu haben Hammer

Mein Denkfehler war dieser: Ich hatte immer die tatsächlichen Zahlen im Kopf, also, z.B. 3 darf nicht kleiner als 2 sein. Daher war meine Schlussfolgerung, dass z.B. R1 nicht transitiv sein kann. Dabei geht es ja nur darum, dass das "Verhältnis" zwischen den 3 verschiedenen Elementen der Tupel stimmt. Und dabei spielt es keine Rolle, ob die Zahl 3 oder 200 ist?

14.06.2018, 14:35

HAL 9000

Auf diesen Beitrag antworten »

Richtig, du musst dich gedanklich von dem konkreten Zahlenwert lösen.

14.06.2018, 14:41

Ahnungslos123

Auf diesen Beitrag antworten »

RE: Wie viele Äquivalenzrelationen gibt es bei einer Menge mit 4 Elementen
Perfekt Big Laugh

Eine daraus resultierende Frage: Reicht es bei R3 einfach nur (2,3) zu ergänzen, oder muss ich auch noch weitere Tupel ergänzen, sodass auch (3,2) "in einer Transitivität stimmig ist"?

14.06.2018, 14:51

HAL 9000

Auf diesen Beitrag antworten »

Es reicht nicht: Betrachte

(1,3),(3,2) --> (1,2)
(3,2),(2,1) --> (3,1)

Es müssen also zu den drei hinteren Paare (x,y) die in umgekehrter Reihenfolge (y,x) mit aufgenommen werden.

Generell: Gibt es wie hier einen solchen Zyklus $\begin{eqnarray*} (x_1,x_2),(x_2,x_3),\ldots,(x_{n-1},x_n),(x_n,x_1)\in R \end{eqnarray*}$ , dann erfordert die Transitivität sogar $\begin{eqnarray*} (x_i,x_j)\in R \end{eqnarray*}$ für sämtliche (!) $\begin{eqnarray*} i,j\in \{1,\ldots,n\} \end{eqnarray*}$ .

14.06.2018, 15:23

Ahnungslos123

Auf diesen Beitrag antworten »

RE: Wie viele Äquivalenzrelationen gibt es bei einer Menge mit 4 Elementen
Vielen Dank :-)

14.06.2018, 19:07

Ahnungslos123

Auf diesen Beitrag antworten »

Eine letzte Frage:

Nun unbeachtet, ob es eine Äquivalenzrelation wird oder nicht, wird die Relation
R3 = {(1,1),(2,2),(3,3),(4,4),(2,1),(1,3),(3,2)} also erst transitiv, wenn man noch
(1,2),(3,1), (2,3) hinzufügt?

Und noch eine Frage zu einer neuen Menge: M = {A,B,C,D}. Die folgende Relation R5 wird aus dem Kreuzprodukt MxM gebildet:
R5={(A,A),(B,B),(D,D),(C,C),(A,B),(B,C),(A,C),(A,D),(D,C)}
Zu beweisen ist die Transitivität. (die reflexiven und antisymmetrischen Eigenschaften sind ja klar).

Nun stimmt ja schonmal das Dreierpaar: (A,B),(B,C),(A,C)
und auch das Dreierpaar: (A,C),(A,D),(D,C) ist korrekt.

Jetzt stellt sich die Frage, ob eines der Tupel (B,D) oder (D,B) inbegriffen sein muss?
Meine Vermutung ist, dass dies nicht geschehen muss, da die Transitivität ja auch ohne (B,D) bzw. (D,B) nicht verletzt wird. Ist dies korrekt?

14.06.2018, 21:43

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Ahnungslos123
Nun unbeachtet, ob es eine Äquivalenzrelation wird oder nicht, wird die Relation
R3 = {(1,1),(2,2),(3,3),(4,4),(2,1),(1,3),(3,2)} also erst transitiv, wenn man noch
(1,2),(3,1), (2,3) hinzufügt?

Ja. Und es ist leicht zu sehen, dass es dann eine Äquivalenzrelation ist, mit den beiden Äquivalenzklassen {1,2,3} sowie {4}.

Zitat:

Original von Ahnungslos123
Jetzt stellt sich die Frage, ob eines der Tupel (B,D) oder (D,B) inbegriffen sein muss?
Meine Vermutung ist, dass dies nicht geschehen muss, da die Transitivität ja auch ohne (B,D) bzw. (D,B) nicht verletzt wird. Ist dies korrekt?

Ja, ist so. Freude

Es gibt hier zwei "Transitivitätsketten" A->B->C sowie A->D->C, aber keine Verbindung zwischen B,D, egal welche Richtung, und das ist Ok.

Neue Frage »

Antworten »

Wie viele Äquivalenzrelationen gibt es bei einer Menge mit 4 Elementen

Verwandte Themen