What type of unsolvable theory is Elementary Function Arithmetic ($EFA$)?

Question

It is known that Robinson Arithmetic ($Q$) is essentially undecidable. Is Elementary Function Arithmetic ($EFA$) also essentially undecidable, and what is the Turing degree of its decision problem?

Answer 1

Since $\mathsf{EFA}$ is a consistent computably axiomatizable theory interpreting $\mathsf{Q}$, it is also essentially undecidable and its decision problem also has Turing degree ${\bf 0'}$. Same for Peano arithmetic, $\mathsf{ZFC}$, etc.

Broadly speaking, computability-theoretic complexity is an extremely coarse invariant. Another instance of this general theme is the result that, for example, the following are equivalent for a Turing degree ${\bf d}$:

• ${\bf d}$ computes a consistent completion of $\mathsf{Q}$ (usually "$\mathsf{PA}$" is quoted here instead of $\mathsf{Q}$, yielding e.g. the term "$\mathsf{PA}$ degree," but the result holds for $\mathsf{Q}$ too).

• For every consistent computably axiomatizable theory $T$, ${\bf d}$ computes a consistent completion of $T$.

(In my opinion this equivalence is demystified when we add a third equivalent condition: "${\bf d}$ computes separating sets for every pair of disjoint c.e. sets." But that's just me.)

More fine-grained computability-theoretic distinctions can be found if we bring some semantics into play. For example, $\mathsf{Q}$ has computable nonstandard models but $\mathsf{PA}$ doesn't, and I'm not sure what the situation for $\mathsf{EFA}$ is (but I suspect it lies on the "$\mathsf{PA}$-like" side). But at least for the specific questions you've asked, all the "vaguely foundational" theories look the same.