In which Gorgonzola backpedals a bit
This statement, which I made as a lame attempt to be witty in my writeup on mapping the power set of the integers to the real numbers, demonstrates the
pitfalls of treating such offhand statements as literal truth. Although this statement seems (if you understand the terms surjection and bijection) to
be common sense it is not precisely "true". Or rather, it is true if you want it to be true -- because it is equvalent to the Axiom of
Choice, something certain mathematicians consider gibberish.
Why? Well, I'm only going to give a quick explanation, even though it can be rigorously proven. You have a surjection, which is a function (call
it F) between two sets (call them A and B) in which all elements of the second set B are represented. Like other relations, a function is usually represented as a set of ordered pairs (a, b) where a ∈ A and b ∈ B.
In a function, each a in A is related to exactly one b in B: ((a, b1) ∈ F & (a, b2) ∈ F) -> b1 = b2)
In a surjection: b ∈ B -> (Ea)((a, b) ∈ F)
A bijection (or "one-to-one correspondence") is also injective, meaning that each b in B is related to exactly one a in A: ( (a1, b) ∈ F & (a2, b) ∈ F) ) -> a1 = a2
With a surjective function, we know that every b
is related to at least
, but A might be larger than B, and many a
's (perhaps an infinite number) might map to a particular b
. So, you might think that it's a simple matter of restricting F
to some subset
that contains one pair for each b
You might wish that to be the case, but without the Axiom of Choice, you can't do it! Particular b's might have an infinite number of a's that map to them. If you can't construct a predicate on elements of A that is true for exactly one element related to each b, you have no choice but to "pick" one a for each b. Only the Axiom of Choice lets you do this.
Counter-intuitive and frustrating, isn't it? We have more than we need, and we can't whittle it down to exactly what we need without outside assistance. And the only "outside assistance" that works for every single function imaginable is the Axiom of Choice. There's simply no way to construct a predicate selecting one a for each b that works for every function where an infinite number of a's correspond to some b's. And we can construct any number of functions where that's precisely the case. We might try to order the set A (or what amounts to the same thing, the function F itself) and pick the lowest a that corresponds to each b. But we need the Axiom of Choice to get an ordering that guarantees a "lowest" a. Actually, we can't necessarily even order A at all without AC.
Of course, the Axiom of Choice is not necessary to take a subset of the power set of the natural numbers, and construct a one-to-one correspondence to the real numbers as described in that other writeup. Each set of natural numbers corresponds to exactly one real number using the function described. Most real numbers (except dyadic rationals) correspond to exactly one (infinite) set of natural numbers. Each dyadic rational corresponds to exactly two sets of natural numbers -- one finite set, and its infinite "evil twin". We can use the property of finiteness or infiniteness to select one or the other without involving nonconstructive choices (For consistency with the rest of the mapping, it's probably better to use the "evil twin" sets).