Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sets - Relations - proof involving transitivity

  1. Feb 18, 2014 #1
    I'm having trouble with the following:

    Let R be a relation on A. Prove that if Dom(R) [itex]\bigcap[/itex] Range(R) = ø, then R is transitive.

    I took the negation of the "R is transitive" to try proof by contrapositive (as the professor suggested), and have the following:

    [itex]\exists[/itex] x,y,z [itex]\in[/itex] A s.t. (x,y) [itex]\in[/itex] R [itex]\wedge[/itex] (y,z)[itex]\in[/itex] R [itex]\wedge[/itex] (x,z) [itex]\notin[/itex] R.

    Now I am stuck
     
    Last edited: Feb 18, 2014
  2. jcsd
  3. Feb 18, 2014 #2
    You are done. [tex]y\in{}\mbox{Dom}(R)\cap\mbox{Range}(R)[/tex]
     
  4. Feb 18, 2014 #3
    To elaborate...
    - If [itex]xRy[/itex], then [itex]y\in\text{Range}(R)[/itex].
    - If [itex]yRz[/itex], then [itex]y\in\text{Dom}(R)[/itex].
    - Therefore, if [itex]xRyRz[/itex], then [itex]y\in\text{Dom}(R)\cap \text{Range}(R)[/itex].

    So you can argue as follows:
    - [itex]\nexists y[/itex] with [itex]y\in\text{Dom}(R)\cap \text{Range}(R)[/itex].
    - Therefore, [itex]\nexists x,y,z[/itex] with [itex]y\in\text{Dom}(R)\cap \text{Range}(R)[/itex].
    - Therefore, [itex]\nexists x,y,z[/itex] with [itex]xRyRz[/itex].
    - Therefore, [itex]\nexists x,y,z[/itex] with [itex]xRyRz[/itex] and [itex](x,z)\notin R[/itex].
    - Therefore, [itex]R[/itex] is transitive.
     
  5. Feb 18, 2014 #4
    So if I understand it right, I have the following:

    Let R be a relation on A. Prove that if Dom(R) ⋂ Range(R) = ø, then R is transitive.

    Taking the negation of the "R is transitive" to try proof by contrapositive gives the following:

    1.) ∃ x,y,z ∈ A s.t. (x,y) ∈ R ∧ (y,z)∈ R ∧ (x,z) ∉ R (statement one is from [itex]\neg[/itex](R is transitive))
    2.) Then (x,y) ∈ R (from statement 1)
    3.) Then y ∈ Range(R) (from definition range)
    4.) Then (y,z) ∈ R (from statement 1)
    5.) Then y ∈ Dom(R) (from definition domain)
    6.) Then y ∈ Dom(R) ⋂ Range(R) (from 3 and 5)
    7.) Therefore [itex]\neg[/itex]( Dom(R) ⋂ Range(R) = ø ) (from 6)
     
  6. Feb 18, 2014 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I'd suggest an alternative approach. The statement itself is fairly non-sensensical, so why is it true? The answer is that R is vacuously transitive:

    If dom(R) and range(R) have no elements in common, then you cannot have xRy and yRz. So, vacuously, for any such x, y, z anything is true, including xRz.
     
  7. Feb 18, 2014 #6
    I think the solution I gave was a proof based on that exact idea.

    I agree that there's no need to go by contradiction here.
     
  8. Feb 18, 2014 #7

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, and I think it's useful and important to recognise when something is vacuously true, as you may get apparent absurdities that are true in this case. E.g.

    If Dom(R) intersect Ran(R) = ø, then xRy and yRz => anything you like (e.g. x is a tree-frog)!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Sets - Relations - proof involving transitivity
Loading...