6
$\begingroup$

This is a rather technical question. I cannot find my mistake in a proof of the (obviously wrong) following sentence: Every countable ordinal is $\Sigma_2$-definable in $J_{\omega_1 + 1}$ by a formula with no parameter.

I first recall the definition of $J_\alpha$, closely following the notations and ideas of "Fine Structure and Class Forcing" by Sy Friedman. Suppose that $J_\alpha$ is defined (with $J_0 = \emptyset$). Let $\{\phi_e(x)\}_{e \in J_\alpha}$ be an enumeration of first-order formulas with one free variable and parameters in $J_{\alpha}$. We define $J_{\alpha+1}$ by first defining sets $X(n, e)$ for $n \in \omega$ and $e \in J_\alpha$, where each $X(n+1, e)$ is meant to be the set of level $n+1$ and index $e$, having as elements the sets of level $n$ whose indices satisfies the formula $\Phi_e$ in $J_\alpha$. $$ \begin{array}{rcl} X(0, e)&=&e\\ X(n+1, e)&=&\{X(n, x)\ :\ J_\alpha \vDash \Phi_e(x)\}\\ \end{array} $$

We then define $J_{\alpha+1} = \bigcup \{X(n, e)\ |\ n \in \omega,\ e \in J_{\alpha}\}$. For $\gamma$ limit we define $J_{\gamma} = \bigcup_{\beta < \gamma} J_\beta$.

In the following, everytime we mention $\Sigma_2$-definable, we mean $\Sigma_2$-definable by a formula with no parameter. Fix some ordinal $\alpha$. Suppose some ordinal of $J_{\alpha+1}$ is not $\Sigma_2$-definable in $J_{\alpha+1}$, and let $a$ be the smallest of them. Then $a$ has the following definition:

$$a \text{ is not } \Sigma_2\text{-definable and } \forall b < a\ b \text{ is } \Sigma_2\text{-definable}$$

Let us try to formalize this properly in $J_{\alpha+1}$. To do so, we use what Friedman calls a universal $\Sigma_1$ predicate, say $W(n, x, y)$. The predicate $W(n, x, y)$ is a $\Sigma_1$ formula which is true in $J_{\alpha+1}$ iff $\phi_n(x, y)$ if true in $J_{\alpha+1}$, where $\phi_n(x, y)$ is the $n$-th $\Sigma_1$ formula of two free variables. Friedman shows that such predicates exist at every level of the hierarchy.

We can now write "$a \text{ is not } \Sigma_2\text{-definable}$" as a $\Delta_3$ formula: $$\forall n \in \omega\ \ \ \forall x\ W(n, x, a) \text{ or } \exists b \neq a\ \exists x\ \neg W(n, x, b)$$

It follows that "$a \text{ is } \Sigma_2\text{-definable}$" is also a $\Delta_3$ formula: $$\exists n \in \omega\ \ \ \exists x\ \neg W(n, x, a) \text{ and } \forall b\ b \neq a \rightarrow \forall x\ W(n, x, b)$$

Suppose now that $\alpha$ is $\Sigma_2$-definable in $J_{\alpha+1}$. Then the following argument shows that we can lower the complexity of the above formulas to $\Sigma_2$: Now the universal quantifications can be replaced by existential quantifications in $J_{\alpha+1}$, given that we can use $J_{\alpha}$. Indeed, "$\forall x \dots$" (meaning $\forall x \in J_{\alpha+1} \dots$) becomes equivalent to:

$$\forall e \in J_\alpha\ \forall n \in \omega\ \exists x\ x=X(n, e)\text{ and } \dots$$

It seems that both $J_\alpha$ and $X(n,e)$ have a $\Sigma_1$ definition (using $\alpha$ as a parameter) in $J_{\alpha+1}$. So it follows that if $\alpha$ is $\Sigma_2$ definable in $J_{\alpha+1}$, then the smallest ordinal not $\Sigma_2$ definable in $J_{\alpha+1}$ is $\Sigma_2$ definable in $J_{\alpha+1}$. Then there cannot be such ordinals.

Now it seems that $\omega_1$ is $\Sigma_2$ definable in $J_{\omega_1+1}$ (which contains all the ordinals strictly smaller than $\omega_1 + \omega$), with the following formula of $\alpha$:

$$\forall \beta\ \exists n<\omega\ \beta < \alpha + n\ \text{ and } \forall \alpha' < \alpha\ \exists \beta\ \forall n<\omega\ \beta > \alpha' + n$$

It follows that every countable ordinal is $\Sigma_2$ definable in $J_{\omega_1}$, by formula with no parameter. This cannot be correct by a cardinality argument. What is wrong ?

$\endgroup$
2
  • $\begingroup$ That $\alpha$ is simply definable in $J_{\alpha+1}$ does not follow from the simple fact that it is the largest ordinal in the structure? I don't understand how you transfer from $J_{\alpha+1}$ to $J_{\omega+1}$: You claim $\alpha$ is $\Sigma_2$-definable in $J_{\alpha+1}$, and then conclude the same in $J_{\omega_1+1}$, but how this is possible without referring to $\alpha$ itself? $\endgroup$ Feb 22, 2017 at 10:23
  • 1
    $\begingroup$ The ordinal $\alpha$ is not the largest of $J_{\alpha+1}$: The ordinals of some class $J_{\beta+1}$ are all those strictly smaller than $\omega \beta + \omega$ (this is the Jensen hierarchy and not Godel's one). Also at the end I simply consider the exemple where $\alpha = \omega_1$. $\endgroup$ Feb 22, 2017 at 11:27

1 Answer 1

3
$\begingroup$

I may have found where is the trick hidden: I mean two different things by "being $\Sigma_2$-definable". When I write "the smallest ordinal which is not $\Sigma_2$-definable" I mean being definable by a formula of the form $\exists \forall \psi$ where $\psi$ only have bounded quantifiers.

But when I define this smallest ordinal with a $\Sigma_2$ definition, I define it with a formula where the bounded quantifiers are spread everywhere in the formula, including (for example) in between two existential quantifiers.

Of course in a model of sufficiently many ZF axioms, these two notions of being $\Sigma_2$-definable are equivalent. You probably need your model to be $\Sigma_1$ or maybe $\Sigma_2$ admissible. But $J_{\omega_1+1}$ is certainly not $\Sigma_1$-admissible...

I think this is what is wrong with this proof.

$\endgroup$
1
  • 2
    $\begingroup$ To be more specific: You need certain instances of Collection (or Replacement) to transform $\forall x\in A\ \exists y\ \varphi$ into a formula where the unbounded quantifier is on the outside, such as $\exists B\ \forall x\in A\ \exists y\in B\ \varphi$. $\endgroup$
    – Goldstern
    Feb 22, 2017 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.