! Disclaimer: Ironically these notes are incomplete.
Overview
Kurt Godel proved that any formulation of logic that can represent arithmetic can encode statements and proofs as numbers, through Godel Numbering. With this Godel encoded a derivation of the Liars Paradox - ‘This problem is not provable in T’ - proving that not all mathematical statements are Decidable.
This proved that there is no solution to the Decision Problem (Entscheidungsproblem)
Takeways
- There is a gap between truth and proof. Truth and provability are not the same thing.
- If we want mathematics to be consistent, we must accept that it is incomplete and undecidable.
- Any Formal System that is powerful enough to describe basic arithmetic is either incomplete or inconsistent.
- Gödel’s Second Incompleteness Theorem demonstrates that a consistent formal system cannot even prove its own consistency, let alone its completeness (? | salt).
Remember
- Consistency ensures no contradiction.
- Decidability ensures that there is a finite, mechanical way to determine the truth or falsehood of any statement within the system.
- Completeness guarantees that every true statement has a proof or counterexample within the system.
- Completeness guarantees consistency, but consistency does not guarantee completeness. (?)
Gödel’s First Incompleteness Theorem
States that any Formal System that is powerful enough to describe basic arithmetic is either incomplete or inconsistent.
Incomplete: There exist statements that cannot be proved or disproved.
Gödel’s Second Incompleteness Theorem
States that any formal which is:
- Consistent
- Sufficiently powerful to describe basic arithmetic (such as Peano arithmetic)
- Formalizable within itself (able to express its own statements)
Inconsistency
Cannot prove its own consistency.
- A formal system T cannot demonstrate its own lack of contradictions.
Miscellaneous Associations & Jottings
Resources
https://en.wikipedia.org/wiki/Complete_theory
https://www.youtube.com/watch?v=I4pQbo5MQOs
https://www.youtube.com/watch?v=O4ndIDcDSGc
https://www.youtube.com/watch?v=HeQX2HjkcNo
https://www.youtube.com/watch?v=9GjCIU_ZHIo
Diagonal Argument: https://www.youtube.com/watch?v=dwNxVpbEVcc
Fact-Check Notes
- Conflation (needs correction): Line 10 states “This proved that there is no solution to the Decision Problem (Entscheidungsproblem)” as a direct consequence of Gödel’s Incompleteness Theorems (1931). This conflates two distinct results. Gödel’s theorems concern completeness: whether every true statement in a sufficiently powerful, consistent formal system is provable within that system (answer: no). The unsolvability of the Entscheidungsproblem — whether a general algorithm can decide the validity of an arbitrary first-order logic statement — was proved independently by Alonzo Church and Alan Turing in 1936, five years later, using different techniques (λ-definability and Turing machines respectively). The two results are historically and technically related (both use diagonalization/self-reference, both stem from the same Hilbert program), but incompleteness does not itself entail undecidability of the Entscheidungsproblem — they answer different questions (provability-within-a-system vs. existence-of-a-decision-algorithm). Notably, the vault’s own Decision Problem (Entscheidungsproblem) file correctly attributes the undecidability result to Turing (not Gödel), so this file is internally inconsistent with it.
- The “Completeness guarantees consistency, but consistency does not guarantee completeness” claim (already flagged ”(?)” by the author) is imprecise: strictly, an inconsistent theory is trivially “complete” (it proves every statement and its negation), so completeness alone does not guarantee consistency. Gödel’s actual result is the reverse pairing under the usual assumptions: for consistent, sufficiently strong, recursively axiomatized systems, completeness fails (First theorem) and self-provable consistency fails (Second theorem).
- All links verified as relevant: Kurt Godel, Liars Paradox, Decision Problem (Entscheidungsproblem), Decidablity, Formal System.