symmetric & transitive -> reflexive

[Fytch]

Hallo

Teil einer Übungsaufgabe ist es, zu zeigen, wo in folgendem Beweis der Fehler steckt. Ich habe alles doppelt mit den gegebenen Definitionen überprüft aber finde den Fehler beim besten Willen nicht. Vielleicht kann mir jemand hier einen Tipp geben?

Consider a non-empty set $A$ and a symmetric and transitive relation $\rho \neq \emptyset$ on $A$.
a) The following proof shows that $\rho$ is always reflexive. Find the mistake in this proof.
Proof: We show that $\rho$ is reflexive, that is that for any $x$, we have $x \rho x$. Let $x \in A$.
Further, let $y \in A$ be such that $x \rho y$. Since $\rho$ is symmetric, it follows that $y \rho x$. Now
we have $x \rho y$ and $y \rho x$. Hence, by the transitivity of $\rho$, it follows that $x \rho x$.

Definitionen
Notation: $x \rho y \Leftrightarrow (x,y)\in\rho\subseteq A^2$
Symmetrisch: $\forall x,y: \left( x \rho y \leftrightarrow y \rho x \right)$
Transitiv: $\forall x,y,z: \left( x \rho y \wedge y \rho z \rightarrow x \rho z \right)$
Reflexiv: $\forall x: x\rho x$

LG

[SG1]

Fytch schrieb:

Further, let $y \in A$ be such that $x \rho y$.

Da ist der Fehler. Gibt es so ein y immer?

(edit: typo)

[Biolunar]

Gehen wir mal Schrittweise durch.

Proof: We show that $\rho$ is reflexive, that is that for any $x$, we have $x \rho x$.

Hier wurde nichts behauptet.

Let $x \in A$.

Gibt es so ein x?

Further, let $y \in A$ be such that $x \rho y$.

Gibt es so ein y?

Since $\rho$ is symmetric, it follows that $y \rho x$.

Stimmt das?

Now we have $x \rho y$ and $y \rho x$.

Ist nur eine Feststellung, hier ist nichts behauptet.

Hence, by the transitivity of $\rho$, it follows that $x \rho x$.

Stimmt das?

[Fytch]

SG1 schrieb:

Fytch schrieb:

Further, let $y \in A$ be such that $x \rho y$.

Da ist der Fehler. Gibt es so ein y immer?

Nein, gibt es nicht. Danke! Aber wenn es x,y gibt mit $x \rho y$ in einem symmetrischen, transitiven $\rho$, dann stimmt der Rest des Beweises und es gilt $x \rho x$ und $y \rho y$? Denn $x \rho y \wedge y \rho x \rightarrow x \rho x$ gemäß Transitivität. Insb. stimmt der Satz dann für alle symmetrische, transitive $\rho$, deren Graph zusammenhängend ist?

Biolunar schrieb:

Let $x \in A$.

Gibt es so ein x?

Ja, $\rho$ ist nichtleer.

Biolunar schrieb:

Further, let $y \in A$ be such that $x \rho y$.

Gibt es so ein y?

Für gewisse x aber nicht zwingendermaßen für alle. Da liegt wohl der Hase im Pfeffer. Hätte man die Quantoren hingeschrieben, dann wäre das offensichtlicher gewesen. $\forall x \exists y: x\rho y$ ist augenscheinlich falsch.

Biolunar schrieb:

Since $\rho$ is symmetric, it follows that $y \rho x$.

Stimmt das?

Falls die Prämisse des letzten Satzes stimmt, dann stimmt auch das. $x\rho y \rightarrow y\rho x$ ist eine Konsequenz der Symmetrie von $\rho$.

Biolunar schrieb:

Hence, by the transitivity of $\rho$, it follows that $x \rho x$.

Stimmt das?

Ja: $x \rho y \wedge y \rho x \rightarrow x \rho x$ gemäss Transitivität.

Danke vielmals für die Hilfe.