5
$\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.

  • 0
    Did you try to read the wikipedia article ( http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Discussion_and_implications )? It contains some implications.2012-06-23
  • 2
    I find it dubious that Gödel's theorems have ramifications outside mathematics.2012-06-23
  • 0
    @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.2012-06-23
  • 0
    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.2012-06-23
  • 0
    @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.2012-06-23
  • 0
    @tomasz I don't really understand what you mean. Surely set theory is part of noneffective mathematics? And yet here the independence of many statements from the usual axioms is a large part of the field.2012-06-23
  • 0
    @MoziburUllah: I don't think the term "effective" has a definite meaning in general mathematics. It can mean a lot of different things, including "constructive", "without axiom of choice", "computable", "efficiently computable" and probably a quite a few others. I meant more or less computable, but not in any particular way, just the intuitive notion. I don't know much about topoi, so I can't say much about it.2012-06-23
  • 0
    @BenedictEastaugh: But the independence of particular statements does not follow from Godel's theorems. All they can say that for any reasonable axiomatization of set theory there will be some such statements. A priori it could turn out that there is an axiomatization for which all these statements are not very interesting. Also they don't say anything about the very nature of set theory itself, only the way it relates to recursively enumerable axiom systems.2012-06-23
  • 0
    The applications outside of mathematics are typically wrong. The "applications" outside of mathematics are normally extrapolations that totally ignore the ideas that Godel's proof involves. The whole fiasco with Wittgenstein is a good example, as are those who try and shoehorn it into various social sciences.2012-06-23
  • 0
    @Mastragostino: Didn't Godel extrapolate from the Liars Paradox? I can just see some ancient greek philosopher shaking his head dolefully at Godels formalisation.2012-06-23
  • 0
    @tomasz of course you're quite right that the independence of CH (for example) doesn't follow from the incompleteness theorems. But they're instances of a more general phenomenon of the incompleteness of the axioms of set theory. And the independence of plenty of statements in the language of set theory from ZFC do follow directly from the second incompleteness theorem, like the existence of inaccessible cardinals.2012-06-23
  • 0
    @MoziburUllah the Gödel sentence for a particular theory is a self-referential statement similar to the Liar statement, yes: it basically says "I am not provable". The clever thing of course is that Gödel's statement leads to a theorem while the Liar appears to lead straight to contradiction. For this reason many researchers in formal theories of truth have formulated theories in which the Liar is formally inexpressible, or is not assigned a truth value.2012-06-23
  • 0
    @Eastaugh: I do know how Godels Theorem works :). I'm arguing against thinking Godels Theorem cannot inspire developments outside of mathematics, given how he himself was inspired by a philosophical statement, and much shorter & easier to digest without advanced training.2012-06-23
  • 0
    @MoziburUllah sorry, I didn't mean to imply that you didn't understand the theorem—I was just trying to draw the parallel a little more explicitly. :) One area that you could look into if you're interested in philosophical applications of Gödel's theorems is the disjunctive thesis which Gödel drew in his 1951 Gibbs lecture: "Either the human mind infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable diophantine problems." Among many others, Soloman Feferman has [addressed this issue](http://math.stanford.edu/~feferman/papers/dichotomy.pdf).2012-06-23
  • 0
    Philosophers have certainly tried to use it.2012-06-23
  • 0
    @Eastaugh: Thanks for the references. The disjunctive thesis definitely looks interesting. I'm interested also in questions as to whether language can be formalised. A linguistics prof might say yes. A poet might say no. I think Wittgenstein was against thought being formalisable (language is always public), but I'm guessing here, as I'm not a trained philosopher :).2012-06-23
  • 0
    If someone made an assertion and you asked them for proof and they replied 'Because I told you so' you wouldn't believe them. Congratulation, you have just applied Godel's incompleteness theorem outside of mathematics!2014-07-28

1 Answers 1

10

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.

  • 0
    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.2012-06-23
  • 0
    Harvey Friedman also has a slew of combinatorial statements that are independent of ZFC.2012-06-26