# How can you elegantly show that the relation is transitive?

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 :)

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

• I don't quite understand. So when every pair's first element is smaller than the second, this implies transitivity? Commented Nov 30, 2017 at 22:05
• Well, it is more like you reduce the problem to the 'known' transitivity of the $<$ relation. Commented Nov 30, 2017 at 23:18

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)$$.

• Oh thanks I didn't know about this trick! :D Would you say that visual inspection counts as a "reason"? Commented Nov 30, 2017 at 22:00
• @cnmesr Not quite that. The reason is that you must perform the check. Inspection is a method to quickly do so. Commented Nov 30, 2017 at 23:15

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.