composition/power of relation

Question

Let $A$ be a finite set so: $|A|=j$ and $S$ a relation on $A$.

Prove that there are $i,j\in \mathbb{N}$ that $i>j$ and $S^{i}=S^{j}$.

I tried to prove it with the definition, but without any success.

Answer 1

This does not have to be true if $\mathbb N$ is allowed to be unfinite.

If e.g. $A=\mathbb N$ and $nSm\iff m=n+1$ then $nS^im\iff m=n+i$ and $i\neq j\implies S^i\neq S^j$.

---

edit (after edit of question). If $A$ is finite then the number of relations on $A$ is finite so the function on $\mathbb N$ to the set of relations on $A$ prescribed by $i\mapsto S^i$ cannot be injective. This means that $i,j\in\mathbb N$ must exist with $i>j$ and $S^i=S^j$.

Answer 2

Suppose not, then for all $i$ and $j$, $S^i\neq S^j$. But now $S^i\subseteq A\times A$ for all $i$, and how many subsets can $A\times A$ even have?