Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Denote by $ZF^\times$ the theory of $ZF$ without the axiom of infinity. We know that $V_\omega$, the set of all hereditarily finite sets in a model of $ZF$, is a model of $ZF^\times$.

We further know that $\newcommand{Ord}{\operatorname{Ord}}\Ord^{V_\omega}=\omega$. Consider the following formula: $$\varphi(x,y)=(x \text{ is an ordinal})\land (y\text{ is an ordinal})\land \Big((x\neq0\land x\in y)\lor y=0\Big)$$

It is not hard to see that the class $\{\langle x,y\rangle\mid \varphi(x,y)\}$ is a well-ordering of order type $\omega+1$. Similarly we can define $\omega+2$, even $\omega+\omega$. We can go even further, much further.

However, we can obviously go so far, there are only countably many formulas and countably many parameters so there can only be countably many order types definable.


  1. What is the least ordinal not definable in $V_\omega$ from $ZF^\times$?

  2. We can push this question into $NBG^\times$, defined as $ZF^\times$. Now we can quantify over classes, surely we can push this even higher?

Vaguely related:

share|cite|improve this question
Vague heuristic idea: $ZF^\times$ is very nearly the same thing as $PA$, so this really ought to be the smallest ordinal not definable in $PA$, which I think (?) is $\omega_1^{CK}$. – Chris Eagle May 8 '12 at 20:26
@Chris: I am not sure it has to be the same ordinal but I think it would have to be at least that. – Asaf Karagila May 8 '12 at 21:19
I'm not 100% sure about that, but [descriptive-set-theory] seems to make some sense here, perhaps [computability] instead? I'd be glad if someone would take the necessary action if needed. – Asaf Karagila May 10 '12 at 23:09
Every definable well ordering over $V_{\omega}$ is isomorphic to an arithmetical well ordering of natural numbers. So it must be below $\omega_1^{CK}$. But every recursive well ordering of natural numbers is definable in $V_{\omega}$. So you are right. – 喻 良 May 11 '12 at 2:12
@Liang: So the answer to the first question is indeed $\omega_1^{CK}$? – Asaf Karagila May 11 '12 at 4:36
up vote 3 down vote accepted

$V_{\omega}$ is recursively biinterpretable with $\omega$. So both are $\omega_1^{CK}$.

Details can be found in my book joint with CT.

See Chapter 3, especially Thm 3.2.5

share|cite|improve this answer
It's a pretty big book. Are there particular chapters/sections/theorems relevant to my question? – Asaf Karagila May 11 '12 at 15:14

Your Answer


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.