Virgil
Posts:
9,012
Registered:
1/6/11


Re: On the infinite binary Tree
Posted:
Dec 12, 2012 4:10 PM


In article <d0fbd129bd8c414491e12f47e5b6a4d5@w3g2000yqj.googlegroups.com>, WM <mueckenh@rz.fhaugsburg.de> wrote:
> On 12 Dez., 11:26, Zuhair <zaljo...@gmail.com> wrote: > > WM has presented the idea that the infinite binary tree must have > > countably many paths. It seems that he thinks that the total number of > > paths in a binary tree is always smaller than or equal to the total > > number of nodes. So since obviously the number of nodes in an infinite > > binary tree is countable, then the number of paths must be so. But > > since each real can be represented by a path in a 0,1 labeled infinite > > binary tree, then we must have countably many reals thus defying > > Cantor. > > Correct. It is nice that there are mathematician who have grasped it.
Zuhair has only grasped what it is that you claim, he has not endorsed it as being valid.
And almost certainly won't because it isn't
Each path in a CIBT (complete infinite binary tree) corresponds uniquely to the set of level numbers at which the path branches left.
Thus there is simple and obvious bijection between the set of all paths of a CIBT and the set of subsets of N+ ( the N without a 0 in it) For every finite set, its power set is of larger cardiality, with the difference in sizes increasing rapidly as the set sizes increases. It seems obvious, and Cantor proved, that for any infinite set its power set would again be larger than the base set.
Thus, despite WM's claims to the contrary, no countable set can surject onto the set of all such paths of a COMPLETE binary tree..
> The issue is this: > Every partial tree from level 0 to level n has > 1 + 2^(n+1) nodes. > The number of all finite paths is the same, because every finite path > ends at some node. > The number of all path traversing the complete partial tree and > branching after that in two paths is > 2^(n+1). > In the limit we have > numbers of paths traversing the complete tree (and after that > branching in two paths) divided by number of nodes of the complete > tree = 1.
How does a path which has finished traversing the complete tree have any further branching possible? It is a stupid selfcontradiction to claim that a process which has been completed will then continue beyond its completion. 

