0

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?

Evgenii.Balai
  • 299
  • 1
    Include your definition of reflexive transitive closure. Your question sounds like it would be immediate from the definition. – coffeemath Apr 03 '16 at 01:16
  • It’s almost true: you forgot the case $A=B$. Are you defining $R^+$ to be the intersection of all reflexive, transitive relations on $S$ that contain $R$? – Brian M. Scott Apr 03 '16 at 01:16
  • I have added the definition of reflexive transitive closure. I think the statement is true for A = B. In this case the sequence consists of one element, A, and the quantified statement from 3. is vacuosly satisfied. – Evgenii.Balai Apr 03 '16 at 01:23
  • 1
    @Evgenii: Fair enough; some of the people asking questions aren’t clear on vacuous truth, so I tend to treat such cases explicitly. \ 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. – Brian M. Scott Apr 03 '16 at 01:28
  • @BrianM.Scott Thank you! Indeed, both directions are easy to verify. If you post the answer below I'll accept it. – Evgenii.Balai Apr 11 '16 at 01:26
  • @Evgenii: Done. (Sorry to be so slow; I was out for most of the day.) – Brian M. Scott Apr 11 '16 at 22:04

2 Answers2

1

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

DanielWainfleet
  • 57,985
  • I think T constructed above is not the reflexive transitive closure of $R$. Consider the set $S = {1,2}$, and relation $R = {(1,2)}$. Then we have: $R' = {(1,2),(2,1),(1,1),(2,2)}$, $T = {(1,2),(2,1),(2,2),(1,1)}$. $T$ however is not the reflexive transitive closure of $R$, because a smaller relation ${(1,2),(2,2),(1,1)}$ is also transtive and reflexive. I wonder if the statement I have is true as given for an arbitrary set and relation, without changing either of sentences 1-3. – Evgenii.Balai Apr 11 '16 at 01:10
  • I think you are right. I recall that when I wrote it I was thinking, wrongly, that $R^t$ had to be symmetric also. – DanielWainfleet Apr 11 '16 at 02:25
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.

Brian M. Scott
  • 616,228
  • Thank you! For completeness, I wrote the proof in detail here: https://github.com/iensen/Math/raw/master/Property%20of%20Reflexive%20Transitive%20Closure/tr_n.pdf – Evgenii.Balai Apr 12 '16 at 02:49
  • 1
    @Evgenii: You’re welcome! I didn’t check absolutely every detail, but it looks good. – Brian M. Scott Apr 12 '16 at 03:02