Sei %%M%% eine Menge und %%P%% eine Zerlegung dieser Menge. Es sei die Relation %%\sim%% durch die folgende Eigenschaft definiert:

%%x \sim y:⇔∃A\in P:x,y \in A%%

Beweise die folgenden Aussagen:

%%\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 $$\left(\exists A\in P: x,x\in A\right) \Rightarrow x\sim x$$

  • %%\sim%% ist symmetrisch: Sei %%x,y\in M%% beliebig. Es ist $$\begin{align} x\sim y & \Leftrightarrow \exists A\in P: x,y\in P \\[0.3em] & \Leftrightarrow \exists A\in P: y,x\in P \\[0.3em] & \Leftrightarrow y\sim x \end{align}$$

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

%%\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.

%%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.