# My Proof of the Compactness Theorem

The Compactness Theorem states: $$F$$ is satisfiable $$\iff$$ every finite subset of $$F$$ is satisfiable.

$$\Rightarrow$$: is trivial.

$$\Leftarrow$$: We assume every finite subset of $$F$$ is satisfiable, i.e. no finite subset of $$F$$ is unsatisfiable. Now we assume by the way of contradiction that $$F$$ is unsatisfiable, i.e. at least one formula in $$F$$ has to be a falsum. But this formula would be a finite subset of $$F$$ which contradicts the fact that by assumption no finite subset of $$F$$ is unsatisfiable. Therefore $$F$$ must be satisfiable. Done.

Why is this simple version wrong for I only find pretty sophisticated proofs of the compactness theorem.

• What is the definition of "satisfiable"? What is "F"? You may want to add a bit more context for that? – Jack Oct 14 at 20:38
• The compactness theorem says that $F$ is satisfiable if and only if every finite subset of $F$ is satisfiable. The argument you use is wrong anyway. – egreg Oct 14 at 21:01
• @Jack "Satisfiable" is the standard technical term in logic - it's fine to use it in a logic question without defining it (similarly to how there's no problem using "scheme" without definition in algebraic geometry questions). – Noah Schweber Oct 14 at 21:10
• @HennoBrandsma That example doesn't work - the two sentences are jointly satisfiable (e.g. the linear order with one element). – Noah Schweber Oct 14 at 21:16
• @HennoBrandsma Still doesn't work: take $\le$ to hold between all pairs. (Even in linear orders it doesn't work, since any linear order with a least element satisfies both sentences because we can take $m=n$ in $\phi_2$.) – Noah Schweber Oct 14 at 21:19

As far as texts go, I recommend Kaye or chapters $$9$$-$$10$$ and $$12$$-$$13$$ of Boolos/Burgess/Jeffrey.

Ignoring the misstatement of the theorem in the first place ("subset" should be "finite subset" per egreg's comment), your mistake is implicit in the following sentence:

Now we assume by the way of contradiction that F is unsatisfiable, i.e. at least one formula in F has to be a falsum.

That "i.e." is false - unsatisfiability of $$F$$ doesn't mean that some specific sentence in $$F$$ is unsatisfiable, but rather that the sentences of $$F$$ can't all be true at once.

For example, consider $$F=\{c=d, c\not=d\}.$$ Each individual sentence is satisfiable, but the whole set $$F$$ is clearly unsatisfiable. (I'm assuming here the context is first-order logic; if you're looking at propositional logic, consider $$F=\{p,\neg p\}$$ instead.)

So in general a set of sentences could be unsatisfiable for a complicated reason. What you're trying to show is that unsatisfiability can't be too complicated: while we can't find a single culprit sentence in general, if $$F$$ is unsatisfiable then there is some finite subset of $$F$$ which is already unsatisfiable. In propositional logic this is already nontrivial, and in first-order logic it's genuinely hard.

Now how does the proof go?

Well, for both propositional and first-order logic, there are multiple different proofs of the compactness theorem. One option in the propositional setting is topological, the key step being Tychonoff's theorem; that's the one I'll outline here.

It's worth noting that this approach has a couple major drawbacks: it does not easily generalize to first-order logic, and it also has significant technical overhead. However, personally I've gradually come to view the finickiness of the topological argument as a positive: understanding precisely why it doesn't generalize gives a lot of insight into how both propositional and first-order logic work, and the additional overhead material is both worth learning on its own and a source of motivation for the study of nonclassical propositional logics and (for me at least) Stone duality.

Suppose I have a finitely satisfiable set $$S$$ of sentences in the propositional language $$\{p_i:i\in I\}$$ (that is, the propositional language built out of the sentence letters $$p_i$$ for $$i\in I$$). Let $$Val$$ be the set of all valuations in this language (that is, all maps from $$\{p_i:i\in I\}$$ to $$\{0,1\}$$, thinking of $$0$$ as false and $$1$$ as true); we want to show that there is some $$f\in Val$$ which makes $$S$$ true.

$$Val$$ can be thought of as the Cartesian product of $$I$$-many copies of $$\{0,1\}$$; as such, it has a natural topology, namely the product topology coming from the discrete topology on each of those sets. It's not hard now to show that in this topology, each propositional sentence $$\sigma$$ picks out a clopen set - that is, for every propositional sentence $$\sigma$$, the set of $$f\in Val$$ which make $$\sigma$$ true is both open and closed in this topology on $$Val$$; basically, just use the fact that Boolean combinations of clopen sets are clopen.

This tells us the following:

We can think of our set $$S$$ of sentences as being a set of clopen subsets of $$Val$$, and the finite satisfiability of $$S$$ says exactly that any intersection of finitely many of these clopen sets is nonempty.

But this topology on $$Val$$ was the product of compact topologies (every finite space is trivially compact), hence by Tychonoff's theorem is itself compact. In a compact space, any collection of closed sets with the finite intersection property (= any intersection of finitely many of them is nonempty) has nonempty intersection. Applying this to the set of clopen subsets corresponding to $$S$$ gives a(t least one) valuation $$f$$ which makes all of $$S$$ true at once.

• Thx Noah, I got it. Can u try to explain how the <= direction of this proof (in propositional logic) is done or at least explain the idea? Also: is there any book or link of math. logic for beginners that still covers the likes of compactness theorem & co. I am not new to logic, I know truth tables and stuff, first order logic and so on, but I have a hard time to understand math. logic for it seems one steep step further. can somebody recommend a book or video lecture (I'd even buy it)? – Pippen Oct 18 at 1:16
• @Pippen I recommend Kaye's book. But this is a genuinely complicated subject. There are several proofs of the compactness of propositional logic, and they're each a bit sophisticated, and the compactness of first-order logic is even more deep. – Noah Schweber Oct 18 at 2:01
• @Pippen I've added a sketch of one correct proof of compactness in the propositional case. – Noah Schweber Oct 18 at 2:36
• What's your take on this: builds.openlogicproject.org/open-logic-complete.pdf ... seems to me the most complete book on logic plus it's kind of easy to understand. – Pippen Oct 19 at 3:10
• @Pippen I'm not familiar with it so I can't vouch for its quality, but it certainly looks cool. I also recommend the section of Boolos/Burgess/Jeffrey on basic first-order logic - specifically, chapters 9-10 and 12-13 (chapter 11 is about computability theory, and can be skipped in this context) - for learning this material; it's what I used, and I don't know why I forgot about it when recommending Kaye's book (not that I don't also recommend Kaye, it's just that BBJ). – Noah Schweber Oct 19 at 19:07