I found a question somewhat difficult, on An Invitation to Discrete Mathematics, by Matousek et al., which goes as below. $\newcommand{\op}[2]{ \left\langle #1 ,\, #2 \right\rangle }$ $\newcommand{\rel}[1]{ \mathcal{#1} }$
Question:
For a relation $\rel{R}$ on a set $X$ we define the symbol $\rel{R}^n$ by induction: $$\rel{R}^1 = \rel{R},\, \rel{R}^{n+1}=\rel{R} \circ \rel{R}^n$$
(a) Prove that if $X$ is finite and $\rel{R}$ is a relation on it, then there exist $r, s \in \mathbb{N}$, $r < s$, such that $\rel{R}^r = \rel{R}^s$.
(b) Find a relation $\rel{R}$ on a finite set such that $\rel{R}^n \neq \rel{R}^{n+1}$ for every $n \in \mathbb{N}$.
(c) Show that if $X$ is infinite, the claim (a) need not hold (i.e. a relation $\rel{R}$ may exist such that all the relations $\rel{R}^n$, $n \in \mathbb{N}$, are distinct).
My Attempt:
I had some trouble to define a finite set rigorously. Later, I decided not to struggle with the definition of the finite set. Instead, I chose to use a concept, Adjacency Matrix, to solve the problem.
First, I start with observing some examples. Let $\rel{R} = \left\{ \op{x}{y} \mid x < y \right\} \subseteq A \times A$, where the set $A = \left\{ 1,\, 2,\, 3,\, 4,\, 5 \right\}$, while $\op{x}{y}$ is an ordered pair: $\op{x}{y} = \left\{ \left\{ x \right\},\, \left\{ x,\,y \right\} \right\}$. Now it is possible to make a graphic presentation of the relation $\rel{R}$ on the set $A$ as followed:
Furthurmore, the adjacency matrix of the relation $\rel{R}$ is:
\begin{align} J_{\rel{R}^1} = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{align}
Similarly, we can get the graphic presentation and the adjacency matrix of the composite relation $\rel{R}^{2} = \rel{R}\circ\rel{R}$.
\begin{align} J_{\rel{R}^2} = \begin{bmatrix} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{align}
And so forth, the adjacency matrix of the composite relation $\rel{R}^{3}$, $\rel{R}^{4}$ and $\rel{R}^{5}$ are:
\begin{align} J_{\rel{R}^3} = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{align}
\begin{align} J_{\rel{R}^4} = \begin{bmatrix} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{align}
\begin{align} J_{\rel{R}^5} = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{align}
It's obvious that $\forall i \in \mathbb{N},\, i > 5 :\: J_{\rel{R}^i} = J_{\rel{R}^5} = 0$, i.e. $\forall i \in \mathbb{N},\, i > 5 :\: \rel{R}^i = \rel{R}^5 = \varnothing$.
Meanwhile, let $\rel{S} = \left\{ \op{x}{y} \mid x = y \right\} \subseteq A \times A$. We can get $\rel{S} = \left\{ \op{1}{1},\, \op{2}{2},\, \op{3}{3},\, \op{4}{4},\, \op{5}{5} \right\}$. it's obvious that $\forall i \in \mathbb{N} :\: J_{\rel{S}^i} = I \;\land\; \rel{S}^{i} = \rel{S}$.
After the observation of some special cases as listed above, I started to prove the first sub-question.
Suppose $A$ is a finite set with n elements.
$$ A = \left\{a_1,\,a_2,\,\ldots{},\,a_n\right\} $$
Suppose $\rel{R}$ is a relation on $A$. It can be completely described by an $n \times n$ matrix $M = \left(m_{ij}\right)$, $i,\,j \in \left[1, n\right] \cap \mathbb{N}$, where \begin{align} m_{ij} = \left\{ \begin{array}{c} 1,\ \text{if}\ \op{a_i}{a_j} \in R \\ 0,\ \text{if}\ \op{a_i}{a_j} \notin R \end{array} \right. \end{align}
I've got so far, but I cannot figure it out how to prove any of three sub-questions at all. Could you please help me? Thx in advance.
Question a) For $X$ is finite, the set of relations on $X$ is also finite, as a relation is a an element of the powerset $\mathcal P(X \times X)$. Therefore $\mathcal R^r = \mathcal R^s$ for some $r \lt s$.
Question b) Take $X = \{1,2\}$ and $\mathcal R = \{(1,2), (2,1)\}$.
Question c) Take $X = \mathbb N$ and $\mathcal R = \{(0,1), (1,2), (2,3), \dots\}$.