Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

When addressing the questions, which are featured below, I use the following definition and two lemmas.

Definition: $\phi$ is a tautology if $[[\phi]]_{v}=1$ for all valuations $v$.

Moreover, $\models \phi $ stands for $\phi$ is a tautology.

Let $\Gamma$ be a set of propositions, then $\Gamma \models \phi$ if and only if for all $v$: ($[[\psi]]_{v}=1$ for all $\psi \in \Gamma$) $\implies [[\phi]]_{v}=1$.

Lemma 1. $\phi_{1}, \dots, \phi_{n} \models \phi \iff [[\phi_{1}]] \land \dots \land [[\phi_{n}]] \leq [[\phi]] $

Proof sketch: This result follows immediately from the definition above.

Lemma 2. $\phi_{1}, \dots, \phi_{n}, \phi \models \psi \iff \phi_{1}, \dots, \phi_{n} \models \phi \to \psi$

Proof sketch: Use lemma 1 to transform the problem into $[[\phi_{1}]] \land \dots \land [[\phi_{n}]] \ $ Then, note that this form satisfy a Galois connection.

Now, here are the problems and my answer.

(a) For every set of formulas $\Gamma$, every formula $\phi$ and every formula $\psi$ we have that if $\Gamma \models \phi \land \psi$, then $\Gamma \models \phi$ and $\Gamma \models \psi$.

True. We may interprete $[[\phi \land \psi]]=\min([[\phi]],[[\psi]])$ and so $\Gamma \leq \phi$ and $\Gamma \leq \psi$, which shows the proposition.

(b) For every set of formulas $\Gamma$, every formula $\phi$ and every formula $\psi$ we have that if $\Gamma \models \phi \lor \psi$, then $\Gamma \models \phi$ or $\Gamma \models \psi$.

True (?). We may interprete $[[\phi \lor \psi]]=\max([[\phi]],[[\psi]])$ and so $\Gamma \models \phi \lor \psi$ really means $\Gamma \leq \text{max}([[\phi]],[[\psi]])$. Now, it is clear that for every instance, either $[[\Gamma]] \leq [[\phi]]$ or $[[\Gamma]] \leq [[\psi]]$, which, together with lemma 1, shows the claim.

(c) $P_{1} \land P_{2}, \neg P_{2} \models \neg P_{1}$

True (?). Combining lemma 2 and lemma 1 we see that the proposition really means $P_{1} \land P_{2} \leq P_{2} \lor \neg P_{1}$, which holds.

(d) $\bot \models \phi$ for any formula $\phi$

True. This is a consequence of lemma 1.

(e) $\phi \models \top$ for any formula $\phi$.

True. Again this is also a consequence of lemma 1.

Am I on the right track, or is there something wicked in the reasoning? Any feedback is very much appreciated.

share|improve this question

2 Answers 2

  1. Lemma 1 should presumably read, given the earlier notation $$\phi_{1}, \dots, \phi_{n} \models \phi \iff \forall v[[\phi_{1}]]_v \land \dots \land [[\phi_{n}]]_v \leq [[\phi]]_v$$
  2. You don't need to appeal to Galois connections to show Lemma 2. Indeed, it goes exactly the other way about -- it is because we have Lemma 2 that we can go on to talk of a Galois connection here, with conjunction being left adjoint to conditionalization.
  3. What is $\Gamma \leq \phi$ supposed to mean? It is non-standard notation. You mean, I take it, that on every valuation, the minimum value taken by the wffs in $\Gamma$ is less than or equal to the value of $\phi$. So the justification for the (correct) answer needs phrasing better.
  4. To answer the actual question, (b) is false [$\Gamma \vDash P \lor \neg P$ -- without either $\Gamma \nvDash P$ or $\Gamma \nvDash \neg P$] and (c) are true. The natural proof for (c) is more direct than given [which is mis-expressed anyway, as there is another notational glitch]. Just argue that there can be no valuation which makes $P_{1} \land P_{2}, \neg P_{2}$ true together, hence no valuation makes them true and $\neg P_{1}$ false.
  5. The answers given to (d) and (e) are correct, but it's not Lemma 1 that shows that, but the preceding definition of semantic entailment.
share|improve this answer
    
So, should I interpret that as all the other questions are true as well? –  user94284 Sep 23 '13 at 13:39
    
I have added remarks about the others. –  Peter Smith Sep 23 '13 at 15:43
    
(b) is false; consider $\Gamma = \{ \phi \lor \psi\}$. Then $\Gamma \vDash \phi \lor \psi$ but e.g. $\Gamma \not \vDash \phi$, because I can name a particular valuation as a counterexample to that latter claim, and similarly $\Gamma \not \vDash \psi$. –  Carl Mummert Sep 24 '13 at 11:19
    
But, I interprete it to be $\Gamma \models \phi$ or $\Gamma \models \psi$ - isn't the case that it will hold for at least one? –  user94284 Sep 24 '13 at 15:39
    
@CarlMummert Ooops my attention flickered in reading the OP! Thanks for correction!! –  Peter Smith Sep 24 '13 at 17:42

The error you made in part (b) is that you write $\Gamma \leq \phi$ as if this was a property of $\Gamma$ and $\phi$. Really you want to write "for every valuation $v$, $[[\Gamma]]_v \leq [[\phi]]_v$". The quantifier over all valuations in the definition of $\vDash$ is crucial.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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