Set Theory, relations, transitivity

[covers]

Homework Statement

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.

Homework Equations

Transitivity: With xRy and yRz ==> xRz

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

 

[Hurkyl]

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)

 

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

 

[covers]

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.

Thank you very much, this was exactly what I was looking for!

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.

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

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)

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