This essay is based on Chapter 1 of A.W. Moore’s book on Gödel’s theorem [1].
1 The Announcement and Impact of Gödel’s Theorem
On September 7, 1930, at a conference in Königsberg on the “Epistemology of the Exact Sciences,” a 24-year-old Kurt Gödel presented the findings that would become his famous theorem. The result was formally published the following year under the title “On Formally Undecidable Propositions of Principia Mathematica and Related Systems I.”
Gödel had intended to publish a sequel. In the first paper, he proved his first theorem in detail and sketched a proof of the second. The sequel was meant to generalise the first theorem and provide a detailed proof of the second. As it turned out, the sequel was never needed; his results were accepted so quickly and understood so well that a follow-up publication was unnecessary. The mathematician Roger Penrose called it “the most important theorem in mathematical logic of all time.”
The theorem showed that any effort to create a definitive and complete set of rules for arithmetic is, in essence, impossible. It challenged prevailing beliefs about the nature of mathematics at a fundamental level and sparked philosophical debates.
2 Core Statement of the Theorem
The following informal statements capture the essence of the theorem:
- “No axiomatization can determine the whole truth and nothing but the truth concerning arithmetic.”
- “Any axiomatization of arithmetic must either be incomplete, that is, fail to capture some arithmetical truths, or be unsound, that is, capture some arithmetical falsehoods.”
- “No finite stock of basic principles and rules enables us to prove every arithmetical truth unless it also enables us to prove some arithmetical falsehoods.”
The term “finite” is crucial. If omitted, one could define each of the infinite arithmetic truths as a distinct basic principle, which would allow each truth to be proven in a single step. Equally vital is the “unless” provision, because an absurd rule permitting the derivation of any statement would prove all truths, but at the unacceptable cost of simultaneously proving all falsehoods.
3 Deconstructing the Theorem: Key Concepts
To fully grasp the theorem, one must first understand its core components: arithmetic, axiomatization and proof.
Arithmetic
- Definition: The study of the natural numbers (0, 1, 2, 3,…) and the algorithmic operations that apply to them, such as addition and multiplication.
- Algorithmic Operations: These are purely mechanical procedures that can be followed step-by-step by a computer, do not rely on randomness, and are guaranteed to produce a result in a finite number of steps.
Gödel’s theorem holds even when the scope of arithmetic is restricted to the study of natural numbers using only addition and multiplication. All other algorithmic operations can be expressed using these two operations, yet this process is more complex than it first appears. For example, while one might assume exponentiation (n^m) is simply n multiplied by itself m times, the concept of “occurring m times” requires a rigorous definition that is surprisingly difficult to achieve. This difficulty is doubly remarkable: it highlights both the power of such limited mathematical resources and the minimal requirements needed for Gödel’s theorem to apply.
Axiomatization
- Definition: A finite collection of basic principles and rules that form the foundation of a formal system.
- “Basic” Principles: A principle or rule is considered “basic” if it is accepted without being derived from anything else within the system. Its status as “basic” is not compromised, even if it is questioned or shown to be incorrect.
For example, a basic principle for multiplication could be stated as: given any natural number n, n multiplied by 0 is 0. An axiomatization also includes rules that are not specific to any one subject but apply universally. These are often said to belong to logic. For instance, a rule of logic allows us to derive a specific instance (like “7 multiplied by 0 is 0”) from a general principle (like the one above).
More generally, in any axiomatization, two distinct categories of principles are recognised:
- Subject-Specific Principles: These are the rules unique to a particular area of study, such as the axioms that define arithmetic.
- Logical Principles: These are the rules that govern valid reasoning itself and apply universally.
The game of chess provides a helpful analogy. The rules specifying how each piece moves are specific stipulations of the game, comparable to the axioms of arithmetic. In contrast, the reasoning used to determine, for example, that a king and a knight cannot checkmate a lone king is not a rule of chess. It is a principle of general logic applied to the game’s specific rules. This characterisation of logic as universally applicable is informal, and the exact demarcation line, as well as the placement of certain principles, remain subjects of ongoing debate.
Proof
- Definition: A proof of a statement, relative to a given axiomatization, is a derivation of that statement from the system’s basic principles using its basic rules.
A robust axiomatization of arithmetic, for instance, should provide the tools to prove both simple calculations (e.g., that 827 × 240 = 198,480) and more complex statements (e.g., that there are infinitely many prime numbers).Proof is relative to the specific set of axioms and rules chosen for a formal system (axiomatization). A statement’s provability or unprovability is never absolute. A statement provable under one axiomatization might be unprovable under another. For example, the Euclidean proof that there are an infinite number of primes is perfectly acceptable. However, a truly formal presentation would require explicitly stating the underlying logical rules and axioms. This essential relativity of proof is the key factor that introduces the central problem of the theorem, focusing on the discrepancy between formal provability and the abstract concept of truth.
4 The Core Dilemma: Truth vs. Formal Proof
Gödel’s theorem creates a schism between the concepts of truth within arithmetic and provability within any given formal axiomatic system. The theorem can be written informally: “Any axiomatization of arithmetic must either be incomplete, that is, fail to capture some arithmetical truths, or be unsound, that is, capture some arithmetical falsehoods.”
This statement implies that no single, finite system of axioms and rules can ever capture the entirety of arithmetical truth unless it also generates contradictions and falsehoods. Any consistent system we can construct will necessarily be incomplete, that is, unable to prove some true statements about numbers. This incompleteness creates a conceptual rift between what is true and what is formally demonstrable.
The following statements clarify the concepts of truth, falsehood, and conjecture.
Truths
- A familiar, simple statement: 827 x 240 = 198,480
- A more complex provable statement: “There are infinitely many primes.”
Falsehoods
- A statement that can be proven wrong by a counterexample, such as “Every natural number is the sum of three squares.” This statement is false because certain numbers, like 7, do not fit this rule.
Conjectures
- A statement whose status remains undetermined because neither a proof nor a counterexample has been found. Goldbach’s Conjecture serves as an illustration: “Every even number greater than 2 is the sum of two primes.”
For the sake of this initial analysis, we proceed with the philosophical assumption that every clear arithmetical statement is unproblematically either true or false. It is worth noting, however, that this assumption itself can be scrutinised. More importantly, the theorem can be stated and proven in a way that bypasses the concept of “truth” altogether. The core dilemma remains: any consistent, finite formal system is limited. This forces us to re-evaluate what it means for a mathematical statement to be true if we cannot demonstrate its truth within its own system. Unfortunately, this dilemma has given rise to numerous misunderstandings.
5 Common Misconceptions
Several prevalent misconceptions obscure the theorem’s precise meaning.
Misconception: Some truths are absolutely unprovable.
Gödel’s theorem does not imply this. A truth that is unprovable in one sound axiomatization may be provable in another (for instance, by being added as a new axiom). The fact that any single system is incomplete does not mean that some truths are beyond the reach of all possible systems. This is like a CCTV system where no single camera covers the entire site, but the combined cameras still do.
Misconception: The theorem applies to all subjects, including all of mathematics.
The theorem concerns explicitly arithmetic. There are other branches of mathematics, notably analysis (the study of real numbers), for which a complete and sound axiomatization exists. This is possible because the language of analysis can refer to specific natural numbers (e.g., 2+2=4), but it lacks the means to refer to the set of natural numbers as a whole. The analogy used is a language with names for individual places (“Mercury”, “Venus”) but no word for “planet.”
Misconception: Arithmetical statements can assert their own unprovability.
While this idea is often associated with the theorem, the text describes it as a misconception until the concept is rigorously and carefully defined. Without the necessary groundwork, one should adhere to the view that arithmetical statements assert things about numbers, not about their own provability.
Misconception: The theorem supports broad philosophical or metaphysical claims.
The theorem is frequently co-opted to support grand claims, such as justifying a belief in God or that “Man will never know the final secret of the universe” (Rudy Rucker). David Foster Wallace connected it to “the great postmodern uncertainty.” The text dismisses these, stating there is “simply no interesting connection between Gödel’s theorem and the ideas being canvassed in these claims.”
6 Conclusion
Gödel’s Incompleteness Theorem is probably the most significant achievement in mathematical logic of the 20th century. It irrevocably changed our understanding of both mathematics and philosophy. The core finding is that any formal axiomatic system about arithmetic must be either incomplete or unsound. This demonstrates a conceptual gap between truth and formal provability.
Gödel’s theorem defines the boundaries of formalisation, but it does not assert the existence of universally unprovable truths or apply to every area of mathematics. His work did not conclude a mathematical investigation. On the contrary, it compelled a deeper examination of arithmetic, axioms and proofs and offered a new path for understanding the nature of certainty and the complexity of natural numbers. The quest for truth persists. However, the idea that one finite set of rules could entirely encapsulate the truth of arithmetic is now recognised as impossible.
References
[1] Moore, A. W. 2022. Gödel’s Theorem: A Very Short Introduction. Oxford: Oxford University Press.