On p. 21 of Forster's Logic, Induction and Sets the reader is asked to check that the following is an exhaustive list of extensions satisfying modus ponens:

  • $\lambda pq.q$
  • $\lambda pq.(p\leftrightarrow q)$
  • $\lambda pq.\neg p$
  • $\lambda pq.(\neg p \vee q)$
  • $\lambda pq. \bot$

Now clearly we cannot have $(\lambda pq.f)(\top,\bot) = \top$, since whenever a candidate $f$ evaluates to $\top$ and $ p $ is $\top$, then q must also be $\top$. As far as I can see this is just what it means to satisfy modus ponens, and certainly this holds for the above list. However, shouldn't we then expect $2^3$ possible extensions? In particular, why does say, $\lambda pq.(\neg p \land \neg q)$ not satisfy?

  • 1
    $\begingroup$ The way I read the exercise is: for each of the proposed truth-functions (this is the meaning of extensions) see if they satisfy "mp" (with the truth-function in place of $\to$). Thus, for the fourth case: if $p$ is true and $\lambda p q . (\lnot p \lor q)$ is true, also $q$ must be. But with $p$ true and $\lambda p q . (\lnot p \land \lnot q)$ this cannot do, because with $p$ true we have $(\lnot p \land \lnot q)$ false. $\endgroup$ – Mauro ALLEGRANZA Sep 24 '17 at 17:26
  • $\begingroup$ @MauroALLEGRANZA well in the third case we also have $\neg p$ false with $p$ true, but this is apparently acceptable. to be precise, the way I read the exercise is: for each proposed truth function $f$, whenever $(f(p,q) = \top) \land (p=\top)$ then we must have also $q=\top$. I take my example $\lambda pq.(\neg p \land \neg q)$ to satisfy this because the condition $(f(p,q) = \top) \land (p=\top)$ is never met. $\endgroup$ – Matt E. Sep 24 '17 at 17:54
  • 1
    $\begingroup$ New try; let use Forster's same words: "f $p$ implies $q$, what does this tell us about what $p$ and $q$ evaluate to ? Well, at the very last, it tells us that $p$ can't evaluate to true when $q$ evaluates to false". $\endgroup$ – Mauro ALLEGRANZA Sep 25 '17 at 7:55
  • 1
    $\begingroup$ Apparently, this can be read: consider the truth table for the proposed truth functions and check that they have false in the row: $p$ true and $q$ false. If so, you are right: also $(\lnot p \land \lnot q)$ satisfies it. $\endgroup$ – Mauro ALLEGRANZA Sep 25 '17 at 8:28

Thanks @MauroALLEGRANZA for your comments. I should have gone in search of errata first: there are indeed 8 possibilities.


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.