Aufgaben zu Äquivalenzrelationen

• $\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}{rl}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$.

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.

• '$\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.