1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Transitive Relation over Set - Feedbacks on proofwriting skills

  1. Dec 10, 2012 #1
    1. The problem statement, all variables and given/known data

    Assume a relation [itex]P[/itex] that is negatively transitive on a set [itex]X[/itex] that is not empty.
    Define the binary relation [itex]R[/itex] on [itex]X[/itex] by [itex]xRy[/itex] iff [itex] y P x [/itex] is false.

    Prove that [itex]R[/itex] is transitive.


    2. Relevant equations

    Negative Transitivity: [itex]xPz \rightarrow xPy \vee yPz [/itex]

    Like in the previous thread (Complete Relation), I think I have a proof, but I am really looking forward to any feedback on the style of this proof. I tried to incorporate the stylistic feedbacks of Michael Redei and pasmith who kindly gave me feedbacks on the previous attempt.

    3. The attempt at a solution

    Proof:
    Let [itex]x[/itex], [itex]y[/itex] and [itex]z[/itex] be arbitrary and assume [itex]xRy[/itex] and [itex]yRz[/itex]. By definition of [itex]R[/itex] it follows that [itex]yPx[/itex] and [itex]zPy[/itex] are both false. Since [itex]P[/itex] is negatively transitive, this implies that [itex]zPx[/itex] is false. Thus, again by definition of [itex]R[/itex], the falsity of [itex]zPx[/itex] implies [itex]xRz[/itex], which proves that the relation [itex]R[/itex] is transitive.
     
    Last edited: Dec 11, 2012
  2. jcsd
  3. Dec 10, 2012 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I think you mean xPy → xPz V zPy, or somesuch.
     
  4. Dec 11, 2012 #3
    I hate typos... :smile:

    I edited the previous post: it is [itex]xPz \rightarrow xPy \vee yPz[/itex]
     
  5. Dec 11, 2012 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    With that correction, your proof looks fine.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Transitive Relation over Set - Feedbacks on proofwriting skills
Loading...