Let $A$ be a finite set such that $|A|=n+1$ for some $2\le n$ and let $R\subseteq A\times A$ be some reflexive relation in $A$. Prove the following:

Question

Let $A$ be a finite set such that $|A|=n+1$ for some $2\le n$ and let $R\subseteq A\times A$ be some reflexive relation in $A$. We'll denote $R^{(k)}=R\circ R\circ .... \circ R$ ($k\in\mathbb{N^+}$ times)

Prove $R^{(n)}$ is a transitive relation.

Hey everyone. I had already proven that for all $1\le k\le m \Rightarrow R^{(k)}\subseteq R^{(m)}$ and proved that if there exists some $1\le k$ such that $R^{(k)}=R^{(k+1)}$ then for all $k \le m \Rightarrow R^{(m)}=R^{(k)}$ by induction.

Now, a relation $S$ is transitive iff $S\circ S \subseteq S$. So I need to show that $R^{(2n)}\subseteq R^{(n)}$.

According to the first claim I've proven, $R^{(n)}\subseteq R^{(2n)}$ so basically I need to prove that $R^{(2n)}=R^{(n)}$. According to the second claim I had proven, it is enough to show that $R^{(n)}=R^{(n+1)}$ and that would indicate $R^{(2n)}=R^{(n)}$ as desired. How can I show that $R^{(n)}=R^{(n+1)}$?

Thanks in advance.

Answer 1

(Getting yet another question off the unanswered list.)

Say that a finite sequence $\langle a_0,\ldots,a_m\rangle$ of elements of $A$ is an $R$-chain of length $m$ from $a_0$ to $a_m$ if $\langle a_k,a_{k+1}\rangle\in R$ for $k=0,\ldots,m-1$; it’s not hard to show that for any $a,b\in A$ and $m\in\Bbb Z^+$, $\langle a,b\rangle\in R^{(m)}$ iff there is an $R$-chain of length $m$ from $a$ to $b$.

Now suppose that $\langle a,b\rangle\in R^{(n+1)}$. Then there are $a_0,\ldots,a_{n+1}\in A$ such that $a_0=a$, $a_{n+1}=b$, and $\langle a_0,\ldots,a_{n+1}\rangle$ is an $R$-chain of length $n+1$ from $a$ to $b$. Then $\langle a_0,\ldots,a_{n+1}\rangle$ is an $(n+2)$-tuple, and $n+2>n+1=|A|$, so by the pigeonhole principle there must be integers $k$ and $\ell$ such that $0\le k<\ell\le m$, and $a_k=a_\ell$. But then clearly $\langle a_0,\ldots,a_k,a_{\ell+1},\ldots,a_{n+1}\rangle$ is an $R$-chain of length $n+1-(\ell-k)\le n$ from $a$ to $b$, so $\langle a,b\rangle\in R^{(n+1-\ell+k)}\subseteq R^{(n)}$. Thus, $R^{(n+1)}\subseteq R^{(n)}\subseteq R^{(n+1)}$, so $R^{(n+1)}=R^{(n)}$.

More generally, the same argument can be used to show that if $\langle a,b\rangle\in R^{(k)}$ for some $k\in\Bbb Z^+$, and $m$ is the smallest positive integer such that $\langle a,b\rangle\in R^{(m)}$, then $m\le n$ (and hence, of course, $\langle a,b\rangle\in R^{(n)}$).