A Crash Course in the Mathematics Of Infinite Sets
legacy.earlham.edu
A very dense and readable summary of some of the key concepts in set theory. Warning!! -- May cause mind-blowing
legacy.earlham.edu
The axiom of choice and the continuum hypothesis are equivalent, meaning the assumption of either one implies the other. <<EDIT: This is wrong, see below>>
For the onlookers:
Axiom of choice -- Given any collection of disjoint sets, there's a set consisting of one element from each.
Axiom of countable choice (this is weaker) -- Given any countable collection of disjoint sets, there's a set consisting of one element from each.
Axiom of dependent choice (this is intermediate in strength) -- Suppose you have a set X and a binary relation R on X such that for any x in X, there's some y in X such that xRy holds. Then there's a sequence x_0, x_1, ..., consisting of elements in X, such that for any i, x_i R x_(i+1) holds.
Countable choice is not enough to prove that aleph_0 is the smallest infinite cardinal; dependent choice is. Of course you could weaken dependent choice and still be able to prove it, but not all the way to countable choice.
(Ignoring the AC/CH thing, that's been addressed already.)
Countable sets are shown to be countable by providing a mapping between the natural numbers and that set. Uncountable sets are shown to be uncountable by assuming they are and creating a new element from the set of all elements and showing that it was not accounted for in the first place.
But what happens when we try to use the mapping argument on the set of the reals, and the contradiction argument in the set of the integers?
For the countability of the reals, I can setup a binary tree of infinite depth with 0 on the left and 1 on the right. I then do a depth first walk of the tree and assign an integer to each of the nodes. Then the sequence of 0s and 1s from the root of the tree to any node we care to go to represents a binary number between 0 and 1 if we treat it as a binary fraction like he does in theorem 16. So any number we care to go down to in the binary tree can be assigned a natural number, and since the binary tree is infinite it can go down to any real number. So according to this argument the reals are countable.
Now for the diagonalization-like argument for incountability of the natural numbers. Assume the positive even numbers are countable, and that we have a list of all the even numbers assigned to a natural number. I can create a new even number by adding all of the numbers in the list, since all the numbers are positive, each number is smaller than the sum of all of the numbers on the list, so the number is not on the list, and we have to conclude that our assumption was wrong, and that the even numbers are uncountable.
If the first argument is wrong, why is it wrong for the reals but not wrong for the naturals? And if the second argument is wrong, why is it wrong for the naturals but not wrong for the reals?
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?
>> 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.
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.