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

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

Äquivalenzrelation

Äquivalenzrelation

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

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

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

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

Mengen-Differenz

Mengen-Differenz

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

Reflexivität

$\mathrm{\forall }a\in M:aRa$

Symmetrie

Symmetrie

$\mathrm{\forall }a,b\in M:aRb\Rightarrow bRa$

Transitivität

Transitivität

$\mathrm{\forall }a,b,c\in M:a\circ b\wedge b\circ c\Rightarrow a\circ c$

Disjunkt

Disjunkte Mengen

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

$A,B\text{disjunkt}⟺A\cap B=\mathrm{\varnothing }$

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

$\mathrm{\forall }i:\mathrm{\forall }j\ne i:M_i\cap M_j=\mathrm{\varnothing }$

Definition der symmetrischen Differenz

$A△B=(A\setminus B)\cup (B\setminus A)$

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

$C=A\mathrm{△}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\mathrm{△}B=(A-B)\cup (B-A)$

VENN-Diagramm:

Reflexivität

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

die Relation ist definiert : A $△$ B = A

dh: wenn A in relation mit A steht => A $△$ A = A

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

Symmetrie

$ARB\Rightarrow BRA$?

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

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

Aus der Definition der symmetrischen Differenz folgt:

$\begin{array}{ccc}A△B=A& \iff & B=\mathrm{\varnothing }\\ B△A=B& \iff & A=\mathrm{\varnothing }\end{array}$

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

Transitivität

$ARB\wedge BRC\Rightarrow ARC$?

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

$\mathrm{\forall }\text{ a,b }\in \text{ R }:\text{ (a,b) }\in \text{ R }\wedge \text{ (b,c) }\in \text{ R }\Rightarrow \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:

---

... oder sich schneiden. Anhand der oben angeführten Definition der symmetrischen Differenz sieht man leicht, daß $A△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△B=A$ nur gelten, wenn $B=\mathrm{\varnothing }$ und damit $A△B=A△\mathrm{\varnothing }=(A\setminus \mathrm{\varnothing })\cup (\mathrm{\varnothing }\setminus A)=A$ gilt.

Daraus kann man folgern:

$\begin{array}{ccc}A△B=A& ⟺& B=\mathrm{\varnothing }\\ B△C=B& ⟺& C=\mathrm{\varnothing }\end{array}$

Und damit gilt:

$A△C=A△\mathrm{\varnothing }=A$

Daraus folgt, daß die Relation R transitiv ist.

Anmerkung hauns:

stimmt mMn nicht, denn:

$\begin{array}{ccc}A△B=A& ⟺& B=\mathrm{\varnothing }\\ B△C=B& ⟺& C=\mathrm{\varnothing }\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△B=A△\mathrm{\varnothing }=A\Rightarrow B=\mathrm{\varnothing }$

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

$\begin{array}{cc}C& =\mathrm{\varnothing }:\\ B△C& =\mathrm{\varnothing }△\mathrm{\varnothing }=\mathrm{\varnothing }\\ C& =C\\ B△C& =\mathrm{\varnothing }△C=C\end{array}$

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

Links

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