Proving with compactness argument

193 Views Asked by At

Let $\sigma$ be the signature and $\Delta \subseteq FO[\sigma]$ is closed under conjunctions and disjunctions. Given structures $A$ and $B$, define $A==>_\Delta B$ by:

for all sentences $\phi$ in $\Delta$, if $A \models \phi$, then $B\models \phi$.

Now using compactness show TFAE,

For every $\phi \in FO[\sigma]:$

i) $\phi$ is preserved under $==>_\Delta$

ii) $\phi \equiv \phi'$ for some $\phi' \in \Delta$

Other direction $(2\rightarrow 1)$ is easy, and I am trying to prove the first direction $1\rightarrow 2$. I first assumed that there is some $\phi$ such that, $\phi\not\equiv \phi'$ for any $\phi'\in \Delta$, and thought to prove that $\phi$ doesn't preserve under $==>_\Delta$. I'm lost here. Professor told me that this proof is similar to that of Los-Tarski theorem

UPDATE:

There is a small section (pages 274 & 275) in Fundamentals of Mathematical Logic -Peter G Hinman

1

There are 1 best solutions below

0
On BEST ANSWER

Let $T_\phi = \{\theta\in \Delta\mid \phi\models\theta\}$.

Claim: $T_\phi\models \phi$.

Suppose $B\models T_\phi$. To show that $B\models \phi$, we want to find some $A$ such that $A\models \phi$ and $A\Rightarrow_\Delta B$.

So let $\Sigma_B = \{\lnot \psi\mid \psi\in \Delta\text{ and }B\not\models \psi\}$. I claim that $\{\phi\}\cup \Sigma_B$ is consistent. If not, by compactness there is a finite subset $\{\phi,\lnot \psi_1,\dots,\lnot \psi_n\}$ which is inconsistent. So $\phi\models \bigvee_{i=1}^n \psi_i$, and since $\Delta$ is closed under disjunction, $\bigvee_{i=1}^n \psi_i$ is in $T_\phi$. But then $B\models \bigvee_{i=1}^n\psi_i$, so $B\models \psi_i$ for some $i$, contradicting $\lnot \psi_i\in \Sigma_B$.

Hence $\{\phi\}\cup \Sigma_B$ has a model, $A$, and we have $A\Rightarrow_\Delta B$, since for all $\psi\in \Delta$, if $A\models \psi$, then $\lnot\psi\notin \Sigma_B$, so $B\models \psi$. And since $A\models \phi$, $B\models \phi$, as was to be shown. $\square$

Now by compactness, there is some finite subset $\{\theta_1,\dots,\theta_m\}\subseteq T_\phi$ such that $\{\theta_1,\dots,\theta_m\}\models \phi$. Since also $\phi\models \theta_i$ for all $i$, $\phi\equiv \bigwedge_{j=1}^m\theta_j$, which is in $\Delta$, since $\Delta$ is closed under conjunction.


As I noted in response to Max's comment above, this proof implicitly assumes that our first-order language includes symbols $\top$ (true, the empty conjunction) and $\bot$ (false, the empty disjunction), and "$\Delta$ is closed under conjunction and disjunction" includes the empty conjunction and disjunction. Otherwise, $\Delta$ might not contain an identically true sentence or an identically false sentence. This is one reason why one should always include $\top$ and $\bot$ in the language of first-order logic.

Here's where the proof goes wrong without this background assumption: If $\phi$ is identically true, then $T_\phi$ is empty. We still (trivially) have $T_\phi\models \phi$, but the finite subset we obtain by compactness is empty, and we need to take the empty conjunction to find the equivalent to $\phi$. On the other hand, if $\phi$ is identically false, then $T_\phi = \Delta$, but we don't have $T_\phi\models \phi$ unless $T_\phi$ contains an identically false sentence. Looking into the proof of the claim, we find that $\Sigma_B$ is empty, and the finite disjunction from $\Sigma_B$ implied by $\phi$ is the empty disjunction.