# Compactness theorem equivalences

i have this equivalence to compactness theorem that i have problems to prove:

For every first-order theory $$T$$, every tuple $$x̄$$ of distinct variables and all sets $$\Phi(x̄),\Psi(x̄)$$ of first-order formulas, if $$T\vDash\forall\bar{x}(\bigwedge\Phi(x̄)\leftrightarrow\bigvee\Psi(x̄))$$ then there are finite sets $$\Phi_{0}(x̄)\subseteq\Phi(x̄)$$ and $$,\Psi_{0}(x̄)\subseteq\Psi(x̄)$$ such that $$T\vDash\forall\bar{x}(\bigwedge\Phi_{0}(x̄)\leftrightarrow\bigvee\Psi_{0}(x̄))$$

• What have you tried? Jun 19, 2021 at 17:16
• I don't know where to start Jun 19, 2021 at 18:40
• What is the exact formulation of the compactness that you are using? Jun 19, 2021 at 18:57
• I tried with both: - Let $T$ be a first-order theory. If every finite subset of $T$ has a model then $T$ has a model - If $T$ is a first-order theory, $\psi$ a first-order sentence and $T \vDash\psi$, then $U\vDash\psi$ for some finite subset $U$ of $T$. Jun 19, 2021 at 19:18

Write $$\neg\Psi$$ for the set containing the negation of formulas in $$\Psi$$. Consider only one implication for the moment. From

(0) $$T\vDash\forall x(\bigwedge\Phi(x)\rightarrow\bigvee\Psi(x))$$

we obtain

$$T \cup \Phi(x) \cup \neg\Psi(x)\models\bot$$

By compactness, for some finite set

$$T \cup \Phi_0(x) \cup \neg\Psi(x)\models\bot$$

Therefore

(1) $$T \models \forall x [\bigwedge \Phi_0(x) \rightarrow \bigvee\Psi(x)]$$

The converse of (0) is equivalent to $$T\vDash\forall x(\bigwedge\neg\Psi(x)\rightarrow\bigvee\neg\Phi(x))$$. Therefore the same argument yield $$T \models \forall x [\bigwedge\neg\Psi_0(x) \rightarrow \bigvee\neg\Phi(x)]$$ which is equivalent to

(2) $$T \models \forall x [\bigwedge\Phi(x) \rightarrow \bigvee\Psi_0(x)]$$

If you put (0), the converse of (0), (1) and (2) together you obtain

$$T \models \forall x [\bigwedge\Phi(x)\rightarrow \bigwedge\Phi_0(x) \rightarrow \bigvee\Psi(x) \rightarrow\bigwedge\Phi(x) \rightarrow \bigvee\Psi_0(x)\rightarrow \bigvee\Psi(x)\rightarrow \bigwedge\Phi(x) ]$$

EDIT. Note that we obtain a stronger claim than required. Namely, $$\bigwedge\Phi(x)\leftrightarrow \bigwedge\Phi_0(x)$$ and $$\bigvee\Psi(x)\leftrightarrow \bigvee\Psi_0(x)$$.

• I think this can be simplified. You can get finite $\Psi_0 \subseteq \Psi$ s.t. $T \cup \Phi_0 \cup \neg \Psi_0 \models \bot$ right away. Then $T \models \bigwedge \Phi_0 \to \bigvee \Psi_0$ does indeed follow as before. After that no more use of compactness is necessary because $T \models \bigvee \Psi_0 \to \bigvee \Psi$ always holds, so now you can tie everything together. (I omitted variables from my notation everywhere, they should of course be added if you want to be precise) Jun 19, 2021 at 21:32
• @MarkKamsma You are right. Jun 20, 2021 at 10:07