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$ Commented 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$ Commented 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
    Commented Feb 22, 2017 at 18:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .