Proving $(\neg P \to \neg Q) \to (Q \to P)$ in PL

[Guest2]

I'm trying to prove $$ : (\neg P \to \neg Q) \to (Q \to P)$$ in PL. Here's my attempt:

$ \left\{1\right\} ~~~~~~~~~~ 1. ~~~~~~ \neg P \to \neg Q ~~~~~~~~~~~~~~~~~~~~~~ \text{Premise}$

$ \left\{2\right\} ~~~~~~~~~~ 2. ~~~~~~ Q ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \text{Assumption for CP}$

$ \left\{1, ~ 2\right\} ~~~~~~ 3. ~~~~~~ P ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \text{1, 2 MT}$

$ \left\{1\right\} ~~~~~~~~~~ 4. ~~~~~~ Q \to P ~~~~~~~~~~~~~~~~~~~~~~~~~~~ \text{2, 3 CP}$

Is that correct?

 

[Evgeny.Makarov]

Hi, and welcome to the forum.

Wikipedia says that Modus Tollens is
\[
\frac{P \to Q\quad \neg Q}{\neg P}
\]
and not
\[
\frac{\neg P \to \neg Q\quad Q}{P}
\]

In general, there is no such things as proving something in propositional logic. There are numerous proof systems for PL, some more natural and interesting than others and none of them standard. Proving only makes sense when one such systems is fixed. So could you say which system you are using?

 

[Guest2]

Thanks for the reply. I'm not really sure what system we're using. There's only one system introduced in the book without any others being mentioned, so I'm not sure what it's called. But I think I've got how they wanted to do it now. This might shed some light on the system used.

♦ A proof consists of a set of consecutively numbered lines of proof. Each line of proof is composed of four parts: (i) a line number; (ii) a formula on that line; (iii) the name of the rule in virtue of which the formula was entered on that line; (iv) the formula’s dependency-numbers [the numbers in braces], i.e. a set of line numbers each of which refers back to a formula upon which the current formula depends.

But I think I've got how they wanted me to do it now. Please tell me if it's right (assuming it's legible/makes sense at all).

{1} 1. ¬ P → ¬ Q ...... premise
{2} 2. Q....... assumption for CP
{2} 3. ¬¬ Q...... 2 DNI (introducing double negation)
{1,2} 4. ¬¬P........1,3 MT
{1,2} 5. P.......4DNE (Getting rid off double negation).
{1} 6. Q → P......2, 5 CP.
{1} 7. (¬ P → ¬ Q) → (Q → P)... 1, 6 CP.

 

[Evgeny.Makarov]

This derivation is correct. Alternatively, you could assume $\neg P\to\neg Q$ and $Q$, then assume $\neg P$ towards RAA, derive a contradiction $Q\land\neg Q$, conclude $\neg\neg P$ and finally apply DNE to get $P$.

I had a look at the book. It uses the term "natural deduction" in non-technical sense several times, apparently to mean deduction that is natural. However, in mathematical logic, "natural deduction" refers to a specific proof system. The author correctly sums up the idea behind it: "[T]he introduction- and elimination-rules for each connective are thought of as capturing our core understanding of each connective in a very immediate way" (p. 47). But viewed from this perspective, his proof system is quite mangled. For example, there are four rules dealing with negation instead of just introduction and elimination. (It is true that regular ND also has three rules for negation instead of two, but the third one -- DNE -- has a very special status different from any other rule. It is the only exception, and this fact is amply stressed in a good text.) Speaking about the form of presentation, I couldn't find a table listing all inference rules of propositional logic for reference. And no surprise because instead of a figure like
\[
\frac{P\to Q\quad P}{Q}
\]
each rule is described by a whole paragraph of text. Last but not least, the book uses English letter "v" for disjunction $\lor$.

 

[Guest2]

Many thanks for taking the time to do this. Yes, the fact that it doesn't collate the rules on anywhere in the book has been a pain, and I had to skip or skim through the verbiage many times (which is probably not serving me well now). I've successfully done most of problems, but I've three that have withstood every attack. If you could help me with these, I would really appreciate it. (I'm posting it here instead of a new thread since the context/system is explained in here).

1. : ( ¬ Q & R) → ((¬ R & P) → S)

2. P ∨ Q, Q → R : (S → P) ∨ R

3. ¬ (P & Q) : ¬P ∨ ¬Q
​

 

[Evgeny.Makarov]

First of all, note that $P\to(Q\to R)$ is equivalent to $(P\land Q)\to R$ in the sense that these formulas derive each other and are semantically equivalent. One way to see their similarity is that when they are being proved, we assume $P$ and $Q$ (or $P\land Q$, from which $P$ and $Q$ are easily derivable) and have to prove $R$. In contrast, $(P\to Q)\to R$ is quite different. It is customary to posit that implication associates to the right, so $P\to Q\to R$ is $P\to(Q\to R)$.

1. : ( ¬ Q & R) → ((¬ R & P) → S)​

Here the idea is that the two assumptions ¬Q & R and ¬R & P are contradictory because they include R and ¬R. Follow the last advice in Box 3.3 on p. 105.

2. P ∨ Q, Q → R : (S → P) ∨ R​

Here we use reasoning by cases (disjunction elimination). If P, then S → P by using CP to discharge a vacuous assumption S. If Q, then together with Q → R it gives R.

3. ¬ (P & Q) : ¬P ∨ ¬Q​

