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!