# Is this equivalence of the compactness theorem true?

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.

• That's usually how the compactness theorem is stated; how is your teacher phrasing the compactness theorem? Nov 18, 2020 at 4:07
• @NoahSchweber I would guess: if $\Gamma$ is finitely satisfiable, then $\Gamma$ is satisfiable. But yes Kira 1998, you should edit the question to clarify the statement of the compactness theorem you're working from. Nov 18, 2020 at 4:12
• Done, already edit the question. Nov 18, 2020 at 4:25
• For one direction, use $\sigma = \bot.$ For the other direction, use the fact that $\Gamma\models\sigma$ means $\Gamma\cup\{\lnot \sigma\}$ is unsatisfiable. Nov 18, 2020 at 4:45
• If it is equivalent to the compactness theorem, which is true, then it is also true. If it is not true, it is not equivalent to the compactness theorem. Nov 18, 2020 at 20:02

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.

• The first bullet point of your proof doesn't make any sense to me. I think something got confused there. Nov 18, 2020 at 13:27
• @AlexKruckman - Thank you for your comment. What is unclear exactly in my proof? Nov 18, 2020 at 14:19
• You have $\sigma$ valid and $\Gamma_0$ satisfiable, and then you conclude $\Gamma_0\not\models \sigma$. Nov 18, 2020 at 14:24
• @Taroccoesbrocco do you agree with what Alex says ? Nov 18, 2020 at 16:36
• @AlexKruckman - Yes, you're right. Thank you for your remark. I should stop posting answers when I'm working, I lose track of what I'm doing and I write an abstract nonsense. Now I fixed it. Nov 18, 2020 at 19:54

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.

• +1. For the second direction, it's a bit cleaner to take $\sigma$ to be $\top$ (or some tautology), rather than removing an element from $\Gamma$. Nov 18, 2020 at 13:21