Roughly speaking, given a set-sized logic $\mathcal{L}$ let $\mathcal{L}'$ be gotten by adding to $\mathcal{L}$ the ability to quantify over $\mathcal{L}$-definable relations. (The details are a bit tedious, so I've put the rigorous definition at the end of this question.) Note that $\mathcal{L}'$ is always strictly stronger than $\mathcal{L}$: let $\kappa$ be some cardinal greater than the set of $\mathcal{L}$-formulas in the language $\{<\}$, and consider the least $\mathcal{L}$-undefinable element of the structure $(\kappa;<)$. We can iterate this jump operation up to any ordinal $\alpha$ by taking unions at limit stages as usual (since we're not worrying about syntax there is no "notation"-flavored issue) to get $\mathcal{L}^{(\alpha)}$. Even iterating through all the ordinals makes sense; call the result $\mathcal{L}^{(\infty)}$.


I'm interested in pinning down $\mathsf{FOL}^{(\infty)}$. Here's what I know so far:


* $\mathsf{FOL}^{(\infty)}$ is (always up to expressive strength) a sublogic of $\mathcal{L}\_{\infty,\omega}^L=\mathcal{L}\_{\infty,\omega}\cap L$. More generally, if $M$ is an inner model and $\mathcal{L}$ is a set-sized sublogic of $\mathcal{L}\_{\infty,\omega}^M$ which is appropriately definable in $M$, then $\mathcal{L}'\subseteq\mathcal{L}^M\_{\infty,\omega}$ as well.
* $\mathsf{FOL}^{(\infty)}$ is strictly weaker than $\mathcal{L}\_{\infty,\omega}^L$: if $(r\_i)\_{i\in\omega}$ are sufficiently mutually Cohen generic (say, generic over a countable elementary submodel of $L\_{\omega\_1}$), then the $\{<,\in\}$-structures $\omega\sqcup\{r\_{2i}:i\in\omega\}$ and $\omega\sqcup\{r\_{2i+1}: i\in\omega\}$ are $\mathsf{FOL}^{(\infty)}$-equivalent but not $\mathcal{L}\_{\infty,\omega}^L$-equivalent.
* The argument of the previous bulletpoint implies that the $\mathsf{FOL}^{(\infty)}$-definable relations on $(\omega;<)$ fall well short of the constructible ones. On the other hand, it's also easy to see that they reach well past the hyperarithmetic: the $\mathsf{FOL}^{(\omega\_1^{CK})}$-definable relations are exactly the hyperarithmetic ones, and $\mathcal{O}$ is then $\mathsf{FOL}^{(\omega\_1^{CK}+1)}$-definable since a computable linear order is a well-order iff it supports a hyperarithmetic jump sequence.
* Finally, despite its clear weaknesses, for every countable structure $\mathfrak{A}$ the automorphism orbit relation on elements (or $n$-tuples for fixed $n$) of $\mathfrak{A}$ is $\mathsf{FOL}^{(\infty)}$-definable (this is just Scott's argument).


My main question is whether there is a better description of this logic as a whole:



> 
> **Question 1**: Is there a snappier description of $\mathsf{FOL}^{(\infty)}$?
> 
> 
> 


The definition of $\mathsf{FOL}^{(\infty)}$ is "bottom-up" (a more snappy version: it's the smallest possibly-class-sized logic containing $\mathsf{FOL}$ and containing $\mathcal{L}'$ whenever $\mathcal{L}$ is a set-sized logic it contains). I would be especially be interested in a "top-down" definition, such as "the largest logic containing $\mathsf{FOL}$ with *[tameness properties]*." Lindstrom's theorem is one motivating example of such a definition, but there are others - e.g. [Barwise's analysis of $\mathcal{L}\_{\infty,\omega}$](https://www.sciencedirect.com/science/article/pii/0003484372900022).


My secondary question, for which I at least have a conjecture, is about its arithmetic power specifically:



> 
> **Question 2**: What are the $\mathsf{FOL}^{(\infty)}$-definable relations on the naturals?
> 
> 
> 


My guess is that these are exactly the relations in $L\_{\beta\_0}$, where ${\beta\_0}$ is the smallest "gap ordinal" (= such that $L\_{\beta\_0}\cap\mathbb{R}=L\_{\beta\_0+1}\cap\mathbb{R}$). This ${\beta\_0}$ is known to also be the least ordinal such that $L\_{\beta\_0}\models\mathsf{ZFC^-}$, or such that $L\_{\beta\_0}\cap\mathbb{R}\models\mathsf{Z}\_2$. See [Putnam](https://projecteuclid.org/journals/notre-dame-journal-of-formal-logic/volume-4/issue-4/A-note-on-constructible-sets-of-integers/10.1305/ndjfl/1093957652.full), [Marek/Srebrny](https://www.sciencedirect.com/science/article/pii/0003484374900059/), or [Madore (entry 2.17)](http://www.madore.org/%7Edavid/math/ordinal-zoo.pdf).




---


Details
-------


Here's a more precise definition of $\mathcal{L}'$. We take the closure of the $\mathcal{L}$-formulas under the addition of a whole family of new relation quantifiers $$\bigtriangledown^{\mathcal{L},p}\_{\delta,\eta,\rho\_1,...,\rho\_n}.$$ Here the $\mathcal{L}$-superscript indicates the logic with respect to which we are quantifying over definable relations, $p\in\omega$ indicates the arity of the relations being quantified over, and $\delta,\eta,\rho\_1,...,\rho\_n$ are $\mathcal{L}$-formulas with respective arities $d, e, r\_1,...,r\_n$ such that $e=2d$ and each $r\_i$ is divisible by $d$. The semantics of these new quantifiers is given as follows:


* In any structure $\mathfrak{A}$, if $\eta^\mathfrak{A}$ is an equivalence relation on $\delta^\mathfrak{A}$ and each $\rho\_i^\mathfrak{A}$ is well-defined on $\delta^\mathfrak{A}/\eta^\mathfrak{A}$ in the obvious sense, then "$\bigtriangledown^{\mathcal{L},p}\_{\delta,\eta,\rho\_1,...,\rho\_n}X[\mathit{stuff}]$" (with $X$ a $p$-ary relation variable) means



> 
> "For every $\eta^\mathfrak{A}$-invariant relation $X\subseteq(\delta^\mathfrak{A})^p$ such that $X/\eta^\mathfrak{A}$ is $\mathcal{L}$-definable in the related structure $(\delta^\mathfrak{A}/\eta^\mathfrak{A}; \rho\_1,...,\rho\_n)$, it is the case that $[\mathit{stuff}]$."
> 
> 
> 


* On the other hand, if $\delta,\eta,\rho\_1,...,\rho\_n$ do not satisfy the above conditions in $\mathfrak{A}$, then we interpret $\bigtriangledown^{\mathcal{L},p}\_{\delta,\eta,\rho\_1,...,\rho\_n}$ in some fixed trivial way (say, always outputting $\perp$).


Note that when we iterate $'$ we get multiple $\bigtriangledown$-quantifiers; so, for example, $\mathsf{FOL}^{(\omega)}$ has a separate quantifier (family) $\bigtriangledown^{\mathsf{FOL}^{(n)}}$ for each $n\in\omega$. *(Incidentally, a stronger version of this construction was suggested in [this MSE post](https://math.stackexchange.com/questions/4605261/non-henkin-non-full-semantics-for-second-order-logic/4605604#4605604), but I've ultimately decided that the more limited approach here is more natural.)*



What is the "iterated definability" limit of first-order logic?
If I understand the question properly (I'm not sure whether I do), then it looks like your conjecture for question 2 is correct, i.e. $L\_{\beta\_0}\cap\mathcal{P}(\omega)$. Here is a hastily written sketch.


For in fact, letting $N\_\alpha$ be the set of $\mathcal{L}^{(\alpha)}$ relations on $\omega$, then $N\_\alpha=L\_{\omega+\alpha}\cap\mathcal{P}(\omega)$ for all $\alpha\leq\beta\_0$, and $\beta\_0$ is a closure point.


The small issue here is to see that over $N\_\alpha$, we can simulate $L\_\alpha$ definably from parameters, assuming that $N\_\alpha=L\_\alpha\cap\mathcal{P}(\omega)$.


Suppose $\alpha=\beta+1$. Since $L\_\beta$ projects to $\omega$, there is a real $x\in N\_\alpha$ which codes $L\_\beta$.
We can refer to $x$, since this is given by some $\mathcal{L}^{(\alpha)}$ relation. Then in fact for all ordinals in $\gamma\in[\alpha,\kappa\_\alpha)$,
where $\kappa\_\alpha$ is the least admissible $\kappa>\alpha$,
we can define simulate $L\_\gamma$ over $N\_\gamma$ by looking at all models $M$
coded by reals which satisfy ``$V=L[x]$''; all of these are wellfounded,
because otherwise the wellfounded part is a model of KP, but it easily enough follows then that $N\notin L\_{\kappa\_\alpha}$, so $N\notin N\_\gamma$. So over $N\_\gamma$ we can simulate $L\_\gamma$, and hence define (from parameters) all reals in $L\_{\gamma+1}$.


So we get that $N\_{\kappa\_\alpha}=L\_{\kappa\_\alpha}\cap\mathcal{P}(\omega)$.


Now suppose that $\alpha$ is a limit of admissibles, and we have $N\_\alpha=L\_\alpha\cap\mathcal{P}(\omega)$. Then over $N\_\alpha$, we can simulate $L\_\alpha$ by looking at all models $M$
coded by reals, which satisfy ``$V=L$'',
and are wellfounded in $N\_\alpha$,
i.e. have no descending sequence through their ordinals which is in $N\_\alpha$.
(Any illfounded such model $M$ gets into some $L\_\kappa$ for some admissible $\kappa<\alpha$, but then we get a descending sequence before $\alpha$.)
So we can simulate $L\_\alpha$ over $N\_\alpha$ as desired.


