Proving if R1 \ R2 is Transitive or Not

[IntroAnalysis]

Homework Statement

Suppose R1 and R2 are relations on A. Therefore, R1 \subseteqA X A
and R2 \subseteqA X A

Homework Equations

Let (x, y) and (y, z) \inR1. Then since R1 is transitive, xR1y, and
yR1z implies xR1z.

Does R1\R2 mean: (x,y) \inR1 \wedge (x,y) \notin
R2?

The Attempt at a Solution

Any suggestions? I am losing what a relation R1 minus R2 means to prove or disprove that it is transitive?

 

[micromass]

Homework Statement

Suppose R1 and R2 are relations on A. Therefore, R1 \subseteqA X A
and R2 \subseteqA X A

Homework Equations

Let (x, y) and (y, z) \inR1. Then since R1 is transitive, xR1y, and
yR1z implies xR1z.

Does R1\R2 mean: (x,y) \inR1 \wedge (x,y) \notin
R2?

The Attempt at a Solution

Any suggestions? I am losing what a relation R1 minus R2 means to prove or disprove that it is transitive?

So (x,y)\in R_1\setminus R_2 means (x,y)\in R_1 and (x,y)\notin R_2.

So, you must prove that if (x,y)\in R_1\setminus R_2 and (y,z)\in R_1\setminus R_2, then (x,z)\in R_1\setminus R_2.

Try to prove it directly. If you're unable to, then try to find a counterexample.

 

[IntroAnalysis]

Let arbitrary (x, y) and (y,z) \in R1\R2. This is equivalent to
(x, y) \in R1 \wedge (x, y)\notin R2 and
(y, z) \in R1 \wedge (y, z)\notin R2.

So (x, y) and (y, z) \inR1. Because R1 is transitive, (x, z) \inR1.

Since (x, y) \wedge (y, z) \notinR2, then (x, z) \notinR2.

Therefore, (x, z) \inR1\R2. Since (x,y) and (y,z) were arbitrary elements of R1\R2, then if R1 and R2 are transitive, then R1\R2 must be transitive.

 

[micromass]

Since (x, y) \wedge (y, z) \notinR2, then (x, z) \notinR2.

Why??

 

[IntroAnalysis]

I had my doubts about this, but I was thinking if (x, y) \notinR2 \wedge (y, z)\notinR2, since R2 is transitive, then (x, z) cannot be an element of R2.

But I now think this is incorrect. Can I just say since (x, z) is \in R1/R2, by definition it is \notinR2?

 

[micromass]

Can I just say since (x, z) is \in R1/R2

No, because that is exactly what you need to prove!

Maybe you should start looking for a counterexample.

 

[IntroAnalysis]

Counterexample. Let A = {1,2,3}
Let R1 be the identity relation, iA. iA is transitive. R1 = {(1,1),(2,2),(3,3)}

Let R2 be the relation, R2 = {(x,y)\inA X A l x \leqy}
R2 = {(1,1), (1,2), (2,2), (2,3), (3,3)}. R2 is also transitive.

Then R1\R2 = Empty set.

I don't believe that the empty set could be transitive. (?) If true, then this would be a
counterexample.

 

[micromass]

Your R2 is not transitive: it misses (1,3).

Also the empty set is trivially transitive: indeed, for each (x,y) and (y,z) in the emptyset (there is no such x,y, and z!), we have that (x,z) is in there. So the condition is vacuously true.

 

[IntroAnalysis]

Thanks for your patience. I think I finally understand "vacuously" and "trivially" in regards to meeting the definition of transitive.

If R2 and R2 are transitive, must R1\R2 be transitive? No.
Counterexample: A = {1, 2, 3} and R1 = {(1,2), (2,3), (1, 3)} and R2 = {(1, 3)}.
R1 is transitive and R2 is transitive (vacuously).

Then, R1\R2 = {(1,2), (2,3)}. Therefore, R1\R2 is not transitive because it does not include
(1, 3).

 

[micromass]

Very good! That is indeed a counterexample!