7
$\begingroup$

There's a large countable ordinal which has cropped up (as a lower bound!) in a computable structure theory problem I'm playing with. At present I don't really understand how big it is, and I'm curious where it fits in amongst better-understood ordinals. (I do have a kind of upper bound, but it's weird and not very helpful to me.)

Say that $\alpha$ is $\Sigma^1_1$-pd iff for every $x\in L_\alpha$ there is some $\Sigma^1_1$ formula $\varphi$ in the language of set theory without parameters such that $\{x\}=\varphi^{L_\alpha}$. (Here "$\Sigma^1_1$" refers to quantification over subsets of $L_\alpha$, not $\omega$, so this is quite broad.) I'm interested in the following:

How large is the smallest non-$\Sigma^1_1$-pd ordinal, $\eta$?

I'm interested in either "theory-oriented" (e.g. "$\eta\ge$ the least $\alpha$ such that $L_\alpha\models\mathsf{KP\omega}$ + '$\omega_1$ exists'") or "stability-oriented" (e.g. "$\eta\le$ the least $\alpha$ such that $L_\alpha\prec_1L_{\omega_1}$") information about $\eta$. A genuine characterization would be great, but I suspect there isn't a snappy one; I'll settle for any interesting bounds (lower or upper) on $\eta$.

(To be fair there are a couple immediate projectum-flavored observations, namely that every $\Sigma^1_1$-pd ordinal is $\Pi^1_2$-projectible to $\omega$ and that if $\alpha$ is $\Sigma^1_1$-projectible to $\omega$ then $\alpha$ is $\Sigma^1_1$-pd, but that line of thought doesn't seem to give me much detailed information about $\eta$. So I'd be happy with projectum-flavored information as well, but I suspect that's the wrong way to go.)

$\endgroup$
4
  • 1
    $\begingroup$ Incidentally, this summary of Madore (to whom thanks are due) is a nice source of information about these and related types of ordinals. $\endgroup$ – Noah Schweber Jan 11 at 0:50
  • 3
    $\begingroup$ 17.${}{}{}{}{}$ $\endgroup$ – Asaf Karagila Jan 11 at 1:41
  • $\begingroup$ Let $\varphi(x)$ be of form $\exists y\ \psi(x)$, where $\psi$ first order in the language of set theory augmented with a predicate $Y$. By $\varphi(x)^{L_\alpha}$, do you mean that there is some $y\subseteq L_\alpha$ such that the structure $(L_\alpha,\in,y)\models\psi(x)$? $\endgroup$ – Farmer S Jan 12 at 17:44
  • $\begingroup$ @FarmerS Yes, exactly. $\endgroup$ – Noah Schweber Jan 12 at 18:20
8
$\begingroup$

Claim: Let $\kappa$ be least such that $L_\kappa$ is admissible and $L_\kappa\models$``$\omega_1$ exists'' and let $\alpha=\omega_1^{L_\kappa}$. Then $\alpha$ is the least non-$\Sigma^1_1$-pd ordinal. Moreover, the 1st projectum of $L_\kappa$ is $\rho_1^{L_\kappa}=\omega_1^{L_\kappa}=\alpha$, and the 1st standard parameter is $p_1^{L_\kappa}=\{\alpha\}$. (Thus, $\kappa$ is also the least admissible such that $\rho_1^{L_\kappa}>\omega$.)

The following lemma is probably standard, but I had not noticed it before:

Lemma: Let $\kappa$ be such that $L_\kappa$ is admissible and $\delta<\kappa$ such that $L_\kappa\models$``$\delta$ is a cardinal''. Then $\rho_1^{L_\kappa}\geq\delta$.

Proof: Suppose not. Then $L_\kappa=\mathrm{Hull}_1^{L_\kappa}(\rho\cup\{p\})$ for some $\rho<\delta$ and $p\in L_\kappa$. (That is, the $\Sigma_1$-hull of parameters in $\rho\cup\{p\}$.) Therefore $L_\kappa\models$``For every $\beta<\delta$ there is an ordinal $\gamma$ such that $\beta\in\mathrm{Hull}_1^{L_\gamma}(\rho\cup\{p\})$''. But then by admissibility, there is $\gamma<\kappa$ which works simultaneously for all $\beta<\delta$, which yields a surjection $f:\rho\to\delta$ with $f\in L_\kappa$, contradicting that $\delta$ was a cardinal there.

Proof of Claim: For the moment let $\alpha$ be any ordinal, and let $\kappa_\alpha$ be the least $\kappa>\alpha$ such that $L_\kappa$ is admissible. Let $\kappa=\kappa_\alpha$. Note that if there is $\beta\in[\alpha,\kappa)$ such that $L_\beta$ projects to $\omega$, then one can identify the least such $\beta$ in a $\Sigma^1_1$-over-$L_\alpha$ way (using the usual relationship between illfounded models and admissibles), and therefore $\alpha$ is $\Sigma^1_1$-pd.

So suppose that $\alpha=\omega_1^{L_\kappa}$, where $\kappa=\kappa_\alpha$. Then $L_\alpha\preceq_1 L_\kappa$, by condensation, and hence $\mathrm{Hull}_1^{L_\kappa}(\alpha)=L_\alpha$. But $L_\kappa=\mathrm{Hull}_1^{L_\kappa}(\alpha+1)$. For if this hull had ordinal height $\beta<\kappa$, just let $\psi$ be some $\Sigma_0$ formula and $p,d\in L_\beta$ such that $L_\beta\models\forall x\in d\ \exists y\ \psi(p,x,y)$ but $\beta$ is least such; then because $p,d$ are in the hull, so is $\beta$ actually, contradiction. Combined with the lemma, this gives $\rho_1^{L_\kappa}=\alpha$ and $p_1^{L_\kappa}=\{\alpha\}$.

Now suppose for a contradiction that $\alpha$ is $\Sigma^1_1$-pd. I claim that $\rho_1^{L_\kappa}=\omega$ and $p_1^{L_\kappa}=\{\alpha\}$, contradicting the previous paragraph. For this, we show that $L_\kappa=\mathrm{Hull}_1^{L_\kappa}(\{\alpha\})$.

We can convert $\Sigma^1_1$-over-$L_\alpha$ to $\Pi_1^{L_\kappa}(\{\alpha\})$ formulas (i.e. $\Pi_1$ over $L_\kappa$, in parameter $\alpha$). (This must be a standard generalization of the situation when $\alpha=\omega$: Given a $\Sigma^1_1$ formula $\varphi(x)=\exists y\psi(x)$, consider the game where player I plays elements of $L_\alpha$ and player II also plays such elements, and player II also decides which of these elements go into a predicate $y$, and then player II wins iff the elements played produce a structure $(M,\in,y)$ such that $(M,\in,y)\models\psi(x)$. Then for $x\in L_\alpha$, $(\varphi(x))^{L_\alpha}$ iff there is a winning strategy for player II in the game iff the standard analysis of the game (see below) does not yield a winning strategy for player I in $L_\kappa$, and the latter is a $\Pi_1^{L_\kappa}(\{\alpha\})$ statement.)

(Edit:) The analysis of the game: The game, at least once one sets up the rules appropriately, has open payoff for player I. Let $E$ be the set of partial plays of the game of even length. Let $S$ be the set of all $p\in E$ from which player I has a winning strategy (for the game continuing from $p$). We rank $S$, writing $S_{\beta}$ for the set of partial plays of rank ${<\beta}$. Let $S_0=\emptyset$ and $S_1$ be the set of $p\in E$ where player I has already won. For limit $\beta$ let $S_\beta=\bigcup_{\gamma<\beta}S_\gamma$. And for $\beta\geq 1$ let $S_{\beta+1}$ be the set of $p\in E$ such that there is $x\in L_\alpha$ such that for all $y\in L_\alpha$, we have $(p,x,y)\in S_\beta$. Note that $\beta\leq\gamma\implies S_\beta\subseteq S_\gamma\subseteq S$. Let $\beta_\infty$ be the least $\beta$ such that $S_\beta=S_{\beta+1}$. Then $S=S_{\beta_\infty}$. Now (by setting up the game rules appropriately) $E$ is definable over $L_\alpha$, and note that it follows that $S_\beta\in L_\kappa$ for each $\beta<\kappa$, and that $\left<S_\beta\right>_{\beta<\kappa}$ is $\Sigma_1^{L_\kappa}(\{\alpha\})$. Now $\beta_\infty\leq\kappa$. For otherwise we have some $p\in S_{\kappa+1}\backslash S_\kappa$, so for all $x\in L_\alpha$ there is $y\in L_\alpha$ such that $(p,x,y)\in\bigcup_{\beta<\kappa}S_\beta$, and note this contradicts admissibility. So player I wins iff $\emptyset\in S_\kappa$, and player II wins iff $\emptyset\notin S_\kappa$.

So, because $\alpha$ is $\Sigma^1_1$-pd, for every $x\in L_\alpha$ there is a $\Pi_1$ formula $\varphi$ such that $x$ is the unique $x'\in L_\alpha$ such that $L_\kappa\models\varphi(x',\alpha)$. But then $x\in\mathrm{Hull}_1^{L_\kappa}(\{\alpha\})$. For we have that for every $x'\in L_\alpha$ with $x'\neq x$, $L_\kappa\models\neg\varphi(x',\alpha)$. So by admissibility, there is $\beta<\kappa$ such that for every $x'\in L_\alpha$ with $x'\neq x$, we have $L_\beta\models\neg\varphi(x',\alpha)$. But then note that the least such $\beta$ can be detected in a $\Sigma_1^{L_\kappa}(\{\alpha\})$ manner, and from that we can compute $x$, so $x$ is in the hull, as desired.

This is a contradiction, showing that $\alpha$ is not $\Sigma^1_1$-pd.

The full Claim follows by putting the things above together above.

Remark: Let $\alpha$ be an ordinal and $\kappa=\kappa_\alpha$. Then conversely to one point above, every $\Pi_1^{L_\kappa}(\{\alpha\})$ subset of $L_\kappa$ is $\Sigma^1_1$-over-$L_\alpha$.

$\endgroup$
8
  • $\begingroup$ Quick question: what's a "first standard parameter?" $\endgroup$ – Noah Schweber Jan 12 at 18:35
  • $\begingroup$ For $L_\gamma$, one can define it as the least finite set $p$ of ordinals (in the top-down lexicographic order) such that $L_\gamma=\mathrm{Hull}_1^{L_\gamma}(\rho\cup\{p\})$, where $\rho$ is the 1st projectum. (And the 1st projectum is the least ordinal $\rho$ such that there is some such $p$.) $\endgroup$ – Farmer S Jan 12 at 18:41
  • $\begingroup$ Hm, it sounds like you're using "1st projectum" differently to how I'm used to. I understood "$n$th projectum" to be "the least $\theta$ such that there is a $\Sigma_n$-over-$L_\kappa$ injection from $\kappa$ to $\theta$." At least for $n=1$, is that equivalent to the definition you give? (If it is, then my now-deleted alternate proof of the lemma does work I believe.) $\endgroup$ – Noah Schweber Jan 12 at 18:51
  • $\begingroup$ I believe this works, and I've upvoted. I'll accept once I've had time to read it through in detail. I'm still curious per my previous comment whether your definition of projecta coincides with mine, though, at least for $n=1$; at a glance I think it does, but I'm not sure. $\endgroup$ – Noah Schweber Jan 12 at 20:28
  • $\begingroup$ Yes, it's the same (assuming you're allowing parameters in $L_\kappa$ in the $\Sigma_n$-over-$L_\kappa$ definitions). (For $n>1$ also.) $\endgroup$ – Farmer S Jan 13 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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