This course has given you two ways to show an argument is good. One is about truth: truth tables and worlds, with no row or world making the premises true and the conclusion false. The other is about rules: a proof, line by line, from Proofs with Identity and everything before it. Do they always agree? This capstone answers that, drawing also on Counterexample Worlds.
Key idea
$\Gamma \vdash \varphi$ ("provable") means there is a proof of $\varphi$ from the premises $\Gamma$. $\Gamma \models \varphi$ ("valid") means every row or world that makes $\Gamma$ true makes $\varphi$ true. A system is sound if everything provable is valid, and complete if everything valid is provable. Our rules are both.
Why it works
Soundness holds because every rule is truth-preserving: each was checked to be a valid form (or an equivalence), and CP, IP and the quantifier rules, with their restrictions, never let a falsehood follow from truths. Completeness is harder and deeper. For statement logic it means the eighteen rules plus CP and IP can reach every tautological consequence. For predicate logic it was proved by Kurt Gödel in his 1929 doctoral thesis: every valid argument of first-order logic has a proof.
| Says | Direction | |
|---|---|---|
| Soundness | If $\Gamma \vdash \varphi$ then $\Gamma \models \varphi$ | proof → truth |
| Completeness | If $\Gamma \models \varphi$ then $\Gamma \vdash \varphi$ | truth → proof |
What each one gives you
- Soundness: a correct proof guarantees validity, so you never need a truth table to back it up. And if an argument has a counterexample, no proof of it exists, however long you search.
- Completeness: if an argument is valid, a proof is out there. If you cannot find one, keep looking, or check validity another way.
- Together: $\vdash$ and $\models$ pick out exactly the same arguments.
Worked examples
Worked example: Use soundness
Someone shows you a "proof" of $p \to q$, $q$, so $p$. What follows?
- The argument is invalid (the row $p$ F, $q$ T).
- Our system is sound, so no correct proof of it exists.
Answer: The "proof" breaks a rule somewhere.
Worked example: Use completeness
A truth table shows $(p \lor q) \land \neg p$ implies $q$. Must a proof exist?
- The argument is valid.
- The system is complete.
Answer: Yes (DS after Simp does it).
Worked example: Changing the rules
If we added the rule "from $p \to q$ and $q$, infer $p$", what would break?
- That rule is affirming the consequent, which is invalid.
- It could prove an invalid argument.
Answer: Soundness. (Removing a rule, by contrast, can only threaten completeness.)
Common mistake
Swapping the two. Soundness: the rules never prove an invalid argument (provable implies valid). Completeness: the rules can prove every valid one (valid implies provable). A memory aid: soundness protects you from proving falsehoods; completeness promises you are not missing anything.
One limit worth knowing: truth tables decide validity in statement logic mechanically, but for predicate logic there is no general mechanical test that always says "invalid" when it should (Church and Turing, 1936). Completeness guarantees a proof for every valid argument, not a quick way to tell when none exists.