Zeigen Sie, dass folgendes eine Äquivalenzrelation ist.

Question

Aufgabe:

Sei \( \leftrightarrow \) eine reflexive und symmetrische Funktion auf der Menge \( X \). Die Relation \( \sim \) sei auf \( X \) dadurch definiert, dass \( x \sim y \) genau dann gilt, wenn es eine natürliche Zahl \( k \) und \( u_{0}, u_{1}, \ldots, u_{k} \in X \) gibt, so dass \( x=u_{0}, y=u_{k} \), und \( u_{0} \leftrightarrow u_{1}, u_{1} \leftrightarrow u_{2}, \ldots, u_{k-1} \leftrightarrow u_{k} \). Zeigen Sie, dass \( \sim \) eine Äquivalenzrelation ist.

Problem/Ansatz:

Wie sieht die Lösung dieser Aufgabe aus?

Comments

Prinzipiell erst mal in Form des Nachweises von Reflexivität, Symmetrie und Transitivität der Relation...

Answer 1

Sei \( \leftrightarrow \) eine reflexive und symmetrische Funktion auf der Menge \( X \).

Dann ist \( x \leftrightarrow y\) genau dann wenn \(x = y\) ist. Das kann man sich klar machen indem man sich die Adjazenzmatrix der Relation \( \leftrightarrow \) auf der Menge \(X = \{1,2,3,4,5\}\) anschaut.

Die Relation \( \sim \) sei auf \( X \) dadurch definiert, dass \( x \sim y \) genau dann gilt, wenn es eine natürliche Zahl \( k \) und \( u_{0}, u_{1}, \ldots, u_{k} \in X \) gibt, so dass \( x=u_{0}, y=u_{k} \), und \( u_{0} \leftrightarrow u_{1}, u_{1} \leftrightarrow u_{2}, \ldots, u_{k-1} \leftrightarrow u_{k} \).

Dann ist \( \sim \) die selbe Relation wie \(\leftrightarrow\).