3 ms·

Neither of your arguments really make sense, unfortunately. For your first argument, the number of nodes in your tree isn't equinumerous with the naturals. If

by jfarmer 13y ago

Neither of your arguments really make sense, unfortunately. For your first argument, the number of nodes in your tree isn't equinumerous with the naturals. If it is, can you define an injective function which takes as its input any (potentially infinite) path in your tree and returns a natural number? For your second argument, what do you mean by "we have a list of all the even numbers assigned to a natural number?" Assigned how? The map n↦2n puts the naturals and even naturals in 1-1 correspondence and so we're done proving that they're equinumerous. It sounds like either you imagine multiple even numbers being "assigned" to a particular natural number (which isn't what we care about) or that you're thinking of adding lists of an infinite number of even numbers somehow?

alok-g 13y ago
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.
- jfarmer 13y ago
  Yeah, 100%. There are (at least) two incorrect things the original commenter took for granted. First, that the infinite binary tree as he created it is equinumerous with the natural numbers and therefore can stand in for the "list" in Cantor's diagonalization argument. Second, that a depth-first traversal of this tree makes sense. Your argument does a good job of showing why the first is a mistake. Assuming we can traverse it at all, it shouldn't matter whether we do so depth or breadth first. By traversing it breadth first we see clearly that we can always find a path through the three which does not correspond to any natural number, proving that the tree is not equinumerous with the naturals and, moreover, proving that there is an infinity which is "larger" than the infinity of the naturals.

by jfarmer 13y ago

alok-g 13y ago

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.

jfarmer 13y ago
Yeah, 100%. There are (at least) two incorrect things the original commenter took for granted. First, that the infinite binary tree as he created it is equinumerous with the natural numbers and therefore can stand in for the "list" in Cantor's diagonalization argument. Second, that a depth-first traversal of this tree makes sense. Your argument does a good job of showing why the first is a mistake. Assuming we can traverse it at all, it shouldn't matter whether we do so depth or breadth first. By traversing it breadth first we see clearly that we can always find a path through the three which does not correspond to any natural number, proving that the tree is not equinumerous with the naturals and, moreover, proving that there is an infinity which is "larger" than the infinity of the naturals.