The lattice of analogues of Robinson's $Q$

Question

This question was asked and bountied at MSE without response.

---

Call a sentence $\varphi$ in the language of arithmetic $Q$-like iff $\mathbb{N}\models\varphi$ and $\{\varphi\}$ is essentially incomplete. The standard example is of course the conjunction of the finitely many axioms of Robinson's $Q$, but this is of course not unique - and indeed the partial order $\mathfrak{Q}$ of equivalence classes of $Q$-like sentences under entailment as in the Lindenbaum algebra ($\varphi\le\psi\iff\vdash\varphi\rightarrow\psi$) is not linear. On the positive side, $\mathfrak{Q}$ is clearly a distributive lattice, and every countable partial order embeds into each element of $\mathfrak{Q}$'s lower cone (see my comment below).

My question is:

What exactly is $\mathfrak{Q}$, up to isomorphism?

There's an obvious candidate, based on the idea that everything that can happen does in this sort of situation: the (countable) random distributive lattice (that is, the Fraisse limit of the set of finite distributive lattices). However, I'm having trouble proving this. Even showing that $\mathfrak{Q}$ has no greatest element isn't trivial, as far as I can see. (EDIT: by "isn't trivial" I now mean "I can't.")

(As a quick remark, note that essentially undecidable theories need not come from elements of $\mathfrak{Q}$: Robinson's $R$ is essentially undecidable but each of its finitely axiomatizable subtheories has a computable completion.)

Answer 1

$\mathfrak{Q}$ is the countable random distributive lattice.

Emil Jeřábek has already pointed in his comments that there are only two possibilities for $\mathfrak{Q}$. Either there are no greatest element in $\mathfrak{Q}$ and it is the countable random distributive lattice. Or there is the greatest element in $\mathfrak{Q}$ and $\mathfrak{Q}$ is the countable random distributive lattice with appended greatest element. So I'll only need to show that there exist no sentence $\varphi_0$ such that $\mathbb{N}\models\varphi_0$ and for any $\varphi$, if $\mathbb{N}\models \varphi$, then $$\varphi\text{ is essentially undecidable }\iff \vdash \varphi\to \varphi_0.$$

Indeed assume for a contradiction that $\varphi_0$ exist.

To simplify things as much as possible here I'll consider $\mathbb{N}$ to have the signature consisting of the constant $0$ and predicates $\mathsf{Succ}(x,y)$, $\mathsf{Add}(x,y,z)$, $\mathsf{Mul}(x,y,z)$, and $x\le y$; it is possible to modify the argument so that it will work with the standard signature $0,S,+,\times$, but it would add additional complications. Let us consider the class $\Pi_1^{-}$ of all formulas of the form $\forall x\;\theta(x)$, where all quatifiers in $\theta$ are $x$-bounded. Note that the set of all true $\Pi_1^{-}$ sentences is $\Pi_1$-complete.

For any $\Pi_1^{-}$ arithmetical sentence $\psi$ of the form $\forall x \;\theta(x)$ let us consider the sentence $\psi^\star$: $$\mathsf{Q}^{-}\land \forall x\;(\theta(x)\to \exists y\;(\mathsf{Succ}(x,y)).$$ Here $\mathsf{Q}^{-}$ should be a version of $\mathsf{Q}-\text{"totality of $S,+,\times$"}$ in our signature. The key properties of $\psi^\star$ that we will need are the following:

1. if $\psi$ is false, then $\psi^\star$ has a finite model;
2. if $\psi$ is true, then any model of $\psi^\star$ contains $\mathbb{N}$ as an initial segment;
3. $\mathbb{N}\models \psi^\star$, regardless of whether $\psi$ were true or not.

Notice that any sentence $\varphi$ (in our finite signature) with a finite model isn't essentially undecidable. And that by the standard argument (that uses a pair of recursively inseparable sets) we see that if any model of a sentence $\varphi$ contain $\mathbb{N}$ as an initial segment, then $\varphi$ is essentially undecidable. To conclude, $\psi^{\star}$ is always true and is essentially undecidable iff $\psi$ is true.

Under the assumption that $\varphi_0$ exists we see that $$\{\psi\in \Pi_1^{-}\mid\mathbb{N}\models \psi\}=\{\psi\in \Pi_1^{-}\mid \psi^{\star}\text{ is essentially undecidable}\}=\{\psi\in \Pi_1^{-}\mid \vdash \psi^{\star}\to \varphi_0\}$$ is $\Sigma_1$. But on the other hand it should be $\Pi_1$-complete, contradiction.

For the sake of completeness let me sketch my reconstruction of Emil's argument. Observe that by Gödel's first incompleteness theorem $\mathfrak{Q}$ has no least element. By Rosser's theorem, for any pair $a<_{\mathfrak{Q}}b$ the interval $[a,b]$ is a countable atomless Boolean algebra. By a standard back and forth argument it is easy to show that for a countable distributive lattice $K$, if all non-trivial intervals in $K$ are countable atomless Boolean algebra, then there are only 4 possibilities for $K$:

1. $K$ is the random distributive lattice;
2. $K$ is the random distributive lattice with appended $0$;
3. $K$ is the random distributive lattice with appended $1$;
4. $K$ is the random distributive lattice with appended $0$ and $1$.