Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

EDIT: I'm bumping this, because while Joel ruled out some naive options, my question in bold below is not yet answered.

Suppose I have a directed partially ordered set $(\Gamma,\leq)$ with a bottom element (every pair of objects has some upper bound), such that $\Gamma$ is well-quasi-ordered. I claim that I have some well-ordering $\phi\colon \gamma \stackrel{\sim}{\to} \Gamma$ for some ordinal $\gamma$ - ignoring $\leq$ - then I can find an order-preserving injective map $c\colon \alpha \to \Gamma$ from some ordinal $\alpha$ with cofinal image.

Since, I can take $c(0) = \bot$, then induct, using judicious amounts of Choice, as follows:

  • $c(\beta+1) = \text{upperbound}\lbrace c(\beta),\phi(\beta)\rbrace$ (using AC)
  • $c(\delta) = \phi(\min\lbrace \eta\in\gamma\ |\ \phi(\eta) \geq c(\beta),\ \forall \beta \lt \delta \rbrace)$, for $\delta$ a limit ordinal.

This procedure cannot continue for more than $\gamma$ steps, so $\alpha \le \gamma$. In fact we can probably take $\alpha \leq cof(\Gamma)$, where the latter is defined as the smallest ordinal mapping to a cofinal sequence in $\Gamma$, and replace $\phi$ by the function witnessing this.

