Complexity of deciding if an incomplete first-order theory has a stable completion

Question

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.

Answer 1

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.