# Transitive closure of a relation

1. Jan 14, 2009

1. The problem statement, all variables and given/known data
Let R be a relation and define the following sequence
$$R^0 = R$$
$$R^{i+1} = R^i \cup \{(s,u) \vert \exists t, (s,t) \in R^i, (t,u) \in R^i \}$$
And
$$R^{+} = \bigcup_{i} R_i$$
Prove that $$R^{+}$$ is the transitive closure.

2. Relevant equations

3. The attempt at a solution
1)
$$R = R_0 \subset R^{+}$$

2) show transitive
Assume $$xR^{+}y,yR^{+}z$$ Then there is a
k, such $$\exists u, xR^{k}u, uR^{k}y$$, and
l, such $$\exists w, yR^{l}w, wR^{l}z$$
Therefore $$\exists m \geq k+l, xR^{k+l}z$$, because ??
I don't know why I think this is the way to go, and I don't know how to finish this part of the proof. I will continue on. Please suggestions here??

3) show smallest transitive relation (by induction)
Let T be any other transitive relation containing R.
(I) $$R^0 = R \subset T$$
(II) Assume $$R^n \subset T$$ and let $$xR{n+1}y$$. Then there is a z, such that
$$(x,y) \in R^n \cup \{(x,y) \vert (x,z) \in R^n, (z,y) \in R^m \}$$
Now if $$(x,y) \in R^n$$ then we are done. Assume $$(x,y) \in \{(x,y) \vert (x,z) \in R^n, (z,y) \in R^m \}$$. Then because $$R^n \in T$$ , then $$(x,z) \in T, (z,y) \in T$$. Then because T is transitive (x,y) is in T.
????Is my last statement here correct????

Therefore $$R^n \subset T$$

Any help on the above two questions would be greatly appreciated.

2. Jan 15, 2009

### tiny-tim

Try it with k = l.

3. Jan 15, 2009

Do you mean max{k,l}?
I got credit for changing my answer to that. Meaning I had the answer right. I seem to have trouble in this area, a lot of times, I know that something is working, but I don't know how to justify it to myself. For example, with this problem I can look at it, and say "yes, that is obvious" and write a proof that is technically right, but then I look back at it and I don't know why. Why does that answer work? Because you are guaranteeing recursively that the relation is transitive one step at a time. So then I realize my question is okay, how do you know you are making the relation transitive one step at a time? And to that I simply answer, "because it is" and that just isn't good enough for me.

How do I correctly state what I am thinking on this problem, what is it that makes this work?

4. Jan 15, 2009

### tiny-tim

mmm … all I can suggest is that, in a problem like this, you start by translating the definition into words before you do anything else

in this case, stare at the definition until you satisfy yourself that Rn is the "pairs of people with 2n degrees of connection" … that is, Bud know Fred knows … … … Ginger knows Lou (with 2n names)

then you can safely predict what will happen, and translate it back into symbols

5. Jan 15, 2009

Then (somewhat removed from the original question) it is appropriate to say something like,
at R^n for any (a,b) there is a set$$\{(a,a_1) (a_1,a_2) , ... , (a_{n-1},b)\}$$whose size is at most n.

Back to the problem:
At any rate, if i take m = max {k,l}, then clearly we have
$$xR^{m}y$$ and also $$yR{m}z$$, and therefore in $$R^{m+1}$$ we will have $$xR^{m+1}z$$. I think I am getting it. Thank you!

6. Jan 15, 2009

### tiny-tim

Yes, that's exactly right!