0
$\begingroup$

The problem goes like this:

Consider the following statement; "Given a set $\Sigma$ of wffs, and a wff $\tau$, $\Sigma\vDash\tau$ iff there is a finite $\Sigma_0\subset\Sigma$ such that $\Sigma_0\vDash\tau$. By using the above statement, prove the compactness theorem; "A set of wffs is satisfiable iff it is finitely satisfiable."

Because of possible usefulness, we note that $\Sigma\not\vDash\tau$ iff $\Sigma\cup\{\neg\tau\}$ is satisfiable.

My input is the following:

Given $\Sigma$, take $\sigma\in\Sigma$.

$\Sigma$ is satisfiable iff

$\Sigma\cup\{\sigma\}$ is satisfiable iff

$\Sigma\not\vDash\neg\sigma$ iff

for all finite $\Sigma_0\subset\Sigma$, $\Sigma_0\not\vDash\neg\sigma$ iff

for all finite $\Sigma_0\subset\Sigma$, $\Sigma_0\cup\{\sigma\}$ is satisfiable then $(*)$

for all finite $\Sigma_0\subset\Sigma$, $\Sigma_0$ is satisfiable $(*)$

Now, the final step $(*)$ is difficult. How can I show "if" part?

$\endgroup$
1
  • $\begingroup$ @spaceisdarkgreen I updated my input. Actually, the problem is not trivial as shown from my input. Please reconsider your thought. $\endgroup$
    – kkkk
    Oct 22, 2020 at 6:16

1 Answer 1

0
$\begingroup$

Keep in mind that making a set of sentences smaller only makes it easier to satisfy: if $\Gamma_0\subseteq\Gamma_1$ and $\Gamma_1$ is satisfiable, then $\Gamma_0$ is satisfiable. In particular, if $\Sigma_0\cup\{\sigma\}$ is satisfiable then so is $\Sigma_0$.

(Maybe it's the other direction you're concerned about, that is going from the last line to the second-to-last line? In that case we just use the fact that $\sigma\in\Sigma$: if $\Sigma_0$ is a finite subset of $\Sigma$ then so is $\Sigma_0\cup\{\sigma\}$, so if every finite subset of $\Sigma$ is satisfiable then so is every set of the form $\Sigma_0\cup\{\sigma\}$ for $\Sigma_0$ a finite subset of $\Sigma$.)


All of this suggests that the particular $\sigma$ is really playing no role. In fact, there's a variant of the argument which ignores it (and I suspect is the intended solution) which is based off of the following equivalence $(*)$: for every set $\Gamma$ we have that that $\Gamma$ is satisfiable iff $\Gamma\not\models\perp$.

Using $\perp$ this way simplifies the argument: if $\Gamma$ is finitely satisfiable then by $(*)$ we know that for each finite $\Gamma_0\subseteq\Gamma$ we have $\Gamma_0\not\models\perp$, so by the quoted fact we have $\Gamma\not\models\perp$ which in turn means that $\Gamma$ is satisfiable (apply $(*)$ again).

(And the other direction, "If $\Gamma$ is satisfiable then $\Gamma$ is finitely satisfiable, is trivial: any $M\models\Gamma$ simultaneously witnesses the satifsiability of all subsets of $\Gamma$.)

$\endgroup$

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