Compactness for propositional logic
Every logical consequence of an infinite collection of propositional sentences is actually a consequence of finitely many of them.
Let us imagine that we are committed to a certain propositional theory Γ, a set of sentences in propositional logic, perhaps even infinitely many sentences, and we are observing logical consequences of our theory. A sentence φ is a logical consequence of the theory Γ, a situation we denote by Γ ⊨ φ, if every model of Γ is also a model of φ.
If the theory Γ does indeed have infinitely many sentences in it, then such an entailment Γ ⊨ φ is infinitary in nature, for what it means is that if a model satisfies all infinitely many sentences in Γ, then it will also satisfy φ. But did we really need all the infinitely many axioms in Γ in order to conclude φ as a consequence? Perhaps we might have hoped to reduce this infinitary entailment to a finitary cause in Γ?
Indeed, that is exactly right, and this is precisely the compactness property of propositional logic, the remarkable feature that every logical entailment reduces ultimately to a finitary entailment. Specifically, a logic is compact if whenever a sentence φ is a logical consequence of a theory Γ, then there is a finite fragment of that theory that suffices for the entailment.
And propositional logic is compact. Let us explain why.
Keep reading with a 7-day free trial
Subscribe to Infinitely More to keep reading this post and get 7 days of free access to the full post archives.