I have a problem understanding the proof for the compactness theorem for propositional logic in my logic course.

The compactness theorem states that there is a model for an infinite set $S$ of propositional formulas, if and only if, there is a model for every finite subset of $S$.

The following (quite lengthy) sketch of the proof was given to us in class: The premise is that we have a model for each finite subset of $S$, so we need to construct from these models a model for the whole set $S$.

First we notice that for any (possibly infinite) set of formulas $S_n \subseteq S$ with $n$ propositional variables there are at max $2^{2^n}$ equivalent formulas with $n$ variables, which is finite. So for every finite equivalence class $E_n$ of $S_n$ there is a model $m_n$, which is also a model for the infinite $S_n$. Furthermore, $m_n$ is also a model for all sets $S_1 \subseteq S_2 \subseteq \cdots \subseteq S_{n-1}$.

Now, from all of the models $m_1, m_2, \ldots$ we derive a model $m$ for the whole set $S$. We start with an empty model $m=\{\}$. We then iterate over all the propositional variables $p_1, p_2, \ldots$ and assign a truth value to each and add them to $m$ as follows: We set $p_1 = \textrm{TRUE}$, if there are infinitely many sets $S_i$, whose model also assigns $\textrm{TRUE}$ to $p_1$. Now we delete all the sets $S_j$, in which $p_1 = \textrm{FALSE}$. Repeat for all $p_2, p_3, \ldots~$.

The proof goes on to proof that the so constructed model $m$ is in fact a model for $S$.

What I have problems with understanding is how we know that there are infinitely many models that assign some truth value to one of the variables. So, I don't find this proof convincing at all.

  • $\begingroup$ Thanks, you're right. I read the FAQ after posting the question. $\endgroup$
    – alexkelbo
    Dec 27, 2012 at 3:34

3 Answers 3


The argument is basically correct, but it could stand to be fleshed out a bit. For convenience I’ll write $\mathbf{T}$ and $\mathbf{F}$ instead of $\text{TRUE}$ and $\text{FALSE}$. I’ll also write $m(p_k)=\mathbf{T}$ to indicate that $p_k$ is true in the model $m$.

Let $S_n$ be the set of all formulas in $S$ containing at most the propositional variables $p_1,\dots,p_n$. There is a finite set $E_n\subseteq S_n$ such that every formula in $S_n$ is equivalent to one in $E_n$, so $S_n$ has a model $m_n$. Note that for any $n\in\Bbb Z^+$, each model $m_k$ with $k\ge n$ assigns $p_n$ a truth value.

Let $N_1=\Bbb Z^+$. Each $m_n$ with $n\in N_1$ assigns $p_1$ a truth value. Let $T_1=\{n\in N_1:m_n(p_1)=\mathbf{T}\}$. If $T_1$ is infinite, set $m(p_1)=\mathbf{T}$, and let $N_2=\{k\in T_1:k\ge 2\}$. Otherwise, set $m(p_1)=\mathbf{F}$, and let $N_2=\{k\in N_1\setminus T_1:k\ge 2\}$. Note that in both cases $N_2$ is infinite, $m_k(p_1)=m(p_1)$ for all $k\in N_2$, and $m_k(p_2)$ is defined for each $k\in N_2$.

Now repeat the process. Let $T_2=\{n\in N_2:m_n(p_2)=\mathbf{T}\}$. If $T_2$ is infinite, set $m(p_2)=\mathbf{T}$, and let $N_3=\{k\in T_2:k\ge 3\}$. Otherwise, set $m(p_2)=\mathbf{F}$, and let $N_3=\{k\in N_2\setminus T_2:k\ge 3\}$. In both cases $N_3$ is infinite, $m_k(p_2)=m(p_2)$ for each $k\in N_3$, and $m_k(p_3)$ is defined for each $k\in N_3$.

For the general step, given an infinite $N_n\subseteq\Bbb Z^+$ such that $m_k(p_n)$ is defined for each $k\in N_n$, let $T_n=\{k\in N_n:m_k(p_n)=\mathbf{T}\}$. If $T_n$ is infinite, set $m(p_n)=\mathbf{T}$, and let $$N_{n+1}=\{k\in T_n:k\ge n+1\}\;.$$ Otherwise, set $m(p_n)=\mathbf{F}$, and let $$N_{n+1}=\{k\in N_n\setminus T_n:k\ge n+1\}\;.$$ As before, in both cases $N_{n+1}$ is by construction infinite, $m_k(p_n)=m(p_n)$ for each $k\in N_{n+1}$, and $m_k(p_{n+1})$ is defined for each $k\in N_{n+1}$, so the recursive construction can proceed.

