Gödel's Incompleteness Theorems: The Limits of Formal Systems

Michael BrenndoerferUpdated May 25, 202613 min read

Kurt Gödel's 1931 results on undecidability in arithmetic and why a consistent, sufficiently strong, effectively axiomatized theory cannot prove its own consistency.

PhilosophyAll chapters
Reading tools Notes & comments
Notes & comments
Part 8 of 12Logic, Language, and Interpretation
Chapter 96The limits of formal proof › When a Proof Has a Number
Reading the full chapter · 8 sections · 13 min8 sections · 13 min

All 8 sections · 13 min read

The limits of formal proof › When a Proof Has a NumberFull chapter · Sections in this chapter1 / 8 ↓

When a Proof Has a Number

Imagine two people reading the same purported proof. The first sees a list of formulas and checks whether each line is an axiom or follows from earlier lines. The second has a numerical code for the same list. Given that code, the second reader can perform essentially the same checks through arithmetic on the numbers. Once the encoding has been fixed, “this list is a proof” and “this number satisfies a certain arithmetical relation” can express the same test.

Kurt Gödel's 1931 paper on undecidable propositions turns that observation against a formal system's claim to completeness. If arithmetic can express a test for proof, a sufficiently strong theory of arithmetic can formulate claims about its own proofs. Gödel shows how to construct a sentence that speaks about its own status under that test. He also uses the relationship between proof and arithmetic to examine whether the same theory can prove that its rules never yield a contradiction.

These are two different results. The first concerns the existence of sentences left undecided by a theory. The second concerns a particular statement expressing the theory's consistency. Both are conditional theorems about formal systems. Keeping the conditions in view helps us see why the proofs work.

The System and Its Proofs

A formal theory specifies a language, axioms, and rules of inference. A proof consists of finitely many steps certified by those rules. One can distinguish this from mathematical truth by considering an ordinary example. A theory might let us express a conjecture about primes without providing a proof or a refutation. The conjecture still has a truth condition in the natural numbers. The relation “has a proof in this theory” asks what follows from a specified collection of axioms by the allowed steps.

For Gödel's construction, the axioms and proof rules must be available through effective procedures. This does not require a computer program that decides whether an arbitrary statement has a proof. It requires a mechanical way to check a proposed derivation, with enough information included in its code to verify why each step is licensed. For example, if the axioms are given by an effective enumeration, the proof can include a record of where any axiom it uses appears in that enumeration. A correct record can be checked even when there is no general procedure for recognizing that a formula will never appear.

Two further conditions matter. The theory has to be strong enough to carry out the arithmetical reasoning used in the construction. Its axioms also need to meet a consistency assumption appropriate to the theorem. The familiar modern examples include effectively axiomatized consistent extensions of Peano arithmetic. Gödel gives his original results for a specified system P and classes of additional axioms, as set out in §2 of the original paper. This is why his title names Principia Mathematica and related systems without making the argument depend on the printed pages of Principia.

Consistency and Completeness

A theory is consistent if it does not prove a contradiction. In the classical theories under discussion, this means it cannot prove both a sentence and its negation. It is complete in the sense at issue if, for each sentence in its language, it proves that sentence or proves its negation. The same distinction explains how a consistent theory can fail to decide a sentence.

Arithmetizing Formulas and Proofs

Gödel assigns numbers to primitive signs and codes sequences using powers of successive primes. As a small illustration, assign the fictional signs A and B the codes 1 and 2. Using the same general style of encoding, the sequence A, B, A could receive the number 2¹ × 3² × 5¹. The unique factorization of the number lets us recover the sequence. Gödel's actual coding maps a richer formal language and, in further steps, whole sequences of formulas. The principle is that a structural test on a written expression can become a test on natural numbers.

One relation concerns substitution. Given the code of a formula with a free variable and the code needed to identify that variable, we can compute the code of the formula obtained by putting a numeral in its place. Another relation concerns proofs. It holds of two numbers p and q when p codes a correct proof whose last formula has code q. Gödel analyzes the requisite computations in §2, before Proposition VI. This detail matters because a suggestive resemblance to arithmetic would be too weak. The needed operations have to be available in sufficiently definite arithmetical form.

A proof checker handles a proposed code p and a proposed conclusion q. To say that q has a proof is then to say that some p passes the test. Arithmetic can express this existential assertion without providing a procedure to settle it in all cases. Trying candidate proof codes in an enumeration will eventually find a proof if there is one. It will run indefinitely if there is none. This difference between verifying evidence and deciding whether evidence exists helps explain why the encoding does not by itself make the theory complete.

Constructing the Sentence

How can a sentence make a claim about its own proof code? Suppose we begin with a formula that says of a number that it is not the code of a theorem. We cannot simply add the words “this sentence” to the formula. Gödel exploits the substitution operation to achieve the effect inside arithmetic. The method, often explained today through the diagonal lemma, produces a sentence G whose equivalence to “there is no proof of the sentence with G's code” is itself provable in the theory.

