1

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.

Ken Horne
  • 11
  • What do you mean by an infinite binary string that ‘end[s] with $0$’? In any case, you don’t need Aronszajn trees: the binary tree of height $\omega$ that you seem to be constructing in your diagram has countably many levels, each of which is finite, and uncountably many branches. The number of branches is larger than the number of nodes. – Brian M. Scott Feb 18 '21 at 20:30
  • If everything else is right, then your "I don't think" clause must be wrong. – GEdgar Feb 18 '21 at 20:33
  • The branches are not the tree. You can construct ${0,1}$ in two steps, but you really constructed four subsets: $\varnothing,{0},{1},$ and ${0,1}$. If you're allowed to construct one thing at a time, then how come you constructed FOUR things in TWO steps? – Asaf Karagila Feb 18 '21 at 20:43
  • 1
    By the way, Aronszajn trees are not countable. – Asaf Karagila Feb 18 '21 at 20:43
  • 1
    I’m confused what the full binary tree of height $\omega$ has to do with Aronszajn trees, or how it “represents an uncountable number of nodes” (it does have an uncountable number of branches if that’s what you mean.) Also, there are certainly uncountably many branches (and nodes and levels) on an Aronszajn tree, but equally certainly there are no uncountable branches... that’s one of its defining properties. – spaceisdarkgreen Feb 18 '21 at 20:52
  • Right, I know Aronszahn trees are not countable, that's why I am having a problem. – Ken Horne Feb 18 '21 at 20:53
  • I was saying the number of nodes was uncountable because it's a tree. On a tree, for any node, there is a unique path to the root. So there has to be a one to one correspondence from the number of nodes to the number of paths to the root of the tree. – Ken Horne Feb 18 '21 at 20:55
  • @Ken That’s not the same thing as a branch... branches go all the way up. – spaceisdarkgreen Feb 18 '21 at 21:00
  • Ok, I must be missing something. As I am using the word, a branch is graph edge between 2 vertices, and a path is a series of vertices connected by edges (branches) . I have also seen branch used as a subtree under a node , ie right branch or left branch. And I was saying a path to the root is unique for each node because it's a tree. – Ken Horne Feb 18 '21 at 21:06
  • 1
    No, a branch is a maximal chain in a tree (starting from the root). Aronszajn trees have specific constructions (e.g. Aronszajn's original construction with sequences of rationals under certain constraints). These constructions are explicitly done in uncountably many steps. – Asaf Karagila Feb 18 '21 at 21:51

1 Answers1

1

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.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
  • That is related to what I was thinking, but I thought you would end up with an uncountable number of nodes. As mentioned above, for a tree, each node has a unique path to the root. And after a countably infinite number of steps, (assuming supertasks so that statement has meaning) you would end up with a fully populated uncountable tree with a countably infinite number of rows. – Ken Horne Feb 18 '21 at 21:01
  • The fully populated tree has countably many nodes. There are uncountably many (countable) paths from the root. – Ethan Bolker Feb 18 '21 at 21:08
  • That is the part that is confusing me. Think of tree graph, How can you have more paths from nodes to the root than you have nodes? That would imply to me there are nodes with more than one path to the root. However, in a tree by definition that can't be true. – Ken Horne Feb 18 '21 at 21:13
  • @Ken Horne In this infinite case, not every path from the root ends at a node. In fact none of the maximal paths do since we can always go down one more node. – Mark S. Feb 18 '21 at 22:51
  • @KenHorne Cantor was confused too, at first. Each node has a finite description. A path requires an infinite description, If you trust Cantor's argument for the uncountability of the reals using binary decimal representations, apply that argument here. – Ethan Bolker Feb 18 '21 at 23:28