Aufgabe zu Äquivalenzrelationen

Aufrufe: 694     Aktiv: 27.03.2021 um 12:37
0
Hallo, ich habe hier eine Aufgabe aus meiner LinA 1 Klausur, die ich vor ein paar Wochen online geschrieben habe. Ich habe mir die Aufgabe jetzt nochmal angeschaut und komme leider auch jetzt noch nicht wirklich weiter. Weil ich die Klausur online geschrieben habe, muss ich die Aufgabenstellung jetzt aus meinen unvollständigen Lösungen rekonstruieren, aber das sollte hinhauen. Also gegeben war eine Relation \(R_{\sigma} \) mit \(sR_{\sigma}t:\Leftrightarrow\sigma(s)R\space \sigma(t) \).

Die Aufgabe war nun: Zeigen oder widerlegen Sie folgende Aussagen.
a) Wenn \(R\) eine Äquivalenzrelation ist, ist auch \(R_{\sigma}\) eine Äquivalenzrelation.
b) Wenn \(R_{\sigma} \) eine Äquivalenzrelation ist, ist auch \(R\) eine Äquivalenzrelation.
c) Wenn \(R\) eine Abbildung ist, ist auch \(R_{\sigma}\) eine Abbildung.
d) Wenn \(R\) eine Halbordnung ist, ist auch \(R_{\sigma}\) eine Halbordnung.

Zu a) habe ich mir erstmal folgendes überlegt:
Sei \(R\) eine Äquivalenzrelation, dann gilt: \(\sigma(s)R\space \sigma(s)\) (reflexiv), \(\sigma(s)R\space \sigma(t) \Rightarrow\sigma(t)R\space\sigma(s) \) (symmetrisch) und \(\sigma(s)R\space \sigma(t), \space \sigma(t)R\space \sigma(u) \space \Rightarrow \sigma(s)R\space \sigma(u)\) (transitiv). Zu zeigen sind Reflexivität, Symmetrie und Transitivität für \(R_\sigma\).
\(\underline{reflexiv}\): Es gelte \(\sigma(s)R\space \sigma(s)\). Nach Definition gilt dann auch \(sR_\sigma s\).
... Analog habe ich dann auch versucht, die Symmetrie und Transitivität zu beweisen. Also ich habe einfach immer hingeschrieben, was nach Voraussetzung, dass \(R\) eine Äquivalenzrelation ist, gilt und was man dann nach der Definiton \(sR_\sigma t: \Leftrightarrow \sigma(s) R\space \sigma(t) \) jeweils daraus folgern könne. Das erscheint mir zugegebenermaßen etwas kurz, aber es hat auf den ersten Blick für mich Sinn ergeben. Allerdings müsste man nach diesem Schema ja auch b) ganz einfach beweisen können - einfach die Rückrichtung. Zu b) ist mir aber ein Gegenbeispiel eingefallen, welches die Aussage widerlegt, weshalb ich auch bei meiner Lösung zu a) sehr skeptisch bin.

Also zu b):
Gegenbeispiel: Betrachte die Abbildung \(\sigma :\space \{0,1\} \longrightarrow \{0,1\}; \space \space 0,1\mapsto 0\).
Dann ist die Menge \(R_\sigma =\{(0,0),(1,1)\}\) eine Äquivalenzrelation auf \(\{0,1\}\), jedoch ist die Menge \(R=\{(\sigma(0),\sigma(0)),(\sigma(1),\sigma(1))\} =\{(0,0),(0,0)\}=\{(0,0)\}\) keine Äquivalenzrelation auf \(\{0,1\}\), da \(R\) nicht reflexiv ist.

Meine Lösung für b) erscheint mir ziemlich plausibel. Bei c) habe ich noch keine wirkliche Idee, ich gehe aber davon aus, dass c) wahr ist. Um zu zeigen, dass \(R_{\sigma} \) eine Abbildung ist, muss ja nur gezeigt werden, dass \(R_{\sigma}\) jedem Element aus seinem Defintionsbereich in eindeutiger Weise ein Element aus dem Wertebereich zuordnet. Wie das jedoch genau angestellt wird, weiß ich leider noch nicht.

