Can an uncountable set be constructed in countable steps?

146 Views Asked by At

I know there is a flaw somewhere in my reasoning, but haven't been able to find it. I have looked at several things, including Cardinality of sets related to infinite tree . I understand Cantors diagonalization argument with respect to the natural numbers and real numbers, that makes sense to me.
However, it seems an Aronszajn tree can be constructed in countable time, however it has uncountable branches. I don't think this should be possible. Here's the construction method I am thinking of, just look at all infinite binary strings that end with 0. That's an uncountable set. To represent them in tree form


Step 1                                    0
                                       /     \
Step 2                                0       1
                                     / \     / \
Step 3                              0   1   0   1
.
.

Each row has twice as many nodes as the row above, so row n has $2^n$ nodes.
This won't map the infinite strings to the natural numbers, so it doesn't contradict the diagonalization argument. However, within a countably time, a tree representing an uncountable number of nodes will have been created. So, what am I missing? Thank you for your help.

1

There are 1 best solutions below

5
On

This tree has countably many nodes, corresponding to the finite strings of $0$'s and $1$'s. There are no nodes "infinitely far down".

Each path from the root corresponds to a countably infinite string of $0$'s and $1$'s. There are uncountably many of those, which is what Cantor's diagonal argument demonstrates.

You can think of the nodes as representing the rational numbers in the unit interval whose denominators are powers of $2$. The paths correspond to the binary infinite "decimal" representations of the real numbers in that interval.