If $B$ is a model for the set of positive consequences of $\Gamma$, then there's $A \subseteq B$ such that $A \models \Gamma$

Question

I'm working through Chang & Keisler again and got stuck on the following exercise (1.2.14) about propositional logic. First, consider a set $\mathscr{S}$ of sentence symbols of arbitrary cardinality; define a model for this language to be simply a subset of it. Now define a sentence as positive if it is built using only $\wedge$ and $\vee$. They propose them the following theorem: if $\Gamma$ is a consistent set of sentences, then $B$ is a model for the set of positive consequences of $\Gamma$ iff there is a model $A$ of $\Gamma$ such that $A \subseteq B$.

I've thought of using Theorem 1.2.16, which relates models (in this sense) and positive sentences as follows: $A \subseteq B$ iff every positive sentence which holds in $A$ also holds in $B$. This can indeed be used to prove the right to left direction, together with the fact that positive sentences are monotonic (C&K call them increasing), i.e. if $\phi$ is positive and $A \models \phi$ and $A \subseteq B$, then $B \models \phi$. But I'm a bit at loss to prove the left to right direction. My first idea was to use the consistency of $\Gamma$ to obtain a model $A'$ and use this model to find the appropriate subset of $B$, but there doesn't seem to be an obvious way of doing so. It seems I must somehow "reduce" $B$ in order to get the desired result, but I can't see exactly how so. Maybe I should exclude the sentence symbols in $B$ which don't entail any sentence in $\Gamma$? But how?

Answer 1

Here's one way to do it (I think). Starting with $B$, we let $B'\subseteq B$ be a minimal model of the positive consequences of $\Gamma$. $B'$ can be obtained by transfinite recursion (taking intersections at limits). Now, we will show that $B'\vDash \Gamma$. Suppose not; that is, suppose $B'\vDash \neg \phi$ where $\phi$ is a consequence of $\Gamma$. It follows that there is a finite sequence of literals $p_0^*,...,p_n^*$ such that $p_0^*,...,p_n^*\vdash \neg\phi$ and $B'\vDash (p_0^*\wedge,...,\wedge p_n^*)$. Without loss of generality, we can assume that $p_0^*,...,p_n^*$ is non-empty and has the least number of positive literals of any such sequence. (Non-emptiness is guaranteed by the consistency of $\Gamma$). If it contains no positive literals, then $\neg(p_0^*\wedge,...,\wedge p_n^*)$ is equivalent to a positive formula and since $\phi\vdash \neg(p_0^*\wedge,...,\wedge p_n^*)$, $ \neg(p_0^*\wedge,...,\wedge p_n^*)$ is a consequence of $\Gamma$, which is impossible. So, without loss of generality we can assume that $p^*_i = p_i$ for some $i\leq n$. Since $p_i\in B'$ and $B'$ is minimal, we know that $B'\setminus\{p_i\}\vDash \neg \psi$ for some positive consequence $\psi$ of $\Gamma$. So $q^*_0,...,\neg p_i,...,q^*_n\vdash \neg \psi$ where $B'\setminus\{p_i\}\vDash (q^*_0\wedge,...,\neg p_i,...,\wedge q^*_n)$. Now, note that since $\psi$ is positive, $\neg \psi$ is equivalent to a combination of negative literals. It follows that if we drop any positive literals from $q^*_0,...,\neg p_i,...,q^*_n$, $\neg \psi$ will still be a consequence. So, without loss of generality, we can assume that each $q^*_i = \neg q_i$ for each $i\leq n$. Finally, we have $(p_0^*\wedge,..., \not p_i,...\wedge p_n^*) \wedge (\neg q_0\wedge,...,\not\neg p_i,...,\wedge \neg q_n)\vdash \neg(\phi\wedge\psi)$ where $B'\vDash (p_0^*\wedge,..., \not p_i,...\wedge p_n^*) \wedge (\neg q_0\wedge,...,\not\neg p_i,...,\wedge \neg q_n)$ (where $(p_0^*,..., \not p_i,...\wedge p_n^*,\neg q_0,...,\not\neg p_i,...,\neg q_n)$ is again non-empty because $\Gamma$ is consistent). But this contradicts the fact that $(p_0^*\wedge,...\wedge p_n^*)$ had the least number of positive literals entailing the negation of some consequence of $\Gamma$ such that $B'\vDash (p_0^*\wedge,...\wedge p_n^*)$.

Answer 2

For the non-trivial direction, you're given a model $B$ of the positive consequences of $\Gamma$ and you want an $A$ satisfying two requirements: (1) $A\subseteq B$ and (2) $A$ is a model of $\Gamma$. Notice that requirement (1) can also be phrased as "$A$ is a model of $\Delta$" for a suitable $\Delta$, namely the set of negations of all the sentence symbols that are not in $B$, i.e., $\Delta=\{\neg p:p\in\mathcal S-B\}$. So the problem is to prove that $\Gamma\cup\Delta$ has a model, and for this purpose it suffices, by compactness, to show that , for any finitely many elements $p_1,\dots,p_n$ of $\mathcal S-B$, the set $\Gamma\cup\{\neg p_1,\dots,\neg p_n\}$ has a model.

So suppose, toward a contradiction, that $\Gamma\cup\{\neg p_1,\dots,\neg p_n\}$ has no model. This means that $\Gamma\vdash p_1\lor\cdots\lor p_n$. But then $p_1\lor\cdots\lor p_n$ is a positive consequence of $\Gamma$ that is not true in $B$ (because all the $p_i$ are $\notin B$), contrary to the hypothesis about $B$.

Answer 3

I've found a related result into :

• Jon Barwise (editor), Handbook of mathematical logic (1999), A.2 : H.Jerome Keisler, Fundamentals of Model Theory, page 47-on.

See page 72 : 5.10 : Lyndon Homomorphism Theorem (Lyndon [1959]).

We can derive from the proof of it the application to the propositional case.

Let $\Gamma$ consistent, and let $\Gamma^+$ the set of positive consequences of $\Gamma$, i.e. :

$\Gamma^+ = \{ \varphi | \varphi $ is positive and $ \Gamma \vDash \varphi \}$.

Let $B$ a model of $\Gamma^+$.

By compactness there is a model $A$ of $\Gamma$ such that every positive sentence true in $A$ is true in $B$.

As you have noticed, the application of compactness must be similar to that of : Theorem 1.2.16 (ii) [page 13]

Thus, applying C&K's Theorem 1.2.16 (i) [page 13] :

$A \subset B$ if and only if every positive sentence which holds in $A$ holds in $B$

we can conclude with $A \subset B$.

---

---

Added

Let $\Delta = \{ \lnot \varphi | \varphi $ is positive and $B \vDash \lnot \varphi \}$.

We have that $\Gamma \cup \Delta$ is consistent, because if $B \vDash \lnot \varphi$, then $\varphi \notin \Gamma^+$, and thus $\Gamma \nvDash \varphi$.

Let $A$ a model of $\Gamma \cup \Delta$ : we have that $A \vDash \Gamma$.

Now assume that there is a positive formula $\psi$ such that $A \vDash \psi$ and $B \nvDash \psi$.

If $B \nvDash \psi$, then $B \vDash \lnot \psi$; thus ($\psi$ is positive) $\lnot \psi \in \Delta$ and so $A \vDash \lnot \psi$ : contradiction.

Thus, we conclude that, for all positive $\varphi$, if $A \vDash \varphi$, then $B \vDash \varphi$ and this, by Theorem 1.2.16 (i) implies : $A \subset B$.