Äquivalenzrelationen

16.11.2008, 11:25

f(x)

Äquivalenzrelationen

Hallo!

Sei ~ eine Relation auf der Menge M, die sowohl symmetrisch als auch transitiv ist.

Folgender "Beweis" soll zeigen, dass ~ dann auch reflexiv ist.
Ich weiß, dass das nicht stimmen kann, finde aber den Fehler nicht.

Beweis:
Seien x,y beliebige Elemente aus M mit x~y.
Dann gilt auch y~x (Symmetrie).
Da x~y und y~x, gilt auch x~x (Transitivität, wobei dies der Spezialfall "x=z" ist).

Wo ist der Fehler?
Ich glaube, dass x,y,z für die Transitivität verschieden sein müssen, habe das aber nirgends gefunden.

Danke Jan

16.11.2008, 13:27

tmo

Auf diesen Beitrag antworten »

RE: Äquivalenzrelationen

Zitat:

Original von f(x)
Beweis:
Seien x,y beliebige Elemente aus M mit x~y.

Wer garantiert dessen Existenz?

Der Beweis zeigt nur, dass Elemente, die mit mindestens einem anderen Element in Relation stehen, auch mit sich selbst in Relation stehen.

16.11.2008, 17:42

f(x)

Auf diesen Beitrag antworten »

Okay, stimmt.

Aber selbst wenn wir davon ausgehen, dass jedes Element mit mind. einem anderen in Beziehung steht, folgt daraus noch nicht, dass die Relation reflexiv ist.

ZB:
Auf der Menge $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$
x~y $\begin{eqnarray*} \leftrightarrow \end{eqnarray*}$ x-y ist eine gerade Zahl $\begin{eqnarray*} \neq \end{eqnarray*}$ 0

Jedes Element steht mit mind. einem anderen Element in Relation.
Trotzdem ist sie nicht reflexiv.
Irgendwo ist da noch was faul.

16.11.2008, 17:46

tmo

Auf diesen Beitrag antworten »

Die Relation ist nicht transitiv.

Z.b. gilt $\begin{eqnarray*} 2 \sim 4 \end{eqnarray*}$ und $\begin{eqnarray*} 4 \sim 2 \end{eqnarray*}$ , aber nicht $\begin{eqnarray*} 2 \sim 2 \end{eqnarray*}$ .

16.11.2008, 22:12

f(x)

Auf diesen Beitrag antworten »

In meinem vertrauenswürdigen Lineare-Algebrabuch (von Beutelspacher) steht, dass sie transitiv ist.

Wahrscheinlich ist genau da der Haken.
Transitivität gilt wohl schon dann, wenn für alle paarweise verschiedenen Elemente x,y,z die Beziehung x~y und y~z => x~z gilt.
Also darf man den letzten Beweisschritt nicht durchführen.

16.11.2008, 22:34

Jacques

Auf diesen Beitrag antworten »

Hallo,

Das Entscheidende ist: Der Mechanismus

$\begin{eqnarray*} x \sim y \ \Rightarrow\ y \sim x \ \Rightarrow\ x \sim x \end{eqnarray*}$

greift doch nur, wenn das Objekt x auch tatsächlich einen „Relationspartner“ y hat. Reflexivität bedeutet aber, dass alle Elemente der Bezugsmenge mit sich selbst in der Relation ~ stehen.

Du musst also nur eine nicht-linkstotale Relation als Gegenbeispiel angeben:

$\begin{eqnarray*} \sim\ = \{(1, 2), (2, 1), (1, 1), (2, 2) \} \subseteq \{ 1, 2, 3 \} \end{eqnarray*}$

Die Relation ist symmetrisch und transitiv, aber nicht reflexiv, denn es gilt nicht 3 ~ 3.

Sobald man noch Linkstotalität voraussetzt, ist die Relation aber auf jeden Fall immer auch reflexiv.

// edit: Übrigens wird bei der Definition der Transitivität nirgendwo gefordert, dass die entsprechenden Objekte verschieden sein müssen. Die Definition lautet einfach:

$\begin{eqnarray*} \forall x, y, z (x R y\ \wedge\ y R z \ \Rightarrow\ x R z) \end{eqnarray*}$

16.11.2008, 22:48

f(x)

Auf diesen Beitrag antworten »

Okay, danke!
Jetzt ist das Problem gelöst.

Neue Frage »

Antworten »

Äquivalenzrelationen

Verwandte Themen