Joel David Hamkins and Atticus Stonestrom, “The pattern of consistency strength for membership in a computably enumerable set,” preprint. arxiv:2610.24919.
Abstract. Every computable preorder relation on the natural numbers is the order of consistency strength for the membership assertions “$n\in A$” in some computably enumerable set $A$. Moreover, for every computably enumerable list of theories $T_0$,$T_1$,$T_2$,…, each extending PA, there is a computably enumerable set $A$ such that each $T_n$ is equiconsistent over PA with the membership assertion $n\in A$. And similarly for both results when using instead the nonmembership assertions $n\notin A$.
Every computably enumerable set $A\newcommand\of{\subseteq}\of\newcommand\N{\mathbb{N}}\N$, taken under the specification of a particular computable enumeration process, gives rise to a natural spectrum of membership assertions
$$n\in A,$$
which assert of the various particular numbers $n$ that they appear in the given computable enumeration of $A$. Such an assertion $n\in A$, when true, is provable in PA, of course, since PA can prove that the computation proceeded as it did to produce the number $n$. If the set $A$ is computably undecidable, however, there will be infinitely many instances of nonmembership $n\notin A$ that are not provable in PA or even in ZFC or ZFC plus large cardinals, for whichever consistent computably axiomatizable foundational theory we might prefer. Otherwise, we would be able to decide membership in $A$ by searching for proofs. Proofs of nonmembership in a consistent theory extending PA, after all, even a very strong one, are trustworthy, for if we can prove nonmembership $n\notin A$, then we won’t later discover that it is a member $n\in A$, since that would also be provable and hence reveal inconsistency in the theory. Many true instances of nonmembership will consequently be unprovable. Every computably undecidable computably enumerable set is thus saturated with logical undecidability—there will be membership assertions that are logically independent of our most aspirational foundational theories (if $\Sigma^0_1$-sound). In this way, the two common uses of “undecidable” in logic come into alignment.
In light of this pervasive logical independence for the membership assertions in a computably enumerable set, we should like to investigate the possible comparative consistency strengths these kinds of statements can exhibit.
Main Question. Which patterns of relative consistency strength occur for the membership assertions $n\in A$ in a computably enumerable set? Exactly which preorders arise this way as the order of consistency strength? And what about the nonmembership assertions $n\notin A$?
Our main theorem provides a sweeping answer: every computable pattern is possible. For any computable preorder relation $\newcommand\triangleleq{\lhd}\triangleleq$ on the natural numbers, we produce a computably enumerable set $A$ for which the membership assertions $n\in A$ exhibit a consistency-strength order that is identical to the $\triangleleq$ relation. By choosing $\triangleleq$ suitably, therefore, we can find a computably enumerable set $A$ whose membership assertions $n\in A$ have consistency strengths in the order of the natural number order itself, or in the reverse order, or in the order of the integers, or the rational line $\mathbb{Q}$, or as an infinite antichain of pairwise incomparable consistency strengths, or as a countably universal preorder, whatever is desired. Every computable preorder is realized as the order of consistency strength of some computably enumerable set $A$. And similarly for nonmembership assertions $n\notin A$. What is more, for any computably enumerable sequence of theories $T_0,T_1,T_2,\ldots$, there is a computably enumerable set $A$ such that every $T_n$ is equiconsistent over PA with the membership assertion $n\in A$, and for another such set $A$ it is equiconsistent with nonmembership $n\notin A$.
Main Theorem.
- Every computable preorder relation $\triangleleq$ on the natural numbers is the order of consistency strength for the membership assertions in some computably enumerable set $A$. That is, for all natural numbers $m,n$, we have: $$m \triangleleq n\ \newcommand\Iff{\iff}\Iff\ \newcommand\PA{\text{PA}}\PA \newcommand\proves{\vdash}\proves\newcommand\Con{\text{Con}}\Con(\PA + n \in A) \to \Con(\PA + m \in A).$$
- For every computably enumerable list of theories $T_0, T_1, T_2, \ldots$, each extending PA or interpreting it in a uniformly computable manner, there is a computably enumerable set $A$ such that each theory $T_n$ is equiconsistent over PA with the membership assertion $n\in A$. That is, for every natural number $n$, we have $$\PA\proves\Con(T_n)\leftrightarrow\Con(\PA+n\in A).$$
- The same as (1), but for non-membership. More precisely, for every computable preorder relation $\triangleleq$ there is a computably enumerable set $A$ such that, for all $m,n$, $$m \triangleleq n\ \Iff\ \PA \proves \Con(\PA + n \notin A) \to \Con(\PA + m \notin A).$$
- The same as (2), but for non-membership. More precisely, for every computably enumerable list of theories $T_0,T_1,\ldots$ as in (2), there is a computably enumerable set $A$ such that, for each $n$, $$\PA\proves\Con(T_n)\leftrightarrow\Con(\PA+n\notin A).$$
These results appear as theorems 3, 6, 12, and 14 in the paper, respectively.
