Transitive closure of a relation

[icantadd]

Homework Statement

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.

Homework Equations

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.

 

[tiny-tim]

Hi icantadd!

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

Try it with k = l.

 

[icantadd]

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?

 

[tiny-tim]

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

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 Rⁿ is the "pairs of people with 2ⁿ degrees of connection" … that is, Bud know Fred knows … … … Ginger knows Lou (with 2ⁿ names)

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

 

[icantadd]

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!

 

[tiny-tim]

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!

Yes, that's exactly right!