Gödel's Incompleteness Theorem and Theories which are not recursively axiomatizable

Question

I'm trying to understand the full extent of Gödel's Incompleteness Theorem with regards to what types of consistent and complete theories it rules out. Does it only prove that number theory/ZFC cannot be a subtheory of a complete consistent theory which is recursively axiomatizable or rather any complete consistent theory regardless of how it might be axiomatized? If it's only the former, are there any known consistent complete theories for which number theory is a subtheory? Thanks.

Answer 1

First, recall that for any structure $\mathcal{A}$ - including $\mathcal{N}:=(\mathbb{N};+,\times)$, the standard model of arithmetic - the theory of $\mathcal{A}$ $$Th(\mathcal{A}):=\{\varphi:\mathcal{A}\models\varphi\}$$ is trivially complete and consistent. Since $\mathcal{N}\models\mathsf{PA}$ this gives as a special case that $Th(\mathcal{N})$ - more commonly denoted "$\mathsf{TA}$" for "true arithmetic" - is a very natural complete consistent theory extending $\mathsf{PA}$.

So Godel's incompleteness theorem cannot possibly apply to arbitrary complexity theories, at least not without additional complicating hypotheses which would rule out things like $\mathsf{TA}$.

---

OK, now let's actually say a bit about Godel.

The proof of the first incompleteness theorem has a key technical limitation: the theory $T$ in question must exhibit a combination of weakness and strength. Roughly speaking, $T$ must be able to prove all "very basic" facts about its own provability predicate. This both requires $T$ to be reasonably strong, and requires $T$ to be not too complicated. For example, true arithmetic $\mathsf{TA}$ is not definable in $\mathcal{N}$, so it can't even talk about itself at all (let alone prove things about itself).

As such, GIT is in fact fairly limited. Here's one way to pose GIT which is pretty close to optimal:

No consistent complete r.e. theory can interpret Robinson arithmetic.

The notion of interpretation here is a particularly technical one, so this isn't necessarily a good formulation of the incompleteness theorem to start off focusing on. But I think it's a good thing to see, if only briefly, early on: the various ingredients (consistency, completeness, r.e.-ness, and "logical strength" in some capacity) are clearly displayed and there is no imprecise language being used.

---

That said, we can indeed push Godel beyond the r.e. theories, at least to a certain extent. Basically, we just need to strengthen the consistency hypothesis to rule out errors which are "low-level" compared to the theory itself. One result along these lines which I think is folklore is discussed at this old answer of mine (albeit focusing on theories in the language of arithmetic for simplicity - note that I just corrected that answer, since looking back on it the original version had an indexing error!).