# Homework Help: Set Theory, relations, transitivity

1. Apr 16, 2007

### covers

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. Apr 16, 2007

### Hurkyl

Staff Emeritus
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)

3. Apr 16, 2007

### AKG

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.

4. Apr 17, 2007

### covers

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...