2

There's one part of an explanation of proof by contradiction that I don't understand at the moment.

Here's the explanation:

"Let's say we desire to prove the truth of a statement,M.
A proof by contradiction will proceed by initially assuming that M is false i.e assuming M'(where M' is the negation of the statement M).
We would try to deduce from this a statement N that is clearly false.
Now having deduced a statement N from M', we have shown that M'=> N.

Hence also N'=>M

Now as we know N is false, N' is true and thus M is also true. Therefore we've proven M."

My question refers to the bold and underlined part of the explanation:

Why is it that N'=>M ?

stochasticmrfox
  • 909
  • 2
    Do you know that if $p \implies q$ then $q' \implies p'$ ? – Adayah Jul 16 '18 at 21:12
  • 4
    It is the contrapositive of $M'\Rightarrow N $, and is equivalent to it. – Bernard Jul 16 '18 at 21:13
  • 1
    What's your definition of "truth" at this point? Probably truth tables. Construct the truth tables for both $M'\to N$ and $N'\to M$. – Git Gud Jul 16 '18 at 21:13
  • 1
    Ah I see. I do know the general idea of a contrapositive(i.e if P=>Q then Q'=>P') but didn't know how to extend it to M' => N being equivalent to N'=>M. Thank you – stochasticmrfox Jul 16 '18 at 21:26

2 Answers2

1

True statements can only lead to true statements. If you had a true statement and could also derive a false statement, the concept of statements being either true or false falls apart.

Therefore this concept of proving something by contradiction works so well, if you already know (but not proven yet!) that something is true: First you assume your statement $M$ is false and then derive an impossible state $N$ from this new assumption $M'$.

Thus: $M'$ can't be true, (if it were, then $N$ would be true!). The only conclusion then is, that $N'$ must be true and therefore also $M$ must be true.

As pointed out by the others: You should look up truth tables and how negation and implication interact with another.

Imago
  • 2,132
0

We know that $P\implies Q$ is equivalent to $$P' \lor Q $$ or $$(Q')' \lor P'$$

which is equivalent to $$Q' \implies P'$$

hamam_Abdallah
  • 62,951