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$
1
  • 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$ Commented Jul 15, 2013 at 1:24

4 Answers 4

8
$\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$
3
  • $\begingroup$ Very nice my friend Amy. +1 $\endgroup$
    – Mikasa
    Commented Jul 15, 2013 at 15:31
  • $\begingroup$ @Amzoti You know I love these sorts of questions! Thanks for the support! $\endgroup$
    – amWhy
    Commented Jul 16, 2013 at 1:03
  • $\begingroup$ @amWhy: I could not tell! :=~~~~~~) (see how long my nose got?) $\endgroup$
    – Amzoti
    Commented Jul 16, 2013 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$
5
  • $\begingroup$ Why was this down-voted? $\endgroup$
    – JLA
    Commented Jul 15, 2013 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
    Commented Jul 15, 2013 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$
    – jimjim
    Commented Jul 15, 2013 at 22:54
  • 1
    $\begingroup$ @TheChaz2.0 : cool dude, not here to offend anyone, apologies and removed. $\endgroup$
    – jimjim
    Commented Jul 16, 2013 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$ Commented Jul 16, 2013 at 20:19

You must log in to answer this question.

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