Is this equivalence of the compactness theorem true?

Question

In my mathematical logic class the teacher asked us the following question: ¿is the compactness theorem equivalent to: let $\Gamma$ be a set of propositional formulas, and let $\sigma$ be a formula. If $\Gamma \models \sigma$ then there is finite ${ \Gamma }_{ 0 }\subseteq \Gamma $ such that ${ \Gamma }_{ 0 }\models \sigma $?, I have tried several times but can't find the correct way to prove it, I appreciate any help.

The statement my teacher gave was: $\Gamma$ is finitely satisfiable if and only if $\Gamma$ is satisfiable.

Answer 1

Yes, the two statements below are equivalent. Let us prove it. Let $\Gamma$ be a set of formulas.

1. For any formula $\sigma$, $\Gamma \models \sigma$ if and only if there is a finite $\Gamma_0 \subseteq \Gamma $ such that $\Gamma_0 \models \sigma $;
2. $\Gamma$ is finitely satisfiable if and only if $\Gamma$ is satisfiable.

Proof that 1. implies 2. We suppose that 1. holds and we prove that the equivalence in 2. holds

• $\Rightarrow$: Assume that $\Gamma$ is finitely satisfiable. Then, for every finite $\Gamma_0 \subseteq \Gamma$, there is a structure that satisfies $\Gamma_0$. Let $\sigma$ be a contradiction formula (i.e. a formula that is not satisfied by any structure, for instance $\bot$ or $\alpha \land \lnot \alpha$). So, for every finite $\Gamma_0 \subseteq \Gamma$, there is a structure that satisfies $\Gamma_0$ and not $\sigma$, i.e. $\Gamma_0 \not\models \sigma$. By 1. (direction left-to-right), $\Gamma \not\models \sigma$ and hence there exists a structure that satisfies $\Gamma$ but not $ \sigma$. In particular, $\Gamma$ is satisfiable.

• $\Leftarrow$: Assume that $\Gamma$ is satisfiable. Then, there exists a structure that satisfies all the formulas in $\Gamma$. In particular, it satisfies every finite $\Gamma_0 \subseteq \Gamma$. Therefore, $\Gamma$ is finitely satisfiable. (Note that here we do not use the hypothesis that 1. holds)

Proof that 2. implies 1. We suppose that 2. holds and we prove that the equivalence in 1. holds. Let $\sigma$ be a formula.

• $\Rightarrow$: Assume that $\Gamma \models \sigma$. Then, every structure that satisfies $\Gamma$ does not satisfies $\lnot \sigma$, i.e. $\Gamma \cup \{\lnot \sigma\}$ is unsatisfiable. By 2. (direction left-to-right), $\Gamma \cup \{\lnot \sigma\}$ is not finitely satisfiable, hence there is a finite $\Gamma_0 \cup \{\lnot \sigma\} \subseteq \Gamma \cup \{\lnot \sigma\}$ that is unsatisfiable. Therefore, for some finite $\Gamma_0 \cup \{\lnot \sigma\} \subseteq \Gamma \cup \{\lnot \sigma\}$, every structure that satisfies $\Gamma_0$ satisfies $\sigma$ too, i.e. $\Gamma_0 \models \sigma$.

• $\Leftarrow$: Assume that $\Gamma_0 \models \sigma$ for some finite $\Gamma_0 \subseteq \Gamma$. Then, every structure that satisfies $\Gamma$ in particular satisfies $\Gamma_0$ and hence $\sigma$, since $\Gamma_0 \models \sigma$. Therefore, $\Gamma \models \sigma$. (Note that here we do not use the hypothesis that 2. holds)

---

In both statements 1. and 2., the interesting part is the left-to right direction. Indeed, in statement 1., the right-to-left direction is trivial and holds independently from the hypothesis that 2. holds. And similarly, in statement 2., the right-to-left direction is trivial and holds independently from the hypothesis that 1. holds.

The left-to-right direction of the compactness theorem (in both formulations 1. and 2.) has the following logical form, at the meta-level: $$\tag{*}\forall \exists \implies \exists \forall$$ What do I mean? Take the left-to-right direction of statement 2. By making explicit the meaning of "satisfiable" and "finitely satisfiable", it says: if for all finite subsets of $\Gamma$ there exists a structure that satisfies it, then there is a structure that satisfies all formulas in $\Gamma$. This is surprinsing, because $\Gamma$ can be an infinite set of formulas and so compactness theorem says that we can somehow transfer a property (satisfiability) from finite to infinite.

Usually, implications of the form $(*)$ does not hold. Think of natural numbers: the fact that for every natural number $n$ there is a natural number greater than $n$, does not imply that there is a natural number greater all other natural numbers. Compactness theorem says that when we talk about satisfiability of sets of formulas, the implication $(*)$ holds, even when the set $\Gamma$ of formulas is infinite.

The other direction (the right-to-left one) is of the form $$\exists \forall \implies \forall \exists$$ which is obvious and indeed it corresponds to the less interesting part of statements 1. and 2.

Answer 2

The version of Compactness you're given is: Γ is finitely satisfiable if and only if Γ is satisfiable. Then:

=> Let Γ be a set of propositional formulas, and let σ be any formula s.t. $Γ \models σ$. Consider the set $Σ = Γ \cup \{¬σ\}$. Clearly this is unsatisfiable, as any model of Γ must satisfy σ, so Γ and ¬σ cannot be satisfied simultaneously. It follows from our assumption that Σ is not finitely satisfiable, so $\exists Σ_0 \subseteq Σ$ finite which is unsatisfiable. Let $Γ_0 = Σ_0 \setminus \{¬σ\}$. We can then see that $Γ_0 \models σ$.

<= Clearly if Γ is satisfiable then it is finitely satisfiable. Suppose that Γ is finitely satisfiable. If Γ is empty then we're done. Otherwise, assume for a contradiction that Γ is not satisfiable, and let $σ \in Γ$. Since Γ is unsatisfiable, we see that $ Γ \setminus \{σ\} \models ¬σ$. By our assumption, we have that $\exists Γ_0 \subseteq Γ \setminus \{σ\}$ finite, such that $Γ_0 \models ¬σ$. We then have that $Γ_0 \cup \{σ\}$ is a finite subset of Γ, which is unsatisfiable. This contradicts our hypothesis, so Γ must be satisfiable.