3
$\begingroup$

This is a somewhat open-ended question — I’m curious whether there are any known results which are able to prove that one theory is not recursively axiomatizable over another, despite both having the same Turing degree. In particular the situation I’m curious about is the following:

We have two first-order theories $A, B$ over a common language, and we want to show that for any recursively-enumerable subtheory $T \subseteq B$, $A + T \not\vdash B$.

Of course there is a straightforward reason this could be true, namely that $A$ is R.E. while $B$ is not, or more generally that $B$ has a sufficiently higher Turing degree than $A$. In such cases we can invoke the first-order completeness theorem to argue that if $B$ were recursively axiomatizable over $A$, then $B$ would in fact be recursively enumerable with oracle access to an enumeration of $A$, which would contradict the fact that $B$ is “harder to enumerate” then $A$.

What I’m curious about is if their are known methods for proving such results in the case where $A$ and $B$ have the same degree of undecidability, so that we would not obtain a contradiction from that existence of an enumeration of $B$ with an oracle for $A$, but nonetheless $B$ cannot be recursively axiomatized over $A$ for some more “logical”/model-theoretic reasons.

$\endgroup$
5
  • 1
    $\begingroup$ Note that if $B$ is enumeration reducible to $A$, then $B$ is recursively axiomatizable over $A$: the enumeration reduction itself is basically such an axiomatization (think of clauses of the form "$(\bigwedge_{1\le i\le n}\alpha_i)\rightarrow\beta$"). So in examples of this phenomenon - which do exist, if memory serves - rely crucially on the ability of a Turing reduction to use positive and negative facts about the oracle. $\endgroup$ Commented Dec 19, 2022 at 4:04
  • $\begingroup$ Thank you! I was not aware of this notion of “enumeration reduction” and the work i’m seeing on it seems to be highly relevant to the question I’m thinking about. $\endgroup$ Commented Dec 19, 2022 at 4:25
  • $\begingroup$ Could you clarify whether you are treating theories as sets of sentences, or do they have to be deductively closed? This can affect the Turing degree. $\endgroup$ Commented Dec 19, 2022 at 12:26
  • $\begingroup$ Just as sets of sentences. $\endgroup$ Commented Dec 19, 2022 at 15:50
  • $\begingroup$ @NoahSchweber on second though I’m not sure your claim holds in general. If we have an enumeration reduction E we can use it to generate a recursive list of $(\alpha_1, \ldots, \alpha_n, \beta)$ where the $\alpha_i,\beta$ are formula, such that whenever all $\alpha_i$ lie in $A$, $\beta$ must lie in $B$ (I think this is what you mean). However this in no way implies that $\bigwedge \alpha_i \vdash \beta$ (I’m using $\vdash$ in the semantic/model theoretic sense) since this implication could be based on some reasoning “beyond” basic FOL deductions. $\endgroup$ Commented Dec 19, 2022 at 17:13

0

You must log in to answer this question.

Browse other questions tagged .