I'm curious about the problem of deciding if a given incomplete first-order theory has a stable completion from a descriptive set theory point of view. It seems likely that this problem is $\Pi\_1^1$-complete, but I can't quite prove it myself and I'm having difficulty finding a reference.


Given a partitioned formula $\varphi(\overline{x};\overline{y})$ an $n$-ladder for $\varphi$ is a pair of sequences of tuples, $\overline{a}\_0,\dots,\overline{a}\_{n-1}$ and $\overline{b}\_0,\dots,\overline{b}\_{n-1}$ such that $\models\varphi(\overline{a}\_i;\overline{b}\_j)$ if and only if $i<j$. The existence of an $n$-ladder for $\varphi$ is a first-order statement. Let $\chi\_{\varphi,n}$ be a sentence meaning "there is no $n$-ladder for $\varphi$". Recall that a theory $T$ is stable if for every partitioned formula $\varphi$ there is an $n<\omega$ such that $T\vdash \chi\_{\varphi,n}$.


Assume we have a fixed incomplete theory $T$ in some countable language $\mathcal{L}$ and let $\{\varphi\_i\}\_{i<\omega}$ be an enumeration of all partitioned $\mathcal{L}$-formulas. We can define a tree $S(T)\subseteq \omega^{<\omega}$ where $\sigma \in S(T)$ if and only if the theory $T\cup\{\chi\_{\varphi\_0,\sigma\_0},\dots,\chi\_{\varphi\_{\ell-1},\sigma\_{\ell-1}}\}$ is consistent, where $\ell=|\sigma|$.


It's clear that $T$ has a stable completion if and only if $S(T)$ has a path, so this problem looks like a question about well-foundedness of trees, which is usually a bad sign for complexity. So the question is:



> 
> Is there a way of encoding the well-foundedness of an arbitrary tree $R\subseteq \omega^{<\omega}$ into the well-foundedness of the tree $S(T\_R)$ for some theory $T\_R$ chosen as a function of $R$ in a low complexity (i.e. Borel) way?
> 
> 
> 


This is really just a roundabout way of asking whether or not this question is $\Pi\_1^1$-complete.



Complexity of deciding if an incomplete first-order theory has a stable completion
EDIT: Thanks to tomasz's comment I realized I was making this more complicated than it needed to be. Here is a simpler construction:


Let $\mathcal{L}=\{\leq\_i\}\_{i<\omega}$ be a countable sequence of binary relations. Given a tree $R\subseteq \omega^{<\omega}$, let $T\_R$ be the theory with the following axioms:


* $\forall x \forall y (x \leq\_i y \wedge y \leq \_i x \rightarrow x=y)$, for each $i$
* $\forall x\forall y \forall z(x \leq\_i y \wedge y \leq\_i z \rightarrow x \leq \_i z)$, for each $i$.
* $\forall x\forall y(x \leq \_i y \rightarrow x\leq \_i x\wedge y\leq\_i y)$, for each $i$.
* $\forall x \forall y (x\leq \_i x \wedge y\leq \_i y \rightarrow x\leq \_i y \vee y\leq\_i x)$, for each $i$.
* $\forall x(x\leq\_i x \rightarrow \neg x\leq\_j x)$, for each $i\neq j$.
* $\neg \bigwedge\_{i<|\sigma|}\exists^{=\sigma(i)}x(x\leq\_i x)$, for each $\sigma \in \omega^{<\omega} \setminus R$.


Where $\exists^{=k}x\varphi(x)$ means 'there exists precisely $k$ $x$ such that $\varphi(x)$ holds'.


Basically this is a countable family of independent linear orders. The only way for this theory to have a stable completion is if all of the linear orders (i.e. the sets of $x$ such that $x\leq\_i x$) are finite and this can happen if and only if $R$ has a path.




---


I realized the answer is yes, there's a computable map from trees $R \subseteq \omega^{<\omega}$ to first-order theories $T\_R$ such that $T\_R$ has a stable completion if and only if $R$ has a path, implying that the class of first-order theories with stable completions is $\Sigma\_1^1$-complete (I got mixed up with $\Pi\_1^1$ in the question), although technically this relies on assuming the following extremely plausible thing that I'm too lazy to look up or prove:



