From the grandparent comment: >> I then do a depth first walk of the tree and assign an integer to each of the nodes. This is clearly wrong as the depth firs

From the grandparent comment: >> I then do a depth first walk of the tree and assign an integer to each of the nodes. This is clearly wrong as the depth first walk on the said tree will keep on just taking the left-most path always and keep on assigning natural numbers to nodes on this left-most path. In other words, since the leftmost path is an infinite string of zeros, it is clearly denumerable and can have one-to-one correspondence to natural numbers (ordinals rather than cardinals though). Any other node in the tree never gets assigned any natural number, making the argument wrong. I was left thinking though about what happens if a "breadth-first" search on this tree is used instead. Each row starting from the root as 2^N nodes (assuming N=0 for the root node). So you can assign '1' to the root node, '2' and '3' to the two children, '4', '5', '6', '7' to the grand children, and so on. Note that this assignment is very similar to that used in the proof of theorem 2 in the original post, just that the number of nodes/elements in theorem 2 is increasing linearly with the slanted row#, while in this binary-tree case, it is increasing exponentially. Applying diagonalization now (by arranging the mapping in the usual way) though shows that 0.111111... is never assigned a natural number. I cannot say however that I am 100% clear about this, and have had a corresponding confusion before using a different line of reasoning.