Finite satisfiability

logicpropositional-calculus

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$

Best Answer

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.

Related Question