Binäre Relation zu einer Potenzmenge?
Ich bin gerade bei der dritten Aufgabe meiner HÜ und bin komplett verwirrt. Aufgabe a) war noch leicht aber ich verstehe nicht wie die Beweisführung für b) und die Angabe bei c) nicht. Kann es jemand bitte lösen / im Detail erklären?
2 Antworten
Für b) zeige, dass ≃ reflexiv, symmetrisch und transitiv ist:
- zeige A≃A: min A=min A (trivial)
- zeige A≃B ⇔ B≃A: min A=min B ⇔ min B=min A (trivial)
- zeige A≃B ∧ B≃C ⇒ A≃C: (kriegst Du selber hin)
Zu c)
Eine Äquivalenzklasse enthält alle Elemente, die zueinander äquivalent sind. Man schreibt sie üblicherweise als [m], wobei m ein beliebiges Element dieser Klasse ist. Die einelementigen Teilmengen bieten sich hier förmlich als Repräsentanten an:
- [{1}], [{3}], [{5}] und [{7}].
Zeige, dass diese Äquivalenzklassen paarweise verschieden sind und insgesamt alle Elemente von M abdecken. Denk aber bloß nicht zu viel nach: Der Beweis ist genau so trivial wie in b).
Ist es wirklich so leicht
Ja! Äquivalenzrelationen sind so fundamental, dass man sie oft gar nicht mehr als solche wahrnimmt und ganz naiv von Gleichheit (im Sinne von Identität) ausgeht:
- Brüche wie 2/3 und 4/6 sind genau genommen nicht identisch, nur äquivalent.
- Geometrie: Äquivalent ist praktisch alles, was man durch verschieben, drehen und spiegeln ineinander überführen kann. Die Winkel in einem Quadrat sind nicht identisch, weil sie an verschiedenen Ecken liegen. Trotzdem sagen wir, sie sind gleich.
- Terme wie 1+2 und 2+1 sind nicht identisch, aber (bezogen auf das Ergebnis) äquivalent.
Eigentlich ist Gleichheit (x=y) immer irgendeine Äquivalenzrelation, aber die ist oft intuitiv. Das macht die Beweise leicht. Schwierig ist es nur, den nötigen Abstand von seiner Intuition zu bekommen, damit man erkennt, was genau man beweisen muss.
Eine Äquivalenzrelation weist man nach, indem man die Eigenschaften Reflexivität, Symmetrie und Transitivität nachrechnet. Aus den Eigenschaften von "=" folgen direkt diese Eigenschaften auch für die vorgegebene Relation.
Die Definition bedeutet, dass zwei Mengen als äquivalent anzusehen sind, wenn deren Minima gleich sind. Die leere Menge ist oben ausgeschlossen, ansonsten wäre das Minimum hier nicht definiert. Somit gibt es vier mögliche Minima: 1, 3, 5, 7. Gib also jeweils alle Teilmengen von {1, 3, 5, 7} außer der leeren Menge an, sodass das Minimum 1, 3, 5, bzw. 7 ist.
Danke erstmal für die Antwort
Nach deiner Angabe hätte ich Aufgabe c) so gelöst:
min A (1) = {{1},{1,3},{1,5},{1,7},{1,3,5},{1,3,7},{1,5,7},{1,3,5,7}}
min A (3) = {{3},{3,5},{3,7},{3,5,7}}
min A (5) = {{5},{5,7}}
min A (7) = {{7}}
Entschuldige falls das jetzt eine dumme frage ist, wir haben bisher Reflexivität, Transitivität und Symmetrie nur mit Mengen bewiesen die Tupel enthielten, welche aus zwei Elementen bestanden, bewiesen. Bsp: {(2,1), (1,2), (1,1), (2,2)}. Wie mache ich bei diesen Mengen aus Mengen. In der Vorlesung wurden die Eigenschaften der Äquivalenzrelation nur anhand von Mengen aus gleichgroßen Tupeln gezeigt. WIe aber mache ich das bei etwas wie beispielsweise {{5}, {5,7}}?
Bsp: {(2,1), (1,2), (1,1), (2,2)}.
Hier wäre M = {1,2} und M × M = {(2,1), (1,2), (1,1), (2,2)}.
Was in deinem Beispiel Zahlen sind, sind in der Aufgabe Mengen.
In der Aufgabe ist M = {{1},{3},{5},{7},{1,3},{1,5},{1,7},{3,5},{3,7},{5,7},{1,3,5},{1,3,7},{3,5,7,}{1,3,5,7}}. M × M würde auch wieder aus Paaren bestehen, wo an der ersten Stelle ein Element aus M steht und an der zweiten Stelle auch wieder ein Element aus M. Die Elemente aus M sind hier selber Mengen. Die Tupel sind hier also auch im Paare und somit gleich groß.
Bei dieser Relation ist die Größe der Teilmengen irrelevant, da du dich eh nur für das minimale Element interessierst. Orientiere dich einfach an der Definition für die Relation und die Kriterien sind offensichtlich nachzuweisen.
Transitivität:
Nimm drei verschiedene Mengen A,B.C an, so dass A≈B und B≈C, dann zeige logisch dass in dem Fall auch A≈C gilt. Anhand des = tatsächlich offensichtlich: wenn minA = minB und minB = minC kannst du minB durch minA ersetzen und es gilt minA=minC und somit A≈C
Reflexivität:
Ähnlich offensichtlich: für jede beliebige Menge X aus M, ist das Minimum dieser Menge ist immer das gleiche: min X = min X. Somit auch X≈X
Symmetrie:
Zwei Mengen A und B aus M, wenn A≈B dann gilt min A = min B und aus der Gleichheit folgt min B= minA und somit auch B≈A
Ooooh. Das ergibt jetzt sehr viel mehr Sinn. Ich danke dir.
wir haben bisher Reflexivität, Transitivität und Symmetrie nur mit Mengen bewiesen die Tupel enthielten, welche aus zwei Elementen bestanden, bewiesen. Bsp: {(2,1), (1,2), (1,1), (2,2)}.
Die Tupel beschreiben die Relation. (2, 1) bedeutet schlicht 2≃1.
Wie mache ich bei diesen Mengen aus Mengen.
In dieser Aufgabe sind die Elemente selbst Mengen. {5}≃{5,7} würde also durch das Tupel ( {5}, {5,7} ) beschrieben. Aber diese Art, die Relation ≃ explizit aufzuzählen, brauchst Du hier gar nicht.
min A = min B ∧ min B = min C ⇒ min A = min C
Ist es wirklich so leicht oder irre ich mich gerade? Ich habe leider seit Jahren mehr kein Mathe gehabt deswegen bin ich so schwer vom Begriff. Danke Nochmals für die Antwort, ich war sehr am verzwefeln.