# Abstract
The $L(\mathrm{aa})$-theory of ordinals - $\mathrm{Th}_{\mathrm{aa}}(\mathrm{On})$ - is studied. It is shown that $\mathrm{Th}_{\mathrm{aa}}(\mathrm{On})$ is primitive recursive. In a suitable language it is possible to eliminate quantifiers. $L$ (aa)-equivalence invariants are given. Both the complete $L(\mathrm{aa})$-theories of ordinals and the complete extensions of $\mathrm{Th}_{\mathrm{aa}}(\mathrm{On})$ are characterized. An ordering is $L(a a)$-inductive if every $L$ (aa)-definable subset (with suitable parameters) has a least element. The models of $\mathrm{Th}_{\mathrm{a} a}(\mathrm{On})$ are the $L$ (aa)-inductive orderings. A variant of the back and forth method is introduced in order to prove primitive recursive decidability and elimination of quantifier results.
# 1. $L(\mathtt{aa})$- preliminaries
>[!info] Definition
> A structure is *finitely determinate* if it satisfies the following scheme:
(DET) $\mathtt{aa}\bar{s} \forall \bar{x}(\mathtt{aa} t \varphi(\bar{x}, \bar{s}, t) \vee \mathtt{aa} t \neg \varphi(\bar{x}, \bar{s}, t))$
where $\varphi$ ranges over formulas in $L(\mathrm{aa})$. (Here $\bar{s}, \bar{x}$ denote finite sequences of variables.)
**1.7. Theorem.** All ordinals are finitely deterninate.
>[!info] Definition
> If $T$ is an $L(\mathtt{aa})$-theory, *$T$ admits elimination of quantifiers* (*elimination of second-order quantifiers*) if for every formula $\varphi(\bar{s}, \bar{x})$ there is a quantifier free (second-order quantifier free) formula $\varphi^*(\bar{s}, \bar{x})$ such that $T \vdash \mathtt{aa}\bar{s} \forall \bar{x}\left(\varphi \leftrightarrow \varphi^*\right)$.
# 2. Neighbourhood systems for $\boldsymbol{L}_{\omega \omega}$
In the following let $A, B$ be structures with no function symbols. If $\bar{a} \in A$, let $\langle\bar{a}\rangle$ denote the substructure of $\langle A, \bar{a}\rangle$ generated by $\bar{a}$. Let $A \subseteq B$ denote $A$ is a substructure of $B$ in their common language.
>[!info] Definition
> Suppose $\mathcal{N}=\left\{\mathcal{N}_n \mid n<\omega\right\}$ is a collection of functions whose domain is $A^{<\omega}$ (i.e. finite sequences of elements of $A$ ) such that for all $n, \bar{a} \in A, \mathcal{N}_n(\bar{a})$ is a structure whose language extends the language of $(A, \bar{a})$; and $\mathcal{N}_n(\bar{a}) \supseteq\langle\bar{a}\rangle$.
> Then $\mathcal{N}$ is a *neighbourhood system*, if for all $n, \bar{a}, \bar{b} \in A$ such that $\mathcal{N}_{n+1}(\bar{a}) \cong \mathcal{N}_{n+1}(\bar{b})$, for all $d$ there is $c$ so that $\mathcal{N}_n(\bar{a}, c) \subseteq \mathcal{N}_{n+1}(\bar{a})$ and $\mathcal{N}_n(\bar{a}, c) \cong \mathcal{N}_n(\bar{b}, d)$.
(various results on decidablity of $Th(\mathrm{On})$ and complexity of the elimination of quantifiers).
## Elementary equivalence invariants
>[!info] Definition
>For $l<\omega$ define *$l$-limit points*, *$l+1$-successor* and *$l+1$-predecessor* inductively:
> - Every $\alpha$ is a $0$-limit point
> - $\beta$ is the $l+1$ successor of $\alpha$ if $\beta$ is the least $l$-limit greater than $\alpha$.
> - Similarly $\beta$ is the $l+1$-predecessor of $\alpha$, if $\beta$ is the greatest $l$-limit less than $\alpha$.
> - Finally $\alpha$ is an $l+1$ limit point if it has no $l+1$-predecessor.
> i.e. it is the limit of $l$-limit points
>[!info] Definition
> Define propositional constants $X_l, Z_l, Y_{l k}$ ($l,k<\omega$) by::
> - $(\alpha,<)\vDash X_{l}$ iff $\alpha$ is an $l$-limit
> - $(\alpha,<)\vDash Z_{0}$ iff $\alpha=0$
> - $(\alpha,<)\vDash Z_{l}$ ($l>0$) iff $\alpha