TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 117

Untersuchen Sie, ob die Relation $ARB\Leftrightarrow A\triangle B=\emptyset$ ($\triangle$ die symmetrische Differenz) auf der Potenzmenge einer Menge M eine Äquivalenzrelation bildet.

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Zusatzaufgabe Gruppe L

Bestimmen Sie ebenfalls die durch die Äquivalenzrelation aufgespannte Partition.

Hilfreiches

Symmetrische Differenz

Symmetrische Differenz

Die symmetrische Differenz zweier Mengen enthält alle Elemente, die nur in einer der beiden Mengen vorhanden sind. $A\triangle B:=(A\setminus B)\cup (B\setminus A)=(A\cup B)\setminus (A\cap B)$

Potenzmenge

Potenzmenge

Die Potenzmenge ${\mathcal {P}}(M)$ einer Menge $M$ ist die Menge aller Teilmengen von $M$.

Zu ihren trivialen Elementen zählen die leere Menge $\emptyset$ und die Menge $M$ selbst.

${\mathcal {P}}(M):=\lbrace T\mid T\subseteq M\rbrace$

Äquivalenzrelation

Äquivalenzrelation

Eine binäre Relation R auf einer Menge A heißt Äquivalenzrelation, wenn folgende drei Eigenschaften erfüllt sind:

Reflexivität: $\forall a\,\in A:aRa$,

Symmetrie: $\forall a,b\,\in A:aRb\Rightarrow bRa$,

Transitivität: $\forall a,b,c\,\in A:(aRb\wedge bRc)\Rightarrow aRc$.

Lösungsvorschlag

Die symmetrische Differenz besagt, daß alle Elemente, die in beiden Mengen vorkommen, ausgeschlossen werden, das Gegenstück zur Schnittmenge.

Wenn also die symmetrische Differenz von A und B die leere Menge ist, dann heißt das, daß es nur Elemente gibt, die in beiden Mengen vorhanden sind, mit anderen Worten A = B.

Und bei Identität sind die drei Voraussetzungen der Äquivalenzrelation (Reflexivität, Symmetrie und Transitivität) gegeben.

Hapi

Lösungsvorschlag von Weaver

Ist die symmetrische Differenz zweier Mengen leer, so müssen diese beiden Mengen gleich sein:

$A\triangle B=\emptyset$

$\Leftrightarrow (A\setminus B)\cup (B\setminus A)=\emptyset$

$\Leftrightarrow (A\setminus B=\emptyset )\land (B\setminus A=\emptyset )$

$\Leftrightarrow A\subseteq B\land B\subseteq A$

$\Leftrightarrow A=B$

Da $R$ die Gleichheitsrelation darstellt, hält sich die Prüfung zur Äquivalenzrelation kurz:

Reflexivität:

$\forall A\in {\mathcal {P}}(M):ARA\Longleftrightarrow A=A\qquad q.e.d.$

Symmetrie:

$\forall A,B\in {\mathcal {P}}(M):ARB\Rightarrow BRA\Longleftrightarrow A=B\Rightarrow B=A\qquad q.e.d.$

Transitivität:

$\forall A,B,C\in {\mathcal {P}}(M):(ARB)\land (BRC)\Rightarrow ARC\Longleftrightarrow (A=B)\land (B=C)\Rightarrow A=C\qquad q.e.d.$

$\Rightarrow R$ bildet auf ${\mathcal {P}}(M)$ eine Äquivalenzrelation.

Partition:

Die Äquivalenzklasse eines Elements $A\in {\mathcal {P}}(M)$ lässt sich folgendermaßen darstellen:

$K(A)=\lbrace B\in {\mathcal {P}}(M)\mid ARB\rbrace$

Die Partition ist die Menge aller Äquivalenzklassen:

${\mathcal {K}}=\lbrace \forall A\in {\mathcal {P}}(M):K(A)\rbrace$

$=\lbrace \forall A\in {\mathcal {P}}(M):\lbrace B\in {\mathcal {P}}(M)\mid A=B\rbrace \rbrace$

$=\lbrace \forall A\in {\mathcal {P}}(M):\lbrace A\rbrace \rbrace$

Wichtig ist, hierbei zu beachten, dass sich die Partition nicht direkt aus den Mengen der Potenzmenge zusammensetzt ("$A$"), sondern aus einelementigen Mengen mit je einer Menge der Potenzmenge ("$\lbrace A\rbrace$").

Beispielsweise wäre die Partition für $M=\lbrace 1,2\rbrace$ mit ${\mathcal {P}}(M)=\lbrace \emptyset ,\lbrace 1\rbrace ,\lbrace 2\rbrace ,\lbrace 1,2\rbrace \rbrace$ die Menge ${\mathcal {K}}=\lbrace \lbrace \emptyset \rbrace ,\lbrace \lbrace 1\rbrace \rbrace ,\lbrace \lbrace 2\rbrace \rbrace ,\lbrace \lbrace 1,2\rbrace \rbrace \rbrace$.