2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But do you mean by encoding, exactly? $\endgroup$ – tomasz Mar 31 '19 at 10:47
  • $\begingroup$ 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. $\endgroup$ – tomasz Mar 31 '19 at 10:54
  • $\begingroup$ 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. $\endgroup$ – James Hanson Mar 31 '19 at 14:31
  • $\begingroup$ 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). $\endgroup$ – James Hanson Mar 31 '19 at 14:34
  • $\begingroup$ Yes, this is what I was thinking about. Well, with disjoint variables for $\varphi_1,\varphi_2$, but that is no big difference. $\endgroup$ – tomasz Mar 31 '19 at 14:55
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – tomasz Apr 2 '19 at 20:57
  • $\begingroup$ 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. $\endgroup$ – James Hanson Apr 3 '19 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.