Simple proof theory - Propositional Logic

Question

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.

Answer 1

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.

Answer 2

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.