Proving if R1 \ R2 is Transitive or Not

[IntroAnalysis]

Homework Statement

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

Homework 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?

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 $\subseteq$A X A
and R2 $\subseteq$A X A

Homework 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?

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

 

[micromass]

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

Why??

 

[IntroAnalysis]

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?

 

[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)$\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.

 

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