Aufgaben zu Äquivalenzrelationen

Um zu zeigen, dass $M/\sim :=\{[x]|x\in M\}$ eine Zerlegung von $M$ ist, müssen wir drei Behauptungen beweisen:

1. Behauptung: ${\bigcup }_{A\in P}A=M$

Es ist genau dann ${\bigcup }_{A\in P}A=M$, wenn ${\bigcup }_{A\in P}A\subseteq M$ und wenn ${\bigcup }_{A\in P}A\supseteq M$ ist.

• '$\subseteq$': Jede Äquivalenzklasse $A\in P$ ist nach Definition eine Teilmenge von $M$. Damit ist auch die Vereinigung aller Äquivalenzklassen ${\bigcup }_{A\in P}A$ eine Teilmenge von $M$.

• '$\supseteq$': Sei $x\in M$ beliebig. Da auf Grund der Reflexivität von $R$ das Element $x$ in Relation zu sich selbst steht, ist $x\in [x]$. Nun ist $[x]\in P$ und damitDa $x$ beliebig war, ist $M\subseteq {\bigcup }_{A\in P}A$

2. Behauptung: $\forall A,B\in P:A\ne B\Rightarrow A\cap B=\varnothing$

Seien $A,B\in P$ mit $A\ne B$. Dann ist $A=[x]$ und $B=[y]$ für ein $x,y\in M$.

Widerspruchsbeweis:

Sei $A\cap B=[x]\cap [y]\ne \varnothing$. Dann gibt es ein $a\in M$ mit $a\in [y]$ und $a\in [x]$. Damit ist $a\sim x$ und $a\sim y$. Aus der Transitivität folgt $x\sim y$ und damit $[x]=[y]$ aus dem Satz über den Zusammenhang zwischen Äquivalenzklassen und der Äquivalenz der Repräsentanten des vorherigem Abschnitts. Jedoch ist $A=[x]=[y]=B$ ein Widerspruch zu Annahme $A\ne B$, so dass $A\cap B=\varnothing$ sein muss.

3. Behauptung: $\forall A\in P:A\ne \varnothing$

Sei $A\in P$ beliebig. Dann ist $A=[x]$ für ein $x\in M$. Wegen der Reflexivität von der Äquivalenzrelation ist $x\sim x$ und damit $x\in [x]$. Daraus folgt, dass insbesondere $A=[x]\ne \varnothing$ ist.

Sei $M$ eine Menge und $P$ eine Zerlegung dieser Menge. Wir führen den Beweis in zwei Schritten. Zunächst beweisen wir die Existenz einer solchen Äquivalenzrelations und danach die Eindeutigkeit.

Beweis: Existenz einer Äquivalenzrelation, die diese Zerlegung induziert

Wir definieren die Relation $\sim$ über folgende Definition:

$x\sim y:\iff \exists A\in P:x,y\in A$

1.Behauptung: $\sim$ ist eine Äquivalenzrelation

• $\sim$ ist reflexiv: Sei $x\in M$ beliebig. Da die Vereinigung aller Mengen von $P$ die Grundmenge ergibt, gibt es eine Menge $A\in P$ mit $x\in A$. Damit ist $(\exists A\in P:x,x\in A)\Rightarrow x\sim x$

• $\sim$ ist symmetrisch: Sei $x,y\in M$ beliebig. Es ist $\begin{array}{cl}x\sim y& \iff \exists A\in P:x,y\in P\\ \iff \exists A\in P:y,x\in P& \iff y\sim x\end{array}$

• $\sim$ ist transitiv: Sei $x,y,z\in M$ mit $x\sim y$ und $y\sim z$. Dann gibt es ein $A\in P$ und ein $B\in P$ mit $x,y\in A$ und $y,z\in B$. Damit ist $A\cap B\ne \varnothing$, da $y$ sowohl ein Element von $A$ als auch ein Element von $B$ ist. Da $P$ eine Partition ist, muss $A=B$ sein. Daraus folgt $x,z\in A=B$ und damit $x\sim z$.

2.Behauptung: $\forall A\in P:\forall x\in A:[x]=A$

Sei $A\in P$ und $x\in A$ beliebig.

• '$\subseteq$': Sei $y\in [x]$ beliebig, also $x\sim y$. Dann gibt es ein $B\in P$ mit $x,y\in B$. Da $x\in A$ und $x\in B$ ist, ist $A\cap B\ne \varnothing$. Daraus folgt $A=B$, weil verschiedene Mengen von $P$ disjunkt sind. Damit ist $y\in B=A$, was zu beweisen war.

• '$\supseteq$': Sei $y\in A$ beliebig. Damit ist sowohl $x$ als auch $y$ ein Element von $A$ und damit $y\sim x$. Daraus folgt $y\in [x]$. Da $y\in A$ beliebig war, ist $A\subseteq [x]$.

Hieraus folgt, dass $[x]=A$ ist.

3.Behauptung: $M/\sim =P$

• '$\subseteq$': Sei $[x]\in M/\sim$ beliebig. Da ${\bigcup }_{A\in P}A=M$ ist, gibt es ein $A\in P$ mit $x\in A$. Aus der Behauptung (2) folgt, dass $[x]=A$ und damit $[x]=A\in P$ ist.

• '$\supseteq$': Sei $A\in P$ beliebig. Da alle Mengen aus $P$ nach Definition nicht leer sind, gibt es ein $x\in M$ mit $x\in A$. Aus Behauptung (2) folgt, dass $A=[x]$ und damit $A=[x]\in M/\sim$ ist.

Beweis: Eindeutigkeit dieser Äquivalenzrelation

Sei ${\sim }_2$ eine weitere Äquivalenzrelation mit $P=M/{\sim }_2$. Sei $x,y\in M$ beliebig. Es gilt dann $\begin{array}{ccl}x{\sim }_{2}y& \iff & \exists [a]\in M/{\sim }_2:x,y\in [a]\\ & \downarrow & P=M/{\sim }_2\\ & \iff & \exists A\in P:x,y\in A\end{array}$