# 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.

Title | paradox of the binary tree |
---|---|

Canonical name | ParadoxOfTheBinaryTree |

Date of creation | 2013-03-22 17:02:37 |

Last modified on | 2013-03-22 17:02:37 |

Owner | WM (16977) |

Last modified by | WM (16977) |

Numerical id | 21 |

Author | WM (16977) |

Entry type | Definition |

Classification | msc 03E75 |

Classification | msc 03E15 |

Synonym | binary tree paradox |

Defines | complete binary tree^{} |

Defines | complete infinite binary tree |