TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 112

Aus VoWi
Zur Navigation springen Zur Suche springen

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

Aufgabe[Bearbeiten]

Zusatzaufgabe Gruppe L[Bearbeiten]

Bestimmen Sie ebenfalls die durch die Äquivalenzrelation aufgespannte Partition.

Hilfreiches[Bearbeiten]

Symmetrische Differenz[Bearbeiten, WP]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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

Anmerkung[Bearbeiten]

A und B können beide Elemente der Potenzmenge P(M) annehmen. Die Potenzmenge P(M) ist die Menge aller möglichen Teilmengenn von M. Bei dieser Relation ist nur Reflexivität gegeben, aber weder Symmetrie noch Transitivität. Diese Relation kann meiner Meinung nach in keinem Fall eine Äquivalenzrelation sein.

lg sunmoonlight

Lösungsvorschlag von Weaver[Bearbeiten]

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): A R A \Longleftrightarrow A = A \qquad q.e.d.

Symmetrie:

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

Transitivität:

\forall A, B, C \in \mathcal{P}(M): (A R B) \land (B R C) \Rightarrow A R C \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 A R B \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.