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

  • 1
    $\begingroup$ Can one embed the rationals inside this lattice? Gerhard "Pardon The Unstated Notational Pun" Paseman, 2020.04.24. $\endgroup$ – Gerhard Paseman Apr 24 '20 at 22:56
  • $\begingroup$ @GerhardPaseman Yes, embedding is easy enough. Specifically, take your favorite sentence $P\in\mathfrak{Q}$ and pick an appropriate collection of sentences $\Phi=(\varphi_q)_{q\in\mathbb{Q}}$ such that $P\vdash\varphi_q\rightarrow\varphi_{q'}$ iff $q\le q'$. The existence of such a $\Phi$ isn't hard to establish. Now consider $\{P\wedge \varphi_q: q\in\mathbb{Q}\}$. More generally, every countable partial order embeds into every (nonempty) upper cone in $\mathfrak{Q}$ viewed as a partial order. $\endgroup$ – Noah Schweber Apr 24 '20 at 23:26
  • 2
    $\begingroup$ Is the order upside down? Because if I use the order $\phi\le\psi\iff{}\vdash\phi\to\psi$, it’s obvious that the funny-letter-lattice has no least element, and every nontrivial interval is the countable atomless Boolean algebra, but I don’t immediately see how to prove it has no largest element (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
  • 1
    $\begingroup$ (The answer to my second question is yes: moreover, the theory of nontrivial distributive lattices such that each nontrivial interval is an atomless Boolean algebra has exactly four countable models, depending on whether top or bottom elements exist. Thus, there are only two candidates for the lattice in question, depending on if it has a largest element or not.) $\endgroup$ – Emil Jeřábek Apr 30 '20 at 13:09
  • 1
    $\begingroup$ The order I wrote is the standard order on the Lindenbaum–Tarski algebra (of which your lattice is a convex sublattice). This makes the algebraic operations ($\land,\lor,\neg,\top,\bot$) agree with logical connectives. $\endgroup$ – Emil Jeřábek Apr 30 '20 at 19:06

$\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$.
  • $\begingroup$ Lovely! My original attempt to show that $\mathfrak{Q}$ had no greatest element was along these lines but not focusing on as small a syntactic class as $\Pi^-_1$, which made coding the necessary complexity into the sentence no longer easy (or doable for me). $\endgroup$ – Noah Schweber May 3 '20 at 19:10
  • $\begingroup$ I think that something like $\Pi_1^{-}$ is essential for this kind of argument. $\endgroup$ – Fedor Pakhomov May 3 '20 at 19:21
  • $\begingroup$ Yes, I think that's right. (Certainly we can't go much higher and get a naive index set argument: $Th_\Gamma(\mathbb{N})$ quickly becomes too complicated as $\Gamma$ gets bigger.) $\endgroup$ – Noah Schweber May 3 '20 at 19:23
  • $\begingroup$ A potentially-interesting followup question: what if we look at the ordering of essentially incomplete sentences (possibly not true of $\mathbb{N}$) ordered by interpretability? Given any $\varphi$ the set of e.i.-sentences interpreting $\varphi$ is d.c.e. (interpreting $\varphi$ is c.e. and consistency is co-c.e.) while a priori essential incompleteness looks $\Pi^0_3$, so there should be no minimal element in this order either. But now d.c.e. seems a bit too big to get this kind of argument to work. $\endgroup$ – Noah Schweber May 3 '20 at 19:26
  • 1
    $\begingroup$ I think that my argument about non-existence of the greatest element could be adopted to this case with almost no changes. We just need to note that the interpretability relation $\psi^{\star}\triangleright \varphi_0$ is $\Sigma_1$. Although I don't know enough about the lattice of interpretability degrees of arbitrary sentences to say whether it would be enough to figure out the answer to your question. $\endgroup$ – Fedor Pakhomov May 3 '20 at 19:52

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.