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 = \emptyset$

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 \emptyset$. 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=\emptyset$ sein muss.

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

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 \emptyset$ 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 :\Leftrightarrow \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 $\def\arraystretch{1.25} \begin{array}{cl}x\sim y &\Leftrightarrow \exists A\in P: x,y\in P \\ \Leftrightarrow \exists A\in P: y,x\in P & \Leftrightarrow 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 \emptyset$, 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\emptyset$. 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 $\def\arraystretch{1.25} \begin{array} {ccl} x\sim_2 y & \Leftrightarrow& \exists [a] \in M/{\sim_2}: x,y\in [a] \\ & \downarrow & P=M/{\sim_2}\\ & \Leftrightarrow & \exists A\in P: x,y\in A \end{array}$