Gödel's incompleteness theorems - First Incompleteness Theorem

Gödel's First Incompleteness Theorem Introduction Gödel's First Incompleteness Theorem is one of the most significant results in mathematical logic. It fundamentally limits what any formal mathematical system can accomplish. The theorem shows that sufficiently powerful formal systems cannot prove all true statements within their own language—there will always be true statements that remain undecidable within the system. This discovery overturned the naive hope that mathematics could be made completely formalized and self-contained. What the Theorem Says The First Incompleteness Theorem states that any consistent, effectively generated formal system capable of representing basic arithmetic is syntactically incomplete. In other words: If a formal system can perform elementary arithmetic operations (addition, multiplication, etc.), and If the system is consistent (meaning it never proves both a statement and its negation), Then there must exist statements in the system's language that can neither be proved nor disproved within that system. This is a profound limitation: completeness (the ability to prove or disprove every statement) is impossible for such systems. The Gödel Sentence: A Statement About Itself The core of Gödel's proof involves constructing a very special statement, known as the Gödel sentence. This sentence has a remarkable property: it asserts something about itself. Specifically, the Gödel sentence $p$ essentially says: "$p$ is not provable in this system." Here's the crucial insight: because the system is consistent, the Gödel sentence must actually be true but unprovable. Here's why: Suppose $p$ were provable. Then the system would prove a false statement (since $p$ says it's unprovable). This would mean the system is inconsistent—contradiction. So $p$ cannot be provable. But then what $p$ asserts is actually true: it correctly claims it's unprovable. However, the system cannot prove this true statement. This illustrates a key distinction: truth is not the same as provability within a formal system. How This Differs from the Liar Paradox You might worry that this seems like the liar paradox: "This sentence is false." The Gödel sentence is similar but avoids the paradox by replacing "false" with "unprovable": Liar paradox: "This sentence is false." (creates a genuine contradiction) Gödel sentence: "This sentence is unprovable." (no contradiction—it's simply true but unprovable) The Gödel sentence can be true without creating inconsistency. The system simply cannot prove it. This is the escape from paradox: we're not claiming the statement is false, just unprovable within the formal framework. Arithmetization: Encoding Proofs as Numbers To make the Gödel sentence work, Gödel used a brilliant technique called arithmetization of syntax. The idea is to convert logical and syntactic properties into arithmetic properties. Encoding Proofs: Any proof in a formal system is essentially a finite sequence of statements, where each statement either follows from the inference rules or is an axiom. Gödel showed how to assign each proof a natural number called its Gödel number. Different proofs get different numbers, and the numbering scheme is computable (you can algorithmically determine what proof any Gödel number represents). The Provability Predicate: Once proofs have Gödel numbers, we can define a formula $\mathrm{Bew}(y)$ (read as "provable") that expresses: "There exists a proof (with some Gödel number) that proves the statement with Gödel number $y$." Crucially, $\mathrm{Bew}(y)$ is itself an arithmetical formula—it makes a statement about natural numbers. The key relationship is: If a statement $p$ is actually provable in the system, then the formula $\mathrm{Bew}(G(p))$ can itself be proven, where $G(p)$ is the Gödel number of $p$. Diagonalization: Creating the Self-Referential Statement With a provability predicate in place, Gödel uses a technique called diagonalization to create the self-referential Gödel sentence. The Diagonal Lemma: For any sufficiently strong formal system and any formula $F(x)$ with one free variable, there exists a statement $p$ such that the system can prove: $$p \leftrightarrow F(G(p))$$ In words: $p$ is logically equivalent to the formula $F$ applied to $p$'s own Gödel number. Applying This to Provability: By setting $F(x) = \neg\mathrm{Bew}(x)$ (the negation of provability), we obtain a statement $p$ such that: $$p \leftrightarrow \neg\mathrm{Bew}(G(p))$$ This means $p$ is logically equivalent to "the statement with Gödel number $G(p)$ is unprovable." But $G(p)$ is exactly the Gödel number of $p$ itself. So $p$ effectively asserts its own unprovability. Consistency and ω-Consistency The incompleteness argument relies on an important distinction between two concepts: Consistency: A system is consistent if it never proves both a statement and its negation. This is the minimal requirement for a system to make sense. ω-Consistency (omega-consistency): A system is ω-consistent if, whenever a formula like $F(n)$ can be proved for every natural number $n$, the system cannot prove the statement "there exists an $n$ such that $\neg F(n)$." In simpler terms: the system doesn't prove universal facts about all numbers while simultaneously proving exceptions. For the Gödel sentence $p$: If the system is merely consistent, we can show that $\neg p$ is not provable (otherwise we'd have both $p$ and $\neg p$ provable). If the system is ω-consistent (which is stronger), we can show that $p$ itself is also not provable, making $p$ genuinely undecidable. Gödel's original proof required ω-consistency. Later, Rosser improved the argument to require only plain consistency—a significant refinement that makes the theorem even more powerful. The Proof in Overview Here's how the proof sketch fits together: Setup: We start with a formal system capable of elementary arithmetic. Encode: We encode proofs as Gödel numbers and define the provability predicate $\mathrm{Bew}(y)$. Construct: Using the Diagonal Lemma, we construct a sentence $p$ that asserts its own unprovability. Derive the Undecidable Sentence: Under consistency (or ω-consistency), the sentence $p$ cannot be proved or disproved within the system. Therefore, the system is incomplete. The result is that no consistent formal system capable of expressing basic arithmetic can prove all truths expressible in its own language. <extrainfo> Alternative Approaches to Incompleteness Berry Paradox Approach Boolos (1989) and independently Saul Kripke discovered an alternative proof of incompleteness using Berry's paradox rather than Gödel's diagonalization. Berry's paradox involves the phrase "the smallest number that cannot be described in fewer than twenty words." This approach constructs true but unprovable sentences using a similar self-reference mechanism but starting from complexity instead of provability. Chaitin's Incompleteness Theorem Gregory Chaitin developed another independent proof using Kolmogorov complexity—a measure of how many bits of information are needed to describe a number. Chaitin showed that sufficiently complex numbers cannot be proven to be complex within the system, yielding independent sentences through information-theoretic reasoning. Recursively Inseparable Sets Smoryński (1977) demonstrated that the existence of recursively inseparable sets (pairs of disjoint sets that cannot be separated by a recursive set) can be used to establish incompleteness. This reveals incompleteness as a consequence of computability theory. These alternative proofs show that incompleteness is not merely an artifact of Gödel's construction method—it's a deep phenomenon appearing in multiple mathematical contexts. </extrainfo> Summary Gödel's First Incompleteness Theorem reveals a fundamental limitation of formal systems: no consistent formal system capable of elementary arithmetic can be complete. Through arithmetization of syntax and self-referential reasoning, Gödel constructed a sentence that is true but unprovable, demonstrating that mathematical truth transcends what any single formal system can prove. This revolutionary result has profound implications for the philosophy of mathematics and the nature of mathematical knowledge itself.