I would like help understanding two related claims being made in the following proof, found in the fourth edition of Elliot Mendelson’s introduction to mathematical logic, which I am reading on my own time to help my studies in philosophy of math and philosophical logic. Here is the proof:

enter image description here

What I do not understand about this proof is the claim being made in case 1 and 2 that when B is equivalent to ¬C and when B is equivalent to C ⇒ D, C / C and D have fewer than n occurrences of ¬ and ⇒. I don’t see how this holds. For example in case 1, let n = 2 and suppose B = (P ⇒ ¬Q). Then C = ¬B = ¬(P ⇒ ¬Q) which has three occurrences of ¬ and ⇒, even more than B. But this cannot be right. And for case 2 I can’t think of a counterexample but I still cannot see why it would always be true. So I must be missing something, but I cannot figure out what.

  • $\begingroup$ If $B = (P \implies \neg Q)$ then $B = (C \implies D)$ with $C = P$ and $D = \neg Q$, so both $C$ and $D$ have fewer than 2 connectives. I don't know where your "$C = \neg B$" comes from. Case 2 applies here, not case 1. $\endgroup$ Commented May 25 at 15:51

1 Answer 1


You are evidently misreading.

To say, e.g., that $\mathscr{B}$ is $\neg\mathscr{C}$ is to say that the wff $\mathscr{B}$ starts with a negation sign which is then followed by the wff $\mathscr{C}$.

So if $\mathscr{B}$ is, as it happens, the wff $(P \to \neg Q)$ then $\mathscr{B}$ is not a wff of the form $\neg\mathscr{C}$, as this $\mathscr{B}$ doesn't start with a negation sign. So Mendelson's Case 1 simply doesn't apply.

Of course, if $\mathscr{B}$ is the wff $(P \to \neg Q)$, it is (classically) semantically equivalent to the wff $\neg\mathscr{C}$ where $\mathscr{C}$ is $\neg(P \to \neg Q)$. But don't be distracted by that! For that's a semantic fact which is quite irrelevant to Mendelson's proof which involves an induction on the syntactic complexity of wffs.

To put it another way, Mendelson's argument is just looking at the shape of wffs, not what they mean. And Case 1 only arises when we are dealing with a wff $\mathscr{B}$ of the right surface shape, actually starting with a negation sign.

Moral: it is hugely important when beginning formal logic to be crystal clear about what is a syntactic question (a question about the surface form of wffs or arrays of wffs that might form a proof) and what is a semantic question (to do with interpretations, truth-tables, and the like). If you muddle the two, then e.g. you'll not grasp the full significance of the soundness and completeness theorems which relate the syntactic to the semantic!


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .