# Proving one compactness theorem from the other

I have 2 versions of the compactness theorem;

Compactness Theorem $1$ - Suppose that $S$ is a set of propositional terms. Then $S$ is satisfiable if and only if every finite subset $S' \subseteq$ $S$ is satisfiable.

Compactness Theorem $2$ - Suppose that $S$ is a set of terms and that $t$ is a term. Then $S \vDash t$ iff there is a finite set $S' \subseteq S$ such that $S' \vDash t$.

Now, I'm trying to figure out how you can get from one version to the other, but I'm not sure how to formally argue it. I can understand it intuitively, but I don't know how to formulate the argument at all. How can I relate the set $S$ being satisfiable to logical consequences $S \vDash t$ etc.

Any help would be appreciated!

• What does it mean "$S \models t$" where $t$ is a term and $S$ is a set of terms? May 17, 2018 at 21:37
• It means that $t$ is a logical consequence of $S$. So whenever there is a valuation which makes all the terms in $S$ true, then $t$ is true. May 17, 2018 at 21:40
• @Taroccoesbrocco The OP uses "term" to mean what is usually called a propositional formula. May 18, 2018 at 1:00

The key insight is that $S\vDash t$ iff $S\cup\{\neg t\}$ is not satisfiable. Indeed, $S\vDash t$ means that if a valuation makes every element of $S$ true, it makes $t$ true, which means exactly that there is no valuation which makes every element of $S$ true and also makes $\neg t$ true.
So, you can use this idea to relate the two versions of the theorem. For instance, to prove Theorem 2 from Theorem 1, just apply Theorem 2 to the set $S\cup\{\neg t\}$. Try it and see what you can get!
Proving Theorem 1 from Theorem 2 is a little trickier, since you will need to make some specific choice of $t$. Since we have $S\vDash t$ iff $S\cup\{\neg t\}$ is satisfiable, and we want to talk about satisfiability of $S$ itself, we want to somehow choose $t$ such that adding $\neg t$ to $S$ does not change whether it is satisfiable. This simplest way to do this is to just choose $t$ such that $\neg t$ is a tautology. That way, $S$ is satisfiable iff $S\cup\{\neg t\}$ is satisfiable.
• I’ve managed to prove Theorem $2$ from Theorem $1$, but I’m not too sure how to start the other one? May 18, 2018 at 9:25
Recall that "$S\models t$" means that every model of $S$ also models $t$. But then, every model of $S$ is also a model for each of its finite subsets. So then it is apparent that if there is a (finite) subset of $S$ whose every model models $t$, then the models of $S$ also model $t$. The compactness comes at play in the inverse - if for no finite subject of $S$ do we have $S' \models t$, then $S'\cup \{\neg t\}$ is always satisfiable, and so is then $S\cup \{\neg t\}$ (by compactness), so $S$ doesn't model $t$ either. Of course, this proof only works when $S$ is satisfiable. Otherwise, taking the empty set as $S'$ should suffice.