Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
You may be interested in a proof of Cantor's theorem that uses injections directly: math.stackexchange.com/questions/284812/… –  Trevor Wilson Feb 19 '13 at 0:41
add comment

1 Answer

up vote 18 down vote accepted

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.

share|improve this answer
    
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? –  vonbrand Feb 14 '13 at 22:48
    
@vonbrand: Yes. For the exact same reason. You already have the function, then you construct from it a set not in its range. –  Asaf Karagila Feb 14 '13 at 22:51
    
@Stefan: Yes. But if there is no surjection from $A$ onto $B$ then there is no injection from $B$ into $A$. As for an elaboration, I will attend to this in a bit. I have a few tasks which I have been procrastinating for a couple of days and finally I got around to doing. Hopefully in an hour or two... –  Asaf Karagila Feb 14 '13 at 23:09
    
@Stefan: Very well, I was going to elaborate on the second part more than I was going to add on the first part though. –  Asaf Karagila Feb 14 '13 at 23:48
    
Dear @Stefan, I have a deep standing issue with the chat system in its current form. I have decided not to use it until such that I decide these issues are resolved. Feel free to ask me anything in the comments if you want. –  Asaf Karagila Feb 15 '13 at 10:43
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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