Compactness Theorem/Proof using Gödel's Completeness Theorem

From ProofWiki
Jump to navigation Jump to search


Let $\LL$ be the language of predicate logic.

Let $T$ be a set of $\LL$-sentences.

Then $T$ is satisfiable if and only if $T$ is finitely satisfiable.


By definition, $T$ is finitely satisfiable means that every finite subset of $T$ is satisfiable.

Because the direction:

$T$ satisfiable implies $T$ finitely satisfiable

is trivial, the proof below justifies the converse:

$T$ finitely satisfiable implies $T$ satisfiable.

This proof is by contraposition.

The idea is to exploit the finiteness of proofs and the relation between satisfiability and deducibility to show that if $T$ is not satisfiable, then it must have a finite subset which can be used to prove to a contradiction.

Suppose $T$ is not satisfiable.

Since $T$ has no models, it vacuously follows that $T \models \phi \wedge \neg \phi$ for some sentence $\phi$.

By Gödel's Completeness Theorem, this implies that $\phi \wedge \neg \phi$ is deducible from $T$.

But any deduction from $T$ involves only finitely many sentences from $T$.

This means that there is a finite subset $\Delta$ of $T$ such that $\phi \wedge \neg \phi$ is deducible from $\Delta$.

By Soundness of First-Order Logic, this means that $\Delta \models \phi \wedge \neg \phi$.

Thus $\Delta$ is not satisfiable.

By the Rule of Transposition, $\Delta$ is satisfiable implies $T$ is satisfiable.


Boolean Prime Ideal Theorem

This proof depends on the Boolean Prime Ideal Theorem (BPI), by way of Gödel's Completeness Theorem.

Although not as strong as the Axiom of Choice, the BPI is similarly independent of the Zermelo-Fraenkel axioms.

As such, mathematicians are generally convinced of its truth and believe that it should be generally accepted.