Bei d) bin auch ganz schön ratlos. Eine Halbordnung zeichnet sich ja zunächst dadurch aus, dass sie reflexiv, transitiv sowie antisymmetrisch ist. Intuitiv hätte ich jetzt wieder so wie in a) argumentiert, ich bin mir aber ziemlich sicher, dass das Quatsch ist und da schon etwas mehr hinterstecken muss.

Danke schonmal für alle Ideen und Lösungen :)
Diese Frage melden
gefragt

Student, Punkte: 68

 
Kommentar schreiben
2 Antworten
1

Deine Schwierigkeiten kommen, glaube ich, daher, dass sich die (leichte) Ungenauigkeit der Formulierung "gegeben war eine Relation \( R_\sigma \) ..." in allen weiteren Überlegungen bemerkbar macht.

Der Formulierung der Teilaufgaben kann man entnehmen, dass die Aufgabe ziemlich sicher folgendermaßen lautete:

Man hat eine Abbildung \( \sigma: S \to X \) zwischen zwei Mengen und eine Relation R auf der Menge X. (Beide sozusagen "vom Gegner vorgegeben", also uns nicht im einzelnen bekannt und nicht beeinflussbar.) Jetzt wird eine neue Relation auf der Menge S konstruiert, die den Namen \( R_\sigma \) bekommt, und die definiert ist durch die von dir angegebene Beziehung \( s R_\sigma t :\Longleftrightarrow \sigma(s) R \sigma(t) \).

Man kann so logisch-pfriemelige Aufgaben fast nur erfolgreich lösen, wenn man diese Dinge ganz genau auseinanderhält. Dann sieht man auch, dass dein Argument für a) schon "im Wesentlichen" stimmt; dein Unbehagen, dass das zu leicht sei, ist aber auch nicht ganz falsch.

a) Ich mache mal die Reflexivität vor: Ich behaupte, aus der Reflexivität von R folgt auch die von \( R_\sigma \). Erstere bedeutet, dass \( xRx \) für alle \( x \in X \) (!!) gilt. Die Frage ist nun, ob auch \( s R_\sigma s \) für alle \( s \in S \) (!!!) gilt. Antwort: Ja, denn \( s R_\sigma s \) gilt definitionsgemäß genau dann, wenn \( \sigma(s) R \sigma(s) \) gilt, und das stimmt, weil R reflexiv ist (hier ist also \( \sigma(s) \) ein spezielles \( x \in X \)).

Diese Antwort melden
geantwortet

Mathematiker auf Abwegen, Punkte: 60

 
Vielen Dank für die Antwort. Das hilft mir schonmal weiter. Allerdings habe ich immer noch ein grundsätzliches Problem mit der Aufgabe. Meinem Verständnis nach müsste man dann dennoch b) nach dem gleichen Schema wie a) lösen können (nur eben die Rückrichtung). Dein Kommentar zu b) finde ich, genauso wie deinen Kommentar zu a) sehr einleuchtend. Trotzdem bleibt bei mir das genannte Problem. Also konkret: könnte ich nicht dann b) analog zu a) folgendermaßen beweisen:
Es sei \(R_{\sigma}\) eine Äquivalenzrelation.
\(\underline{reflexiv}\): Es gelte nach Voraussetzung \(sR_{\sigma} s\) für alle \(s \in S\). Zu zeigen ist, dass dann auch \(\sigma(s) R\space\sigma(s) \) für alle \(\sigma(s)\in X, s\in S\) gilt. Das ist aber erfüllt, da nach Definition \(\sigma(s) R\space \sigma(s) \) genau dann gilt, wenn \(sR_{\sigma} s\) gilt.
... und so dann auch Symmetrie und Transitivität.

