## You are here

Homeparadox of the binary tree

## Primary tabs

# 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 [0,1] 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 2^n paths and 2^(n+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.)

Literature: W. Mückenheim: Die Mathematik des Unendlichen, Shaker-Verlag, Aachen 2006.

## Mathematics Subject Classification

03E75*no label found*03E15

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## paradox of the binary tree

This article should detail the argument (more like it is in "W. MÃƒÂ¼ckenheim: Die Mathematik des Unendlichen, Shaker-Verlag, Aachen 2006.") In that paper the author makes a number of elementary errors that can be pointed out as being in error. In this short version, its not even clear what is being claimed, other than that in finite binary trees, you have one set of facts, and in the infinite case things change. Well, yeah, of course.

The claim "the number of separated paths is the number of nodes" may be an error if it were clearer what "separated paths" really meant. Every "separation" (i.e., every node node in fact) gives rise to an uncountable number of infinite paths below it that share that node and the path to the root as "prefixes". So what? For any finite length binary fractional number (.e.g, .00101010101) there are an uncountable number of binary numbers that start out that way. If "separated paths" is just a path, then clearly "the number of separated paths is the number of nodes" is out and out wrong.

Joe N