502 – Propositional logic (4)

September 14, 2009

11. Completeness

We now want to show that whenever {S\models A,} then also {S\vdash A.} Combined with the soundness Theorem 22, this shows that the notions of provable and true coincide for propositional logic, just as they did for the tree system. The examples above should hint at how flexible and useful this result actually is. This will be even more evident for first order (predicate) logic.

Theorem 26 (Completeness) For any theory {S} and any formula {A,} if {S\models A,} then {S\vdash A.}

Read the rest of this entry »