This construction defines a model $m$ that assigns a truth value to each $p_k$. Take any formula $\varphi$ in $S$; it belongs to some $S_n$. Pick any $k\in N_{n+1}$; then $m_k$ is a model for $S_n$ and hence for $\varphi$. Moreover, the construction ensures that $m_k(p_i)=m(p_i)$ for $i=1,\dots,n$, so $m$ is also a model for $S_n$ and hence for $\varphi$.

  • $\begingroup$ In your 3rd paragraph, how do you decide if $T_1$ is infinite? $\endgroup$
    – alexkelbo
    Dec 27, 2012 at 10:19
  • 1
    $\begingroup$ @alexraasch: You don’t. Either $T_1$ is infinite, or it’s finite, and if it’s finite, then $N_1\setminus T_1$ is infinite; that’s all that you need to know. This isn’t an effective procedure: there’s no general algorithm to determine which case holds. But one must, so the recursion goes through. $\endgroup$ Dec 27, 2012 at 14:32
  • $\begingroup$ Ok, I have to admit your proof is too hard for me to digest. I think the basic idea is to say that every formula $\phi$ has only finitely many propositional variables. Let $n$ be that number. Then $\phi$ belongs to $S_n$, which has a model. So there is a model for every $\phi$ in $S$. Therefore, $S$ has a model. $\endgroup$
    – alexkelbo
    Dec 29, 2012 at 18:09
  • 1
    $\begingroup$ @alexraasch: My proof is simply the one that you were given in class, but with more of the details filled in. What you’re calling the basic idea is how you show that $m$ is a model of all of $S$, but it’s not the basic idea of the proof as a whole. The really important part of the proof is the recursive construction of $m$, and the basic idea of that is that for each $n\in\Bbb N$ we can find an infinite set of $N_n\subseteq\Bbb N$ such that for all $k\in N_n$, the models $m_k$ assign the same truth value to all $p_i$ with $i<n$. $\endgroup$ Dec 29, 2012 at 18:17
  • $\begingroup$ I accepted your answer but I still don't get it. There are too many symbols to keep in my head at the same time. :) I'll keep trying. $\endgroup$
    – alexkelbo
    Dec 29, 2012 at 19:40

Either your construction is a bit off or I don't understand it. Does it not claim it constructs a model S' in the following setup: Let $S$ be any arbitrary set of propositional formulas, let $p$ be a fresh symbol not appearing in $S$, and let $S' = \{p\} \cup \{\lnot p \land \phi | \phi \in S\}$. I think if you apply your construction, you could get $S_1 = \{p\}$, then $m_1$ sets the $p$ to true, the rest of $S'$ is promptly thrown away (or "deleted"), every other variable can then safely be set to true, and $S'$ is satisfied by setting everything to true. Something is rotten here.

There are a lot of proofs online you can try examining. This proof is rather jargon free.

  • $\begingroup$ Your counterexample misses the "every finite subset has a model" part. $\endgroup$ Dec 27, 2012 at 4:34
  • $\begingroup$ Sorry, I can't access the page you linked, none of the images are loaded due to some authorization error. $\endgroup$
    – alexkelbo
    Dec 29, 2012 at 13:56

Isn't a simpler way to prove the compactness theorem using the following moduls tollens proof?

One direction is trivial since if $\Sigma$ is satisfiable, then certainly $\Sigma_0 \subseteq \Sigma$ is satisfiable for some finite $\Sigma_0$.

For the other direction, say $\Sigma$ is a set of sentences that is not satisfiable. Then, by the completeness theorem, there exists a finite subset of that set that is inconsistent $-$ i.e., $\exists \ \Sigma_0 \subseteq \Sigma$ such that $\Sigma_0$ is finite and proves a proposition of the form $P \ \& \sim P $. So $\Sigma_0$ must not be satisfiable.

Or am I missing something here?

  • $\begingroup$ But then you need to prove the completeness theorem, which is no simpler. $\endgroup$
    – Mark
    Aug 10, 2017 at 8:45
  • $\begingroup$ I know this is an old post, but how do you get this from the completeness theorem? $\endgroup$
    – ngc1300
    Mar 3, 2021 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.