2
$\begingroup$

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̄))$

$\endgroup$
4
  • 2
    $\begingroup$ What have you tried? $\endgroup$
    – Hew Wolff
    Jun 19, 2021 at 17:16
  • $\begingroup$ I don't know where to start $\endgroup$ Jun 19, 2021 at 18:40
  • $\begingroup$ What is the exact formulation of the compactness that you are using? $\endgroup$ Jun 19, 2021 at 18:57
  • $\begingroup$ 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$. $\endgroup$ Jun 19, 2021 at 19:18

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$
2
  • 1
    $\begingroup$ 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) $\endgroup$ Jun 19, 2021 at 21:32
  • $\begingroup$ @MarkKamsma You are right. $\endgroup$ Jun 20, 2021 at 10:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .