0
$\begingroup$

There is an implication that I can't quite understand:

Given a set $\Sigma$ of well-formed-formulas and a well-formed-formula $\tau$, if $\Sigma_0\cup \{\tau\}$ is satisfiable for every finite $\Sigma_0\subseteq\Sigma$, then $\Sigma\cup\{\tau\}$ is finitely satisfiable

But I don't understand. Isn't the converse of the statement true, because finite satisfiability of $\Sigma\cup\{\tau\}$ implies the finite satisfiability of $\Sigma$?:

Given a set $\Sigma$ of well-formed-formulas and a well-formed-formula $\tau$, if $\Sigma\cup\{\tau\}$ is finitely satisfiable, then $\Sigma_0\cup \{\tau\}$ is satisfiable for every finite $\Sigma_0\subseteq\Sigma$

$\endgroup$
10
  • $\begingroup$ What do you mean by "finitely satisfiable"? $\endgroup$ Oct 22, 2020 at 2:52
  • $\begingroup$ A set of well-formed-formulas is finitely satisfiable iff all the subsets of it are satisfiable. $\endgroup$
    – kkkk
    Oct 22, 2020 at 2:58
  • $\begingroup$ Okay, then the first statement follows from the compactness theorem (a set of sentences is satisfiable if and only if all finite subsets of said set are satisfiable). The converse statement is also true, but trivially so and this is not a contradiction to the first one being true. $\endgroup$ Oct 22, 2020 at 3:01
  • $\begingroup$ @Watercrystal Can you prove the first implication? $\endgroup$
    – kkkk
    Oct 22, 2020 at 3:09
  • $\begingroup$ The first part implies that $\Sigma \cup \{\tau\}$ is satisfiable. If a set of FO sentences is satisfiable, then so is every subset of said set. $\endgroup$ Oct 22, 2020 at 3:12

1 Answer 1

0
$\begingroup$

Making a set smaller only makes it more easy to satisfy: if $\Delta\subseteq\Gamma$ and $\Gamma$ is satisfiable then $\Delta$ is also satisfiable.


Here's how this applies to your question in detail:

Suppose we have $\Sigma,\tau$ as in the OP and let $X\subseteq\Sigma\cup\{\tau\}$ be finite; we want to show that $X$ is satisfiable. Let $\Sigma_0=X\cap \Sigma$, and let $X'=\Sigma_0\cup\{\tau\}$. Clearly $X'\supseteq X$ since in fact $X'=X\cup\{\tau\}$; moreover, by hypothesis on $\Sigma$ and $\tau$ we know that $X'$ is satisfiable (since $\Sigma_0$ is finite, being a subset of the finite set $X$).

So we know that the set $X$ which we care about has a satisfiable superset - but that means that $X$ itself is satisfiable.

$\endgroup$

You must log in to answer this question.

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