However, what if $\Gamma$ is a proper class, with a class ordering $\leq$ (EDIT: and is 'set-like', in that initial segments are all sets)? Firstly, is it possible to get a cofinal, order-preserving class function $Ord \to \Gamma$ in ZFC? (EDIT: No; see Joel's answer) How about if I have a given class function $Ord \to \Gamma$ with cofinal image, but not assumed to preserve orderings?

If I can, it would seem I could get something like (this is my main aim)

$$\Gamma = \bigcup_{\alpha \in Ord'} \downarrow c(\alpha),$$ where $Ord' \subset Ord$ is some cofinal subclass and all the $\downarrow c(\alpha)$ are sets, all in ZFC (EDIT: or NBG+GC..). Is this correct?

share|improve this question
    
It's simpler to just say $\Gamma$ is a well-founded directed poset with a bottom element and no infinite antichains (making it a well-quasi-ordering). You have a well-ordering $\phi$ due to Choice, there's no need to phrase the claim as a conditional since you're assuming choice to construct $c$ anyways. You can take $\alpha = \mathrm{cof}\Gamma$. Why are you replacing $\phi$? –  Amit Kumar Gupta Apr 10 '13 at 8:55
    
For $\Gamma=(L,\leq_L)$ then you get a well-ordering $\mathrm{Ord}\to L$. So in that sense it's "possible." Did you mean for arbitrary $\Gamma$? –  Amit Kumar Gupta Apr 10 '13 at 8:57
    
What's the difference between a cofinal, order-preserving class function, and a class function with cofinal image, assumed to preserve orderings? –  Amit Kumar Gupta Apr 10 '13 at 8:59
    
Hi Amit, there was a typo, a missing "not" :-) –  David Roberts Apr 10 '13 at 9:01
    
And yes I mean arbitrary $\Gamma$ –  David Roberts Apr 10 '13 at 9:06
show 2 more comments

1 Answer 1

up vote 6 down vote accepted

Update: A counterexample. I've realized that the claim you are trying to generalize from sets to classes is not actually true for sets. Specifically, there are directed well-quasi-ordered sets that do not admit any linearly ordered cofinal subset. And a similar counterexample exists for classes.

Theorem. There is a directed well-quasi-order set having no cofinal well-ordered subset.

Proof. Consider the order on $\omega_1\times\omega$, where $(\alpha,n)\leq(\alpha',n')$ just in case $\alpha\leq\alpha'$ and $n\leq n'$. It is easy to see that this is well-founded and directed. Furthermore, it is well-quasi-ordered, because suppose that $A$ is an infinite antichain in $\Gamma$. Let $(\alpha,n)$ have the smallest value of $n$ arising from a pair in $A$. Thus, all other pairs $(\beta,m)$ in $A$ have $\beta\lt\alpha$ and $m\gt n$. And as $m$ goes up, the $\beta$'s must go down, which is impossible.

But I claim that there is no well-ordered cofinal suborder of $\Gamma$. The reason is the mis-match of the cofinality on the two coordinates. If $\langle \alpha_\xi,n_\xi\rangle$ for $\xi\lt\delta$ is cofinal and increasing in the order, then it must be that $\{n_\xi\mid\xi\lt\delta\}$ is cofinal in $\omega$ and also $\{\alpha_\xi\mid\xi\lt\delta\}$ is cofinal in $\omega_1$. So $\delta$ would have to have cofinality $\omega$ and also $\omega_1$, a contradiction. QED

The conclusion is that it is not generally possible to find cofinal linearly ordered suborders of well quasi orders, even when they are sets.

A slightly easier example shows the flaw in your construction. Consider the order on $\mathbb{N}\times\mathbb{N}$ for which $(n,m)\leq (n',m')$ when both $n\leq n'$ and $m\leq m'$. This is a well quasi-order, since it is well-founded and there is no infinite antichain, since for a given point $(n,m)$, any point incomparable must either have smaller $n$ or smaller $m$, but any two points with one coordinate the same are comparable; so any antichain containing $(n,m)$ has at most $n+m+1$ many elements. Also, the order is clearly upward directed. But observe that your procedure, depending on $\phi$, could easily have led you to choose $(0,0), (1,0), (2,0), (3,0),\ldots$ as the initial segment of your sequence. In this case, you would be stuck, since this is an increasing sequence in the order, but it is not cofinal---since nothing in it is above $(3,3)$---but meanwhile, there is no way to continue the sequence, since the sequence also is not dominated in the order; there is nothing to put at stage $\omega$. (Meanwhile, the order does have a cofinal $\omega$-sequence, namely, $(0,0),(1,1),(2,2),\ldots$. The point is that the procedure you describe in your proof doesn't necessarily find it.)

One may modify the counterexample to proper classes, to give a counterexample to your question about proper classes, as follows. Consider the similar class order on $\text{Ord}\times\omega$, where $(\alpha,n)\leq(\alpha',n')$ if and only if $\alpha\leq\alpha'$ and $n\leq n'$. This is directed and well-quasi-ordered, just as the order above, but there is no cofinal order-preserving map $\xi\mapsto (\alpha_\xi,n_\xi)$ from $\text{Ord}$ into it, since the values of $n_\xi$ must eventually increase, and so there will be a stage $\beta$ for which $\sup_{\xi\lt\beta}n_\xi=\omega$, after which time the sequence cannot continue. This is essentially the same kind of counterexample as above, resulting from the mismatched cofinalities of $\text{Ord}$ and $\omega$. Meanwhile, there is a surjective map $\text{Ord}\to\text{Ord}\times\omega$, whose image is therefore cofinal, by using pairing functions on the ordinals, and therefore your extra hypothesis is also fulfilled for this counterexample.


Original answer. In general, you cannot get an order-preserving cofinal map from Ord to a class order $\Gamma$, even when $\Gamma$ is fully well-ordered. The reason is that the cofinality of $\Gamma$ may be strictly less than Ord.

For example, consider the order $\Gamma=\text{Ord}\cdot\omega$, meaning $\omega$ many copies of Ord, one on top of another. You can build this on $\omega\times\text{Ord}$ with the lexical order. This is a well-order (and hence a quasi well order), in the sense that every subclass has a least member, but since it has a cofinal $\omega$ sequence, there can be no order-preserving cofinal map from Ord to $\Gamma$, since this would give a cofinal $\omega$ sequence in Ord, contrary to the replacement axiom. Indeed, there is also no order-preserving cofinal map from $\omega_1$ or indeed, from any uncountable regular cardinal, into $\text{Ord}\cdot\omega$.

The essential issue here is that this $\Gamma$ is not set-like, where a relation is set-like when the sets of predecessors of any point form a set. For a set-like proper class well-ordering $\Lambda$, your construction from the set case adapts to give you an order-preserving cofinal map from Ord to $\Lambda$, for in this case, as you construct the cofinal Ord sequence, at each ordinal stage the sequence you have produced so far will not yet be cofinal, and so you can continue.

Let me now give an example showing that even in the case the quasi-well-order is set-like, one nevertheless needs global choice to find the embedding, and so it not possible to do it merely in GB+AC. To see this, consider one of the standard models of GB+AC + $\neg$ global choice. For example, such a model is constructed in my answer to Asaf Karagila's question, Does ZFC prove the universe is linearly orderable?. The corollary in that argument can be strengthed to the following claim, proved by the same argument.

Theorem. Every model of ZFC has a class forcing extension to a model of GB+AC, in which there is a class of pairs, such that no class makes proper-class-many choices from those pairs.

Thus, in this model we have a class $\{\{A_\alpha,B_\alpha\}\mid \alpha\in\text{Ord}\}$, such that no class makes a choice for unboundedly many $\alpha$. We may now form the quasi-well-order $\Gamma$ that puts the pairs as antichains in a tower of height $\text{Ord}$, but there can be no order-preserving cofinal embedding of $\text{Ord}$ into $\Gamma$ in this model, since such an embedding would make unboundedly many choices from the family.

Conclusion: one really needs global choice, and not just ZFC or even GB+AC, even when the relation is set-like.

share|improve this answer
    
So in your example you have $A_\alpha \lt B_\beta$, $B_\alpha \lt A_\beta$, $A_\alpha \lt A_\beta$ and $B_\alpha \lt B_\beta$ for $\alpha \lt \beta$? It turns out that I was implicitly assuming the set-like condition in the application I'm considering, so we are ok there (in terms of my last equation, the down-closures $\downarrow c(\alpha)$ all need to be sets). To consider my second question, given some cofinal, non-order-preserving injection $Ord \to \Gamma$, can we get a cofinal order-preserving injection (or at least an injective partial map)? –  David Roberts Apr 10 '13 at 23:50
    
Yes, you have the right order; it is like a ladder of height Ord, with each antichain pair $\\{A_\alpha,B_\alpha\\}$ forming a rung. In my model, there is no injection from Ord to the points in the order, since from such an injection, you could choose from unboundedly many pairs, but there isn't any such class. (So I guess vacuously you get the implication that from any such injection, you can get what you want, but the hypothesis never holds.) –  Joel David Hamkins Apr 10 '13 at 23:59
    
I mean the general form of my second question, for arbitrary $\Gamma$, not just for your example. –  David Roberts Apr 11 '13 at 3:40
1  
Very nice counterexample! –  Asaf Karagila Apr 13 '13 at 18:27
    
Thanks Joel. I wasn't 100% sure of my claim, but couldn't think of a counterexample. –  David Roberts Apr 14 '13 at 0:32
show 2 more comments

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.