What did Gödel show with his first incompleteness theorem?

By Philippos Papayannopoulos

It’s very common to read and hear people talking about Kurt Gödel’s famous (first) incompleteness theorem, in popular media, books, discussions, etc. Which is a very good thing I think, given how wonderful and ingenious the ideas and the reasoning behind this theorem are. But even though it’s more than almost 85 years since the first proof of the theorem was given by K. Gödel (1931), it’s still quite common to read and hear misconceptions about what this theorem really tells us.

To give an example, in my previous post I discussed this year’s Isaac Asimov memorial debate where five physicists and one philosopher investigated the simulation universe hypothesis, that is, the idea that we live in a universe which in fact is a simulation. There, Gödel’s theorem was brought up in the context of discussing that mathematics is often not adequate to capture the great complexity of the physical world; or, at least, we are not able to do it, because even when we come close to achieving this, the mathematics of our models becomes intractable. So, the view expressed in effect was that mathematics is incomplete and, hence, not adequate to capture the complexity of the real world — a fact supposedly established by Gödel’s incompleteness theorem, since Gödel proved that ‘there are things in mathematics that you cannot prove’ (see @1:09:16 of the video). Well, it is indeed correct that mathematics may sometimes be “incomplete” in the sense that it gives us a limited description of the physical situation under examination. But there is also a different sense of “incompleteness” (which I will explain below), and this latter sense is actually what Gödel’s first incompleteness theorem is about. So, is there any room for interpreting Gödel’s theorem as establishing anything relevant to the “incompleteness” of mathematics in the first sense, i.e. in the sense of not being adequate to express fully the complexity of a real physical system?

The answer is ‘no’. This is so because in Gödel’s sense, “incompleteness” is a technical term exclusively referring to an axiomatized formal theory that is not able to tell us whether specific sentences (or their denials) can be inferred from the theory. Let’s briefly see what is meant by all these terms. In order to get an idea of what an “axiomatized theory” is, it is enough to recall Euclidean geometry from our school years. Back then, we were drilled into deriving theorems about circles, triangles, etc. from simpler results, which in turn could be derived from other earlier results, and so on, ultimately coming from a small collection of fundamental principles (the axioms).

By “formal theory”, on the other hand, we mean a theory which has been couched in an artificial language, that is, a language designed to reveal the underlying logical structure of our statements and be free from the obscurities and ambiguities found in ordinary natural languages. One, most commonly used, such language is called “the language of the 1^st order predicate logic”. Languages of that sort are equipped with a very precise syntax and semantics. That is, it is a purely mechanical task to decide whether a given string of symbols constitutes a syntactically correct sentence in the language and whether any given sentence is true or false, according to its intended meaning (interpretation). The advantage in ‘regimenting’ our theories by expressing them in such formal languages is that the validity of proofs and the successions of any inferential steps can also be checked mechanically, that is, solely based on the form of strings of symbols. Intuitively, this is like saying that such checks could be performed even by a machine or an illiterate person who only perceives strange meaningless symbols and understands nothing of what those symbols purport to be about.

The practice of axiomatically systematizing our theories has influenced mathematics profoundly, since Euclid’s time, and remained for centuries an ideal to aim for. On the other hand, the practice of formalizing mathematical theories in formal languages is more recent (it originates around the beginnings of the 20^th century) and is not really pursued in everyday mathematics.

Now, crucially, it is only to theories meeting both ideals that Gödel’s theorems apply.* And for any such theory, Gödel’s first incompleteness theorem says that some sentences exist which, although they can be formed in the precise formal language in which the theory is formalized, the theory itself is not able to tell us anything about whether they hold or not. That is, neither their affirmation nor their denial can be proved by the theory. In logicians’ terminology: there are sentences which are undecidable by the theory. This has the consequence that even our humble, elementary school arithmetic is inexhaustible, in the sense that it is impossible for all of its truths to fit into one single axiomatized formal system. It is impossible for all of them to be derived from results which are also derived from other results, all the way back to a set of few fundamental axioms, which, in turn, can be specified in an algorithmic, mechanical way. Differently put, it’s impossible to try to prove everything within one unified formal system; there will always be true sentences left out.

So what is important to stress is that the above is in no sense about limitations of mathematics in general, as it is often assumed and said to be (see, for one more example, this very interesting talk by S. Hawking, in which, Gödel’s theorem seems to be interpreted to be about mathematics in general). Rather, the theorem is about limitations of the above-described two ideals (of axiomatization and formalization) conjoined together. More often than not, we come to know, by informal proofs, things in everyday mathematics which indeed cannot be proved within some formal system because of Gödel’s result. Nevertheless, we can always construct richer formal systems which will prove these truths (even trivially, we can always add such truths as axioms, since we hold them to be true, persuaded by our informal mathematical reasoning). Now, whether the Gödelian results can be brought to bear on the everyday informal mathematics as well, that is, whether there are true but absolutely unprovable mathematical facts, is still an open foundational question in mathematics, very interesting, but far from settled.

—-

*With the extra conditions that these theories are consistent, rich enough to capture arithmetic and that there exist effective finite procedures to decide whether a given sentence is one of the axioms of the theory and whether a given array of sentences is a valid proof.

Further readings

Books:

Smith, P. (2013), An Introduction to Gödel’s Theorems, Cambridge University Press, 2^nd edition [An excellent, accessible, and very friendly introduction to the two famous Incompleteness results, along with elements from computability theory. It takes the reader by the hand and gently leads them deeply to the world of the Gödel’s two famous results, only presupposing some knowledge of elementary logic. Highly recommended!]
Boolos, G., J. Burgess and R. Jeffrey (2007), Computability and Logic, Cambridge University Press, 5^th [A classic introduction to computability issues and the Gödel’s theorems, covering similar ground as the previous, but a bit more demanding at some times]
Franzén, T. (2005), Gödel’s Theorem: An Incomplete Guide to Its Use and Abuse, A K Peters/CRC Press [Also a very accessible introduction, less technical than the previous two, but valuable for its serious discussions of the many alleged ‘philosophical’ implications of the theorems].

Encyclopedia entries:

Raatikainen, Panu, “Gödel’s Incompleteness Theorems” in The Stanford Encyclopedia of Philosophy (Spring 2015 Edition), Edward N. Zalta (ed.)
Kennedy, Juliette, “Kurt Gödel“, The Stanford Encyclopedia of Philosophy (Winter 2015 Edition), Edward N. Zalta (ed.)

For a beautifully lucid discussion about the relation between formal and informal mathematics and the extent to which Gödel’s first theorem can be brought to bear on the everyday informal mathematical practice, see: