I'm not really that familiar with AC, I've just started talking about it in my classes. But from what I understand, one of its formulations is that it is possible to create a set made from choosing elements from a series (potentially infinite) of other sets. Are we doing this in the Diagonal argument? We have a countably infinite number of sets (each with a real number) and we create a different one by choosing a digit from each of the subsets. Is this correct? Or am I misunderstanding AC, making some other error?

EDIT: It seems that someone asked which axioms of ZF did the argument use and it got answered. My question then becomes: Why doesn't Cantor's Diagonal argument depend on the Axiom of Choice?

  • $\begingroup$ In Cantor's argument, you can come up with a scheme that chooses the digit, for example 0 becomes 1 and anything else becomes 0. AC is only necessary if there is no obvious way to choose something. For example, if you have a surjective function $f:A\to B$ and you want to find an injective function $g:B\to A$. It seems obvious that you want $g(x)\in f^{-1}(x)$, but there is no obvious choice for which element it is. $\endgroup$ – SmileyCraft Oct 16 '18 at 21:44
  • 1
    $\begingroup$ If you're not really that familiar with AC, perhaps it would be wise to familiarize yourself with it before asking technical questions about it? $\endgroup$ – Asaf Karagila Oct 16 '18 at 21:47
  • $\begingroup$ Cantor did not give an argument in terms of digits etc. He did give a proof of the uncountability of the reals (but he used topological arguments, essentially). His most famous theorem states that no surjection $f: X \to \mathcal{P}(X)$ exists (which uses no choice) and this can also be used to show uncountability of the reals (the Cantor set in $[0,1]$ easily has the same size as $\mathcal{P}(\mathbb{N})$ and so is uncountable. $\endgroup$ – Henno Brandsma Oct 16 '18 at 21:48
  • 2
    $\begingroup$ I've added another duplicate, which might answer your question more explicitly. $\endgroup$ – Asaf Karagila Oct 16 '18 at 21:50
  • 1
    $\begingroup$ You're welcome. Admittedly, that was the duplicate I thought was the one suggested. But as long as we got there reasonably fast, I guess it's fine. :) $\endgroup$ – Asaf Karagila Oct 16 '18 at 22:21