|
|
| Author |
Message |
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
 Posted: Fri May 19, 2006 8:28 am Post subject:
Proof on transitive closure
|
|
|
I don't quite understand following proof.
Definition: Let R subset X^2 (cartesian product). Transitive closure of
R, TC(R), is smallest transitive relation T subset X^2 that contains R.
Lemma: TC(R) = intersection T_i, where T_i subset X^2, T_i is
transitive and R subset T_i for all i in I (I is an index set).
Clearly family {T_i} is non-empty because X^2 is transitive and R
subset X^2. Let R' = intersect T_i. Now R subset R' because R subset
T_i for all i. This is clear.
R' is also transitive: let <x,y> in R and <y,z> in R. Now for every T_i
holds
{ <x,y>, <y,x> } subset R subset T_i
because T_i is transitive <x,z> in T_i for every i and hence T is
transitive.
I'm not fully satisfied with the R' being transitive part. I think it
only proves that some subset, in this case R, of R' is transitive. What
am I missing here? [proof of T being smallest dropped out] |
|
| Back to top |
|
 |
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
| Posted: Fri May 19, 2006 8:53 am Post subject:
Re: Proof on transitive closure
|
|
|
un student wrote:
| Quote: | R' is also transitive: let <x,y> in R and <y,z> in R. Now for every T_i
holds
{ <x,y>, <y,x> } subset R subset T_i
because T_i is transitive <x,z> in T_i for every i and hence T is
transitive.
I'm not fully satisfied with the R' being transitive part. I think it
only proves that some subset, in this case R, of R' is transitive. What
am I missing here? [proof of T being smallest dropped out]
|
Doh, somehow I read <x,z> in R... Nevermind... |
|
| Back to top |
|
|
William Elliot
science forum Guru
Joined: 24 Mar 2005
Posts: 1906
|
| Posted: Fri May 19, 2006 9:07 am Post subject:
Re: Proof on transitive closure
|
|
|
On Fri, 19 May 2006, un student wrote:
| Quote: | Definition: Let R subset X^2 (cartesian product). Transitive closure of
R, TC(R), is smallest transitive relation T subset X^2 that contains R.
Lemma: TC(R) = intersection T_i, where T_i subset X^2, T_i is
transitive and R subset T_i for all i in I (I is an index set).
Clearly family {T_i} is non-empty because X^2 is transitive and R
subset X^2. Let R' = intersect T_i. Now R subset R' because R subset
T_i for all i. This is clear.
R' is also transitive: let <x,y> in R and <y,z> in R. Now for every T_i
holds
{ <x,y>, <y,x> } subset R subset T_i
|
No. Replace " in R " with " in R' "
| Quote: | because T_i is transitive <x,z> in T_i for every i and hence T is
transitive.
No, hence (x,z) in R' showing R' is transitive. |
You are confusing your variables. First you consider R' as the transitive
closure, then you use T, as was used in the first statement.
| Quote: | I'm not fully satisfied with the R' being transitive part. I think it
only proves that some subset, in this case R, of R' is transitive. What
am I missing here? [proof of T being smallest dropped out]
You are being most sloppy with variable names, carelessly confusing |
R,R' and T. Were you a programmer, your code would have crashed.
R' is transitive, R subset R' and in addition if
R" is transitive and R subset R", bby simple set theory
the construction gives R' subset R". Hence R' is the smallest
transitive relation with R subset R'. |
|
| Back to top |
|
|
William Elliot
science forum Guru
Joined: 24 Mar 2005
Posts: 1906
|
| Posted: Fri May 19, 2006 9:58 am Post subject:
Re: Proof on transitive closure
|
|
|
On Fri, 19 May 2006, William Elliot wrote:
| Quote: | On Fri, 19 May 2006, un student wrote:
Definition: Let R subset X^2 (cartesian product). Transitive closure of
R, TC(R), is smallest transitive relation T subset X^2 that contains R.
Lemma: TC(R) = intersection T_i, where T_i subset X^2, T_i is
transitive and R subset T_i for all i in I (I is an index set).
Clearly family {T_i} is non-empty because X^2 is transitive and R
subset X^2. Let R' = intersect T_i. Now R subset R' because R subset
T_i for all i. This is clear.
R' is also transitive: let <x,y> in R and <y,z> in R. Now for every T_i
holds
{ <x,y>, <y,x> } subset R subset T_i
No. Replace " in R " with " in R' "
Whoops, missed that, { (x,y), (y,z) } subset R'. |
However you are fuzzing thinking, making too much step at once.
Here's detailed logic to clarify the situtation.
Assume (x,y), (y,z) in R'
Thus for all i in I, (x,y), (y,z) in T_i
and as all T_i are transitive
for all i in I, (x,z) in T_i.
Thus (x,z) in R' which shows how R' is transitive.
| Quote: | because T_i is transitive <x,z> in T_i for every i and hence T is
transitive.
No, hence (x,z) in R' showing R' is transitive.
You are confusing your variables. First you consider R' as the transitive
closure, then you use T, as was used in the first statement.
I'm not fully satisfied with the R' being transitive part. I think it
only proves that some subset, in this case R, of R' is transitive. What
am I missing here? [proof of T being smallest dropped out]
You are being most sloppy with variable names, carelessly confusing
R,R' and T. Were you a programmer, your code would have crashed.
R' is transitive, R subset R' and in addition if
R" is transitive and R subset R", bby simple set theory
the construction gives R' subset R". Hence R' is the smallest
transitive relation with R subset R'.
|
|
|
| Back to top |
|
|
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
| Posted: Sun May 21, 2006 7:33 am Post subject:
Re: Proof on transitive closure
|
|
|
William Elliot wrote:
| Quote: | You are being most sloppy with variable names, carelessly confusing
R,R' and T.
|
Yep. I'm doing too much in my head and taking too big steps, which
leads to problems exactly like this.
| Quote: | Were you a programmer, your code would have crashed.
|
Well, I am  Actually this gives an interesting idea, maybe I should
start to "program" my proofs instead "making notes" while I make
progress. It could actually work |
|
| Back to top |
|
|
William Elliot
science forum Guru
Joined: 24 Mar 2005
Posts: 1906
|
| Posted: Sun May 21, 2006 9:47 am Post subject:
Re: Proof on transitive closure
|
|
|
On Sun, 21 May 2006, un student wrote:
| Quote: | William Elliot wrote:
You are being most sloppy with variable names, carelessly confusing
R,R' and T.
Yep. I'm doing too much in my head and taking too big steps, which
leads to problems exactly like this.
Were you a programmer, your code would have crashed.
Well, I am Actually this gives an interesting idea, maybe I should
start to "program" my proofs instead "making notes" while I make
progress. It could actually work :)
Don't. The similarity between math and computerese is like the similarity |
between a woman and a transvestite. If you don't understand the material
at hand, math, accounting, inventory control, etc. how can you make useful
program design, much less useful code. No, problem description, problem
solution, program design and finally coding, in that order.
No your honor, I did crash into those cars. My automatic driving software
crashed. Charge MicroSoft with that reckless driving and those wrecks. |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Thu Jan 08, 2009 10:43 pm | All times are GMT
|
|
Debt Consolidation | Mortgage | Unblock Myspace | Bad Credit Mortgages | Mortgage insurance
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Undergraduate
