3

I'm trying to understand the logic behind "proof by contradiction" and hoping that I can clear up a few things in this post.

First of all, suppose I have a proposition $P$ and from this I can imply some statement $Q$, i.e. $P\Rightarrow Q$, then to prove this by contradiction I assume the negation of this, $\neg \left(P\Rightarrow Q \right)$, which is equivalent to assuming $P\wedge \neg Q$, i.e. $\neg \left(P\Rightarrow Q \right)=P\wedge \neg Q$. Is there any way to prove this algebraically (apologies, I'm fairly new to logic)? I have shown this is true via a truth table, but not sure whether this counts as a proof or not?!

Next, having assumed $P\wedge \neg Q$, following logically from this if we find some statement $R$ such that a contradiction arises, $R\wedge \neg R$ then it follows that $\neg \left(P\Rightarrow Q \right)\Rightarrow R\wedge \neg R$. Now, my understanding of this is that, as $R\wedge \neg R$ is always false, then the only way this implication can be true is if $\neg \left(P\Rightarrow Q \right)$ is false, which implies that $P\Rightarrow Q $ is true, hence proving think intial claim. Is this the correct reasoning?

Thanks for your time.

Will
  • 3,265
  • For the equivalence between $¬(P⇒Q)$ and $P∧¬Q$ we can prove it with a proof system, like Natural Deduction. Do you know it ? – Mauro ALLEGRANZA Sep 21 '14 at 10:29
  • 1
    Basically YES. See also this post. In general, a proof by contradiction of $A$ exploit the following rule : $(¬A→B)→((¬A→¬B)→A)$. We assume the falsity of $A$, i.e. $\lnot A$ as true and derive both $B$ and $\lnot B$, i.e. a contradiction. Thus, by modus ponens, having proved $(¬A→B)$ and $(¬A→¬B)$ we can conclude with $A$. In your example, $A$ is $P⇒Q$. – Mauro ALLEGRANZA Sep 21 '14 at 10:32
  • @MauroALLEGRANZA Ah, thanks for the information! I'm fairly new to the subject, so unfortunately haven't heard of 'Natural deduction'. If you know of any useful introductory notes on logic (and/or propositional logic) that you can suggest, that'd be great. In any case, really appreciate the help! – Will Sep 21 '14 at 10:53
  • There are many good textbook. See e.g. Peter Smith, An Introduction to Formal Logic (2003) and (available on-line) : Stephen Simpson, Mathematical Logic – Mauro ALLEGRANZA Sep 21 '14 at 11:17
  • Great! Thanks for the recommendations. – Will Sep 21 '14 at 11:26
  • @Will - Also, there is a way to prove the equivalence of $\neg (P \implies Q)$ and $P \wedge \neg Q$ algebraically. You can either consider the associate Boolean algebra or consider the implication sign as introducing a linear order among the truth values, i.e. $P \implies Q$ is true iff $[P] \leq [Q]$, where $[P]$ is the truth-value of $P$. On the other hand, take the $\wedge$ operation as the operation which gives you the inf of $[P]$ and $[Q]$ (this will give you a lattice, btw); it's not difficult to see that $[P] \leq [Q]$ iff $[P] \wedge [\neg Q] = 0$. – Nagase Sep 21 '14 at 22:41
  • Thanks Naast :) ... Is proving it via a truth table (i.e. showing that the two logical connectives give equivalent truth tables) also valid/acceptable? – Will Sep 22 '14 at 20:25
  • ^^ sorry, the above should have said "Nagase" and not "Naast"... Autocorrect fail! – Will Sep 22 '14 at 22:34

0 Answers0