I hope that mathematical logic / recursion theory type questions are welcome here. I am sorry this question is so long and technical, but I believe that if you read it you will find that it is well-motivated.

Definitions

• Let $a leq_T b$ denote that set $a$ is Turing reducible to set $b$. Additionally, call $a$ and $b$ Turing equivalent if $a leq_T b$ and $b leq_T a$.
• If $A$ is a set of sentences of first-order logic, let $Theory(A)$ denote the set of all sentences of first-order logic (FOL) that are logical consequences of $A$. If $A$ is a finite set we say that $Theory(A)$ is finitely-axiomatizable.
• If $A$ and $B$ are finite sets of sentences of FOL, then let $A Longrightarrow B$ denote that the sentence $land_{a in A} a$ logically implies the sentence $land_{b in B} b$, or equivalently that $Theory(B) subseteq Theory(A)$.
• Let $0$ denote the Turing degree that contains all decidable sets, and let $0’$ denote the Turing degree that contains all sets that are Turing equivalent to the set of all pairs $(M, x)$ such that Turing machine $M$ halts on input $x$.
• Let $bot$ denote a logically unsatisfiable sentence of FOL, and let $top$ denote a logically valid sentence of FOL.

Motivation

This question is motivated by the similarities between the set of recursively enumerable (r.e.) sets under the Turing-reducibility partial order and the set of sentences of FOL under the logical implication partial order. Here are some connections I noticed:

• For every r.e. set $c$, we have that $0 leq_T c leq_T 0’$. Analogously, for every finite set $A$ of sentences of FOL, we have that $bot Longrightarrow A Longrightarrow top$.

• $Theory(bot) in 0$ and $Theory(top) in 0’$ (This second statement only holds for languages with enough non-logical symbols).

• Let $A$ and $B$ be finite sets of sentences of FOL. If $A Longrightarrow B$, then $Theory(A) leq_T Theory(B)$.

The third observation can be proven by observing that if $A Longrightarrow B$, then for every sentence $C$ of FOL, we have that $C in Theory(A)$ if and only if $A longrightarrow C in Theory(B)$, where $A longrightarrow C$ is shorthand for $lnot A lor C$.

These three observations suggest that there are many structural similarities between the r.e. Turing degrees under $leq_T$ and the sentences of FOL under $Longrightarrow$. Thus the following question is natural:

Question

Is there a language of first-order logic such that every recursively enumerable set is Turing equivalent to a finitely-axiomatizable theory of sentences in that language?

Note that the converse of this question, that every finitely-axiomatizable theory of FOL is Turing equivalent to a recursively enumerable set, is trivially true. Additionally, I can prove this question is true if I remove the requirement that the theory is finitely-axiomatizable.

One problem I’ve run into is the following. Suppose you are trying to construct a finite set of sentences $A$ such that $Theory(A) leq_T c$, where $c$ is a r.e. theory that is strictly ‘easier’ than the halting problem (i.e. $ 0′ not leq_T c$). Well, $Theory(A)$ necessarily contains all valid statements (i.e. $Theory(top)$). But $Theory(top)$ is Turing equivalent to the halting problem, so we must ensure somehow that $Theory(top)$ cannot be recovered from $Theory(A)$. I cannot figure out how to ensure this condition.

It is worth noting that the proof of the undecidability of first-order logic given in Computability and Logic by Boolos and Jeffrey only requires a language $L$ containing the following non-logical symbols: a single constant, four dyadic predicates, and enumerably many monadic predicates.

Consequences

If the answer to my question is yes, then I can prove some exciting consequences. Specifically, if the above question is true for a language $L$ of FOL, then I can convert statements about Turing degrees into statements about sentences in language $L$. I give an example:

Sacks Density Theorem: If $a <_T b$, where $a$ and $b$ are r.e. sets, then there is an r.e. set $c$ such that $a <_T c<_T b$ (note that $a <_T b$ means $a leq_T b$ and $b not leq_T a$).

Assuming my question is true for a language $L$, I can get the following statement:

Logical Density: There exists a subset of the set of sentences on $L$ that is dense under the not logical implication ($not Rightarrow$) relation.

Proof (edited for clarity): We build the following set $Gamma$ of sentences on $L$. For every distinct r.e. Turing degree $a$, choose exactly one finite set of sentences $A$ such that $Theory(A)$ is Turing equivalent to $a$. Convert $A$ to a single finite sentence by taking the conjunction of each sentence in $A$, and add this conjunction to set $Gamma$.

Now we have the following connection between r.e. sets and our set $Gamma$. Consider r.e. sets $a$ and $b$ such that $a <_T b$. Then there exists sentences $A, B in Gamma$ such that $a$ is Turing equivalent to $Theory(A)$ and $b$ is Turing equivalent to $Theory(B)$. Then by an observation made earlier, this implies that $B not Rightarrow A$ (because if $B Rightarrow A$, then $b leq_T a$, a contradiction). By Sacks density theorem, we must have that there is an r.e. set $c$ such that $a <_T c <_T b$. Then there exists a sentence $C in Gamma$ such that $Theory(C)$ is Turing equivalent to $c$, and by a similar argument as before, $B not Rightarrow C not Rightarrow A$. Now because we’ve mapped $not leq_T$ to $not Rightarrow$, a subset of $Gamma$ can be chosen that is dense under $not Rightarrow$ (we must choose a subset of $Gamma$ that corresponds to a total order of Turing degrees).

There are many results like Sacks theorem that we could convert into statements on sets of sentences in $L$ if my question was answered affirmatively! It may also be possible to convert statements on sentences in $L$ to statements on r.e. sets, but this seems harder.

Are there any existing results in the literature that are of a similar flavor to my inquiry?

Thank you for reading!