Äquivalenzklassen

13.11.2010, 11:04

Monk

Äquivalenzklassen

Hallo,

ich habe folgende Aufgabenstellung:

Sei A eine Menge und ~ eine Äquivalenzrelation auf A. Z.z.: A/~ (die Menge der Äquivalenzklassen) ist eine Partition von A.

Also muss ich zeigen, dass A/~ gleich einer Partition ist; eine Partition ist nichtleer, disjunkt und enthält alle Elemente von A.

Also muss ich zeigen, dass diese Eigenschaften auch für A/~ gelten.

Nun bin ich mir nicht ganz sicher: dass eine Äquivalenzrelation nichtleer ist und alle Elemente von A enthält, gilt doch per Definition, oder?
Oder muss/kann man das noch irgendwie zeigen?

Etwas verzwickter ist die Eigenschaft, dass die Äquivalenzklassen disjunkt sein müssen.
Hierzu habe ich mir folgendes überlegt:

Seien $\begin{eqnarray*} A_1, A_2 \end{eqnarray*}$ Äquivalenzklassen, dann muss gelten: $\begin{eqnarray*} A_1 \cap A_2 = 0 \end{eqnarray*}$ .
Nun kann ich auch annehmen, dass $\begin{eqnarray*} A_1 \cap A_2 \neq 0 \end{eqnarray*}$ und daraus folgern, dass gelten muss $\begin{eqnarray*} A_1 = A_2 \end{eqnarray*}$

Ich weiß auch schon mehr oder weniger, woraus das folgt. Allerdings habe ich Probleme, meine Gedanken zu formalisieren.

Sei $\begin{eqnarray*} a \in A \end{eqnarray*}$ und sei $\begin{eqnarray*} [a] \end{eqnarray*}$ eine Äquivalenzklasse. Wenn nun $\begin{eqnarray*} b \in A \end{eqnarray*}$ und $\begin{eqnarray*} [b] \end{eqnarray*}$ eine zweite Äquivalenzklasse ist und es gilt, dass $\begin{eqnarray*} [a] \cap [b] \neq 0 \end{eqnarray*}$ dann heißt das, dass mind. ein Element von $\begin{eqnarray*} [a] \end{eqnarray*}$ in $\begin{eqnarray*} [b] \end{eqnarray*}$ bzw. umgekehrt.
Aus der Symmetrie und der Transitivität folgt dann, dass die beiden Äquivalenzklassen gleich sein müssen.

Aber ich weiß nicht, wie ich das korrekt formal aufschreiben kann.

13.11.2010, 13:20

Elvis

Auf diesen Beitrag antworten »

Du musst viel konkreter formulieren. Tipp: Definiere eine Äquivalenzrelation ~ auf A durch ihre drei Axiome. Definiere Äquivalenzklasse [a] für ein Element a aus A.
Dann kannst du die Beweise führen. Die erste Aussage "Jedes a aus A liegt in einer Äquvalenzklasse" beweist man z.B. so: $\begin{eqnarray*} a\in A\Rightarrow a \end{eqnarray*}$ ~ $\begin{eqnarray*} a \end{eqnarray*}$ (reflexiv) $\begin{eqnarray*} \Rightarrow a\in [a] \end{eqnarray*}$

14.11.2010, 09:00

Monk

Auf diesen Beitrag antworten »

Ok, ich habe es jetzt versucht smile

Sei $\begin{eqnarray*} \sim \end{eqnarray*}$ eine Äquivalenzrelation auf $\begin{eqnarray*} A \end{eqnarray*}$ . Die Äquivalenzrelation ist per Definition reflexiv, symmetrisch und transitiv.

Sei $\begin{eqnarray*} a \in A \end{eqnarray*}$ und $\begin{eqnarray*} [a] \end{eqnarray*}$ die Äquivalenzklasse von $\begin{eqnarray*} a \end{eqnarray*}$ .

Beweis, dass $\begin{eqnarray*} A/\sim \end{eqnarray*}$ alle Elemente von $\begin{eqnarray*} A \end{eqnarray*}$ enthält:

$\begin{eqnarray*} a\in A\Rightarrow a \end{eqnarray*}$ ~ $\begin{eqnarray*} a \end{eqnarray*}$ (reflexiv) $\begin{eqnarray*} \Rightarrow a\in [a] \end{eqnarray*}$

Das ist doch auch gleichzeitig der Beweis, dass [a] nichtleer ist, so wie ich das verstanden habe.

Beweis, dass Äquivalenzrelationen paarweise disjunkt sind:

