```Date: Dec 12, 2012 5:26 AM
Author: Zaljohar@gmail.com
Subject: On the infinite binary Tree

WM has presented the idea that the infinite binary tree must havecountably many paths. It seems that he thinks that the total number ofpaths in a binary tree is always smaller than or equal to the totalnumber of nodes. So since obviously the number of nodes in an infinitebinary tree is countable, then the number of paths must be so. Butsince each real can be represented by a path in a 0,1 labeled infinitebinary tree, then we must have countably many reals thus defyingCantor.The 0,1 labeled infinite binary tree he is speaking of is thefollowing:     0   /    \  0     1 / \    / \0  1 0  1.  .  .     ..  .  .     .Answer: in order to justify this claim one must first see what ishappening at the finite level. And make a simple check of the numberof nodes and the number of paths through those nodes. If thatconfirmed that the total number of nodes is more or equal to pathsthen there would be some justification for that claim.Let's see:Lets take the first degree binary tree which is the following0.  One node, no pathsThe second degree binary tree is: 0/  \0 1This has three nodes and two paths.Lets take the third degree binary tree     0   /    \  0     1 / \    / \0  1 0  1Now this has 7 nodes BUT 8 paths, those are0-00-11-01-10-0-00-0-10-1-00-1-1Of course I'm treating paths as directed paths away from the rootnode, and so a path contain edges linking nodes in the SAME direction.IF we remove the directional requirement matters would really differ,since the number of paths will increase significantly compared tonumber of nodes, for example the second degree binary tree would haveThree paths those are:0-00-10-0-1However we will not adopt that, well keep with the directionalapproach we'll stipulate that paths must be uni-directional, i.e alledges between nodes of a path must be in the same direction. So in theexample above the third path would be shunned.As the degree of the binary tree increase the total number of pathsincreases more and more relative to the total number of nodes, asshown above this begins with the third degree binary tree (8 pathswith 7 nodes).So the impression we have from the finite world is that of paths beingactually MORE in number than nodes in any binary tree of a degreehigher than 2.One must remember an important matter here is that in the exampleabove of the third degree binary tree, we saw that the number of pathsIS bigger than the number of nodes and yet we are still away fromrepresenting all 3 node size paths with labels 0,1. Clearly thefollowing paths are missing:1-1-11-1-01-0-11-0-0However all of those would be represented in the 4th degree binarytree. The point here is that is at each x_th degree binary tree thenumber of paths is MORE than the number of nodes for a finite x > 2.And at each x_th level we don't have even a full representation of allpossible paths of size x. So we are only representing SOME of thepossible paths, but even that some is bigger in number than the totalnumber of nodes at the respective level.One can easily say that the defective representation of all possiblepaths of size x will be remedied by the binary tree at x+1 level, andso the infinite binary tree will succeed in representing all possiblepaths, which is OK. But still the total number of paths (given all therestrictions stipulated above which are meant to lessen their number)is MORE than the number of nodes, actually way more than it for >2finite level binary trees.So there is NO justification at intuitive level for the idea that thenumber of paths of a binary tree must be smaller than or equal thetotal number of nodes in it.We would think that if we go infinitely, i.e. if we have the actualinfinite binary tree, then the number of paths would be equal to thenumber of nodes. However Cantor's argument showed that this is not so.STILL even at infinite level, the trend displayed at finite levelcontinues up there. Still we have more infinite paths of the binarytree than we have nodes in it. This is very easy to prove, assume that the infinite binary tree hascountably many paths, then this mean by definition the existence of abijection between the set N of all natural numbers and the set of allpaths of the infinite binary tree, Now just diagonalize, and theresulting path would be a path missing from the set of all paths, Acontradiction. Thus it is not possible for the infinite binary tree tohave maximally countably many paths.This only shows how some arguments against Cantor which seem at thefirst glance to be justified only to turn finally to be unjustifiableat all.The truth of the matter is that the infinite binary tree does havecountablymany nodes, but it has uncountably many paths going through thosenodes.Zuhair
```