-1

Is the relation R = {(1,1), (1,2),(1,3),(3,3)} transitive?

The definition of transitive relation is; if (a,b) and (b,c), then (a,c). but there is no (b,c). Does it make R transitive?

Asaf Karagila
  • 393,674
user3622981
  • 17
  • Yes, it's transitive. – Stefan Mesken Nov 15 '18 at 15:52
  • Note, $a,b,c$ do not need to be distinct. They could all be the same, two of them the same in whatever order, or all distinct. Your relation is transitive. For a different example the relation ${(1,2),(2,1)}$ is not transitive because although $(1,2)$ and $(2,1)$ are in the relation you have that $(1,1)$ is not. Here, $a,b,c$ are $1,2,1$ respectively. – JMoravitz Nov 15 '18 at 16:27
  • A rephrasing of transitivity using concepts from graph theory: Any directed path you can travel between elements of the relation along the directed edges of the relation, regardless of distance, must be traversable in a single step. Like how if $a<b$ and $b<c$ and $c<d$ and $d<e$, you must have that $a<e$ (as well as several others). – JMoravitz Nov 15 '18 at 16:29

1 Answers1

1

If I understand correctly, you're saying that $R$ is transitive because we never see any situation that transitivity applies to: e.g. if we had $(1, 2),(2,3)\in R$ then transitivity would require that $(1,3)$ be in $R$, but you're saying that this situation never occurs and hence $R$ is (vacuously) transitive.

This isn't quite right - there are transitivity-relevant situations. In fact, there are exactly two:

  • $(1,1)$ and $(1,2)$ are in $R$ (in this case $a=1, b=1, c=2$).

  • $(1, 3)$ and $(3, 3)$ are in $R$ (in this case $a=1, b=3, c=3$).

However, each of these are "silly" in a precise sense. Namely, they don't lead to anything new: the first says that in order for $R$ to be transitive we must have $(1,2)\in R$, and the second says that in order to be transitive we must have $(1,3)\in R$, but each of these required instances is already present in the situation described. This is an example of a more general phenomenon:

Suppose $R$ is such that whenever we have $(a,b),(b,c)\in R$, either $a=b$ or $b=c$. Then $R$ is transitive.

So while $R$ isn't quite vacuously transitive, it's still transitive in a kind-of-vacuous way: it has no serious instances to which transitivity applies.

So I would say that your reasoning is in the right direction, but isn't quite right. Your conclusion, however, is correct: $R$ is indeed transitive.

Noah Schweber
  • 245,398