1

I encountered a question in doing my exercise about relations: {1; 2; 3; 4; 5}.

R = {(1; 1);(1; 2);(1; 4);(3; 3);(4; 2);(4; 4);(5; 3);(5; 5)}

I need to answer whether the relation is transitive.

My guess is YES, because for every ordered pair (x,y)∈ R and ordered pair (y,z)∈ R, it implies the ordered pair (x,z)∈ R:

(1,1) (1,2) --> (1,2) (1,1) (1,4) --> (1,4) (4,4) (4,2) --> (4,2) (5,3) (3,3) --> (5,3)

But my classmate says NO. He suggests one counter-example:

If (x,y) = (1,2) ∈ R and (y,z) = (2,4) ∉ R, then (x,z) = (1,4) ∈ R

Which is correct? Thank you for your advice.

ronzenith
  • 131
  • You are correct. Your classmate did not provide a real counterexample. – drhab Oct 20 '16 at 10:25
  • 1
    Your classmate is dead wrong. He has confused up the entire condition of transitivity. The statement is : given that $(a,b) \in R$ and $(b,c) \in R$, it should follow that $(a,c) \in R$. The contradiction of this statement is: there are $a,b,c$ such that $(a,b), (b,c) \in R$ but $(a,c) \notin R$. You classmate has got the negation wrong. The fact that $(a,b), (a,c) \in R$ but $(b,c) \notin R$ has nothing to do with transitivity at all. If your classmate is adamant, call him to this forum.We will explain this to him. – Sarvesh Ravichandran Iyer Oct 20 '16 at 10:26
  • Your classmate has not given a counterexample to the relation being transitive, but he has given a counterexample to the relation being Euclidean. – mrp Oct 20 '16 at 10:33

1 Answers1

1

The relation in question is transitive, but you have not provided a proof according to the rules.

In order to test for transitivity we only have to test pairs of entries $(x,y)\in R$ with $x\ne y$. In your case these are the entries $$(1,2),\quad(1,4),\quad (4,2),\quad(5,3)\ .$$ Here only $4$ appears both as first and as second coordinate of some entry. It follows that $(1,4)$ and $(4,2)$ is the only pair of entries we have to test, and as $(1,2)\in R$ we are done.

Christian Blatter
  • 226,825