if for every finite statement set is satisfiable by 2 then any statement set is satisfiable by 2

47 Views Asked by At

Let S be a statement set of first order logic. We say that it is satisfiable by 2 if one can split to 2 the set, so each set is satisfiable . Prove or disprove, if every finite is satisfiable by 2, then the original set is also satisfiable by 2.

I believe it is a proof, with some variation on the compactness theorem, though I wasn't able to find an elegant proof.

1

There are 1 best solutions below

4
On BEST ANSWER

We use the following "two-structure trick:"

$X$ is satisfiable by $2$ iff there are structures $\mathcal{A},\mathcal{B}$ such that $Th(\mathcal{A})\cup Th(\mathcal{B})\supseteq X$.

(This is just a quick definition check.)

Now supposing $S$ is satisfiable by $2$, consider a new set $S'$ of sentences defined as follows:

  • The language of $S'$ is the language of $S$ plus two new unary relation symbols $A$ and $B$.

  • For each sentence $\varphi\in S$ we have in $S'$ the sentence $\varphi^A\vee\varphi^B$ in $S'$, where "$\psi^C$" is the relativization of $\psi$ to $C$ (just bound all quantifiers in the sentence $\psi$ by the unary predicate $C$).

(We could add a sentence saying that $A$ and $B$ partition the domain, but we don't have to.)

By compactness, $S'$ is satisfiable (why? use the two-structure trick above); letting $\mathcal{M}\models S'$, the substructures $A^\mathcal{M}$, $B^\mathcal{M}$ of $\mathcal{M}$ satisfy $$Th(A^\mathcal{M})\cup Th(B^\mathcal{M})\supseteq S$$ (why?), so by the two-structure trick above $S$ is satisfiable by $2$.