Mein Knackpunkt besteht, denke ich, in der Defintion \(sR_{\sigma}t:\Leftrightarrow \sigma(s) R\space \sigma(t)\). Das ist ja eine Äquivalenzbeziehung, also "genau dann, wenn"-Beziehung. Deshalb denke ich da immer noch, dass ich die Argumentation aus a) auch bei b) nur andersherum durchführen können müsste.

Vielleicht kannst du mir hier auch nochmal weiterhelfen.
LG   ─   mrchucuchucu 22.03.2021 um 10:54
1
Dein Denkfehler besteht darin, dass du zum Überprüfen der Reflexivität von \( R \) nur Elemente von \( X \) überprüfst, die von der Form \( \sigma(s) \) für ein \( s \in S \) sind. Für solche gilt tatsächlich \( \sigma(s) R \sigma(s) \), denn das ist ja (wie du richtig sagst) definitionsgemäß gleichwertig zu \( s R_\sigma s \) (und das ist wahr, weil nach deiner Voraussetzung \( R_\sigma \) reflexiv ist.
Aber was ist mit solchen \( x \in X \), die ich nicht als \( x = \sigma(s) \) für irgendein \( s \) bekomme? Anders gesagt, was ist, wenn \( \sigma \) nicht surjektiv ist?   ─   lfm 22.03.2021 um 22:59
Dankeschön, das leuchtet mir ein :)
Ich müsste demnach d) aber wieder ähnlich wie a) zeigen können, oder? (nur, dass ich die Axiome der Halbordnung jetzt nachweisen muss). Denn das Problem, dass \(\sigma\) nicht surjektiv sein muss, entfällt ja hier wieder, da es für jedes \(x,y\in X \) mit \(xRy\) mindestens ein \(s,t \in S\) mit \(sR_{\sigma}t\) geben muss. Stimmt das?   ─   mrchucuchucu 24.03.2021 um 09:41
1
Ich fürchte, nein: Denn zu einer Halbordnung gehört ja die Antisymmetrie, die besagt, dass aus "irgendwas" (egal, wie die genaue Bedingung heißt) folgt, dass zwei gegebene Elemente der Grundmenge gleich sein müssen. Wenn du das zugehörige Argument aufschreibst, siehst Du, dass man im Falle von \( R_\sigma \) nur bis zum Punkt kommt, "dass dann \( \sigma(s) = \sigma(t) \) sein muss", aber das bedeutet nicht zwangsläufig \( s = t \). Dass der Beweis an dieser Stelle klemmt, ist auch mehr oder weniger die Anleitung zum Basteln eines Gegenbeispiels.   ─   lfm 27.03.2021 um 12:37

Kommentar schreiben

1
Weiter geht's:

b) Dein Instinkt ist richtig, hier kann man ein Gegenbeispiel konstruieren. Du konstruiert es aber falsch herum: Du darfst die Relation \( R_\sigma \) nicht einfach hinschreiben, denn sie _ergibt sich_ aus einer Relation \( R \) und einer Abbildung \( \sigma \). (Die darfst du beide willkürlich wählen.) Tatsächlich funktionieren auch die von dir gewählte Relation \( R \) und deine Abbildung \( \sigma \), nur ergibt sich nicht \( R \) aus \( R_\sigma \), sondern umgekehrt. (Je nachdem, wie genau ein Korrektor ist, gibt es dafür noch Punkte oder eben auch nicht.)

Vielleicht ist das schon erst einmal genug zu verdauen; melde dich bei Rückfragen! Als Tipp noch: Ich würde (glaube ich) lieber zuerst d) als c) lösen, aber vielleicht bin das nur ich (die Vorstellung einer Abbildung als Relation hat mir, auch wenn sie natürlich stimmt, noch nie sonderlich gut gefallen und ist mir immer sehr kontraintuitiv vorgekommen, weil ich mir Abbildungen immer eher wie "Maschinen" vorstelle).
Diese Antwort melden
geantwortet

Mathematiker auf Abwegen, Punkte: 60

 

Kommentar schreiben