The regularity of successor cardinal

I was looking at two different proofs of the fact that successor cardinals are regular. It struck me as odd that both proofs used AC. Looking at the concepts involved in defining cofinality I feel as if there should a proof of this that doesn't use AC.

So, is my intuition correct or is this statement dependent on AC? Also in either case could you point me to a reference to the fact?

-
Is it even clear successor cardinals exist without AoC? – Thomas Andrews Feb 28 '14 at 3:21
@Thomas Andrews: Of course, you just take the least greater cardinal, which should exists, because you can look at well orderings of the original cardinal. – user2345215 Feb 28 '14 at 3:36
@ThomasAndrews It is just not true that "you can't well-order any cardinal without AoC." The argument just sketched works fine: For instance, to show that $\omega_1$ exists, consider all well-orderings of $\mathbb N$. This is a set. There is a natural way of comparing any two of these well-orderings, and so we can put together their isomorphism classes in a long well-ordering that has type exactly $\omega_1$. No choice is involved here. The same idea shows that given any set of ordinals there is an ordinal larger than all of them. – Andrés Caicedo Feb 28 '14 at 4:01
@ThomasAndrews Of course, without choice it is also true that there are cardinalities that are non-well-orderable. But the question is explicitly about ordinals. – Andrés Caicedo Feb 28 '14 at 4:02
@ThomasAndrews I use "cardinalities" for arbitrary sizes, whether they are well-orderable or not, and "cardinals" for those that are well-orderable (and therefore identified with suitable initial ordinals). This is standard. – Andrés Caicedo Feb 28 '14 at 4:10

The statement depends on the axiom of choice. It is consistent, modulo large cardinals, that all (well-ordered) infinite cardinals have cofinality $\omega$.

This was first proved by Gitik, around 1980, from a proper class of strongly compact cardinals. The result is significant, and rather involved. It is actually an interesting construction. In a forcing extension of the universe, a suitable inner model $N$ (of $\mathsf{ZF}$) is identified and a cardinal $\kappa$ such that, inside that model, the level $N_\kappa$ is shown to satisfy the statement. I do not think we have models of the statement obtained by class forcing, without at the end cutting the universe at some level.

The result has been improved since, reducing the large cardinals involved, but they are still pretty large, beyond anything we can reach with inner model theory. The best lower bound that we know of is that the statement that all cardinals are singular implies that $\mathsf{AD}$ holds in the $L(\mathbb R)$ of some suitable inner model of a forcing extension. This is a fairly recent (2008) result due to Ralf Schindler and Daniel Busche, see here. Again, it would be interesting to get the result directly in $V$ without having to pass to an extension, but technical difficulties in the implementation of the technique known as the core model induction prevent us from doing this at the moment.

(That large cardinals were needed at all has been known for a long while. A nice short argument, due to Magidor, shows how the fact that $\omega_1$ and $\omega_2$ are singular violates the covering lemma in some inner model and therefore implies that $0^\sharp$ exists, see here.)

-
Thank you for the answer. I find this really surprising. It seems kind of counter-intuitive (the definitions kind of led me to believe that there might be a, albeit very involved, proof of the fact from just ZF) – UserB1234 Feb 28 '14 at 4:14

Let me add on Andres' wonderful answer, something which I think is missing.

Despite the necessity of large cardinals, it was in fact one of the first uses of the technique of forcing (and symmetric extensions) to show that in fact $\omega_1$ and $\Bbb R$ can be countable unions of countable sets.

This is a classical result due to Feferman and Levy. In her Ph.D. Thesis Ioanna Dimitriou extended this result, and proved the following theorem:

Theorem (2.10) If $V$ is a model of $\sf ZFC$, $\kappa_0$ is a regular cardinal of $V$ and $\rho$ is an ordinal in $V$, then there is a model of $\sf ZF$ with a sequence of successive alternating singular and regular cardinals that starts at $\kappa_0$ and that contains $\rho$-many singular cardinals.

And all that without large cardinals. The large cardinals come into play when we want two successive singular cardinals.

-
Thank you. I thought you might be the first answer this since you are interested in Set Theory without AC. – UserB1234 Feb 28 '14 at 14:30
It was one of those rare occasions when I was asleep. But your question was the first thing I did when I got out of bed :-) – Asaf Karagila Feb 28 '14 at 14:31
Ah, OK :) One quick question; (one of) the definition I have for cofinality says that given a limit ordinal $\theta$ the increasing sequence $\langle\gamma_{\nu}:\nu<\theta\rangle$ of ordinals in $\alpha$, is cofinal in $\alpha$ iff $\langle\gamma_{\nu}:\nu<\theta\rangle$ is unbounded in $\alpha$. I'm having some trouble figuring out why you want this sequence to be increasing. (One of the proofs that I looked at requires AC to get an increasing sequence). Why doesn't any unbounded sequence work? – UserB1234 Feb 28 '14 at 14:38
You don't need choice to ensure it is increasing. You can always define a subsequence which is strictly increasing by defining $\gamma'_\nu = \gamma_\mu$ where $\mu=\min\{alpha<\theta\mid\forall \nu'<\nu,\gamma'_{\nu'}<\gamma_\alpha\}$. – Asaf Karagila Feb 28 '14 at 15:10
Thank you. I just figured that out and was about delete my comment. Oh well. – UserB1234 Feb 28 '14 at 15:14