Proving if R1 \ R2 is Transitive or Not

In summary, R1 \ R2 is the set difference between two relations, R1 and R2. A relation is transitive if, for any elements a, b, and c, if a is related to b and b is related to c, then a is also related to c. To prove if R1 \ R2 is transitive, you must show that for any elements a, b, and c in R1 \ R2, if a is related to b and b is related to c, then a is also related to c. A counterexample is a specific case where the given statement or property does not hold. R1 \ R2 can only be either transitive or not transitive. It cannot be
  • #1
IntroAnalysis
64
0

Homework Statement


Suppose R1 and R2 are relations on A. Therefore, R1 [itex]\subseteq[/itex]A X A
and R2 [itex]\subseteq[/itex]A X A


Homework Equations


Let (x, y) and (y, z) [itex]\in[/itex]R1. Then since R1 is transitive, xR1y, and
yR1z implies xR1z.

Does R1\R2 mean: (x,y) [itex]\in[/itex]R1 [itex]\wedge[/itex] (x,y) [itex]\notin[/itex]
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?
 
Physics news on Phys.org
  • #2


IntroAnalysis said:

Homework Statement


Suppose R1 and R2 are relations on A. Therefore, R1 [itex]\subseteq[/itex]A X A
and R2 [itex]\subseteq[/itex]A X A


Homework Equations


Let (x, y) and (y, z) [itex]\in[/itex]R1. Then since R1 is transitive, xR1y, and
yR1z implies xR1z.

Does R1\R2 mean: (x,y) [itex]\in[/itex]R1 [itex]\wedge[/itex] (x,y) [itex]\notin[/itex]
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 [itex](x,y)\in R_1\setminus R_2[/itex] means [itex](x,y)\in R_1[/itex] and [itex](x,y)\notin R_2[/itex].

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

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


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

So (x, y) and (y, z) [itex]\in[/itex]R1. Because R1 is transitive, (x, z) [itex]\in[/itex]R1.

Since (x, y) [itex]\wedge[/itex] (y, z) [itex]\notin[/itex]R2, then (x, z) [itex]\notin[/itex]R2.

Therefore, (x, z) [itex]\in[/itex]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


IntroAnalysis said:
Since (x, y) [itex]\wedge[/itex] (y, z) [itex]\notin[/itex]R2, then (x, z) [itex]\notin[/itex]R2.

Why??
 
  • #5


I had my doubts about this, but I was thinking if (x, y) [itex]\notin[/itex]R2 [itex]\wedge[/itex] (y, z)[itex]\notin[/itex]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 [itex]\in[/itex] R1/R2, by definition it is [itex]\notin[/itex]R2?
 
  • #6


IntroAnalysis said:
Can I just say since (x, z) is [itex]\in[/itex] R1/R2

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

Maybe you should start looking for a counterexample.
 
  • #7


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)[itex]\in[/itex]A X A l x [itex]\leq[/itex]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


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


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


Very good! That is indeed a counterexample!
 

1. What is R1 \ R2?

R1 \ R2 is the set difference between two relations, R1 and R2. It consists of all the elements in R1 that are not in R2.

2. What does it mean for a relation to be transitive?

A relation is transitive if, for any elements a, b, and c, if a is related to b and b is related to c, then a is also related to c.

3. How do you prove if R1 \ R2 is transitive or not?

To prove if R1 \ R2 is transitive, you must show that for any elements a, b, and c in R1 \ R2, if a is related to b and b is related to c, then a is also related to c. If you can find a counterexample where this is not true, then R1 \ R2 is not transitive.

4. Can R1 \ R2 be both transitive and not transitive?

No, R1 \ R2 can only be either transitive or not transitive. It cannot be both at the same time.

5. What is a counterexample in relation to proving transitivity?

A counterexample is a specific case where the given statement or property does not hold. In the context of proving transitivity, it is an example where the elements a, b, and c do not follow the rule that if a is related to b and b is related to c, then a is also related to c.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
994
  • Calculus and Beyond Homework Help
Replies
17
Views
10K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
150
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
414
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
Back
Top