2

Proof by contradiction proves a statement by proving that the statement cannot be untrue. If a statement is FALSE, can we still use proof by contradiction? For example, here is a statement:

Let $m$ and $n$ be inegers. If $2m+n$ is even, then $m$ and $n$ are both odd.

This statement is obviously false. If $m=1$ and $n=2$, then $2m+n=4$ is even, but $n$ is not odd in this case. Have I already proved a statement by giving a counter-example? Can we use proof by contradiction in this case?

Prove by contradiction: Let $p$ be "$2m+n$ is even" and $q$ be "$m$ and $n$ are both odd". Since we want to prove that $p\implies q$ is TRUE, we assume that $p$ is TRUE and $q$ is FALSE. Thus, $m$ and $n$ cannot both be odd.

  • $m$ and $n$ are both even: $m=2k$ and $n=2j$. $2m+n=4k+2j=2(2k+j)$ is even.
  • $m$ is odd and $n$ is even: $m=2k+1$ and $n=2j$. $2m+n=4k+2+2j=2(2k+1+j)$ is even.
  • $m$ is even and $n$ is odd: $m=2k$ and $n=2j+1$. $2m+n=4k+2j+1$ is odd, which is a contradiction.

A contradiction occurs. Therefore the statement is FALSE.

I THINK I'M WRONG.

Ludwig Gershwin
  • 198

2 Answers2

4

That works, because if you have a statement $P$ and you want to show $P$ is false, you can do proof by contradiction with the statement $Q=\neg P$. You deduce $Q$ is true, so you deduce $P$ is false. (where [that] is the statement in the title of your question)

You just would say "if $P$ is true, then ... [contradiction] therefore... so $P$ is false". I don't see what the trouble is.

Giving a counterexample is a correct way to show the statement is false, yes.

N.B. I am ignoring issues with $\neg\neg P$ being different to $P$ in some logics etc. just read this as applicable to standard mathematics.

FShrike
  • 40,125
  • So we want to prove $p \implies q$ is false. Shouldn't we assume that $p \implies q$ is true? – Ludwig Gershwin May 22 '23 at 19:04
  • I think I understand now. If we want to prove that $p\implies q$ is false, we first assume that $p\implies q$ is true. There are 3 cases that can make $p\implies q$ true: $p$ is true and $q$ is true; $p$ is false and $q$ is true; $p$ is false and $q$ is false. If $p$ and $q$ are both true, then $2m+n$ is even $\Rightarrow 2m+n=2k$ where $k$ is an integer. Thus, $m+0.5n=k$. Since $m$ and $k$ are both integers, $n$ must be an even number, thus $q$ is false, so $p\implies q$ can't be true, a contradiction. Thus, $p\implies q$ is false. – Ludwig Gershwin May 22 '23 at 19:59
  • @LudwigGershwin In your particular case, showing there is a counterexample is definitely the easiest technique. Whether this is logically the same thing as performing proof by contradiction, I'm not sure. But for a general statement, this is a valid proof structure: "assume $p\implies q$ is true. Then whenever $p$, we have $q$ .... which is absurd, a contradiction, ... therefore there must be some $p$ for which $\neg q$ so $p\implies q$ is false" – FShrike May 22 '23 at 20:29
0

you can indeed prove that something is false by using proof by contradiction an example for that occurs in real analysis

a function $f$ cannot approach two different limits near $a$ , if $f$ approach $l$ near $a$ and $f$ approach $m$ near $a$ ,then $m=l$

the proof of this theorem was merely done by (proof by contradiction )

you can check the proof in Spivak's Calculus in chapter $5$ p.98

Mans
  • 512
  • If I have understood it correctly, "a function $f$ cannot approach two different limits near $a$, if $f$ approach $l$ near $a$ and $f$ approach $m$ near $a$, then $m=l$" is a TRUE statement. Thus, using prove by contradiction is valid. What I'm asking is if the original statement is FALSE, can we still prove by contradiction? – Ludwig Gershwin May 22 '23 at 19:16
  • the proof was done based that the function can approach two different limits near the same point (which a false statement ) we considered it to be true until at the end of the proof the (false statement) which we considered to be true have lead us to a contradiction which proves that the false statement is false – Mans May 22 '23 at 19:25
  • I don't think you understand what I'm saying. If you want to prove by contradiction, you have to assume the original statement is false, which leads to a contradiction that proves the original statement is true. In this case, the original statement is true, therefore it's valid to assume the original statement is false (can approach two different limits near the same point). What I'm trying to say is, if the original statement is already false, what can I do to prove by contradiction. – Ludwig Gershwin May 22 '23 at 19:27
  • you can't say that statement is true or false until you proves it .

    if you have a statement which you suspect to be false and want to prove that it's really false all you have to do is assume that it's true which lead you to a contradiction

    that what I've written to you we began the with the false statement which we suspected to be false by considering that it's true and then a contradiction appears

     – Mans May 22 '23 at 19:37
  • If we suspect that a statement is false - let's say we know the statement is false beforehand. We still want to prove it. So we assume that it's true, Thus we want to prove that $p\implies q$ is true. Using proof by contradiction, we assume that $p$ is true and $q$ is false, which is the negation of the original statement. Since the original statement is false, the negation of the original statement is true, therefore we shouldn't find any contradictions. BTW, using punctuation is always good. – Ludwig Gershwin May 22 '23 at 19:50