A worked propositional example
Parent: soundness-and-completeness
The smallest place to see both directions at once. Propositional logic is sound and complete (Post, 1921): ⊢ φ ⟺ φ is a tautology. Its semantics = truth tables (a model = a truth assignment; ⊨ φ means true under every assignment).
Take φ = P → (Q → P).
Semantics (⊨). The truth table is T in every row, so φ is a tautology — ⊨ φ:
P | Q | Q→P | P→(Q→P) |
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | F | T |
| F | F | T | T |
Syntax (⊢). A proof: assume P; assume Q; then P (reuse the first assumption); so Q→P; discharge P to get P→(Q→P). Hence ⊢ φ.
Both hold — exactly as soundness + completeness promise.
The soundness contrast. P → Q is not a tautology (false at P=T, Q=F), so ⊭ (P→Q). By soundness (⊢ ⟹ ⊨, contrapositive ⊭ ⟹ ⊬) it is therefore not provable — you can never prove a falsehood. (And by completeness, every tautology you can write down does have a proof.)