Understanding the method for the proof of compactness theorem

Question

In Sets, Logic, Computation, the compactness theorem is stated as follows:

For any sentences $\Gamma$ and $A$, the following holds:

1. $\Gamma\models A$ iff there is some finite $\Gamma_0\subseteq\Gamma$ s.t. $\Gamma_0\models A$.

2. $\Gamma$ is satisfiable iff for any finite $\Gamma_0\subseteq\Gamma$, $\Gamma_0$ is satisfiable.

I have an impression that properties 1 and 2 are logically equivalent, i.e. property 1 holds iff property 2 holds.

However, it appears to me that the textbook proves properties 1 and 2 separately. The proof for property 2 presented in the textbook does not assume property 1 holds. I also found a proof for property 1 without assuming property 2 holds.

So since properties 1 and 2 can be proved independently, it trivially follows that property 1 holds iff property 2 holds? It is analogous to saying that the natural number $n=2$ is both (i) $n$ is even and (ii) $n$ is prime, and hence (i) iff (ii).

Is there an alternative proof for "property 1 iff property 2" that does not involve proving 1 and 2 independently?

Answer 1

Indeed, statements 1. and 2. are equivalent. Each one can be easily derived from the other.

Note that in the book you cited, there is no proof at all of 1. (I guess the authors think it is obvious to derive 1. from 2.), but there are two independent proofs of 2.

The fact that 2. implies 1. is already proved and discussed here, using purely semantic methods (actually, it proves that 2. implies the left-to-right implication in 1., which is the hard task. The right-to-left implication of 1. is trivial, as it immediately follows from the definition of logical consequence $\models$).

Now, let us prove that 1. implies 2. Since 2. is an equivalence statement, we must show the left-to-right and right-to-left implications in 2.

• Left-to-right: Let $\Gamma$ be a satisfiable set of formulas. This means there is a structure $\mathcal{M}$ such that: $\mathcal{M} \models B$ for every $B \in \Gamma$. Hence, $\mathcal{M} \models \Gamma_0$ for every finite $\Gamma_0 \subseteq \Gamma$. Therefore, every finite $\Gamma_0 \subseteq \Gamma$ is satisfiable.

• Right-to-left (proof by contraposition): Let $\Gamma$ be an unsatisfiable set of formulas. Then, $\Gamma \neq \emptyset$ (otherwise satisfiability of $\Gamma$ would be vacuously true) and so there is $A \in \Gamma$. Thus, $\Gamma \models \lnot A$ (vacuously, since there is no model of $\Gamma$). By 1. (left-to-right), there is a finite $\Gamma_0 \subseteq \Gamma$ such that $\Gamma_0 \models \lnot A$, that is, $\mathcal{M} \models \lnot A$ for every model $\mathcal{M}$ of $\Gamma_0$. Hence, $\mathcal{M} \not\models A$ for every model $\mathcal{M}$ of $\Gamma_0$. Therefore, the finite set of formulas $\Gamma_0 \cup \{A\} \subseteq \Gamma$ is unsatisfiable. $\qquad\square$

Some remarks:

• The left-to-right implication in 2. is trivial, it immediately follows from the definition of satisfiability, without appealing to 1.

• The proof of the right-to-left implication in 2. is not trivial and it crucially exploits 1. (left-to-right).

• The above proof that 1. implies 2. is completely semantic, and in particular, it never uses the completeness theorem.