Aufgaben zu Äquivalenzrelationen

Die Menge der Äquivalenzklassen ist die Menge aller Klassen der Schule. Dabei ist jede Klasse als Menge aller Schüler modelliert, die diese Klasse besuchen.

Es gibt zwei Äquivalenzklassen:

Die Menge $\{\mathrm{2,4,6,8},\dots \}$ aller Zahlen, die restlos durch 2 geteilt werden können und die Menge $\{\mathrm{1,3,5,7},\dots \}$ aller Zahlen, die bei Division durch 2 den Rest 1 lassen. Damit zerfällt die Grundmenge ${\mathbb{N}}_{\ge 1}$ in die Menge der geraden und in die Menge der ungeraden Zahlen.

Jede Äquivalenzklasse ist einelementig. Die Grundmenge zerfällt also in die Menge $\{\{x\}:x\in M\}$.

(Beachte, dass dies eine Menge von einelementigen Mengen ist. Die Zerlegungsmenge ist ungleich der Grundmenge)

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}$

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