$R$ can be any binary relation on $S$. $R^0:=I=\{(x,x):x\in S\}$, and $R^{i+1}:=R^i\cup(R;R^i)$ for $i\geq 0$. [Here, $(R;R^i)$ denotes the composition of relations - ed.]
If $|S|=k$, explain why $R^k=R^{k+1}$. I think it should prove if $(a,b)\in R^{k+1}$ then $(a,b)\in R^i$ for some $i<k+1$. But I don't know how to prove it.
Thanks.
Let $(a,b)\in R^{k+1}$. Then either $(a,b)\in R^{k}$ or there is a chain of $k+1$ elements $x_1,x_2,...x_{k+1}$ such that $x_1=a, x_{k+1}=b$ and each $(x_i,x_{i+1})\in R$.
However, $S$ only has $k$ elements and so at least two of the first $k$ elements of the chain must be the same. Let this element be $e$ and then we can replace all the elements between the two $e$s by $e$ itself whilst still keeping a chain of related elements. Furthermore we can remove one of these $e$s whilst still keeping a chain of related elements.
We have therefore proved that $(a,b)\in R^k$.