Showing that if $X$ is finite and $R$ is a relation on $X$, then there exists $r,s\in\mathbb{N}$ such that $R^r=R^s$ I've been asked to prove that if $X$ is finite and $R$ is a relation on it, then there exists $r,s\in\mathbb{N},r<s$, such that $R^r=R^s$. For context, the symbol $R^n$ is defined inductively as follows: $R^1=R$, $R^{n+1}=R\circ R^n$.
Here is my attempt:
Since $X$ is finite, we know also that $X\times X$ is finite, and there are a finite number of subsets with an upper bound being $|\mathcal{P}(X\times X)|$. Assume $R^r\neq R^s$ for all $r,s\in\mathbb{N}$. Then we have an infinite number of distinct subsets $R^1,R^2,R^3,\ldots$. However, we know that this is untrue, as the maximum number of distinct subsets of $X\times X$ is $|\mathcal{P}(X\times X)|$. Therefore, there exists some $r,s\in\mathbb{N}$ such that $R^r=R^s$.
To me, this looks quite unsatisfying for reasons I can't explain, and I would like to know how I could better do this. Thanks for your time!
 A: Your argument is completely fine; you can trim things down a bit and still have it work out nicely. I would write it like this:

Since $X$ is finite, we also know that $X\times X$ is finite, and therefore that $P(X\times X)$ is finite. Since the infinite sequence $R^1,\,R^2,\,R^3\,\ldots$ always lies in this finite set, by the pigeonhole principle, there must be some $r$ and $s$ such that $R^r = R^s$.

where we eliminate using the $|\cdot |$ notation exactly once (even though we'd already been using the language of finiteness) and eliminated the contradiction argument, since this contradiction of "assume they are all distinct" more properly belongs to the pigeonhole principle (or, even more properly, is not necessary at all to prove the statement "any function from an infinite set to a finite one has some pair of distinct inputs mapping to the same output"). Of course, this relies on all the facts that you cite (products and power sets of finite sets are finite and the pigeonhole principle) being already evident to the reader.
