6
$\begingroup$

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.

$\endgroup$
17
  • $\begingroup$ Did you try to read the wikipedia article ( en.wikipedia.org/wiki/… )? It contains some implications. $\endgroup$
    – Listing
    Commented Jun 23, 2012 at 14:49
  • 4
    $\begingroup$ I find it dubious that Gödel's theorems have ramifications outside mathematics. $\endgroup$
    – Zhen Lin
    Commented Jun 23, 2012 at 14:51
  • $\begingroup$ @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. $\endgroup$
    – tomasz
    Commented Jun 23, 2012 at 15:25
  • $\begingroup$ 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. $\endgroup$
    – tomasz
    Commented Jun 23, 2012 at 15:30
  • $\begingroup$ @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. $\endgroup$ Commented Jun 23, 2012 at 15:52

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Jun 23, 2012 at 17:43
  • $\begingroup$ Harvey Friedman also has a slew of combinatorial statements that are independent of ZFC. $\endgroup$ Commented Jun 26, 2012 at 13:48
0
$\begingroup$

I could expand this answer later, but the most important application of Gödel's Incompleteness theorems not yet mentioned is that they put an end to Hilbert's Program of reducing all of mathematics to finitary proofs. This constrained the predicate of computability and led to the invention of computers. Both Church's and Turing's seminal papers are formulated as responses to Gödel's Incompleteness theorems.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .