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

Homework Help: Set Theory, relations, transitivity

  1. Apr 16, 2007 #1
    1. The problem statement, all variables and given/known data

    A is some set.
    R is a relation (set of ordered pairs), and is transitive on A.
    S = {(x,y) | (x,y) is element of R, (y,x) is not element of R}

    Show that S is transitive and trichotomic on A.

    2. Relevant equations

    Transitivity: With xRy and yRz ==> xRz

    3. The attempt at a solution

    For all x, y, z element of A : xRy and yRz ==> xRz
    and for all a, b, c element of A: aRb and bRc ==> aRc

    Now my problem: when I want to show transitivity from S on A, how can I be sure that c != x and a != z, because S is defined as (x,y) element R but not (y, x).

    It would be nice if someone could write out the solution for this problem in full. I need a good example to hold on to when trying to solve other problems. I hope I don't ask for to much...
  2. jcsd
  3. Apr 16, 2007 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For all x, y, z element of A : xRy and yRz ==> xRz​
    for all a, b, c element of A: aRb and bRc ==> aRc​
    Those two statements say exactly the same thing. What did you mean to say here? (In words, if you can't say it in symbols)
  4. Apr 16, 2007 #3


    User Avatar
    Science Advisor
    Homework Helper

    Suppose (x,y) and (y,z) are in S. You then want to show that (x,z) is in S. Well looking at the definition of S, this means that if (x,y) and (y,z) are in R and (y,x) and (z,y) aren't in R, then (x,z) is in R and (z,x) is not in R. So we have the following four premises:

    1. (x,y) in R
    2. (y,z) in R
    3. (y,x) not in R
    4. (z,y) not in R

    and want to conclude

    5. (x,z) in R
    6. (z,x) not in R.

    5 follows from 1 and 2 by transitivity of R. To prove 6 false, suppose it were true, then we'd have the following fact:

    6'. (z,x) in R.

    By 1 and 6' and transitivity of R, we'd conclude:

    7'. (z,y) in R.

    but this contradicts premise 4, so 6' is false, meaning 6 is indeed true, as desired. By 5 and 6, we conclude (x,z) is in S, so S is transitive.

    You can't prove trichotomy, since it doesn't hold in general. For example, let A = {1,2} and let R be the empty relation. R is trivially transitive. Since R is empty, S is empty. Hence neither (1,2) nor (2,1) is in S, but clearly 1 is not equal to 2 either.
  5. Apr 17, 2007 #4
    Thank you very much, this was exactly what I was looking for!

    There must be an error in the problem statement then...

    Sorry for that. Actually I am not sure anymore what I wanted to say with that... but I believe it was something like that:

    Say (x, y) and (y, z) is in R, then it follows that (x, z) is in R
    Say also that (a, b) and (b, c) is in R, then (a, c) must be in R too.

    Now I wanted to show that S is transitive, but as for any two elements of S it can never be that (x, y) is in S and (y, x) is in S. So I thought I had to show somehow that (a, c) is not equal to (y, x). But it was the wrong approach, because as far as I can see, this doesn't prove anything anyway...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook