1
$\begingroup$

This is exercise 1.3.22 from Hinman's Fundamentals of Mathematical Logic. Let $\mathrm{Sent}_{\neg, \vee, \wedge}$ be the set of all sentences from propositional logic closed under negation, disjunction, and conjunction and consider a mapping $\circ: \mathrm{Sent}_{\neg, \vee, \wedge} \to \mathrm{Sent}_{\neg, \vee, \wedge}$ defined as: if $\phi$ is an atomic sentence, then $\phi^\circ = \phi$; if $\phi$ is $\neg \psi$, then $\phi^\circ = \neg \psi^\circ$; if $\phi$ is $\psi \wedge \theta$, then $\phi^\circ = \psi^\circ \vee \theta^\circ$; finally, if $\phi$ is $\psi \vee \theta$, then $\phi^\circ = \psi^\circ \wedge \theta^\circ$. Basically, $\circ$ interchanges $\vee$ and $\wedge$ while leaving everything else the same (that's why I called it a "semi-dual" -- I don't know if there's a more appropriate name for it).

Given this setting, Hinman asks us to prove that, if $\models \neg \phi$, then $\models \phi^\circ$. This seems simple enough, but I'm having troubles actually carrying out the proof. It seems that the obvious way is by proceeding by induction, yet I don't see a way of framing the induction hypothesis strongly enough to get what I want.

Specifically, in the disjunction case, the result is straightforward:

\begin{align*} \models \neg \phi &\implies \models \neg(\psi \vee \theta)\\ &\implies \models \neg \psi \wedge \neg \theta\\ &\implies \models \neg \psi \text{ and } \models \neg \theta\\ &\implies \models \psi^\circ \text{ and } \models \theta^\circ\\ &\implies \models \psi^\circ \wedge \theta^\circ \end{align*}

But what about the other cases? For negation, for instance, I just have that $\models \neg \phi \implies \models \neg \neg \psi \implies \models \psi$, but then I can't apply the induction hypothesis. Similarly, for the conjunction case, I just get $\models \neg \phi \implies \models \neg(\psi \wedge \theta) \implies \models \neg \psi \vee \neg \theta$, so I can't apply the induction hypothesis either.

Therefore, it seems that, for these other cases, I need a lemma or something to be able to get the induction off the ground. In the conjunction case, I tried to show that if a conjunction is contradictory, either one of its conjuncts is contradictory or else each conjunct is equivalent to the negation of the other, but that didn't help much. Any hints or ideas?

$\endgroup$
1
$\begingroup$

How about this: For every interpretation $\mathcal I $ (truth assignment to all atomics), consider the opposite interpretation $\mathcal I^o$ (negated truth assignment). Then $\phi^o$ is true under $\mathcal I^o$ iff $\phi$ is true under the $\mathcal I$ (here, structural induction goes through). As $\models$ means true under all interpretations, the result follows.

$\endgroup$
  • $\begingroup$ So, just to see if got it right, your idea is to define, for any propositional letter $p$, $\mathcal{I}^\circ(p) = T$ iff $\mathcal{I}(p) = F$? $\endgroup$ – Nagase Aug 23 '15 at 20:50
  • $\begingroup$ I asked e above because, according to the definition of $\circ$, $p^\circ = p$, so if $\mathcal{I}^\circ$ is defined as in my comment, then it follows that it's not the case that $\phi^\circ$ is true under $\mathcal{I}^\circ$ iff $\phi$ is true under $\mathcal{I}$ (just take any literal as a counter-example). $\endgroup$ – Nagase Aug 24 '15 at 12:28

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.