Gödel's incompleteness theorems Study Guide

📖 Core Concepts Formal system – A set of symbols, formation rules, and inference rules together with an axiom set. Effective (recursive) axiomatization – Theorems can be listed by a computer program; the set of theorems is recursively enumerable. Consistency – No statement and its negation are both provable. Syntactic completeness – For every sentence $\varphi$, either $\varphi$ or $\neg\varphi$ is provable. Semantic completeness – Every semantically true sentence is provable (holds for first‑order logic, not for arithmetic). Gödel sentence – A self‑referential sentence $G$ that asserts “$G$ is not provable in the system”. If the system is consistent, $G$ is true but unprovable. Rosser sentence – A variant of the Gödel sentence that needs only consistency (not ω‑consistency). Consistency statement $Cons(F)$ – Formal formula saying “no number codes a proof of $0=1$ from the axioms of $F$”. Undecidable / independent – Neither provable nor refutable in the given formal system. Diagonal lemma – Guarantees a formula $p$ with $p \leftrightarrow F(\ulcorner p\urcorner)$ for any $F(x)$. Provability predicate $\mathrm{Bew}(y)$ – “$y$ is the Gödel number of a provable sentence”. --- 📌 Must Remember First Incompleteness Theorem: Any consistent, effectively generated system capable of elementary arithmetic is syntactically incomplete. Gödel sentence $G$ is true (in the standard model) but unprovable if the system is consistent. Rosser’s improvement: Only plain consistency (no ω‑consistency) is needed. Second Incompleteness Theorem: Such a system cannot prove its own consistency $Cons(F)$. $Cons(F)$ is expressed as “¬∃n $\mathrm{Bew}F(\ulcorner 0=1\urcorner, n)$”. Key examples of independence: Continuum Hypothesis (CH) – independent of ZF + AC. Axiom of Choice (AC) – independent of ZF. Paris–Harrington, Goodstein’s theorem, Kruskal’s tree theorem – independent of PA. Halting problem undecidability ⇒ a complete, consistent arithmetic system cannot exist. --- 🔄 Key Processes Gödel‑sentence construction Assign a Gödel number to every symbol, formula, and proof. Define the provability predicate $\mathrm{Bew}(y)$. Apply the Diagonal Lemma to the formula $F(x) \equiv \neg\mathrm{Bew}(x)$. Obtain a sentence $G$ such that $G \leftrightarrow \neg\mathrm{Bew}(\ulcorner G\urcorner)$. Rosser sentence (weakening the hypothesis) Define two provability predicates: “there is a proof of $\varphi$ earlier than any proof of $\neg\varphi$”. Diagonalize to get $R$ that says “if $R$ has a proof, there is a shorter proof of $\neg R$”. Consistency alone forces $R$ to be undecidable. Second‑theorem proof sketch Inside the system, formulate $Cons(F)$ as “no number codes a proof of $0=1$”. Use the first theorem to obtain a Gödel sentence $G$ asserting “$G$ is unprovable”. Show that $Cons(F)$ would imply $G$ is provable, contradicting $G$’s unprovability. Conclude $Cons(F)$ cannot be proved in $F$. --- 🔍 Key Comparisons Syntactic vs. Semantic completeness – Syntactic: every sentence is provable or refutable. Semantic: every logically true sentence is provable (holds for first‑order logic, not for arithmetic). Consistency vs. ω‑consistency – Consistency: no $\varphi$ and $\neg\varphi$ provable. ω‑consistency: stronger; prevents proving “∃x P(x)” while proving each individual “¬P(n)”. Rosser eliminates the need for ω‑consistency. Gödel sentence vs. Rosser sentence – Gödel needs ω‑consistency; Rosser works with plain consistency. Undecidable (proof‑theoretic) vs. Undecidable (computability) – Proof‑theoretic: not provable nor refutable in a theory. Computability: no algorithm decides the truth of every instance (e.g., halting problem). --- ⚠️ Common Misunderstandings “Gödel sentence is false” – It is true in the standard model; only unprovable. “All consistent systems are incomplete” – Incompleteness requires the system to be effectively axiomatized and to express enough arithmetic (e.g., multiplication). “Second theorem means the system is inconsistent” – It only says the system cannot prove its own consistency. “Undecidable = unsolvable algorithmically” – In logic, “undecidable” means independent of the given axioms, not that no algorithm exists to decide the statement in general. --- 🧠 Mental Models / Intuition Liar‑paradox analogy: Replace “false” with “unprovable”. The sentence “This sentence is unprovable” can’t be settled inside the system, just as “This sentence is false” can’t be settled in ordinary language. Library catalog: A catalog that tries to list all books including itself leads to a paradox; Gödel numbering is the catalog, the Gödel sentence is the entry that says “I am not listed”. Provability predicate as a “truth‑telling robot” that can comment on its own statements; diagonalization forces the robot to utter a claim about its own inability to speak that claim. --- 🚩 Exceptions & Edge Cases Presburger arithmetic (addition only) lacks multiplication → escapes Gödel’s incompleteness. Robinson arithmetic (Q) – minimal system sufficient for the theorems. Primitive recursive arithmetic (PRA) can prove consistency of very weak fragments but cannot prove $Cons(\text{PA})$. Systems that are not effectively axiomatized (e.g., true arithmetic) are not covered by the theorems. --- 📍 When to Use Which Gödel‑sentence proof – When you have a theory known to be ω‑consistent (or you want the classic proof). Rosser‑sentence proof – When you only know the theory is consistent; use Rosser’s trick to avoid ω‑consistency. Second‑incompleteness argument – To show a theory (e.g., PA, ZF) cannot internally certify its own consistency; apply whenever the theory satisfies the Hilbert–Bernays derivability conditions. Undecidability examples – Cite CH, AC, Paris–Harrington, Goodstein when asked for natural independent statements. --- 👀 Patterns to Recognize Self‑reference via diagonalization → sentences that talk about their own Gödel numbers. “No proof of 0=1” pattern in consistency statements. Encoding: every syntactic object (formula, proof) → natural number; look for statements of the form “∃n $\mathrm{Bew}(n)$”. “If provable then …” → derivability conditions (Löb’s theorem style) often appear in second‑theorem sketches. --- 🗂️ Exam Traps Distractor: “Gödel’s theorem shows that arithmetic is contradictory.” – Wrong; it shows incompleteness, not inconsistency. Distractor: “If a system is consistent it must be complete.” – Opposite of the first theorem. Distractor: “The halting problem proves the first incompleteness theorem.” – Related but distinct; the halting problem shows undecidability of a different kind. Distractor: “Semantic completeness implies syntactic completeness.” – Only the reverse holds for first‑order logic; arithmetic is not semantically complete. Distractor: “Presburger arithmetic is incomplete because it lacks multiplication.” – Actually it is complete (decidable) precisely because it lacks enough arithmetic. ---