A useful distinction is between a number and the numeral for it. The number is the code assigned to a formula. The numeral is a term in the formal language designating that number. When the construction feeds a numeral into a formula, it can refer to the code of an expression without using that expression as a literal part of itself. In particular, the finished sentence can be finite. The construction works through a relation between numerical descriptions. It does not require the sentence to reprint itself anywhere.

We can now ask what would happen if the theory proved G. There would be an actual finite derivation, with a particular code p. Verification of the concrete derivation yields an arithmetical certificate that p is a proof of G, one the theory can recognize. But proving G also gives a proof of the claim that there is no such code. The theory would thus prove conflicting assertions. Consistency suffices to exclude a proof of G in this construction.

What if the theory proves the negation of G? This is the other half of the argument and has a different logical shape. Given consistency, there is no actual proof of G. For each particular numeral, the theory can check that the numeral does not code a proof of G. A proof of the negation of G would nevertheless establish that some number is a proof code. It would thereby assert that an instance of a condition exists while denying that each particular numeral satisfies it. That combination can occur in a merely consistent theory. To rule it out by this route, Gödel appeals to ω-consistency. This is the stronger assumption in his original Proposition VI.

This point is easy to miss if the construction is told only as a story about the liar paradox. G says something specific about provability under a fixed set of rules. The proof treats the positive and negative cases separately, and the historical version needs different resources for them. J. Barkley Rosser's 1936 paper changes the construction and obtains undecidability from ordinary consistency, with the other relevant hypotheses on the theory. The common modern statement is stronger than the 1931 argument for Gödel's original G.

Expressing the Theory's Consistency

The second result, Proposition XI in §4, uses the fact that proof has been arithmetized. In a familiar modern presentation, write Con(T) for the arithmetical sentence saying there is no code of a T-proof of a fixed contradiction such as 0 = 1. By the rules of the classical theory and the arithmetic it includes, such a derivation would undermine its consistency. Con(T) is thus a concrete sentence about numbers through which the theory can express its own consistency.

The external argument for nonprovability gives a route to the second theorem. In suitable systems, enough of the reasoning can be carried out within the theory to prove that Con(T) implies G. Now suppose the theory proved Con(T). It could combine the consistency statement with that implication and prove G. The first part of the previous argument shows that this is impossible if the theory is consistent. For this inference it is enough to use the part excluding a proof of G, so the result does not need the original ω-consistency assumption simply carried over from the full first theorem.

The phrase “enough of the reasoning” names an important requirement. The formula for provability has to behave correctly inside the theory, for example when proofs are combined along its inference rules. Gödel proves a corresponding internal implication for his own definitions. Modern presentations often spell out derivability conditions that support the argument. Simply writing a sentence labeled “this system is consistent” does not make it the consistency formula involved in the theorem.

The result puts a condition on attempts to certify a theory from within itself. It leaves room for proofs of consistency from different assumptions, in a stronger or otherwise appropriate theory. In such a proof one can ask what warrants the stronger assumptions. The second theorem applies again when deliberation turns to the stronger theory's own consistency, provided it meets the requisite conditions.

Truth, Proof, and New Axioms

What do we mean when we say Gödel's sentence is true? For the Gödel sentence constructed with the standard arithmetical proof predicate, its interpretation concerns ordinary natural numbers. In those numbers, a code satisfying the proof test would correspond to a genuine finite proof. Under the stated consistency hypothesis, there is no such code. That is why the sentence can be said to hold in the intended interpretation even though its truth cannot be established by a proof in the theory it describes. The reasoning about the theory is taking place in a mathematical setting where we can use the hypothesis of its consistency.

There is still something one can do with an undecidable sentence. If neither it nor its negation follows from a consistent theory, one can adjoin either as a new axiom while preserving ordinary consistency. This follows because a contradiction derived after adding one side would yield a refutation of that side in the original theory. If the original axioms are true in the natural numbers, adding the sentence true there preserves that feature. Adding its false negation can preserve formal consistency while losing truth in the intended interpretation. In that case, models satisfying the extended theory do not give the usual natural numbers with their usual arithmetic as the interpretation.

The nonstandard interpretation makes the point concrete. Suppose a model satisfies the arithmetical assertion that some number codes a proof of G. For every ordinary natural number, the theory can verify that its numeral is not a proof code. In any model satisfying the assertion, a witness therefore has to be an element other than the ones designated by those standard numerals. The model treats that element as a number. The external proof checker does not thereby receive a finite proof whose code it could write down. This is a place where the gap between a model of a theory and its intended interpretation makes an observable difference to the argument.

The same distinction helps with the status of an assumption made outside the system. An argument that starts by assuming T is consistent can establish something about T without turning into a T-proof. To get a T-proof we would have to show that T admits every step, including whatever assumption the argument invokes. This is exactly what comes under scrutiny when the premise is Con(T). Citing the external result as a proof inside the theory would make the transition that the second theorem puts in question.

