Can somebody please give a proof to why this relation is transitive?

Question

Relation

I don't understand why this relation is transitive as for (1,1) there isn't for example a (1,2) ?

Answer 1

Transitivity means that whenever the second element of one pair matches the first element of another something happens ...

Since there is no such match in this relation, the "whenever" never happens so there's nothing to check. The relation is transitive by default.

Answer 2

A rewording of transitivity can be thought of using terms borrowed from graph theory.

A (directed) walk is a sequence of pairs of any length (including one) such that consecutive pairs (if any exist) are such that the earlier pair's endpoint (second entry) is the same as the latter pair's starting point (first entry). The length of the walk is the number of pairs used to make the walk.

Examples of walks in this context would be

• $(1,2),(2,3),(3,4),(4,5),(5,6)$ (note that the length can be greater than two)
• $(1,3),(3,7)$ (note that the numbers themselves don't need to appear consecutively)
• $(2,5),(5,2),(2,5),(5,2)$ (note that we can revisit numbers as many times as we like)
• $(2,2),(2,5),(5,5)$ (note that we can even start and end in the same place in one of the pairs)
• $(1,1)$ (note that the walk can even be of length one)

Now... transitivity reworded in terms of these walks is that a relation is transitive iff every possible directed walk we can take made using pairs from our relation has an available "shortcut" or "direct route", a directed walk of length precisely $1$ such that we started and ended in the same place as the original walk did.

For example, if we had the pairs $(x,y),(y,z)$ in our relation, then we would also have wanted $(x,z)$ in our relation as well (among possibly many more) for the relation to be considered transitive. Similarly, if we had the pairs $(1,2),(2,1)$ in our relation we would have wanted $(1,1)$ in our relation too. (Note that in the traditional definition, we did not require that $x,y,z$ all be different).

As a special case to consider, the empty relation with no pairs in it at all is also considered transitive. After all, there aren't any directed walks who are missing a shortcut. The only way that a relation is not considered transitive is if you can find an example of a directed walk that is missing a shortcut. (equivalently, finding an $x,y,z$ not necessarily distinct such that $(x,y)$ and $(y,z)$ are in your relation but $(x,z)$ is not).

In your specific example, all possible available directed walks were of length $1$ in the first place, so of course they each have a "shortcut"... namely themselves. (we didn't require the shortcut actually save us time... just that it be of length $1$). Since we aren't in the situation that we had a directed walk who was missing a shortcut, the relation is indeed transitive.