21
$\begingroup$

Math people:

It is my understanding that set theorists/logicians compare cardinalities of sets using injections rather than surjections. Wikipedia defines countable sets in terms of injections. Cantor's diagonal proof that the real numbers are uncountable involves showing that there is no surjection from $\mathbb{N}$ to $(0,1)$. So do I need the Axiom of Choice to accept Cantor's Diagonal Proof?

I browsed the Similar Questions and I could not find an answer. I apologize if this is a duplicate.

StEFAN (Stack Exchange FAN)

$\endgroup$
30
$\begingroup$

No. You don't need choice for this.

For two reasons:

  1. If there is an injection from a non-empty set $A$ into $B$ then there is a surjection from $B$ onto $A$. This does not require the axiom of choice, although the inverse implication (that a surjection has an injective inverse) is in fact equivalent to the axiom of choice.

    To add on this, $\mathbb N$ is well-ordered without the axiom of choice, so if there is a surjection from $\mathbb N$ onto a set $A$, then there is an injection from $A$ into $\mathbb N$ as well.

  2. The axiom of choice is used when the existence of something is to be shown. In the diagonal proof you assume that you are given a certain list, and you define from that list a new function which is not on the list. This process does not require the axiom of choice.

$\endgroup$
  • $\begingroup$ Cantor's proof that the cardinality of $A$ is less than that of its powerset also uses the diagonal argument. Is the above still valid? $\endgroup$ – vonbrand Feb 14 '13 at 22:48
  • 1
    $\begingroup$ @vonbrand: Yes. For the exact same reason. You already have the function, then you construct from it a set not in its range. $\endgroup$ – Asaf Karagila Feb 14 '13 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.