A property of reflexive transitive closure

Question

Suppose $R$ is a binary relation on a set $S$. Let $R^+$ be the reflexive transitive closure of $R$. That is, $R^+$ is minimal relation which includes $R$ and is both transitive and reflexive. By minimal I mean that no proper subset of $R^+$ which includes $R$ is transitive and reflexive.

If a pair $(A,B)$ belongs to $R^{+}$, then there exists a finite sequence $C_1,\ldots,C_n$ of elements of $S$ such that:

1. $C_1 = A$
2. $C_n = B$
3. For every $i$ in $\{1,\ldots,n-1\}$, $R(C_i,C_{i+1})$ (that is, the pair $(C_i, C_{i+1})$ belongs to $R$).

Is this statement true? (I guess so) If so, is there a theorem which justifies it?

Answer 1

It’s straightforward to show that any pair $\langle A,B\rangle$ that satisfies your condition belongs to $R^+$, since it must belong to any reflexive, transitive relation containing $R$. On the other hand, it’s also easy to check that that the set of all pairs satisfying your condition is a reflexive, transitive relation containing $R$ and hence contains $R^+$. Thus, $R^+$ is precisely that set of pairs.

Answer 2

In sentence 3, you must replace $R$ with $$R'=\{(x,y):x=y\lor (x,y)\in R\lor (y,x)\in R\}.$$ Define the relation $T$ on $S$ where $(A.B)\in T$ iff there exist $c_1,..c_n$ with $A=c_1,\; B=c_n$, and $(c_i,c_{i+1})\in R'\;$ if $1\leq i<n$. It is easy to show that $T$ is reflexive and transitive, and that $T\supset R'.$

Suppose $U$ is transitive and reflexive on $S$, and $S\supset R$. Obviously $ S\supset R'.$ From the def'n of $T$ we can easily show that $U\supset T\;$. (Observe that if $j=i$ or $j=i+1$, and $(c_i,c_j)\in R'$, then $(c_i,c_j)$ belongs to both $T$ and to $ U$.) Hence $T$ is minimal, that is, $T=R^+$.