Re: infinity
- From: Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx>
- Date: Fri, 2 Sep 2005 11:54:53 -0400
Virgil said:
> In article <MPG.1d7f9000c6e111a298a19f@xxxxxxxxxxxxxxxxxxxxxxxxx>,
> Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> wrote:
>
> > > > > I mapped paths from the same tree to sets of naturals so as to
> > > > > establish a bijection between them and the power set of N.
> > > >
> > > > Now you are trying to change things, but fine, let's examine what you
> > > > are now proposing. You claim to have branches mapped to all the
> > > > naturals in a 1-1 correspondence, and therefore countable. Then you
> > > > claim that the set of paths is the powerset of that set, and
> > > > therefore uncountable? You really should draw pictures before writing
> > > > words. Then you won't waste 1,000 of them sounding stupid. Here's
> > > > your tree, with each number being a branch/node:
> > > >
> > > > .
> > > > 1 2
> > > > 3 4 5 6
> > > > 7 8 9 10 11 12 13 14
> > > >
> > > > Which path contains the set {1,2,8,9}? None? How can this be? Is
> > > > there really a bijection between the paths of this tree and the
> > > > powerset of the naturals? Absolutely not. Each path will start with
> > > > either 1 or 2, so one of those will ALWAYS be a member of any path.
> > > > For any given subset defined by a path in this tree, the next largest
> > > > element to any n in the subset is either 2n+1 or 2n+2, not any
> > > > arbitrary m>n. This is obviously not corresponding to the power set
> > > > of N, but of a set of subsets which, given proper attention, can
> > > > undoubtedly be shown to be exactly N/2, if there are N branches,
> > > > since this is the correct answer.
> > > > >
> > > > > > Using the first, you "proved" that the branches are "countable",
> > > > > > and using the second you "proved" that the paths are
> > > > > > "uncountable".
> > > > >
> > > > > Precisely!
> > >
> > > > Ummmm.....didn't you just deny that you used two different trees, and
> > > > claim they were the same, above?
> > >
> > > No! I used one maximal binary tree, which has both branches and paths. I
> > > showed that the branches biject with the naturals and the paths bijecte
> > > with the power set of the naturals,
> > But look at the tree above. Is this not what you just described, a tree where
> > each branch is a natural? If that is the case, then the paths do NOT
> > correspond
> > to the power set, since most of the subsets of N are not included as paths.
> > Did
> > you not see my question, above? Which path corresponds to the set {1,2,8,9},
> > which would be a member of the power set? None. You have 8 paths with your 14
> > nodes in this initial segment. Why do you not have 2^14 paths, if the paths
> > biject with the power set? That is quite a discrepancy.
>
> The disrepancy is between what I described and what TO misunderstood me
> to have described. If he could actually read, perhaps such discrepancies
> would not occur, at least so often.
>
> Each path in an infinite binary tree consists of a sequence of branches
> which can be uniquely numbered with the infinitely many finite naturals,
> so that all paths have a branch 1 and a ranch 2 and a branch 3 and so on
> without end. Each path determines a set by including the numbers for
> each right branch and excluding the numbers for each left branch (the
> reverse would work equally well).
>
> This clearly bijects paths with subsets of N (the infinite set of finite
> naturals).
>
> Each node in the same tree can be matched with a unique natural in
> binary notation as follow: The root node is 1. For each left branch on
> the finite path from the root node to a given node, append 0, and for
> each right branch append 1. So the children of the root will be numbered
> 10 and 11, the grandchildren 100, 101, 110, and 111, and so on. the
> number of binary digits will be one more than the number of branches
> between the root and the node which matches the binary number.
>
> This clearly bijects the set of nodes of that same maximal binary tree
> with N (the infinite set of finite natural numbers).
>
> So that unless TO can construct a bijection between N (the infinite set
> of finite natural numbers) and P(N), there are more (in the sense of
> Cantor) paths than nodes.
>
Grrrrr.....you moron! That's exactly the way I described your proof to begin
with, which you denied. You have one tree where you label each node with a
natural number, and then another tree where you label each node with a bit
representing the membership of a natural in a set which is a member of the
powerset. If you think that the labeling of balls in the vase problem is
important, and the labeling of nodes in this problem is irrelevant, then you
have everything ass-backwards. In your first tree, where each node is a
natural, the tree represents the set of naturals and each path consists of SOME
set of naturals, but in this case the tree does not represent the power set of
the naturals, because only a very small subset of the possible sets of naturals
exist as paths. In the second, each path represents a unique set of naturals,
and the tree represents the power set of the naturals, but each node does not
represent a natural number. Each ROW represents a natural number, and for row
n, all of the 2^n nodes in the row correspond to that natural. So, you did do
exactly what I said you did, which is change your interpretation of the tree
mid-proof.
Let us try inductive proofs regarding the relationship between branches and
paths.
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.
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.
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.
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.
n=0: An empty binary tree with depth of 0 has b(0)=0 branches, and p(0)=1
paths.
n->n+1: With the addition of level n+1, each of the 2^n paths is doubled by the
addition of 2 branches, for a total addition of 2^(n+1) branches. Doubling the
paths we get 2*2^n = 2^(n+1) p(n+1) paths. Adding 2^(n+1) branches to the 2(2
^n-1) in tree n, we get 2^(n+1) + 2*2^n - 2 = 2(2^(n+1)-1) = b(n+1) branches.
all n: Therefore, for all maximal binary trees of any depth n, there are b(n)
branches and p(n) paths. b(n) = 2(p(n)-1) <=> p(n) = b(n)/2+1
Now, if we can establish this relationship between branches and paths, and you
have constructed a bijection between branches and elements of the set of
naturals, and between paths and elements of the power set of the naturals, then
you have just constructed the bijection which you challenge me to construct
between the set of naturals and the power set of the naturals. Certainly such a
bijection is possible, even though the sets are obviously different sizes.
--
Smiles,
Tony
.
- Follow-Ups:
- Re: infinity
- From: Virgil
- Re: infinity
- From: imaginatorium
- Re: infinity
- Prev by Date: Re: infinity
- Next by Date: Re: Poincare Duality
- Previous by thread: Re: infinity
- Next by thread: Re: infinity
- Index(es):
Relevant Pages
|
