Representing real numbers in $[0,1]$ with a binary tree

666 Views Asked by At

All we know Cantor's famous argument about counting real numbers in [0,1]. He basically suppose that we list every real number in [0,1] with a binary representation, then we use the diagonal argument to find a real number which is not listed there.

Let's think of an infinite binary tree. Root node is 0, and following every node has 0 as its left child and 1 as its right child. So, as far as I can see every branch of this tree corresponds to real number in [0,1] with a binary representation, which means that we can find every element in Cantor's list in this tree. Moreover, even the element constructed by diagonal argument can be found there.

If we count the nodes of this infinite binary tree, we have countable set since countable union of countable sets is countable. However, the set of infinite binary sequences is uncountable.

What is going wrong here?

1

There are 1 best solutions below

4
On BEST ANSWER

The real numbers in this tree do not correspond to nodes, they correspond to infinite chains starting at the root. There are uncountably many of those.

To prove that, you can mimic Cantor's diagonal argument. If the number of chains were countable you could list them $$ C_1, C_2, \ldots $$ Now build a chain $D$ that goes left at level $i$ (choice $0$) when $C_i$ goes right there (choice $1$) and vice versa. Then $D$ is a chain that's not in the list.

There really are more chains than nodes.

(Clever idea, that didn't quite work, as you suspected.)