Propositional Logic - Main Theorem

TheoremSoundness and Completeness Theorem

Let $\Gamma$ be a set of propositional formulas and $\phi$ be a propositional formula. Then $\Gamma$ semantically entails $\phi$ (written $\Gamma \models \phi$ ) if and only if $\Gamma$ syntactically proves $\phi$ (written $\Gamma \vdash \phi$ ) in any standard proof system for propositional logic.

In symbols: $\Gamma \vdash \phi$ if and only if $\Gamma \models \phi$ .

This fundamental theorem has two parts:

Soundness (left-to-right): If $\Gamma \vdash \phi$ , then $\Gamma \models \phi$ . Every formula provable from $\Gamma$ is indeed a logical consequence of $\Gamma$ . The proof system doesn't prove false statements.

Completeness (right-to-left): If $\Gamma \models \phi$ , then $\Gamma \vdash \phi$ . Every logical consequence of $\Gamma$ is provable from $\Gamma$ . The proof system is powerful enough to prove all true semantic relationships.

Remark

The completeness direction is the deeper result, first proved by Gödel in 1929 for first-order logic (which includes propositional logic as a special case). For propositional logic, the proof is considerably simpler than for first-order logic.

The theorem establishes the equivalence of two fundamentally different notions:

Semantic consequence ( $\models$ ): defined via truth assignments and truth tables
Syntactic provability ( $\vdash$ ): defined via formal manipulation of symbols according to proof rules

ExampleApplication

Consider $\Gamma = \{p \to q, q \to r\}$ and $\phi = p \to r$ .

Semantically: We can verify with truth tables that whenever both $p \to q$ and $q \to r$ are true, $p \to r$ must also be true. Thus $\Gamma \models \phi$ .

Syntactically: We can construct a formal proof:

$p \to q$ (premise)
$q \to r$ (premise)
Assume $p$
From 1 and 3, derive $q$ (modus ponens)
From 2 and 4, derive $r$ (modus ponens)
Conclude $p \to r$ (conditional proof)

Therefore $\Gamma \vdash \phi$ . The theorem guarantees these two approaches always yield the same result.

This theorem is the cornerstone of propositional logic, assuring us that semantic truth and formal provability are two sides of the same coin. It justifies using proof systems as reliable methods for establishing logical truth.

Remark

While propositional logic enjoys completeness, this property does not extend to all logical systems. Gödel's incompleteness theorems show that sufficiently strong systems (like arithmetic) cannot be both complete and consistent, making the completeness of propositional logic all the more remarkable.