1

I am having a hard time understanding why $\{(1,2),(3,4)\}$ is a transitive relation to $S = \{1,2,3,4\}$.

My understanding is for this to be transitive, $1$ would have to relate to $4$ which is not in the relation. If $x = 1$, $y = 2$ and $y = 3$ and $z = 4$ then x!Rz. I know I'm missing something in my understanding of transitive relationships.

petehockey
  • 13
  • 4
    Why do you think that $(1,4)$ would have to be in the relation? That would be the case only if there some $x\in S$ such that both $(1,x)$ and $(x,4)$ were in it. – Brian M. Scott Oct 10 '16 at 17:15
  • Why do you think that $1$ would have to relate to $4$? – Matt Samuel Oct 10 '16 at 17:16
  • 1
    Notice that 2 !R 3. Transitive relation xRz requires xRy and yRz to exist. – Eemil Wallin Oct 10 '16 at 17:17
  • It might help to draw a graph of this, with the nodes representing elements of $S$, and edges from $x$ to $y$ representing $xRy$. You thus have an edge from $1$ to $2$, and another edge from $3$ to $4$. Since the edges do not connect head to tail (or, indeed, at all), transitivity is not violated. – Brian Tung Oct 10 '16 at 17:22
  • 1
    This is an instance of vacuous transitivity. See here, here and here. –  Oct 10 '16 at 17:24
  • 1
    "If $y=2$ and $y=3$ then..." - Well, it's definitely not the case that $2=3$, so we don't need to worry about what happens when $y$ equals both, since that never happens. That is, you can't redefine $y$ in the middle of your statement! – Milo Brandt Oct 10 '16 at 17:31

2 Answers2

2

Transitive relations are vacuously true. Thus if there is nothing to prove that a relationship is not transitive then it is inherently transitive. In the relation you mention here there is no $xRy$ and $yRz$ in the relation that makes the statement $xRy\land yRz\Rightarrow xRz$ false. Thus the relation is transitive.

ClownInTheMoon
  • 1,987
  • Thanks for your response, makes perfect sense. – petehockey Oct 10 '16 at 17:42
  • I think you mean 'true' instead of 'false' in the penultimate sentence. – heptagon Oct 10 '16 at 17:48
  • @heptagon no I meant false. Everything in the relation makes the statement evaluate to true since $F\Rightarrow T$ evaluates to true (if it evaluated to false our relation would not be transitive). Thus there is nothing in the relation that makes the statement evaluate to $T\Rightarrow F$ which would be false. – ClownInTheMoon Oct 10 '16 at 17:51
  • Thanks, I think you are right. Curiously, the sentences 'there is nothing in the relation, which [fact] makes the statement true' and 'there is nothing in the relation that makes the statement false' seem to have the same meaning in this context, and my initial understanding was as in the former sentence. – heptagon Oct 10 '16 at 19:19
2

A relation $R$ on a set $S$ is said to be transitive iff it fulfills the following:

For any $x, y, z$ in $S$, if $xRy$ and $yRz$, then $xRz$.

Now, in your case we cannot find $x, y, z$ such that $xRy$ and $yRz$. So what does the above definition even mean in this case?

This is a phenomenon (or perhaps a convention) in mathematics and logic called vacuous truth. If you have an "if-then" statement, and whatever follows the "if" is false, then the statement itself is considered true, no matter what follows after "then".

It might be a bit difficult to wrap your head around at first. I offer two explanations / interpretations, and hope that at least one of them can help you.

  1. An "if-then" statement is a promise. What I mean by that is that to prove an "if-then" statement true, then you have to guarantee that every time someone comes up to you with a case demonstrating that whatever follows "if" is true, you have to demonstrate that whatever follows the "then" is true.

    Take, for instance, "If it's raining outside, then the ground is wet." Someone points out and tells you that it's raining, you point to the ground and say it's wet. Promise kept. If you can show that you can always keep that promise, then the "if-then" statement is considered true.

    In this specific case, no one can ever come forward with a case of "$xRy$ and $yRz$", so you will be able to keep your promise. Therefore $R$ is transitive.

  2. Look at the contrapositive. The contrapositive of any statement is equivalent to the statement in itself. The contrapositive (or perhaps a contrapositive) of the definition of transitivity is

    For any $x, y, z \in S$, if $x\not R z$, then either $x \not R y$ or $y \not R z$ (where the slash means "not", so $x \not R y$ is equivalent to $(x, y) \notin R$).

    This is a bit of work to check, but hopefully the logic itself is a bit more intuitive.

Arthur
  • 199,419
  • Thanks for the explanation and this made perfect sense. My issue is applying this logic to different types of problems but I'll just have to keep practicing these until I get it down. – petehockey Oct 10 '16 at 17:42