|
|
|
Viewing Version
1
of
'paradox of the binary tree'
|
[ view 'paradox of the binary tree'
|
back to history
]
| Title of object: |
paradox of the binary tree |
| Canonical Name: |
ParadoxOfTheBinaryTree |
| Type: |
Definition |
| Created on: |
2007-05-04 08:31:05 |
| Modified on: |
2007-05-04 08:31:05 |
| Creator: |
WM |
| Modifier: |
WM |
| Author: |
WM |
| Keywords: |
set theory, Cantor's theorem, uncountability |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
|
Content:
The complete infinite binary tree consists of nodes (namely the numerals 0 and 1). Every node has two children. 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 \emph{n} there are $2^{n}$ paths and $2^{n+1} - 1$ nodes.
Every 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. While the set of nodes remains countable, however, the set of paths is uncountable by CANTOR's theorem.
\textbf{Links and Literature}
http://www.fh-augsburg.de/~mueckenh/MR.mht
W. M\"uckenheim: Die Mathematik des Unendlichen, Shaker-Verlag, Aachen 2006. |
|
|
|
|
|
