Question

Bestimmen die Strukturen

Aufrufe: 1084 Aktiv: 12.07.2019 um 11:38

0

Hallo,

wer kann mir hierzu weiterhelfen?

Aufgabe:

Bestimmen Sie bis auf Isomorphie alle Strukturen mit einer zweistelligen symmetrischen Relation R auf einer zweielementigen Grundmenge M. Es sei hierbei keines der Elemente ausgezeichnet.

Meine Überlegungen sind:

Es sei eine Menge M = {1,2} und die Relation auf der Menge ist symmetrisch R(a,b). D.h. für alle a,b: R(a,b) -> R(b,a)

Ich zerbreche meinen Kopf mit der Frage, ob ich in diesem Fall alle Morphismen, ausser Isom. zeigen soll. Sind sie Strukturen?

Kann es sein, dass wir in dieser Aufgabe Monomorphismus und Epimorphismus haben?

Danke für jede Hilfe. Bald ist die Klausur und ich habe dieses Kap kaum verstanden.

Beste Grüße

Eva

Teilen Diese Frage melden

gefragt 04.07.2019 um 20:38

evatsigkana
Student, Punkte: 50

Hm, das ist schwer zu erklären...Mal einige Überlegungen: Auf einer zwei-elementigen Menge gibt es erstmal 16 "verschiedene" Relationen, denn es gibt vier mögliche Paare (a,a), (a,b), (b,a) und (b,b) und jedes dieser Paare kann Teil der Relation sein oder nicht.
Soll die Relation symmetrisch sein, reduziert sich die Anzahl auf nur noch 8, denn dann ist die Relation durch den Wert auf (a,b) schon für (b,a) festgelegt.
Von diesen 8 sind aber einige isomorph. Der einzig mögliche Isomorphismus ist der, der die beiden Elemente der Menge vertauscht (es ist ja keines ausgezeichnet), das liefert eine neue Relation, die isomorph zur ursprünglichen ist.
Das macht aber nur dann einen Unterschied, wenn der Wert der Relation auf (a,a) und (b,b) nicht identisch ist.
Summa Summarum kommt man also auf 6 Isomorphieklassen:
\( R_1 = \{ \} \)
\( R_2 = \{ (a,a) \} \cong R_2' = \{ (b,b) \} \)
\( R_3 = \{ (a,a), (b,b) \} \)
\( R_4 = \{ (a,b), (b,a) \} \)
\( R_5 = \{ (a,b), (b,a) , (a,a) \} \cong R_5' = \{ (a,b), (b,a) , (b,b) \} \)
\( R_6 = \{ (a,b), (b,a) , (a,a), (b,b) \} \)

Hm, das ist schwer zu erklären...Mal einige Überlegungen: Auf einer zwei-elementigen Menge gibt es erstmal 16 "verschiedene" Relationen, denn es gibt vier mögliche Paare (a,a), (a,b), (b,a) und (b,b) und jedes dieser Paare kann Teil der Relation sein oder nicht.
Soll die Relation symmetrisch sein, reduziert sich die Anzahl auf nur noch 8, denn dann ist die Relation durch den Wert auf (a,b) schon für (b,a) festgelegt.
Von diesen 8 sind aber einige isomorph. Der einzig mögliche Isomorphismus ist der, der die beiden Elemente  der Menge vertauscht (es ist ja keines ausgezeichnet), das liefert eine neue Relation, die isomorph zur ursprünglichen ist.
Das macht aber nur dann einen Unterschied, wenn der Wert der Relation auf (a,a) und (b,b) nicht identisch ist.
Summa Summarum kommt man also auf 6 Isomorphieklassen:
\( R_1 = \{ \} \) 
\( R_2 = \{ (a,a) \} \cong R_2' = \{ (b,b) \} \)
\( R_3 = \{ (a,a), (b,b) \} \)
\( R_4 = \{ (a,b), (b,a) \} \)
\( R_5 = \{ (a,b), (b,a) , (a,a) \} \cong R_5' = \{ (a,b), (b,a) , (b,b) \} \)
\( R_6 = \{ (a,b), (b,a) , (a,a), (b,b) \} \)

─ dr_lars 05.07.2019 um 14:37

dr_lars,
wunderbare Antwort! Tausend Dank!
Kannst du mir bitte kurz erklären, wie auf die 16 verschieden Relationen kommst? Ich weiss von 2 hoch 4, aber wie kommt man darauf?
Das andere Problem ist, wie verstehe ich, dass die Relationen, die du angibst, isomorph sind? Ausserdem sollten wir nicht alles ausser Isomorph zeigen?
Es ist alles etwas kompliziert.
Viele Grüße
Eva ─ evatsigkana 05.07.2019 um 18:03

@dr_lars ... könntest du deine Antwort vielleicht noch als "Antwort" und nicht als Kommentar posten? Das wäre super! :) ─ 06.07.2019 um 15:49 Bearbeiten Löschen

@evatsigkana:
Erstmal die Frage nach den 16 Relationen, die es insgesamt auf einer 2-elementigen Menge gibt:
Eine Möglichkeit, eine Relation ~ zu sehen ist ja, dass für je zwei (nicht notwendig verschiedene) Elemente a und b meiner Menge entweder gilt\(a \sim b\) oder eben \(a \not\sim b\).
Wenn ich keine weiteren Forderungen an meine Relation habe (wie z.B. reflexiv, symmetrisch, etc.), dann habe ich hier alle Freiheiten und kann für je zwei Elemente "frei" entscheiden, ob sie in Relation stehen sollen oder nicht und je nach diesen Entscheidungen erhalte ich eine Relation.
Eine andere (äquivalente) Möglichkeit eine Relation zu betrachten ist, alle Tupel (a,b), für die diese Relation "gelten" soll, in eine Menge zu stecken und diese Menge dann als Beschreibung der Relation zu verstehen. So habe ich das unten gemacht:
Die Relation \( R_1 = \{ \} \) ist die leere Menge, also steht kein Element in Relation zu irgendeinem anderen. Die Relation \(R_2 = \{(a,a)\}\) bedeutet, dass für das Element A gilt \( a \sim a\), aber alle anderen Elementpaare stehen nicht in Relation zueinander.
Und jetzt das Argument: Da es insgesamt vier Tupel auf einer zwei-elementigen Menge gibt, kann ich immer eine Relation erzeugen, wenn ich für jedes dieser vier Tupel entscheide: Drin (in der Relation) oder nicht.
Für das erste Tupel gibt es zwei Möglichkeiten (drin oder nicht), für das zweite (unabängig davon) ebenso, etc. Insgesamt also \( 2 \cdot 2 \cdot 2 \cdot 2 = 2^4 = 16 \)

@evatsigkana:
Erstmal die Frage nach den 16 Relationen, die es insgesamt auf einer 2-elementigen Menge gibt: 
Eine Möglichkeit, eine Relation ~ zu sehen ist ja, dass für je zwei (nicht notwendig verschiedene) Elemente a und b meiner Menge entweder gilt\(a \sim b\) oder eben \(a \not\sim b\).
Wenn ich keine weiteren Forderungen an meine Relation habe (wie z.B. reflexiv, symmetrisch, etc.), dann habe ich hier alle Freiheiten und kann für je zwei Elemente "frei" entscheiden, ob sie in Relation stehen sollen oder nicht und je nach diesen Entscheidungen erhalte ich eine Relation.
Eine andere (äquivalente) Möglichkeit eine Relation zu betrachten ist, alle Tupel (a,b), für die diese Relation "gelten" soll, in eine Menge zu stecken und diese Menge dann als Beschreibung der Relation zu verstehen. So habe ich das unten gemacht:
Die Relation \( R_1 = \{ \} \) ist die leere Menge, also steht kein Element in Relation zu irgendeinem anderen. Die Relation \(R_2 = \{(a,a)\}\) bedeutet, dass für das Element A gilt \( a \sim a\), aber alle anderen Elementpaare stehen nicht in Relation zueinander.
Und jetzt das Argument: Da es insgesamt vier Tupel auf einer zwei-elementigen Menge gibt, kann ich immer eine Relation erzeugen, wenn ich für jedes dieser vier Tupel entscheide: Drin (in der Relation) oder nicht.
Für das erste Tupel gibt es zwei Möglichkeiten (drin oder nicht), für das zweite (unabängig davon) ebenso, etc. Insgesamt also \( 2 \cdot 2 \cdot 2 \cdot 2 = 2^4 = 16 \)

─ dr_lars 11.07.2019 um 14:28

Die zweite Deiner Fragen bezog sich auf die Isomorphie. Gefragt war die Anzahl der Relationen "bis auf Isomorphie" und das heißt eben nicht "alles außer isomorph", sondern heißt, dass zwei Relationen, die isomorph sind nur ein Mal gezählt werden sollen.
Was heißt es aber, dass zwei Relationen auf einer Menge M isomorph sind? Das bedeutet, dass es eine Bijektion der Menge M in sich selbst gibt, welche die Relationen aufeinander abbildet, oder in Formeln:
Sind \(R_1\) und \(R_2\) zwei Relationen auf einer Menge M, dann ist eine bijektive Abbildung \( \varphi: M \ to M \) ein Isomorphismus der Relationen, falls gilt:
\( (a,b) \in R_1 \iff (\varphi(a),\varphi(b)) \in R_2 \)
In unserem Beispiel hat M nur zwei Elemente und es gibt nur zwei Bijektionen eine solchen Menge auf sich selbst: Die Identität (die alles festhält) und die Bijektion, welche die beiden Elemente vertauscht. Die Identität kann aber nie einen Isomorphismus zwischen verschiedenen Relationen induzieren (was man sofort sieht, wenn man die Bedingung oben anschaut). Um also "echte" nicht-triviale isomorphe Relationen zu finden, müssen wir schauen, ob es von den 8 symmetrischen Relationen welche gibt, die ineinander überführt werden, wenn wir die Rollen von a und b tauschen.
Wenn wir uns die 8 gefundenen Relationen anschauen (siehe Liste oben), stellen wir fest, dass ein Vertauschen der Elemente nur einen Unterschied macht, wenn eine der beiden reflexiven Tupel \( (a,a) \) und \((b,b)\) Teil der Relation ist und das andere nicht - dann ändert eine Vertauschung etwas.
Schau Dir am besten die Liste nochmal an und überlege Dir, warum das so ist, also warum \(R_2 \) und \(R_2'\) isomoprh sind, aber z.B. \(R_2\) und \(R_3\) nicht.
Als Übung kannst Du Dir dann ja noch weiter überlegen, wie die Situation aussieht, wenn man die Bedigung "symmetrisch" fallen lässt, also mit allen 16 Relationen arbeitet - wie sehen die Isomorphieklassen dann aus?

Good luck, have fun!

Die zweite Deiner Fragen bezog sich auf die Isomorphie. Gefragt war die Anzahl der Relationen "bis auf Isomorphie" und das heißt eben nicht "alles außer isomorph", sondern heißt, dass zwei Relationen, die isomorph sind nur ein Mal gezählt werden sollen.
Was heißt es aber, dass zwei Relationen auf einer Menge M isomorph sind? Das bedeutet, dass es eine Bijektion der Menge M in sich selbst gibt, welche die Relationen aufeinander abbildet, oder in Formeln:
Sind \(R_1\) und \(R_2\) zwei Relationen auf einer Menge M, dann ist eine bijektive Abbildung \( \varphi: M \ to M \) ein Isomorphismus der Relationen, falls gilt:
\( (a,b) \in R_1 \iff (\varphi(a),\varphi(b)) \in R_2 \)
In unserem Beispiel hat M nur zwei Elemente und es gibt nur zwei Bijektionen eine solchen Menge auf sich selbst: Die Identität (die alles festhält) und die Bijektion, welche die beiden Elemente vertauscht. Die Identität kann aber nie einen Isomorphismus zwischen verschiedenen Relationen induzieren (was man sofort sieht, wenn man die Bedingung oben anschaut). Um also "echte" nicht-triviale isomorphe Relationen zu finden, müssen wir schauen, ob es von den 8 symmetrischen Relationen welche gibt, die ineinander überführt werden, wenn wir die Rollen von a und b tauschen.
Wenn wir uns die 8 gefundenen Relationen anschauen (siehe Liste oben), stellen wir fest, dass ein Vertauschen der Elemente nur einen Unterschied macht, wenn eine der beiden reflexiven Tupel \( (a,a) \) und \((b,b)\) Teil der Relation ist und das andere nicht - dann ändert eine Vertauschung etwas.
Schau Dir am besten die Liste nochmal an und überlege Dir, warum das so ist, also warum \(R_2 \) und \(R_2'\) isomoprh sind, aber z.B. \(R_2\) und \(R_3\) nicht.
Als Übung kannst Du Dir dann ja noch weiter überlegen, wie die Situation aussieht, wenn man die Bedigung "symmetrisch" fallen lässt, also mit allen 16 Relationen arbeitet - wie sehen die Isomorphieklassen dann aus?

Good luck, have fun!

─ dr_lars 11.07.2019 um 15:10

Kommentar schreiben

1 Antwort

dr_lars · Accepted Answer · 2019-07-11T11:56:16Z

Mal einige Überlegungen: Auf einer zwei-elementigen Menge gibt es erstmal 16 "verschiedene" Relationen, denn es gibt vier mögliche Paare (a,a), (a,b), (b,a) und (b,b) und jedes dieser Paare kann Teil der Relation sein oder nicht.

Soll die Relation symmetrisch sein, reduziert sich die Anzahl auf nur noch 8, denn dann ist die Relation durch den Wert auf (a,b) schon für (b,a) festgelegt.

Von diesen 8 sind aber einige isomorph. Der einzig mögliche Isomorphismus ist der, der die beiden Elemente der Menge vertauscht (es ist ja keines ausgezeichnet), das liefert eine neue Relation, die isomorph zur ursprünglichen ist.

Das macht aber nur dann einen Unterschied, wenn der Wert der Relation auf (a,a) und (b,b) nicht identisch ist.

Summa Summarum kommt man also auf 6 Isomorphieklassen:

\( R_1 = \{ \} \)

\( R_2 = \{ (a,a) \} \cong R_2' = \{ (b,b) \} \)

\( R_3 = \{ (a,a), (b,b) \} \)

\( R_4 = \{ (a,b), (b,a) \} \)

\( R_5 = \{ (a,b), (b,a) , (a,a) \} \cong R_5' = \{ (a,b), (b,a) , (b,b) \} \)

\( R_6 = \{ (a,b), (b,a) , (a,a), (b,b) \} \)