3
$\begingroup$

In this proof extracted from the Wikipedia

A classic proof by contradiction from mathematics is the proof that the square root of 2 is irrational. If it were rational, it could be expressed as a fraction $a/b$ in lowest terms, where a and b are integers, at least one of which is odd. But if $a/b = \sqrt 2$, then $a^2=$ $2b^2$. Therefore $a^2$ must be even. Because the square of an odd number is odd, that in turn implies that $a$ is even. This means that $b$ must be odd because $a/b$ is in lowest terms. On the other hand, if $a$ is even, then $a^2$ is a multiple of $4$. If $a^2$ is a multiple of $4$ and $a^2=2b^2$, then $2b^2$ is a multiple of $4$, and therefore $b^2$ is even, and so is $b$. So $b$ is odd and even, a contradiction. Therefore the initial assumption—that $\sqrt 2$ can be expressed as a fraction—must be false.

Knowing that a proof by contradiction you assume P and Not(Q) what's P and what's not Q in this proof?

$\endgroup$
  • 3
    $\begingroup$ Proof by contradiction applies to any statement, not just to implications. So, proving that by contradiction that $P$ is true entails assuming $P$ fails and arriving at a contradiction. $\endgroup$ – Ittay Weiss Jul 15 '13 at 1:24
7
$\begingroup$

I'm assuming you are more accustomed to seeing proof by contradiction used largely with statements that are implications or conditionals. And indeed, when writing a proof by contradiction to prove statements of the form $$P \implies Q,$$ we typically assume $(P\land \lnot Q)$.

But in this particular case, we do not seem to have an implication to prove. Rather, we have the proposition:

The square root of $2$ is irrational. $\quad$( $Q$).

There's no helpful "if, then", or "this implies that" to indicate any sort of implication being asserted. So we have an example of the use of a proof by contradiction where to prove a statement other than an implication.

What we can do is to think of the assertion to be proven as a simple "atomic" proposition: $\,Q.\,$ Then $\,\lnot Q\,$ is the statement to the effect:

Suppose $\,\sqrt 2\,$ is not irrational. $\;$ Put differently, suppose $\,\sqrt 2\,$ is rational.$\quad(\lnot Q)$

The proof then proceeds, after having supposed $\,\lnot Q\,$ to invoke the definition of a rational number in order to arrive at a contradiction.

In a sense then, the proof amounts to a "bare-bones" proof-by-contradiction:

To prove that $\,Q,\,$ we assume $\,\lnot Q,\,$ and then we work to obtain a contradiction. Once we arrive at a contradiction, we can conclude that our assumption is false, and so we are justified in negating the false assumption: "therefore, $\lnot\lnot Q.$" $\;\;$ And this amounts to affirming the desired conclusion/assertion: therefore $Q$, since $\;\lnot \lnot Q\equiv Q$.

The contradiction in this proof happens to come from our knowledge about the rational numbers, information which could be considered a premise: the "implicit" premise $P$ being the definition of a rational number.

$\endgroup$
  • $\begingroup$ Very nice my friend Amy. +1 $\endgroup$ – mrs Jul 15 '13 at 15:31
  • $\begingroup$ @Amzoti You know I love these sorts of questions! Thanks for the support! $\endgroup$ – Namaste Jul 16 '13 at 1:03
  • $\begingroup$ @amWhy: I could not tell! :=~~~~~~) (see how long my nose got?) $\endgroup$ – Amzoti Jul 16 '13 at 1:05
1
$\begingroup$

You can phrase "$\sqrt 2$ is irrational" as the implication "if $x=\sqrt 2$, then $x$ is irrational". Or better (which also handles $-\sqrt 2$): if $x^2 = 2$, then $x$ is irrational.

$\endgroup$
0
$\begingroup$

You can see the proof as showing that if you assume "$\sqrt2$ rational" you get a contradiction.

Or you can take P$=$"$\sqrt2=a/b$", Q="$a,b$ are both divisible by $2$". The proof shows that P implies Q. As you can always write a rational with a coprime numerator and denominator, the contrapositive shows that $\sqrt2$ is irrational.

$\endgroup$
-2
$\begingroup$

P would be that $\sqrt{2}$ is rational, Q that it is irrational, and so not(Q) is that it is not irrational.

$\endgroup$
  • $\begingroup$ Why was this down-voted? $\endgroup$ – JLA Jul 15 '13 at 3:24
  • 1
    $\begingroup$ Thanks! I figured specifying what Q is and then inferring what not(Q) is makes more sense than just saying what not(Q) is. $\endgroup$ – JLA Jul 15 '13 at 18:44
  • $\begingroup$ And you were correct, but during my time here I have noticed downvoting here is not about correct/incorrect answers. Sometimes changing something doesn't attract the downvoters. $\endgroup$ – Arjang Jul 15 '13 at 22:54
  • 1
    $\begingroup$ @TheChaz2.0 : cool dude, not here to offend anyone, apologies and removed. $\endgroup$ – Arjang Jul 16 '13 at 0:55
  • $\begingroup$ I was one of the downvotes. With that $P$ and $Q$, the implication $P\implies Q$ reads "if $\sqrt2$ is rational, then $\sqrt2$ is irrational", which makes no sense. $\endgroup$ – Martin Argerami Jul 16 '13 at 20:19

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.