Conjecture about the transitive closure of a relation $\mathcal R $ over a finite set $A$

Question

Given a binary relation $\mathcal R$ over a set $A$,then the transitive closure of $\mathcal R$ over $A$ is the smallest transitive relation on $A$ containing $\mathcal R$, it's indeed the intersection of all transitive relations over $A$ that are a superset of $\mathcal R$.

The transitive closure of $\mathcal R$ is denoted by $\mathcal R^{+}$ and has the following explicit formula: $$\mathcal R^{+}=\bigcup_{n=1}^{\infty} \mathcal R^n$$

Where $\mathcal R^1=\mathcal R$, and

$\mathcal R^{n+1}=\mathcal R^n ∘ \mathcal R^1\tag{$n \in \mathbb N^+$}$

---

The first time I faced the formula I thought that it is not practically applicable,since it's needed to take the union of infinitely many relations (with infinity many distinct relations).

However after working with some sets I realized that it's not generally true,for example let $\mathcal R$ be a set over $A=\left\{1,2,3\right\}$ defined as $$\mathcal R:=\left\{(3,2),(2,3)\right\}$$ Then one can prove by induction that $$\mathcal R^{2n}=\left\{(3,3),(2,2)\right\}=\text{id}_A \setminus \left\{(1,1)\right\}\;,\;\mathcal R^{2n-1}=\left\{(3,2),(2,3)\right\}=\mathcal R\tag{$n \in \mathbb N^{+}$}$$

So the transitive closure of $\mathcal R$ over $A$ is given by:

$$\mathcal R^{+}=\bigcup_{n=1}^{\infty} \mathcal R^n=\left[\bigcup_{n=1}^{\infty} \mathcal R^{2n-1}\right]\cup \left[\bigcup_{n=1}^{\infty} \mathcal R^{2n}\right] $$ $$=\mathcal R \; \cup \text{id}_A \setminus \left\{(1,1)\right\}=\left\{(3,2),(2,3),(3,3),(2,2)\right\}$$

I computed the transitive closure of $\mathcal R$ over a few sets,and all of them had such a pattern,neither of them needed the union of an infinite number of infinity many distinct relation to be taken.

The questions are :

• Is this true that to determine the transitive closure of a relation $\mathcal R $ over a finite set $A$, we always just need to take the union of infinite number of finitely many distinct relations on $A$?
• If no,then give a counterexample, if yes then please prove it.

Answer 1

Let $A$ be a set with $n$ elements. Let $a, b \in A$ such that $a \mathcal{R}^{+} b$. Then there is a $k$ and there are are $c_{i} \in A$, for $i = 1, 2, \dots, k$, such that $$ \tag{chain} a \mathcal{R} c_{1} \mathcal{R} c_{2} \mathcal{R} \dots \mathcal{R} c_{k} \mathcal{R} b.$$ Suppose further that $k$ is smallest such that (chain) holds.

If $c_{i} = c_{j}$ for some $i < j$, we also have $a \mathcal{R} c_{1} \mathcal{R} \dots \mathcal{R} c_{i} \mathcal{R} c_{j+1} \mathcal{R} \dots \mathcal{R} b$, a shorter chain. (The same holds if $a = c_{i}$ or $c_{i} = b$ for some $i$.) Therefore we may assume that in (chain) $a, b$ and the $c_{i}$ are distinct. It follows that $k \le n - 2$, so that $$ \mathcal{R}^{+} = \bigcup_{i=1}^{n-1} \mathcal{R}^{i}. $$

Answer 2

It helps to understand intuitively what the transitive closure does at each step. Suppose $A$ is a set, and we have a relation $R$ on $A$. Then, for any $n\geq1$, the relation $aR^nb$ says that there exist $x_1,\dots,x_n$ such that $aRx_1$, $x_nRb$, and $x_iRx_{i+1}$ for all $i$.

Formally, the transitive closure $R^+ := \bigcup_{n\geq1}R^n$ is given so that $aR^+b$ if $aR^nb$ for some $n\geq1$; that is, $a$ is related to $b$ in the transitive closure of $R$ iff we can connect $a$ to $b$ through finitely many $x_1,\dots,x_n$ such that $aRx_1$, $x_nRb$, and $x_iRx_{i+1}$ for some $n$.

If we truncate the union and consider $R^{\leq N} := \bigcup_{n=1}^NR^n$, we get a similar relation, except that $aR^{\leq N}b$ iff we can connect $a$ to $b$ through at most $N$ intermediate $x_1,\dots,x_n$ (that is, $n\leq N$).

Now, in the case that $A$ is finite, let $N := |A|$, then it turns out that $R^+ = R^{\leq N}$ (that is, you only need to take a finite union $\bigcup_{n=1}^{|A|}R^n$ to obtain the transitive closure)! To see this, suppose $aR^+b$, so $a$ is related to $b$ in the transitive closure of $R$. Connect $a$ to $b$ via $x_1,\dots,x_n$.

• if $n\leq N$, then this means $aR^{\leq N}b$ and there is nothing to do
• otherwise, $n>N$, meaning that there are more $x_i$'s than there are elements of $A$ (since $|A|=N$). By the pigeonhole principle, we will have for some $i<j$ that $x_i=x_j$. Therefore, we can shorten our chain $aRx_1Rx_2\dots x_nRb$ by removing the terms $x_{i+1},\dots,x_j$. This produces a strictly shorter chain $x_1,\dots,x_i,x_{j+1},\dots,x_n$ connecting $a$ to $b$. Inductively, we can repeat this process until the length of the chain is $\leq N$, showing that $aR^{\leq N}b$ as before.

Therefore, you're right: if $A$ is a finite set, then we need only take the union up to $N := |A|$ (in fact, it is enough to take the union up to $|A|-1$) to form the transitive closure. Why is the transitive closure defined with an infinite union then? This is because we may need to take an arbitrarily large (albeit still finite) union to obtain the transitive closure. To see this, just consider the set $A = \{1,\dots,N\}$ and the relation $R$ defined by saying $iR(i+1)$ for all $1\leq i<N$. Taking the transitive closure of $R$ will require at least $N-1$ iterations of the union to ensure that $1$ gets related to $N$.

Moreover, the reason that we take an infinite union in the definition is because it continues to work even if $A$ is infinite. If $A$ is an infinite set and $R$ is some relation on $A$, you can check that $R^+ := \bigcup_{n\geq1}R^n$ will in fact be the smallest transitive relation containing $R$ (transitivity is easy to see by using the interpretation of $R^+$ provided in the second paragraph).