0

$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.

metamorphy
  • 39,111
LIQI JIANG
  • 1
  • Since you speak about the reflective relation, you can notice that there is never an 'inter-mediate' to composite a new pair, but the element itself. Try induction, it will be easy to show this way – friedvir Oct 31 '19 at 08:28

1 Answers1

1

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$.