This one is a little tricky and has to be proved using DNE. That is, we prove ¬¬(¬P ∨ ¬Q). We can do this by deriving ¬(¬P ∨ ¬Q) → (P & Q) and then using MT. So, assume ¬(¬P ∨ ¬Q). Further, assume ¬P towards RAA. Then ¬P ∨ ¬Q, a contradiction with ¬(¬P ∨ ¬Q), so we get ¬¬P and P. The second part, i.e., Q is obtained similarly.

In fact, MT is not necessary as a separate inference rule because it is easy to see that it can be derived using RAA, but using it can make derivations a little shorter.

 

[Guest2]

Many thanks again for all of this. I had a go at the last one. Please let me know if this is right.

{1}-------1. ¬(P & Q).......Premise
{2}-------2. P ∨ Q........Assumption for RAA
{3}-------3. ¬P........Assumption for RAA
{4}-------4. ¬Q........Assumption for RAA
{3}-------5. ¬P ∨ ¬Q ......3 ∨I
{2,3}-----6. (P ∨ Q) & ¬ (P ∨ Q)......2,5 &I
{2}-------7. P .........3,6 RAA.
{4}-------8. ¬P ∨ ¬Q........4 ∨I.
{2,4}-----9. (P ∨ Q) & ¬(P V Q)......2, 8 &I
{2}------10. Q .........4,9 RAA
{2}------11. P & Q .......7,10 & I
{1,2}----12. ¬(P & Q) & (P & Q).....1, 11 &I
{1}------13. ¬(P V Q) ........2,12 RAA.
{1}------14. ¬P V ¬Q ...... ...13, ?

I'm not sure what to denote the rule for the last step or whether I'm allowed to use that. (Wasntme)

 

[Evgeny.Makarov]

By the way, you can use the [code]...[/code] tag (# sign on the toolbar), which uses a fixed-width font and does not remove spaces, thus preserving alignment.

{1}-------1. ¬(P & Q).......Premise
{2}-------2. P ∨ Q........Assumption for RAA
{3}-------3. ¬P........Assumption for RAA
{4}-------4. ¬Q........Assumption for RAA
{3}-------5. ¬P ∨ ¬Q ......3 ∨I
{2,3}-----6. (P ∨ Q) & ¬ (P ∨ Q)......2,5 &I

Line 5 has ¬P ∨ ¬Q, not ¬(P ∨ Q).

{2}-------7. P .........3,6 RAA.

RAA derives only negations. You must have used DNE as well.

{4}-------8. ¬P ∨ ¬Q........4 ∨I.

¬Q should be assumed just before this line and not in step 4. This is because subderivations between assumptions and the corresponding RAA or CP cannot intersect, though they may be nested. I am not sure the book talks about this.

Instead of assuming P ∨ Q in line 2, assume ¬(¬P ∨ ¬Q). Then you'll get a legitimate contradiction in line 6.

 

[Guest2]

Line 5 has ¬P ∨ ¬Q, not ¬(P ∨ Q).

Is there a way to fix this? Instead I could negate line two, not introduce line five at all, and take what you said about introducing ¬Q later and using DNE. Would it work then? Also, what's the rule that turns ¬P ∨ ¬Q into ¬(P ∨ Q)?

EDIT: Realised what I said wouldn't make sense. Ignore it. The book definitely doesn't talk about what you said about subderivations between assumptions and the corresponding RAA or CP not being allowed to intersect.

Instead of assuming P ∨ Q in line 2, assume ¬(¬P ∨ ¬Q). Then you'll get a legitimate contradiction in line 6.

Thanks.

 

[Guest2]

Instead of assuming P ∨ Q in line 2, assume ¬(¬P ∨ ¬Q). Then you'll get a legitimate contradiction in line 6.

Finally had the chance to reattempt this. Is this correct?

[SIZE=3]
3.	{1}...1. ¬(P & Q)........Premise
{2}...2. ¬(¬ P ∨ ¬Q)........Assumption for RAA
{3}...3. ¬P.........Assumption for RAA
{4}...4. ¬Q........Assumption for RAA
{3}...5. ¬P ∨ ¬Q.......4, VI
{2,3}...6. (¬P ∨ ¬Q) & ¬(¬P ∨ ¬Q)...2,5 &I 
{2}...7. Q..........4,6 RAA.
{4}...8. ¬P v ¬Q....... 3 VI.
{2,4}...9. (¬P ∨ ¬Q) & ¬(¬P V ¬Q)....2, 8 &I 
{2}...10. P.........3,9 RAA
{2}...11. P & Q.........7,10 & I
{1,2}...12. (P & Q) & ¬ (P & Q) ......1, 11 &I
{1}...13. ¬¬(¬P V¬ Q)........2,12 RAA.
{1}...14. ¬P V ¬Q .......13DNE
[/SIZE]

 

[Evgeny.Makarov]

The only remark is that, as I said in post #8, RAA derives only negations, so in steps 7 and 10 additional DNEs are needed, just like you did in steps 13 and 14. Otherwise the derivation is correct.

Concerning the code tag, it was supposed to make life easier, not harder. For this you need to type using a fixed-width font. Since the text area where posts are typed on this forum uses a regular proportional font, I usually type text that requires alignment in an external text editor, e.g., Notepad in Windows. It is necessary to select a fixed-width font, such as Courier, Courier New, Lucida Console or Consolas. Check that letters "i" and "w" have the same width. Then type the derivation using spaces and newlines. No need for dots or to have lines of the same width. Then copy and paste this text between the code tags.