# If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexample

1. Oct 10, 2011

### IntroAnalysis

1. The problem statement, all variables and given/known data
Suppose R1 and R2 are relations on A. Therefore, R1 $\subseteq$A X A
and R2 $\subseteq$A X A

2. Relevant equations
Let (x, y) and (y, z) $\in$R1. Then since R1 is transitive, xR1y, and
yR1z implies xR1z.

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

3. 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?
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Oct 10, 2011

### micromass

Staff Emeritus
Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

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.

3. Oct 10, 2011

### IntroAnalysis

Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

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) $\in$R1. Because R1 is transitive, (x, z) $\in$R1.

Since (x, y) $\wedge$ (y, z) $\notin$R2, then (x, z) $\notin$R2.

Therefore, (x, z) $\in$R1\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.

4. Oct 10, 2011

### micromass

Staff Emeritus
Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

Why??

5. Oct 11, 2011

### IntroAnalysis

Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

I had my doubts about this, but I was thinking if (x, y) $\notin$R2 $\wedge$ (y, z)$\notin$R2, 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 $\notin$R2?

6. Oct 11, 2011

### micromass

Staff Emeritus
Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

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

Maybe you should start looking for a counterexample.

7. Oct 12, 2011

### IntroAnalysis

Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

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)$\in$A X A l x $\leq$y}
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.

8. Oct 12, 2011

### micromass

Staff Emeritus
Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

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.

9. Oct 12, 2011

### IntroAnalysis

Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

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

10. Oct 12, 2011

### micromass

Staff Emeritus
Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

Very good!! That is indeed a counterexample!!