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.
Gödel’s Incompleteness Theorem and Theories which are not recursively axiomatizable
axiomsfirst-order-logicincompletenesslogic
Related Solutions
Perhaps "surprising" is no longer the right word; what is surprising to one person may not be surprising to another. The fundamental theorem of calculus is another result which is sometimes claimed to be "surprising" but which may not surprise everyone. So I don't want to dwell on the "surprising" part, but I want to address a few other questions from the post.
One point is that, even if the incompleteness theorem is not surprising, its proof is far from obvious - particularly the theorem as stated in the question, which requires Rosser's trick in addition to Gödel's argument. If the incompleteness theorem was as obvious as the fact that a group can be commutative or noncommutative, we might expect the proof to be simpler.
The second point is that, although it is true that (e.g.) the axioms of a group are not complete, they are easy to make complete. For example, the theory of torsion free, divisible Abelian groups is complete, consistent, and axiomatizable, as is the theory of algebraically closed fields of a fixed characteristic. The theory of real closed fields is axiomatizable, consistent, and complete, as is Tarski's axiomatization of Euclidean geometry.
So there is something different about arithmetic, compared to real closed fields or geometry. In that sense, the incompleteness theorems may not be surprising, but they are fundamental. They show that we cannot hope to attain the kind of axiomatization for arithmetic that we can obtain for the field of real numbers or for geometry.
Many of the theories in the mathematical literature describe a class of structures (all groups, all fields, all posets, etc.) and so we don't expect them to be complete. But other theories might be intended to describe a particular structure - the real line, the Euclidean plane, the natural numbers. In these cases, once we pick the signature, there is already a complete theory at hand, namely the set of all true sentences of the structure in that signature. So the question is not so much about whether a particular theory is complete (as in the penultimate paragraph of the post), but whether we could in principle write a complete ''and effective'' set of axioms for the theory of the structure and signature we are looking at. For the specific structure $\mathbb{N}$, the incompleteness theorem shows that this is impossible, but goes beyond that to show more.
Below, all theories/sentences are first-order.
First, let's recall the meaning of (in)completeness:
A theory $T$ is incomplete if there is some sentence $\alpha$ in the language of $T$ such that $T$ neither proves nor disproves $\alpha$.
Note that $\alpha$ must be a sentence - that is, it cannot involve free variables.
It turns out that this purely syntactic situation can equivalently be described semantically:
$T$ is incomplete iff there is some sentence $\alpha$ in the language of $T$ such that $\alpha$ is true in some models of $T$ and false in other models of $T$.
This is (an equivalent rephrasing of) what could be called the "Fundamental Theorem of Provability" - but is unfortunately called the completeness theorem (even worse, it's also due to Godel!). Note that the term "(in)complete" is annoyingly overloaded: (in)completeness of a theory is a very different thing from (in)completeness of a proof system.
With that out of the way, you are correct: induction plays no role in Godel's first incompleteness theorem. The most general common phrasing of GFIT is the following (basically observed by Robinson, following Rosser's improvement on Godel's original argument):
Suppose$^1$ $T$ is a consistent first-order theory which is computably axiomatizable and interprets Robinson arithmetic $\mathsf{Q}$. Then $T$ is incomplete - that is, there is a sentence $\alpha$ in the language of $\mathsf{Q}$ such that $T$ neither proves nor disproves $\alpha$ (and so by the completeness theorem, is true in some models of $T$ and false in others).
(The term "interprets" here is a technical one - basically, it lets us shift attention to theories in other languages, like $\mathsf{ZFC}$. If you like, ignore it for now and replace it with "contains $\mathsf{Q}$.")
So $\mathsf{Q}$ is in fact very strongly incomplete. This property is called essential incompleteness.$^2$ Note that unlike mere incompleteness, essential incompleteness is not "downwards hereditary" - every essentially incomplete theory has a subtheory which is not essentially incomplete, namely the set of all tautologies. So while the incompleteness of $\mathsf{Q}$ trivially follows from the incompleteness of $\mathsf{PA}$, the essential incompleteness of $\mathsf{Q}$ isn't a trivial consequence of the essential incompleteness of $\mathsf{PA}$. This failure of downwards hereditariness means that the irrelevance of induction here is actually quite interesting.
For an in-depth analysis of what exactly is necessary for GFIT, and why in particular interpreting $\mathsf{Q}$ is fairly optimal, see e.g. this article of Beklemishev, especially section $4$.
$^1$Each of the hypotheses in GFIT (consistency, computable axiomatizability, and interpreting $\mathsf{Q}$) is necessary. It's obvious that consistency can't be dropped. To see that computable axiomatizability can't be dropped, consider the set of all true sentences of arithmetic; this is trivially complete and consistent and interprets $\mathsf{Q}$, but it isn't computably axiomatizable. Finally, there are in fact quite interesting examples of computably axiomatizable complete consistent theories - e.g. real closed fields (and this means that in a precise sense $\mathbb{R}$ is logically simpler than $\mathbb{N}$!) - but these are "weak" in the sense that they do not interpret $\mathsf{Q}$.
$^2$ Actually, essential incompleteness is usually phrased as the weaker property "$T$ is essentially incomplete iff every consistent computably axiomatizable extension of $T$ is incomplete," rather than in terms of interpretability, but this in fact implies the stronger version involving interpretations.
Best Answer
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:
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!).