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.)



How big is the least non-$\Sigma^1_1$-pointwise-definable ordinal?
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$.


