Proof Theory Summary

Mathematical Logic · Axiom Academy

Let's review how formal proofs work, the key inference rules that justify each step, different proof strategies, and the fundamental properties of soundness and completeness. Formal proof: A sequence of statements where each step follows from previous steps or axioms by applying valid inference rules Rigor over intuition: Unlike informal arguments, every step must be explicitly justified - no leaps or "it's obvious" Mechanical verification: A formal proof can be checked by a computer because rules are precisely defined Premises to conclusion: Start with given assumptions (premises) and apply rules step-by-step until reaching the desired conclusion Validity matters: A valid proof guarantees that if premises are true, the conclusion must be true - truth preservation is the core principle Modus Ponens (MP): From p → q and p , infer q . If the implication holds and premise is true, conclusion must be true Modus Tollens (MT): From p → q and ¬q , infer ¬p . If conclusion is false, premise must be false Hypothetical Syllogism (HS): From p → q and q → r , infer p → r . Chain implications together Disjunctive Syllogism (DS): From p ∨ q and ¬p , infer q . If one disjunct is false, the other must be true Many more rules: Addition, Simplification, Conjunction, Resolution - each captures a valid pattern of reasoning Introduction rules: Rules that allow you to introduce a new logical connective (e.g., if you have p and q, introduce p ∧ q )

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