$\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:

- if $\psi$ is false, then $\psi^\star$ has a finite model;
- if $\psi$ is true, then any model of $\psi^\star$ contains $\mathbb{N}$ as an initial segment;
- $\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$:

- $K$ is the random distributive lattice;
- $K$ is the random distributive lattice with appended $0$;
- $K$ is the random distributive lattice with appended $1$;
- $K$ is the random distributive lattice with appended $0$ and $1$.

leastelement, and every nontrivial interval is the countable atomless Boolean algebra, but I don’t immediately see how to prove it has nolargestelement (though it is probably true). Is the random distributive lattice completely described by these three conditions? $\endgroup$ – Emil Jeřábek Apr 30 '20 at 5:39