Why doesn't choice imply global choice (in NBG)?

I thought ZFC proved the existence of an inductive well-ordering that is itself a set for any stage of V. NBG with only the regular AC should then prove/assert the existence of a class R of ordered pairs (a,b) such that either:

a has lesser rank than b, or:

they both have rank α and (a,b) exists in the ZFC well-ordering of the complement of V(α) within V(α+1).

I don't see that we have to quantify over classes there. By another phrasing it just unites for all V(β) their inductive well-orderings along these lines, which are already supersets of the same ordering for any previous stage. And then NBG should easily prove this well-orders V. How does this proof fail?

• I disagree with closing this question. We also have two questions on related topics: this question and this question. Commented Mar 25, 2014 at 8:43
• I did not vote to close, but I think this is borderline for MO; the issue here is much less deep than in either linked question, and comes down to just examining the details carefully. By contrast, if the question were "What do models of ZFC with no global well-ordering look like?" instead of "why doesn't this argument work?", that would definitely fit, IMHO. Commented Mar 25, 2014 at 9:07
• @Noah: I agree that the question could have used some improvement. But the question itself is definitely on topic, in my opinion. Commented Mar 25, 2014 at 9:28
• I think this is a fine question, but it's basically the same as this question that was migrated a few days ago. Commented Mar 25, 2014 at 17:08

Your first sentence is true (modulo the word "inductive"), but not in the way you mean: $ZFC$ proves the existence of many set well-orderings of each $V_\alpha$. Now, under some further assumption - say, $V=L$ - there might be a sequence of somehow canonical well-orderings of the $V_\alpha$, in which case we can indeed "glue them together" to get the global well-ordering you seek. However, if there is no such definable sequence, then we can't define your well-ordering, since we would need to pick some specific well-ordering of each of the $V_\alpha$s simultaneously - that is, find a choice function for a class-sized sequence of sets. And this, of course, is exactly global choice.

EDIT: One positive point. Even though choice doesn't imply global choice, $NBG$ is strongly conservative over $ZFC$, so in some sense $ZFC$ is not enough to show that a well-ordering of $V$ exists, but is enough to show that a well-ordering of $V$ isn't too destructive to the universe. :)

• I thought I just gave a formula that does exactly that. If you mean we need to pick a specific well-ordering of the new sets in each stage (which form a set A), take the choice function of the powerset of A and start with the image (least element) of the whole set A. The next least element is the image of the subset that just leaves out the least element, etc. Do we really need to define the choice function further? Commented Mar 25, 2014 at 6:38
• Yes. What do you mean by "take the choice function of the powerset of $A$?" There are many such choice functions. The real problem, though, is going to be the complete lack of a way to get from one level to the next: given a well-ordering of $V_\alpha$, there is no way to define a well-ordering of $V_{\alpha+1}$. If you want to find the problem with your construction, that's where you should look: how do I get a well-ordering of $V_{\alpha+1}$ from a well-ordering of $V_\alpha$? Commented Mar 25, 2014 at 6:40
• I think you meant to ask something else. The elements of the new stage not in the previous stage form a set, so there exists at least one well-ordering for them. We could combine this with the one that exists by the inductive hypothesis - again, assumed to be consistent with some well-ordering for each previous stage that exists - and then unite the result with the Cartesian product of the previous stage and its complement. Commented Mar 25, 2014 at 6:52
• No, I didn't mean to ask something else: your mistake is at the sentence "we could combine this with the one that exists by the inductive hypothesis" - what do you mean by this? Since there is no canonical way to choose a well-ordering of the next level, all this induction proves is "for every $\alpha$, there is a well-ordering of $V_\alpha$ in which $\beta<\gamma$ implies every element of $V_\beta$ lies below every element of $V_\gamma$." In order to get a well-order of the whole universe, we'd need a way to "keep making choices" all along the ordinals - which is exactly countable choice. Commented Mar 25, 2014 at 6:57
• No - I mean that, consistently, there is no such sequence! This is exactly analogous with the situation of finite choice vs. choice for $\omega$-sequences of sets in ZF: given an $\omega$-sequence of nonempty sets $(A_i)_{i\in\omega}$, we may - in ZF alone - show that for each $i$, there is a choice function $f: i\rightarrow \bigcup_{j\in\omega}A_j$ with $f(k)\in A_k$. However, there will be no way to extend these finite-length choice functions into a full choice function. Now, if we imagine that there is some external universe in which choice holds, then (cont'd) Commented Mar 25, 2014 at 7:03

The other answers are great. Let me point out, however, that one doesn't need the inaccessible cardinal in Asaf's argument, because one can force over any ZFC model, and there is a pure-forcing argument, not using symmetric models (which some find confusing). Specifically, one can use the argument I provided in my answer to a previous question of Asaf's Does ZFC prove the universe is linearly ordered?.

Theorem. Every model of ZFC has a class forcing extension that is a model of ZFC, in which there is no class global linear ordering of the universe that is definable from parameters.

By augmenting the model with its definable classes, this provides a model of GB+AC in which there is no global linear order (and hence also no global well-order).

The proof is to perform a class product that adds two sets of Cohen subsets at each stage, and then argue that one cannot definably linearly order them in the extension, because the forcing has automorphisms that preserve any given condition, but swap the resulting sets. And so no condition can decide which order to put them in.

• You're absolutely right, Joel. The reason that I made this argument is that I wanted to have a universe where choice actually fails. One might argue that over the model obtained there might be a class which is not necessarily definable and so and so. One has to argue that when extending the model to a model of $\sf NBG$ you did not introduce a global choice function. While I'm sure it's not a difficult argument, it's much easier to just slap it out as I did -- there is no way to well-order the intended model in the universe, so certainly there is no way to do it as a model of $\sf NBG$. Commented Mar 25, 2014 at 13:41
• The argument that "slaps it out" is essentially the same as the argument that there is no definable class that is a linear order. One considers a given condition and finds a suitable automorphism of the forcing that fixes that condition, yet swaps the items being ordered. Commented Mar 25, 2014 at 13:47
• Fair enough, I generally wrote my comment to defend my choice of inaccessible. :-) Commented Mar 25, 2014 at 16:01

As Noah S said, you have to use global choice to choose a well-order for each $V_\alpha$.

But we can have a concrete example for this sort of failure. Consider an inaccessible cardinal $\kappa$, and add using Easton forcing a subset for every regular cardinal below $\kappa$. Now consider the symmetric model defined by things definable by bounded parts of the forcing. Let $N$ be that model.

This can be seen as a class forcing over $V_\kappa$. The class of generics does not have a well-order by standard arguments, but each $(V_\alpha)^N$ below $(V_\kappa)^N$ does have a well-ordering. Therefore $(V_\kappa)^N\models\sf ZFC$ but nowhere in $(V_{\kappa+1})^N$ we can find a well-ordering of $(V_\kappa)^N$. In particular, $(V_{\kappa+1})^N$ as a model of $\sf NBG$ satisfies the axiom of choice, but not global choice.

• That's a very nice construction, Asaf! Commented Mar 25, 2014 at 7:16
• Let me just add the one piece being implicitly used: the strong conservativity of $NBG$ over $ZFC$. Given any model $V$ of $ZFC$, the structure consisting of definable classes within $V$ is a model of $NBG$. Commented Mar 25, 2014 at 7:19
• Noah, yes, but in this case we even take more than just the definable classes. Commented Mar 25, 2014 at 7:36