symmetric & transitive -> reflexive



  • 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 AA and a symmetric and transitive relation ρ\rho \neq \emptyset on AA.
    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 xx, we have xρxx \rho x. Let xAx \in A.
    Further, let yAy \in A be such that xρyx \rho y. Since ρ\rho is symmetric, it follows that yρxy \rho x. Now
    we have xρyx \rho y and yρxy \rho x. Hence, by the transitivity of ρ\rho, it follows that xρxx \rho x.

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

    LG



  • Fytch schrieb:

    Further, let yAy \in A be such that xρyx \rho y.

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

    (edit: typo)



  • Gehen wir mal Schrittweise durch.

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

    Hier wurde nichts behauptet.

    Let xAx \in A.

    Gibt es so ein x?

    Further, let yAy \in A be such that xρyx \rho y.

    Gibt es so ein y?

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

    Stimmt das?

    Now we have xρyx \rho y and yρxy \rho x.

    Ist nur eine Feststellung, hier ist nichts behauptet.

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

    Stimmt das?



  • SG1 schrieb:

    Fytch schrieb:

    Further, let yAy \in A be such that xρyx \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ρyx \rho y in einem symmetrischen, transitiven ρ\rho, dann stimmt der Rest des Beweises und es gilt xρxx \rho x und yρyy \rho y? Denn xρyyρxxρxx \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 xAx \in A.

    Gibt es so ein x?

    Ja, ρ\rho ist nichtleer.

    Biolunar schrieb:

    Further, let yAy \in A be such that xρyx \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. xy:xρy\forall x \exists y: x\rho y ist augenscheinlich falsch.

    Biolunar schrieb:

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

    Stimmt das?

    Falls die Prämisse des letzten Satzes stimmt, dann stimmt auch das. xρyyρxx\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ρxx \rho x.

    Stimmt das?

    Ja: xρyyρxxρxx \rho y \wedge y \rho x \rightarrow x \rho x gemäss Transitivität.

    Danke vielmals für die Hilfe.


Log in to reply