2

Does there exist a set $S$ and a binary relation $R$ on $S$ such that the sequence $$\DeclareMathOperator{\sym}{sym} \DeclareMathOperator{\tr}{tr} R,\ \sym(R),\ \tr(\sym(R)),\ \sym(\tr(\sym(R))),\ \tr(\sym(\tr(\sym(R)))),\ \ldots $$ (where sym means symmetric closure and tr means transitive closure) contains infinitely many distinct elements?

If not, what is the largest number of elements it can contain, if indeed there is a largest number it can contain?

Rócherz
  • 3,976
user107952
  • 20,508

1 Answers1

4

A useful fact is that if $R$ is symmetric, then $\mathsf{tr}(R)$ is symmetric. To prove this, go back to the definition of transitive closure. If there is a sequence of edges in $R$ from $u$ to $v$, then because $R$ is symmetric, we can read the same sequence in reverse.

It follows from this that if $R$ is symmetric, $\mathsf{sym}(\mathsf{tr}(R)) = \mathsf{tr}(R)$. Also, you should see that $\mathsf{tr}(\mathsf{tr}(R)) = R$ and $\mathsf{sym}(\mathsf{sym}(R)) = R$.

From the above facts, we can see that your entire sequence of relations can have at most three distinct relations: $R$, $\mathsf{sym}(R)$, and $\mathsf{tr}(\mathsf{sym}(R))$. All the rest of the operations are no-ops.