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

Aus VoWi
Wechseln zu: Navigation, Suche

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

Hilfreiches[Bearbeiten]

Ä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.

Mengen-Differenz[Bearbeiten]

A - B - A\B
e - e - ne
e - ne - e
ne - e - ne
ne - ne - ne


e .... ist Element
ne .... ist kein Element

=)

Reflexivität[Bearbeiten, WP, 1.55 Definition]

\forall a\in M:\quad aRa

Symmetrie[Bearbeiten, WP, 1.55 Definition]

\forall a,b \in M: aRb \Rightarrow bRa

Transitivität[Bearbeiten, WP, 1.55 Definition]

\forall a,b,c\in M:\quad a\circ b\wedge b\circ c\Rightarrow a\circ c

Disjunkte Mengen[Bearbeiten]

Zwei Mengen A und B heißen disjunkt (oder elementfremd), wenn sie keine gemeinsamen Elemente besitzen.

A, B \; \text{disjunkt} \Longleftrightarrow A \cap B = \emptyset

Mehrere Mengen M_i heißen paarweise disjunkt, wenn je zwei Mengen keine gemeinsamen Elemente besitzen.

\forall i: \forall j \neq i: M_i \cap M_j = \emptyset

Definition der symmetrischen Differenz[Bearbeiten]

A \bigtriangleup B = (A \setminus B) \cup (B \setminus A)

C heißt symmetrische Differenz der Mengen A und B,

 C = A \triangle B ,

wenn C alle Elemente aus A enthält, die nicht zu B gehören und alle Elemente aus B, die nicht zu A gehören, d.h.:

 A \triangle B = (A - B) \cup (B-A)

VENN-Diagramm:

Praes22 symmdiff.png

Reflexivität[Bearbeiten]

Reflexivität heißt, dass jedes Element in Relation zu sich selbst steht:


die Relation ist definiert : A \bigtriangleup B = A

dh: wenn A in relation mit A steht => A \bigtriangleup A = A

Aber das ergibt nicht A, sondern eine leere Menge => nicht reflexiv

Symmetrie[Bearbeiten]

A R B \Rightarrow B R A?

Symmetrie heißt, wenn für alle a,b mit aRb auch bRa folgt.

 \forall \text{ a,b } \in \text{ }A^2: \text{ (a,b) } \in \text{ R } \qquad \Rightarrow \qquad \text{ (b,a) } \in \text{ R }

Aus der Definition der symmetrischen Differenz folgt:


\begin{array}{rcl}
  A \bigtriangleup B = A & \Leftrightarrow & A = \emptyset \\
  B \bigtriangleup A = B & \Leftrightarrow & B = \emptyset
\end{array}

Daher ist die Relation R nur dann symmetrisch, wenn A = B. D. h. sie ist im allgemeinen nicht symmetrisch.

Transitivität[Bearbeiten]

A R B \land B R C \Rightarrow A R C?

Eine Relation R transitiv, wenn stets gilt: (a,b) aus R UND (b,c) aus R FOLGT (a,c) aus R

 \forall \text{ a,b } \in \text{ R }: \text{ (a,b) } \in \text{ R } \wedge \text{ (b,c) } \in \text{ R } \qquad \Rightarrow \qquad \text{ (a,c) } \in \text{ R }

Zwei Mengen A und B können entweder disjunkt sein ...


Die Mengen A und B heißen disjunkt, wenn gilt:

 A \cap B = \varnothing

 \varnothing symbolisiert eine leere Menge.

Als VENN-Diagramm dargestellt:

Praes22 venndisjunkt.png


... oder sich schneiden. Anhand der oben angeführten Definition der symmetrischen Differenz sieht man leicht, daß A \bigtriangleup B die Menge A \cup B ist, wenn die Mengen disjunkt sind, oder aber die Vereinigung zweier echter Teilmengen von jeweils A und B umfaßt, wenn sie nicht disjunkt sind. Daher kann A \bigtriangleup B = A nur gelten, wenn B = \emptyset und damit A \bigtriangleup B = A \bigtriangleup \emptyset = (A \setminus \emptyset) \cup (\emptyset \setminus A) = A gilt.

Daraus kann man folgern:


\begin{array}{rcl}
A \bigtriangleup B = A & \Longleftrightarrow & B = \emptyset\\
B \bigtriangleup C = B & \Longleftrightarrow & C = \emptyset
\end{array}

Und damit gilt:


A \bigtriangleup C = A \bigtriangleup \emptyset = A

Daraus folgt, daß die Relation R transitiv ist.

Anmerkung hauns:

stimmt mMn nicht, denn:


\begin{array}{rcl}
A \bigtriangleup B = A & \Longleftrightarrow & B = \emptyset\\
B \bigtriangleup C = B & \Longleftrightarrow & C = \emptyset
\end{array}

B kann nicht bei ARB die leere Menge sein und dann bei BRC plötzlich nicht mehr die leere Menge sein, es ist ja ein und dieselbe Menge


A \bigtriangleup B = A \bigtriangleup \emptyset = A \Rightarrow B = \emptyset

Das bedeutet aber, dass egal was du machst, bei BRC bekommt man als Ergebnis nur die leere Menge, oder C:


\begin{align}
C & = \emptyset :\\
B \bigtriangleup C & = \emptyset \bigtriangleup \emptyset = \emptyset\\
C & = C\\
B \bigtriangleup C & = \emptyset \bigtriangleup C = C
\end{align}

für ARB & BRC  \Rightarrow ARC würde das aber wegen B =  \emptyset bei BRC bereits nicht B ergeben, sondern entweder  \emptyset oder C ... daher sicher nicht transitiv

Links[Bearbeiten]

Siehe auch f.thread:23103 , f.thread:22874