Soundness and Completeness

Mathematical Logic · Axiom Academy

LESSON Soundness and Completeness Explore the fundamental metatheorems that establish the deep connection between provability and truth in mathematical logic systems. 1. Syntax vs. Semantics: Two Perspectives Think of syntax as the game of logic—manipulating symbols according to rules—and semantics as the meaning behind those symbols. The notation ⊢ φ means "φ is provable from axioms," while ⊨ φ means "φ is valid (true in all interpretations)." 2. Soundness: No False Theorems Soundness guarantees that our proof system is reliable : if we can prove a formula, then it must be valid (true in all interpretations). In other words, we cannot prove false statements . This is the minimal requirement for any logical system—without soundness, our proofs would be worthless! 3. Proving Soundness: Induction on Proofs The proof of soundness uses structural induction on the length of proofs. The strategy is to show: For example, modus ponens says: from φ and φ → ψ, derive ψ. If both φ and φ → ψ are valid (true in all models), then ψ must also be valid. Why? If φ is true and "if φ then ψ" is true, then ψ must be true! 4. Completeness: All Truths Are Provable Completeness is the converse of soundness and is far less obvious! It states that our proof system is powerful : if a formula is valid (true in all interpretations), then there exists a formal proof of it. In other words, every truth is reachable through formal proof . 5. Gödel's Completeness Theorem for First-Order Logic

This is the written version of the interactive lesson above. See the full Mathematical Logic course.