Do you need the Axiom of Choice to accept Cantor's Diagonal Proof?

Solution 1:

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.