Re: infinity
- From: Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx>
- Date: Tue, 6 Sep 2005 14:16:39 -0400
imaginatorium@xxxxxxxxxxxxx said:
> Tony Orlow (aeo6) wrote:
> > Virgil said:
> > > In article <MPG.1d7f9000c6e111a298a19f@xxxxxxxxxxxxxxxxxxxxxxxxx>,
> > > Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> wrote:
> > > ...[?]
> > > > > > > I mapped paths from the same tree ...
>
> That's enough. I'm generally avoiding both tree and vase arguments,
> since they are far too complex. But let's just try a little...
>
> > Let us try inductive proofs regarding the relationship between branches and
> > paths.
>
> Uh-oh. OK, I'll try as well. I'll investigate how many ends there are
> in an endless tree (that's one in which every node branches into two
> child nodes, and this never never never never ends). Intuitively, I'd
> expect that an endless tree would not have any ends, since I've defined
> it that way, but let's see.
>
> > Proof: In a maximal binary tree, number of paths is half the number of
> > branches, plus 1.
> >
> > 1. For an empty tree consisting of the root node, there is one path in the
> > tree, of length zero, and no branches. 1 path = 0 branches/2 + 1.
>
> For an "empty" [not quite the right word, is it] tree, there is one
> end.
Uh, yeah, one path, like I said.
>
> > 2. If there are n branches, and n/2+1 paths, on level x, and we add level x+1,
> > each of the n/2+1 leaf nodes corresponding to a path will be extended by one
> > level by adding two branches, and each of the n/2+1 paths will be divided into
> > two paths, doubling the number of paths. So, our original n branches are
> > increased by 2*(n/2+1), and our original n/2+1 paths is doubled. This gives n+2
> > *(n/2+1) = n+n+2 = 2n+2 branches, and 2*(n/2+1) = n+2 paths. 1/2(2n+2)+1 = n+2.
>
> I think you mean that considering the tree that stops at level x, there
> are 2^x [plus/minus epsilon*] ends.
Yes, we are proving something true for a maximal binary tree of depth
corresponding to the natural numbers starting from zero, as a property of that
number.
>
> * Your notation is so woolly I can't be bothered to work it out
> exactly.
You can't understand the inductive part of the inductive proof? Did you try? If
n is the number of branches and n/2+1 is the number of paths, we add twice the
number of paths to the branches and double the paths at each step, so if b(n)
is the branches on level n, and p(n) is the number of paths on level n, and p
(n)=b(n)/2+1, then p(n+1)=b(n+1)/2+1, and the realtionship is maintained from n
to n+1.
>
> > 3. Therefore, each additional level added to the binary tree maintains this
> > relationship between branches and paths, and the number of paths is half the
> > number of branches, plus 1.
>
> Notice how the word "Therefore" is completely wrong. The statement is
> true, but is not a logical deduction from the previous one. Anyway,
> turtles all the way down.
Reread. In any case, you don't seem to disagree with the conclusion, so why
don't you explain it to Virgil?
>
> > Proof: In a maximal binary tree with paths of length n, or depth of n, there
> > are p(n)=2^n paths and b(n) = 2(2^n-1) = 2(p(n)-1) branches.
>
> What do you mean by "Proof"? Isn't this still part of the same
> argument? You would get more respect if you took the trouble to
> understand elementary notational conventions.
This was a second proof, using a slightly different statement.
>
> Anyway, never mind: to finish off *my* proof... By induction, the
> number of ends of an endless tree is infinity. Da-dah!!
yes, you are very clever......
>
> Brian Chandler
> http://imaginatorium.org
>
>
--
Smiles,
Tony
.
- Follow-Ups:
- Re: infinity
- From: imaginatorium
- Re: infinity
- References:
- Re: infinity
- From: aeo6
- Re: infinity
- From: imaginatorium
- Re: infinity
- Prev by Date: Re: Questions about Cartesian product
- Next by Date: Re: infinity
- Previous by thread: Re: infinity
- Next by thread: Re: infinity
- Index(es):
Relevant Pages
|
