How can you elegantly show that the relation is transitive?

Question

I have a problem in keeping my reasoning short (that a relation is transitive). As example, let's take the set $S = \left\{1,2,3,4\right\}$ where the relation is $R = \left\{(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)\right\}$.

That relation is transitive but how can you easily show that?

My approach was going pairwise until I realized that's probably the most inefficient way. By pairwise I mean something like that:

$R$ is transitive because:

$(1,2) \in R$ and $(2,3) \in R \Rightarrow (1,3) \in R$ is satisfied,

$(1,2) \in R$ and $(2,4) \in R \Rightarrow (1,4) \in R$ is satisfied,

...

Although my approach is very bad, I'd like to know if it's correct?

But I'm more interested in knowing a better way of showing this :)

Answer 1

Note that $(i,j)\in R$ is equivalent to $i<j.$ Now transitivity translates into a general property of the less-than property.

Answer 2

By visual inspection $R = \begin{Bmatrix} \times&(1,2),& (1,3),& (1,4),\\ \times&\times& (2,3),& (2,4),\\ \times&\times&\times& (3,4)\\\times&\times&\times&\times\end{Bmatrix}$ and thus the matrix is transitive.

$(1,2) \in R$ and $(2,3) \in R \Rightarrow (1,3) \in R$ is satisfied,

$(1,2) \in R$ and $(2,4) \in R \Rightarrow (1,4) \in R$ is satisfied,

...

Exactly. You need to make an exhaustive check that nowhere does $(x,y),(y,z)$ exist without also $(x,z)$.

Answer 3

Note that on the natural numbers $<$ is defined using the successor operator $s$.

We say that $x<y$ iff there exists $k$ such that $y=s^k(x)=\underbrace{s\circ\cdots\circ s}_{k\text{ times}}(x)$.

So the transitivity is ensured because of composition properties $x<y$ and $y<z$ then $z=s^l(y)=s^l(s^k(x))=s^{l+k}(x)$ so $x<z$.

Here in $S=\{1,2,3,4\}$ seen as a subset of $\mathbb N$ your $R$ is defined such that $1$ is in relation only with its successors $2,3,4$ and same for $2$ and $3$ and $4$, so $R$ is just the restriction of $<$ to the set $S$ and thus is transistive.