*This question was [asked and bountied](https://math.stackexchange.com/q/3619818/28111) 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$](https://en.wikipedia.org/wiki/Robinson_arithmetic), 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.)



The lattice of analogues of Robinson's $Q$
$\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$.


