Aufgaben
Betrachte die Relation "xx und yy besitzen dieselbe ISB-Nummer" auf der Grundmenge aller bisher gedruckten Buchexemplare.
Welche Eigenschaften besitzt diese Relation?
Tipp: Untersuche, ob die Relation reflexiv, irreflexiv, symmetrisch, antisymmetrisch, transitiv und/oder linear ist.
  • ''reflexiv:'' Für jedes Buchexemplar xx gilt: xx und xx besitzen dieselbe ISB-Nummer. Sprich: ein Buchexemplar hat immer dieselbe ISB-Nummer wie es selbst.
  • ''nicht irreflexiv:'' Weil die Grundmenge nicht leer ist, gibt es mindestens ein Buchexemplar xx. Dieses steht mit sich selbst in Relation, weil die Relation reflexiv ist, und damit ist die Relation nicht irreflexiv.
  • ''symmetrisch:'' Wenn xx und yy dieselbe ISB-Nummer besitzen, dann besitzen auch yy und xx dieselbe ISB-Nummer.
  • ''nicht antisymmetrisch:'' Es gibt mindestens zwei verschiedene Buchexemplare xx und yy, die dieselbe ISB-Nummer besitzen. Für diese beiden Exemplare steht zwar xx in Relation zu yy und y in Relation zu xx, aber es ist xyx\ne y.
  • ''transitiv:'' Wenn die Buchexemplare xx und yy dieselbe ISB-Nummer besitzen und die Buchexemplare yy und zz dieselbe ISB-Nummer besitzen, dann besitzen auch xx und zz dieselbe ISB-Nummer.
  • ''nicht-linear:'' Nehme zwei verschiedene Buchexemplare xx und yy, so dass beide eine verschiedene ISB-Nummer haben. Dann steht weder xx mit yy noch yy mit xx in Relation. Damit ist die Relation nicht linear.

Entscheide, welche der folgenden Relationen eine Äquivalenzrelation ist:

%%x%% und %%y%% sind ungerade“ auf der Menge %%\mathbb{N}_{\ge1}%%

Leider falsch. Prüfe nochmal die Reflexivität nach, beispielsweise von %%2 \in \mathbb{N}%%.

Super, das ist richtig. Die Relation ist nicht reflexiv – beispielsweise steht %%2%% nicht mit sich selbst in Relation.

Wie viele lineare Äquivalenzrelationen auf einer Grundmenge %%M%% gibt es?

Sei %%R\subseteq M\times M%% eine Äquivalenzrelation auf der Grundmenge %%M%%. Seien %%x,y\in M%% beliebig. Da %%R%% linear ist, steht entweder %%x%% in Relation zu %%y%% oder %%y%% in Relation zu x. Sei o.B.d.A. %%x\,R\,y%%. Auf Grund der Symmetrie ist dann aber auch %%y\,R\,x%%. Damit steht jedes Element mit jedem anderen Element in Relation.

Es gibt also genau eine lineare Relation auf einer Grundmenge %%M%%, nämlich %%R=M\times M%%, bei der jedes Element mit jedem anderen in Relation steht.

Beschreibe, wie die Äquivalenzklassen der folgenden Äquivalenzrelationen aussehen:

%%x%% und %%y%% besitzen denselben Rest bei der Division durch zwei“ auf der Menge %%\mathbb{N}_{\ge1}%%

Es gibt zwei Äquivalenzklassen:

Die Menge %%\{2,4,6,8, … \}%% aller Zahlen, die restlos durch 2 geteilt werden können und die Menge %%\{1,3,5,7, … \}%% 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.

%%x=y%%“ auf einer beliebigen, nicht leeren Grundmenge %%M\ne \emptyset%%

Beweise die folgenden Sätze:

Sei %%R%% eine Äquivalenzrelation auf der Grundmenge %%M%%. Dann ist die Menge aller Äquivalenzklassen %%{M/{\sim_R}}:= \{ [x]_R\,|\,x\in M\}%% eine Zerlegung 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 damit $$x\in [x] \subseteq \bigcup_{A\in P} A \Rightarrow x\in \bigcup_{A\in P} A$$ Da %%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. Dann gibt es genau eine Äquivalenzrelation %%\sim%%, die diese Zerlegung induziert, für die also %%M/{\sim}=P%% ist. Diese Äquivalenzrelation ist definiert durch:

%%x\sim y :\Leftrightarrow \exists A\in P: x,y\in A%%

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

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 $$\begin{align} x\sim_2 y & \Leftrightarrow \exists [a] \in M/{\sim_2}: x,y\in [a] \\[0.3em] & \ \left\downarrow\ P=M/{\sim_2}\right.\\[0.3em] & \Leftrightarrow \exists A\in P: x,y\in A \end{align}$$

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.
Kommentieren Kommentare