> 
> *Assumption*: For every $n<\omega$ there is a stable theory $T$ with a binary predicate $P$ such that $P(x;y)$ has an $(n-1)$-ladder but no $n$-ladder. (Where we say by default that every formula has a $(-1)$-ladder.)
> 
> 
> 


Let $\mathcal{L}$ be a language with countably many unary predicates $\{U\_i\}\_{i<\omega}$, countably many binary predicates $\{P\_i\}\_{i<\omega}$, and countably many $k$-ary predicates $\{Q\_{i,k}\}\_{i<\omega}$ for each $k<\omega$.


For any $n<\omega$, let $\chi\_{i,n}$ be a sentence that says that $P\_i(x;y)$ has an $(n-1)$-ladder but does not have an $n$-ladder. 


Given a tree $R \subseteq \omega^{<\omega}$, let $T\_R$ be the $\mathcal{L}$-theory with the following axioms:


* $\forall x\forall y(P\_i(x,y)\rightarrow U\_i(x)\wedge U\_i(y))$, for each $i<\omega$.
* $\forall x\neg(U\_i(x)\wedge U\_j(x))$, for each $i<j<\omega$.
* $\neg \bigwedge\_{k<|\sigma|}\chi\_{k,\sigma(k)}$, for each $\sigma \in \omega^{<\omega} \setminus R$.


These axioms are clearly c.e. in $R$. It's also not too hard to see that $T\_R$ is always a consistent theory, even if the tree is empty, since we can always make it so that each $P\_i$ has arbitrarily long ladders.


Now I claim that $T\_R$ has a stable completion if and only if $R$ has a path.


*Proof:* $(\Rightarrow)$: Assume that $T\_R$ has a stable completion $T$. For each $i<\omega$, there must be an $\alpha\in \omega^\omega$ such that $P\_i(x;y)$ has an $(\alpha(i)-1)$-ladder but no $\alpha(i)$-ladder. So in particular this means that $T\vdash \chi\_{k,\alpha(k)}$ for each $k<\omega$, so for any $k<\omega$, $\alpha \upharpoonright k \in R$, i.e. $R$ has a path.


$(\Leftarrow)$: Assume that $R$ has a path, $\alpha \in \omega^\omega$. For each $k>\omega$, let $T\_i$ be a complete stable theory with infinite models in a language including the predicate $P\_i$ with the property that $P\_i(x;y)$ has a $(\alpha(i)-1)$-ladder but no $\alpha(i)$-ladder. We may assume that each $T\_i$ is in some sub-language $\mathcal{L}\_i$ of $\mathcal{L}$ such that for any $i,j$, $U\_i \notin \mathcal{L}\_j$ and for any $i\neq j$, $\mathcal{L\_i}\cap\mathcal{L\_j}=\varnothing$. We may also assume that $\mathcal{L}=\{U\_i\}\_{i<\omega}\cup\bigcup\_{i<\omega}\mathcal{L}\_i$ by adding any unused predicates to $T\_0$ and adding axioms saying that they are always false.


Now we can combine these into a single theory $T$ extending $T\_R$ by making it so that the predicate $U\_i$ is a model of the theory $T\_i$ with no interaction between the theories, i.e. for each $i<\omega$, we let $T\_i^\prime$ be $T\_i$ with all quantifiers relativised to $U\_i$, then we let $T$ be the axioms in $T\_R$ and the $T\_i^\prime$'s together with axioms of the form $\forall\overline{x}(S(\overline{x})\rightarrow (U\_i(x\_0)\wedge \cdots \wedge U\_{i}(x\_{n-1})))$ for each $n$-ary relation symbol $S\in \mathcal{L}\_i$. A type counting argument shows that any such 'disjoint union' of stable theories is stable, so we have that $T$ is a stable completion of $T\_R$. $\square$


It's not too hard to see that having a stable completion is $\Sigma\_1^1$, so we get that the class of first-order theories with stable completions is $\Sigma\_1^1$-complete.


