0

Given the relation on the set $\{1,2,3,4\}$ why is $\{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)\}$ considered to be transitive?

As I go through it I can see that we have $(2,2)$ and $(2,3)$ so we'd need $(3,2)$ as well. But then I see $(3,3)$ and $(3,4)$ but not $(4,3)$? Obviously my processing of this is flawed, so I am asking this:

What is the process one would go through to determine if a relation set is transitive? Does the sequence/ordering of the set matter? I feel there's a key I don't understand yet.

Moo
  • 11,311
Adam Caverhill
  • 125
  • Oh, sorry. I'm pretty new here so I didn't think it was such an issue. I appreciate you taking the time to do it for me. – Adam Caverhill Apr 11 '17 at 02:17
  • 1
    ordering matters. If you compose (2,2) and (2,3) you get (2,3) which is already there. (You do not get (3,2).) If you compose (3,2) and (2,4) you get (3,4) which is already there. In general a relation is transitive if it is the same as its transitive closure https://en.wikipedia.org/wiki/Transitive_closure – Mirko Apr 11 '17 at 02:37
  • Ah, that makes a lot more sense then! – Adam Caverhill Apr 11 '17 at 02:37

1 Answers1

1

You've misunderstood transitivity. Transitivity says that if $(x,y)$ and $(y,z)$ are in the set, then $(x,z)$ must also be; transitivity tells us nothing about $(z,x),(z,y),$ or any other ordered pair made from these elements.

With transitivity, $(3,3)$ and $(3,4)$ together only imply that $(3,4)$ and $(3,3)$ must be part of the set, which they clearly are. The situation is exactly the same for $(2,2)$ and $(2,3)$; $(3,2)$ may be in the set, but we could exclude it without violating transitivity.

But we do have things like $(2,3)$ and $(3,2)$ in our set, and it would not be transitive if we didn't have $(2,2)$ in as well. Likewise, if we notice that we have $(3,4)$ and $(2,3)$, we'd better have $(2,4)$, which we do.

Malice Vidrine
  • 9,653