2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What is the definition of "satisfiable"? What is "F"? You may want to add a bit more context for that? $\endgroup$ – Jack Oct 14 at 20:38
  • 4
    $\begingroup$ 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. $\endgroup$ – egreg Oct 14 at 21:01
  • 3
    $\begingroup$ @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). $\endgroup$ – Noah Schweber Oct 14 at 21:10
  • 1
    $\begingroup$ @HennoBrandsma That example doesn't work - the two sentences are jointly satisfiable (e.g. the linear order with one element). $\endgroup$ – Noah Schweber Oct 14 at 21:16
  • 1
    $\begingroup$ @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$.) $\endgroup$ – Noah Schweber Oct 14 at 21:19
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Pippen Oct 18 at 1:16
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber Oct 18 at 2:01
  • $\begingroup$ @Pippen I've added a sketch of one correct proof of compactness in the propositional case. $\endgroup$ – Noah Schweber Oct 18 at 2:36
  • $\begingroup$ 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. $\endgroup$ – Pippen Oct 19 at 3:10
  • $\begingroup$ @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). $\endgroup$ – Noah Schweber Oct 19 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.