Adding a new axiom also changes what it is to have a proof. A proof code that formerly did not certify anything might now do so because a line has become an axiom. If the extended system still meets the hypotheses, Gödel's or Rosser's method applies to it with its own proof predicate. This gives a different question from whether the old sentence now has a proof. The newly constructed sentence refers to the enlarged collection of available proofs.

It is also possible to specify a complete consistent theory by taking all sentences true of the natural numbers. The condition that fails for that theory is effective axiomatizability. If its axioms could be enumerated mechanically, it would be an effective complete theory of arithmetic satisfying the relevant strength requirements, and the incompleteness result would apply. The choices of what to express and how to check proofs therefore matter just as much as consistency. A bare claim about what can or cannot be known leaves out those distinctions.

Seeing the Boundaries of the Result

The completeness theorem for first-order logic concerns a different use of the word complete. If a sentence follows from premises in every interpretation satisfying them, the logical calculus can derive it from those premises. An arithmetic theory can still be incomplete because its axioms do not determine each sentence across all such interpretations. A sentence recognized as true in the standard natural numbers may fail in another model of the same arithmetic theory. Keeping the class of models in view makes room for both the completeness of the logic and incompleteness of an arithmetic theory formulated with it.

The two results also enter foundational debates in different ways. The first tells us why an effective and sufficiently expressive derivation system can leave questions unanswered. The second challenges a proposal that such rules could certify their own reliability by deriving their own ordinary consistency statement. Questions about which mathematical objects there are, or whether every piece of human reasoning can be modeled by a given procedure, require premises beyond these theorems. The mathematical work here is to specify an obstacle precisely enough that one can tell when it applies.

A good way to follow that work is to keep three statements separate. There is the sentence inside the theory. There is the assertion that a particular numerical code passes the test for being its proof. There is also the argument we make about whether any such proof exists. Gödel's construction makes these statements interact. Its strength comes from making that interaction explicit through arithmetic.

Reading the Paper

Read the German original or J. R. Meyer's English translation beginning with the informal sketch in §1. Proposition VI in §2 gives the original undecidability result and its ω-consistency hypothesis. Proposition XI in §4 is the consistency result. Rosser's published abstract identifies the strengthening of Gödel's Proposition VI that uses ordinary consistency.

Join the discussionAsk a question or share what you learned.

Comments

Add to the conversation

A question, a correction, or an example from your own work.

No comments yet. Be the first to share your thoughts!

A different angle
All writing
Philosophy

Derrida's Of Grammatology: Writing, Trace, and the Supplement

Jacques Derrida's 1967 inquiry into the relation between speech and writing, with close readings of Saussure, Lévi-Strauss, and Rousseau.

13 min read
Philosophy

Derrida's Writing and Difference: Structure, Sign, and Play

Jacques Derrida's 1967 collection of essays, with a close reading of “Structure, Sign, and Play” and companion essays on Foucault, Freud, and Levinas.

13 min read
Philosophy

Kripke's Naming and Necessity: Rigid Designation and Essentialism

Saul Kripke’s lectures on how names refer, why some necessary truths are discovered empirically, and what people and things could have been.

13 min read

About the author

Reference

Citation details

Cite or share this article.

BIBTEXAcademic
@misc{brenndoerfer2026gdel, author = {Michael Brenndoerfer}, title = {Gödel's Incompleteness Theorems: The Limits of Formal Systems}, year = {2026}, url = {https://mbrenndoerfer.com/writing/godel-incompleteness-theorems-formal-systems-limits-guide}, organization = {mbrenndoerfer.com}, note = {Accessed: 2026-11-19} }
APAAcademic
Michael Brenndoerfer (2026). Gödel's Incompleteness Theorems: The Limits of Formal Systems. Retrieved from https://mbrenndoerfer.com/writing/godel-incompleteness-theorems-formal-systems-limits-guide
MLAAcademic
Michael Brenndoerfer. "Gödel's Incompleteness Theorems: The Limits of Formal Systems." 2026. Web. November 19, 2026. <https://mbrenndoerfer.com/writing/godel-incompleteness-theorems-formal-systems-limits-guide>.
CHICAGOAcademic
Michael Brenndoerfer. "Gödel's Incompleteness Theorems: The Limits of Formal Systems." Accessed November 19, 2026. https://mbrenndoerfer.com/writing/godel-incompleteness-theorems-formal-systems-limits-guide.
HARVARDAcademic
Michael Brenndoerfer (2026) 'Gödel's Incompleteness Theorems: The Limits of Formal Systems'. Available at: https://mbrenndoerfer.com/writing/godel-incompleteness-theorems-formal-systems-limits-guide (Accessed: November 19, 2026).
SimpleBasic
Michael Brenndoerfer (2026). Gödel's Incompleteness Theorems: The Limits of Formal Systems. https://mbrenndoerfer.com/writing/godel-incompleteness-theorems-formal-systems-limits-guide
Newsletter

Stay up to date

Get new articles, book updates, and notes on AI and technology.

Unsubscribe at any time. Privacy policy