Is Godel's incompleteness theorem unavoidable?

Question

So after Godel's Incompleteness theorem and the fact that some theorems mathematicians are interested in are independent of ZFC (e.g. Continuum Hypothesis) is there some hope for some other foundational theory which will be (provably) complete and the fact that it is complete will not imply it`s inconsistency ? Furthermore, is there hope for such theory to have have most of axioms to be intuitive, I mean not to be ad hoc ? If it is not, can it still be that there is some way different from foundations based on one foundating theory from which we build all other theories, which will allow us to avoid Godel incompletness theorem ? Or is it just unavoidable ?

Answer 1

The MRDP theorem gives a very good case that there is no satisfying way around this. Specifically, any foundational system we use surely needs to be able to talk about Diophantine equations. Specifically, let me phrase it this way:

Suppose $T$ is a complete computable theory. Then there is no computable function $f$ from Diophantine equations to sentences in the language of $T$ such that $T$ proves $f(E)$ iff $E$ has a solution.

Why should this be weird? Well, note that such an $f$ does exist for many natural computable, but incomplete, theories: PA, ZFC, etc., really any theory which is (i) $\Sigma_1$-sound and (ii) reasonably powerful.

Proof: otherwise, we could computably tell whether a Diophantine equation $E$ has a solution by searching through $T$-proofs - if $E$ has a solution we eventually find a proof of $f(E)$, and if $E$ has no solution then by completeness we eventually find a proof of $\neg f(E)$. And we can't find both, since then $T$ would be inconsistent and hence prove everything, and in particular prove $f(D)$ for some $D$ with no solutions, contradicting our hypothesis. $\Box$

So if we want to build a complete computable theory, we'll need to accept that this won't allow us to talk about even Diophantine equations in any reasonable way.

---

More generally, we're just running into the fact that the set of Diophantine equations without solutions isn't c.e.; so even if we move away from classical logic we won't be able to get completeness for Diophantine equations without proving that some Diophantine equation simultaneously does and doesn't have solutions, which is surely something we don't want!

---

The obvious thing to try to drop at this point is computability, but at that point our system isn't usable: we have no way to tell whether a purported proof in the system is in fact valid.

Now, this doesn't rule out interesting fragments of mathematics being fully decidable, such as arithmetic with only addition. But these are the exceptions, not the rule, and they don't even account for basic high school mathematics. Nobody would consider such a weak theory to be an appropriate foundation for mathematics.