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

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

• But do you mean by encoding, exactly? – tomasz Mar 31 '19 at 10:47
• In any event, it is not hard to show that given any two formulas $\varphi_1,\varphi_2$, you can construct a formula $\varphi$ (purely syntactically, independently of $T$) such if $\varphi_1$ is not $k$-stable or $\varphi_2$ is not $k$-stable, then $\varphi$ is not $k$-stable. Using this (for countable languages), you can recursively construct a sequence $(\varphi_n)_{n\in \mathbf N}$ such that the $\varphi_n$s are increasingly unstable, and $T$ is stable iff each $\varphi_n$ is stable. I don't fully understand the question, but this should give you a negative answer. – tomasz Mar 31 '19 at 10:54
• I assume you're talking about coding in a 'switch' with something like $\psi(\overline{x},y_1,y_2) = (y_1=y_2 \wedge \varphi_1(\overline{x})) \vee (y_1 \neq y_2 \wedge \varphi_2(\overline{x}))$? That does seem relevant but I'll have to think about it. Thank you. – James Hanson Mar 31 '19 at 14:31
• What I mean by coding is something like Slaman and Woodin's result that the class of partial orders with a linearization with the same order type as $\mathbb{Q}$ is $\Sigma$_1^1$-complete. The proof goes by taking an arbitrary tree and constructing a partial order such that the partial order has such a linearization if and only if the original tree was not well-founded. It's an 'encoding' since the construction is relatively low complexity (I believe it's computable from the tree, even). – James Hanson Mar 31 '19 at 14:34 • Yes, this is what I was thinking about. Well, with disjoint variables for$\varphi_1,\varphi_2$, but that is no big difference. – tomasz Mar 31 '19 at 14:55 ## 1 Answer 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. • $$\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. • This assumption is pretty trivial. A linear order of size$n$witnesses what you ask for if$n>0$. Trivial relation witnesses that for$n=0\$. – tomasz Apr 2 '19 at 20:57
• Thanks for pointing that out. For some reason I thought the theories needed to have only infinite models, and even if it did need that it's easy to add infinitely many dummy points. I think I made this more complicated than it needed to be. – James Hanson Apr 3 '19 at 2:32