Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Computing pi (or not)
Posted:
Sep 14, 2012 11:04 AM


Dave Renfro says: >The tree "paradox" is a standard technique/idea in set theory and logic,
Dave, did you mean to include the word paradox here? It looks very interesting, a really excellent paradox, but I don't see it very widely discussed. Actually not discussed at all, even on Planet Math where we find it summarized (see below.)
A more in depth versions appears here as referenced by planetMath: http://arxiv.org/ftp/arxiv/papers/0709/0709.4102.pdf
I'll gladly admit I don't see any easy way to dispose of this. Others?
paradox of the binary tree   The complete infinite binary tree is a tree that consists of nodes (namely the numerals 0 and 1 ) such that every node has two children which are not children of any other node. The tree serves as binary representation of all real numbers of the interval [01] in form of paths, i.e., sequences of nodes.
Every finite binary tree with more than one level contains less paths than nodes. Up to level n there are 2n paths and 2n+1?1 nodes.
Every finite binary tree can be represented as an ordered set of nodes, enumerated by natural numbers. The union of all finite binary trees is then identical with the infinite binary tree. The paradox is that, while the set of nodes remains countable as is the set of paths of all finite trees, the set of paths in the infinite tree is uncountable by Cantor's theorem. (On the other hand, the paths are separated by the nodes. As no path can separate itself from another path without a node, the number of separated paths is the number of nodes.)
 End of Forwarded Message



