Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Gödel's incompleteness theorems was a major achievement with ramifications outside the field of mathematics itself. Are there any direct applications of the theorem(s), or any of the methods pioneered in the proof(s) outside the field of logic itself but within mathematics itself. For example, say in Category Theory.

share|cite|improve this question
Did you try to read the wikipedia article (… )? It contains some implications. – Listing Jun 23 '12 at 14:49
I find it dubious that Gödel's theorems have ramifications outside mathematics. – Zhen Lin Jun 23 '12 at 14:51
@ZhenLin: depending on your philosophical stance, they may have ramifications in philosophy, or more specifically, epistemology, or maybe even ontology. I'm pretty sure it did provoke some development in those areas. – tomasz Jun 23 '12 at 15:25
That said, I don't think it has any significant consequences in noneffective mathematics. (Finitary logic is by its nature effective.) If you try to develop EFFECTIVE category theory, imposing restrictions of computability on categories and morphisms, for example, you likely will find some reflection of Godel's theorems. – tomasz Jun 23 '12 at 15:30
@tomasz: What do you mean by effective mathematics. I thought the term was a synonym for computable? I mentioned category theory specifically as I know its used in logic, and that toposes have an internal logic, so there might be applications there. – Mozibur Ullah Jun 23 '12 at 15:52
up vote 10 down vote accepted

To apply Gödel's incompleteness theorems one needs to be working with formal theories. Whether or not there are mathematical applications outside logic depends on how one draws the boundary of logic, as a subfield of mathematics.

For example, consider the Paris–Harrington theorem which shows that a certain statement of Ramsey theory, formulable in the language of arithmetic, implies the consistency of Peano arithmetic (PA). The Paris–Harrington sentence is a natural combinatorial statement which, by Gödel's second incompleteness theorem, is not provable in our usual system of first-order arithmetic.

There are a number of morals which one could draw from this theorem, but the one I want to call attention to here is this: there are number-theoretic propositions which go beyond our usual axioms for arithmetic, and which we must account for. If we hold the Paris–Harrington statement to be true then we're committed to stronger mathematical axioms than PA; for instance, we might want to assert that we can perform induction up to $\varepsilon_0$ and not just $\omega$ (since this is the usual way the consistency of PA is proved).

In fact a common use of the second incompleteness theorem is to draw boundaries to provability within certain formal systems. For example, we know that we can't prove a version of the Montague–Levy reflection theorem for infinite, rather than finite sets of sentences, because if we could then one of the infinite sets of sentences we could reflect would be the axioms of ZFC itself. Thus we'd have shown in ZFC that ZFC has a model, proving Con(ZFC) and contradicting the second incompleteness theorem. This also gives us the following corollary: ZFC is not finitely axiomatisable.

Assume for a contradiction that there is some finite set of sentences $\Phi$ such that for every formula $\varphi$ in $\mathcal{L}_\in$, $\Phi \vdash \varphi \Leftrightarrow \mathrm{ZFC} \vdash \varphi$. Of course this means that every axiom $\psi \in \Phi$ is a theorem of ZFC. So by the reflection theorem, there is some $V_\alpha$ such that $V_\alpha \models \Phi$. But by our assumption such a model will also be a model of ZFC, so Con(ZFC), contradicting the second incompleteness theorem.

Again, is this an application within logic? If set theory is part of logic, yes. But direct applications of Gödel's results will only ever show up when we deal with formal systems, so if we say that anytime we do that we're working within logic, then by definition they won't be applicable outside of it. Nonetheless incompleteness is, I would argue, a deep phenomenon; the only reason it doesn't appear more often—or more obviously—in mathematics is just that many results are proved in areas which employ in the background systems like ZFC which are far stronger than they need, and that mathematicians are often not careful about stipulating precisely what resources (that is to say, axioms) they do assume.

share|cite|improve this answer
Great answer. I wasn't aware that a natural unprovable sentence had been discovered. In Topos theory, logic is a part of set theory (suitably categorified) - it is its internal language, so in your second part we can invert your question about whether set theory is part of logic. – Mozibur Ullah Jun 23 '12 at 17:43
Harvey Friedman also has a slew of combinatorial statements that are independent of ZFC. – Quinn Culver Jun 26 '12 at 13:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.