The compactness theorem

What is used from the previous lessons

This lesson works almost entirely in semantics, and uses the following from it. A valuation is a function $v\colon V \to \{0, 1\}$ on the set $V$ of the variables $v_1, v_2, v_3, \ldots$, which extends in a unique way to all formulas; a valuation satisfies a set $\Gamma$ of formulas, $v \models \Gamma$, if it gives the value $1$ to each of them, and $\Gamma$ is satisfiable if some valuation satisfies it and unsatisfiable otherwise. All this is in the lesson on the semantics of propositional logic, together with the central instrument of this lesson, the coincidence lemma: if two valuations agree on the variables of $\varphi$, which form a finite set $V(\varphi)$, they give $\varphi$ the same value.

From the lesson on semantic consequence and equivalence, the following are used: the definition of $\Gamma \models \varphi$ (every valuation that satisfies $\Gamma$ satisfies $\varphi$), its structural properties, in particular monotonicity (if $\Gamma \subseteq \Delta$ and $\Gamma \models \varphi$, then $\Delta \models \varphi$) and the fifth (an unsatisfiable set has every formula as a consequence), and the consequence and unsatisfiability theorem: $\Gamma \models \varphi$ if and only if $\Gamma \cup \{\neg\varphi\}$ is unsatisfiable. From the lesson on the generalized De Morgan and distributive laws, the value lemma is used: $\bigwedge_{i=1}^{n} \varphi_i$ has the value $1$ if and only if all its terms have the value $1$, and $\bigvee_{i=1}^{n} \varphi_i$, if and only if some term has the value $1$. Finally, $\top := (v_1 \rightarrow v_1)$ is a tautology and $\bot := \neg\top$, a contradiction.

On the side of deduction, the lesson on formal deductive systems proved monotonicity (Mon: if $\Gamma \subseteq \Delta$ and $\Gamma \vdash \varphi$, then $\Delta \vdash \varphi$) and finiteness (Fin: if $\Gamma \vdash \varphi$, some finite subset $\Gamma_0$ of $\Gamma$ is such that $\Gamma_0 \vdash \varphi$), and the lesson on the four deduction techniques checked that both hold in the course system (the schemas A1, A2 and A3, modus ponens and the replacement of double negation, RDN), to which the symbol $\vdash$ refers from now on. Finally, the lesson on soundness and completeness proved the soundness theorem ($\Gamma \vdash \varphi$ implies $\Gamma \models \varphi$, for every $\Gamma$) and completeness for finite sets of premises: if $\{\gamma_1, \ldots, \gamma_k\} \models \varphi$, then $\{\gamma_1, \ldots, \gamma_k\} \vdash \varphi$.