Sei $\begin{eqnarray*} b \in A \end{eqnarray*}$ . Dann gilt: $\begin{eqnarray*} b \sim a \end{eqnarray*}$ . Wegen der Symmetrie gilt dann: $\begin{eqnarray*} a \sim b \end{eqnarray*}$ und für jedes $\begin{eqnarray*} x \sim b \end{eqnarray*}$ gilt $\begin{eqnarray*} b \sim x \end{eqnarray*}$ . Und wegen der Transitivität gilt: $\begin{eqnarray*} a \sim x \sim b \end{eqnarray*}$ bzw. $\begin{eqnarray*} b \sim x \sim a \end{eqnarray*}$ .

14.11.2010, 11:58

Elvis

Auf diesen Beitrag antworten »

Zitat:

Original von Monk
$\begin{eqnarray*} a\in A\Rightarrow a \end{eqnarray*}$ ~ $\begin{eqnarray*} a \end{eqnarray*}$ (reflexiv) $\begin{eqnarray*} \Rightarrow a\in [a] \end{eqnarray*}$

Das ist doch auch gleichzeitig der Beweis, dass [a] nichtleer ist, so wie ich das verstanden habe.

Stimmt, also liegt jedes a aus A in einer nichtleeren Äquvalenzklasse.

Zitat:

Original von Monk

Beweis, dass Äquivalenzrelationen paarweise disjunkt sind:

Das ist der falsche Begriff, du willst vermutlich zeigen, dass Äquivalenzklassen paarweise disjunkt sind.

Zitat:

Original von Monk

Sei $\begin{eqnarray*} b \in A \end{eqnarray*}$ . Dann gilt: $\begin{eqnarray*} b \sim a \end{eqnarray*}$ .

Nein, das gilt nicht. Wenn du b aus A wählst, ist a nicht definiert. Damit ist der Beweisversuch gescheitert.

14.11.2010, 13:04

Monk

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis

Das ist der falsche Begriff, du willst vermutlich zeigen, dass Äquivalenzklassen paarweise disjunkt sind.

Ja, das hatte ich gemeint; habe mich da vertan.

Zitat:

Original von Monk

Sei $\begin{eqnarray*} b \in A \end{eqnarray*}$ . Dann gilt: $\begin{eqnarray*} b \sim a \end{eqnarray*}$ .

Zitat:

Original von Elvis
Nein, das gilt nicht. Wenn du b aus A wählst, ist a nicht definiert. Damit ist der Beweisversuch gescheitert.

Ok. Soll ich es dann so machen, dass ich zwei Äquivalenzklassen $\begin{eqnarray*} [a] \end{eqnarray*}$ und $\begin{eqnarray*} [b] \end{eqnarray*}$ definiere und dann annehme, dass $\begin{eqnarray*} [a] \cap [b] = x \end{eqnarray*}$ also $\begin{eqnarray*} [a] \cap [b] \neq 0 \end{eqnarray*}$ ist?

Nun gilt ja $\begin{eqnarray*} a \sim x, b \sim x \end{eqnarray*}$
Aus Symmetrie und Transitivität folgt nun: $\begin{eqnarray*} a \sim x \sim b \end{eqnarray*}$ und $\begin{eqnarray*} b \sim x \sim a \end{eqnarray*}$ ; also $\begin{eqnarray*} [a] = [b] \end{eqnarray*}$

14.11.2010, 13:14

Elvis

Auf diesen Beitrag antworten »

Die Annahme $\begin{eqnarray*} [a]\cap [b]=x \end{eqnarray*}$ ist nicht sinnvoll. Links stehen Mengen, rechts ein Element von A. Die Folgerung am Ende, "also $\begin{eqnarray*} [a]=[b] \end{eqnarray*}$ " kann ich nicht nachvollziehen.

14.11.2010, 13:27

Monk

Auf diesen Beitrag antworten »

Oh, ich hoffe, dass mir jetzt gerade der ursprüngliche Fehler aufgefallen ist:

Statt

Sei $\begin{eqnarray*} b \in A \end{eqnarray*}$ ...

sollte es heißen:

Sei $\begin{eqnarray*} b \in [a] \end{eqnarray*}$ . Dann gilt: $\begin{eqnarray*} b \sim a \end{eqnarray*}$ . Wegen der Symmetrie gilt dann: $\begin{eqnarray*} a \sim b \end{eqnarray*}$ und für jedes $\begin{eqnarray*} x \sim b \end{eqnarray*}$ gilt $\begin{eqnarray*} b \sim x \end{eqnarray*}$ . Und wegen der Transitivität gilt: $\begin{eqnarray*} a \sim x \sim b \end{eqnarray*}$ bzw. $\begin{eqnarray*} b \sim x \sim a \end{eqnarray*}$ . Also $\begin{eqnarray*} [b] = [a] \end{eqnarray*}$ .

14.11.2010, 13:37

Elvis

Auf diesen Beitrag antworten »

Ich glaube, jetzt hast du's geschafft. Prost

Neue Frage »

Antworten »

Äquivalenzklassen

Verwandte Themen