Überprüfen von Äquivalenzrelation?

Hallo Leute,

ich habe jetzt die letzte Übung durchgemacht anhand der Vorlesungen und möchte jetzt fragen ob ich es richtig gemacht habe.

1. Ist richtig, da (1,1), (2,2), (3,3), (5,5) reflexiv sind. (4,4) ist nicht vorhanden aber ich denke es ist nicht unbedingt notwendig dies in der Menge zu haben. (1,3), (3,1), (1,5), (5,1) und (3,5), (5,3) sind symmetrisch. Somit ist es eine Äquivalenzrelation.
2. Hier habe ich geraten um ehrlich zu sein xD. Potenzmenge ist ja eine Menge von allen möglichen Mengen, die bijektiv (injektiv und surjektiv) sein soll. Um ehrlich zu sein weiss ich nicht wie man hier begründen soll.
3. Ist richtig, da z.B (4,4) = 0 (reflexiv), (4,6) und (6,4) = gerade (symmetrisch) und transitiv (4,6), (4,8) => (6,8) = gerade
4. Ist falsch, da es nur diese möglichen Szenarien gibt: (1,x) oder (x,1). Hier kann man nicht auf Transitivität schließen.
5. Ist falsch, da man reflexiv nie auf 1 kommt sondern nur auf 0 mit Operator -.

Vielen Dank im Voraus

Answer 1

[Willibergi]

Schau mal, dass du allgemein begründest, Beispiele sind noch kein Beweis.

Kurz intuitiv zu reflexiv, transitiv und symmetrisch:

• Reflexiv bedeutet, dass jedes Element aus der Menge in Relation zu sich selbst steht. Das prüfst du, indem du für jedes Element x aus der Menge prüfst, ob (x,x) in der Relation liegt.
• Transitiv bedeutet, dass wir Tupel zusammenpuzzlen können. Das heißt, liegt (x,y) und (y,z) in der Relation, können wir die beiden Tupel am y aneinander "puzzlen" und sehen dann, dass (x,z) auch in der Relation enthalten ist. Das prüfst du, indem du für jedes Element in der Relation guckst, mit was du es zusammenpuzzlen kannst - und ob das entstehende Element dann (immer!) auch in der Relation liegt (gibt es nur ein Beispiel, bei dem das nicht so ist, ist die Relation nicht mehr transitiv).
• Symmetrisch bedeutet, dass wir Elemente spiegeln können und das gespiegelte Element dann auch immer in der Relation ist. Ist also (x,y) in der Relation, ist auch (y,x) in der Relation. Das prüfst du auch ganz einfach, indem du dir jedes Element anguckst und prüfst, ob das gespiegelte auch in der Relation liegt.

Eine Äquivalenzrelation ist nur dann vorhanden, wenn sie alle drei Eigenschaften hat. Hat sie nur eine nicht, kann sie keine Äquivalenzrelation mehr sein.

Im ersten Beispiel scheitert es schon an der Reflexivität. Du hast es schon selbst gesagt, (4,4) ist nicht in der Menge - und das wäre definitiv notwendig. Denn für jedes Element in der Menge (hier {1,2,3,4,5}) muss dieses "Identitätstupel" in der Relation liegen, damit sie eine Äquivalenzrelation sein kann.

Im zweiten Beispiel beziehen wir uns auf die Potenzmenge von Z, also die Menge aller Teilmengen mit ganzen Zahlen.

• Prüfen wir Reflexivität: Wir nehmen uns eine beliebige Menge M aus der Potenzmenge raus und prüfen, ob (M, M) in der Relation liegt - also ob es eine bijektive Abbildung von M nach M gibt. Die gibt es, nämlich zum Beispiel einfach die Identität. Die Relation ist also reflexiv.
• Prüfen wir Transitivität: Wir nehmen uns zwei Elemente (U, V) und (V, W) aus der Relation raus und prüfen, ob dann auch (U, W) in der Relation liegt, also ob es eine bijektive Abbildung von U nach W gibt, wenn es bijektive Abbildungen von U nach V und von V nach W gibt. Das ist der Fall, überlege dir selbst mal warum. Die Relation ist also auch transitiv.
• Prüfen wir Symmetrie: Wir nehmen uns ein Element (U, V) aus der Relation raus und prüfen, ob auch (V, U) in der Relation liegt, ob es also eine bijektive Abbildung von V nach U gibt, wenn es eine bijektive Abbildung von U nach V gibt - die gibt es, nämlich die Umkehrfunktion. Die Relation ist also auch symmetrisch.

Die Relation ist also reflexiv, transitiv und symmetrisch: Also eine Äquivalenzrelation. Im Grunde geht es immer ähnlich - prüfe nacheinander Reflexivität, Transitivität und Symmetrie so wie oben und wenn eine Eigenschaft nicht erfüllt ist, kannst du aufhören, denn dann kann die Relation keine Äquivalenzrelation mehr sein.

Zu deinen Begründungen:

1. Siehe oben.
2. Siehe oben.
3. Schau dir nochmal an, was transitiv genau bedeutet. Da hast du was verdreht.
4. Auch -1 ergibt im Quadrat 1. Aber die Idee ist richtig erkannt: Jedes Tupel muss entweder -1 oder 1 enthalten und die Transitivität ist nicht erfüllt. Aber gib ein konkretes Gegenbeispiel, zum Beispiel (5,1) und (1,9) (und zeige, warum das die Transitivität verletzt).
5. Richtig. Ein Gegenbeispiel reicht: (1,1) ist nicht in der Relation, aber in Q².

LG

Comments

[vikiller01]

Vielen Dank.