0
$\begingroup$

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

$\endgroup$

3 Answers 3

4
$\begingroup$

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

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

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

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

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .