3
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ @JonasGomes - I don't think it's a duplicate. That question, as the title says, is about how to prove that the set of all positive $L$-formulas is consistent. My question is, given that the set of all positive consequences of a given set of formulas is consistent, and thus has a model, how can we find a model for the original set; in other words, I'm here assuming the consistency of the set of all positive consequences. $\endgroup$
    – Nagase
    Dec 13 '14 at 4:46
  • $\begingroup$ Also, note that this is a question about propositional logic, not FOL. $\endgroup$
    – Nagase
    Dec 13 '14 at 4:47
  • 1
    $\begingroup$ Doesn't the intersection of all models of $\Gamma$ (which is given to be consistent) give you a good candidate for $A$ in the left-to-right direction? $\endgroup$
    – Rob Arthan
    Dec 14 '14 at 23:19
  • 2
    $\begingroup$ @RobArthan - Hmm, I may be mistaken, but I don't think there's any guarantee that the intersection won't be empty. Say $\Gamma = \{S_1 \vee S_2\}$. In this case, $A = \{S_1\}$ and $B=\{S_2\}$ are models for $\Gamma$, yet their intersection is empty. I think this also provides a counter-example to taking the intersection of the models of all positive consequences, as $A$ and $B$ will also be models for all positive consequences of $\Gamma$ (which will be disjunctions of the original disjunctions, I think). $\endgroup$
    – Nagase
    Dec 15 '14 at 14:35
  • $\begingroup$ I don't think you are mistaken. My suggestion doesn't work. $\endgroup$
    – Rob Arthan
    Dec 16 '14 at 0:35
3
$\begingroup$

I've found a related result into :

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$.

$\endgroup$
4
  • $\begingroup$ Hmm, I'm not totally sure about the adaptation of Keisler's proof; in any case, the application of the compactness theorem in the proof of Lyndon's theorem is very mysterious to me. But the second one nails it, I think! Did you adapt it from C&K's proof of Lemma 3.2.1? $\endgroup$
    – Nagase
    Dec 16 '14 at 19:00
  • $\begingroup$ @Nagase - No, but I've found the same result in J.Shoenfield, Mathematical Logic (1967), page 94. $\endgroup$ Dec 16 '14 at 19:37
  • $\begingroup$ Hmm, I just noticed that there's a very similar reasoning in the proof of C&K's Theorem 1.2.16 (ii) itself. Since the reasoning there uses compactness, it's probably closer to what Keisler had in mind in that article. $\endgroup$
    – Nagase
    Dec 16 '14 at 19:53
  • 1
    $\begingroup$ You can shorten Google Books link to: books.google.com/books?id=b0Fvrw9tBcMC&pg=PA72 http://books.google.com/books?id=b0Fvrw9tBcMC&pg=PA72 (I did not do the edit myself, since it is possible that you want to preserve highlighting of some words. The highlighting would be lost in the shortened form.) $\endgroup$ Dec 17 '14 at 12:22
3
$\begingroup$

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^*)$.

$\endgroup$
5
  • $\begingroup$ That's interesting. Can you be a bit more detailed about how to construct the minimal model $B'$, though? Since you need to take intersections at limits, I'm a bit worried that my concerns regarding Rob's suggestion above will also apply, i.e. that there's no way to guarantee that the intersection won't be empty. $\endgroup$
    – Nagase
    Dec 16 '14 at 19:01
  • $\begingroup$ @Nagase The difference is that I'm taking intersections of chains of models of the positive consequences, not arbitrary such models. $\endgroup$
    – GME
    Dec 16 '14 at 19:09
  • $\begingroup$ @Nagase In any case, Mauro's amended answer is much neater. So I will delete mine. $\endgroup$
    – GME
    Dec 16 '14 at 19:18
  • $\begingroup$ Well, I'd be interested in seeing the explicit construction anyway; I had thought about taking chains of models, but couldn't see how. $\endgroup$
    – Nagase
    Dec 16 '14 at 19:21
  • $\begingroup$ @Nagase Let $B_0 = B$. Then if $B_\alpha$ is not a minimal model of $\Gamma^+$, we let $B_{\alpha+1}\subset B_\alpha$ be such a model. At limits we take intersections. Suppose $\bigcap_{\alpha<\lambda} B_\alpha\vDash \neg \phi$ for some $\phi\in \Gamma^+$. Since there are only finitely many propositional variables in $\phi$, there will be some $B_\alpha$ that agrees with $\bigcap_{\alpha<\lambda} B_\alpha$ on them, which is impossible. $\endgroup$
    – GME
    Dec 16 '14 at 19:26
3
$\begingroup$

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.