9
$\begingroup$

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.

Questions:

  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:

  • 0
    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}$.2012-05-08
  • 0
    @Chris: I am not sure it has to be the same ordinal but I think it would have to be at least that.2012-05-08
  • 0
    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.2012-05-10
  • 0
    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.2012-05-11
  • 0
    @Liang: So the answer to the first question is indeed $\omega_1^{CK}$?2012-05-11
  • 0
    @Liang: It is a conservative extension of ZF which allows classes.2012-05-11
  • 0
    For your second question. Just note that every definable class over $V_{\omega}$ is an arithmetical real. So the well ordering upper bound is still $\omega_1^{CK}$.2012-05-11
  • 0
    @Liang: I see. Can you put that in the form of an answer (please include references to what you quoted, if you have them)?2012-05-11

1 Answers 1

4

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

Details can be found in my book joint with CT.

http://math.nju.edu.cn/~yuliang/course.pdf

See Chapter 3, especially Thm 3.2.5

  • 0
    It's a pretty big book. Are there particular chapters/sections/theorems relevant to my question?2012-05-11