1
$\begingroup$

Simple exercise 6.2 in Hammack's Book of Proof. "Use proof by contradiction to prove"

"Suppose $n$ is an integer. If $n^2$ is odd, then $n$ is odd"

So my approach was:

Suppose instead, IF $n^2$ is odd THEN $n$ is even

Alternatively, then you have the contrapositive, IF $n$ is not even ($n$ is odd), then $n^2$ is not odd ($n^2$ is even).

$n = 2k+1$ where $k$ is an integer. (definition of odd)

$n^2 = (2k+1)^2$

$n^2 = 4k^2 + 4k + 1$

$n^2 = 2(2k^2 + 2k) + 1$

$n^2 = 2q + 1$ where $q = 2k^2 + 2k$

therefore $n^2$ is odd by definition of odd.

Therefore we have a contradiction. Contradictory contrapositive proposition said $n^2$ is not odd, but the derivation says $n^2$ is odd. Therefore the contradictory contrapositive is false, therefore the original proposition is true.

Not sure if this was the efficient/correct way to prove this using Proof-By-Contradiction.

$\endgroup$
2
  • 1
    $\begingroup$ Yes, this looks correct. A simpler way would be to prove the contrapositive of your original statement: "If n^2 is odd, then n is odd". $\endgroup$ Commented Jan 24, 2017 at 6:19
  • 2
    $\begingroup$ @PragnyaJha: This is not technically correct. You do NOT assume "IF $n^2$ is odd THEN n is even" but rather "$n^2$ is odd AND n is even", and you aim to deduce a contradiction. $\endgroup$
    – user21820
    Commented Jan 24, 2017 at 7:43

4 Answers 4

2
$\begingroup$

To prove $$ n^2\text{ is odd}\implies n\text{ is odd}\tag{1} $$ by contradiction, you need to prove that $$ n^2\text{ is odd}\wedge n\text{ is even}\tag{2} $$ is false. That is, you need to suppose that $n^2$ is odd and that $n$ is even and obtain a contradiction from those two statements.

This method of proof becomes clearer when the implication $$ n^2\text{ is odd}\implies n\text{ is odd} $$ is written in a logically equivalent way as $$ \neg((n^2\text{ is odd})\wedge\neg(n\text{ is odd}))\tag{3} $$ The proof by contradiction assumes the negation of the statement and obtains a known contradiction from it. In this case, you see that the negation of $(3)$ is $(2)$.

You propose to show $$ n^2\text{ is odd}\implies n\text{ is even}\tag{4} $$ is false in order to show $(1)$. That is incorrect.

For example, one could prove that $$ x>0\implies\sin(x)\geq0 $$ is false and yet $$ x>0\implies\sin(x)<0 $$ is also false.

In fact, what you did is show the converse of $(1)$. That is, you showed $$ n\text{ is odd}\implies n^2\text{ is odd} $$

In this case, in order to prove $(1)$, a proof of its contrapositive is the simplest way to go. Indeed, if $n=2k$ is even, then $n^2=(2k)^2=2(2k^2)$ is even. Here there is no real difference between the proof by contradiction and the proof by contrapositive: the hypothesis that $n^2$ is odd in $(2)$ doesn't need to be used.

$\endgroup$
0
$\begingroup$

Your proof looks correct to me, but I would like to share with you my strategy for proof by contradiction.

Consider the if/then statement $p\Rightarrow q$. In your case, $p$ represents "$n^{2}$ is odd" and $q$ represents "$n$ is odd". To achieve the proof by contradiction, we want to show that when $p$ is true, then it is impossible for $\neg q$, that is to say $n$ is even, to also be true. So we will assume that $p$ and $\neg q$ are both true (i.e., at the same time).

Applying this to your particular problem, we have $n^{2}$ is odd and $n$ is even. By definition, $n=2k$ for some integer $k$. Then $$n^{2}=(2k)^{2}=4k^{2}=2\cdot(2k^{2}).$$ Since the integers are multiplicatively closed, we have that $n^{2}$ is $2$ times an integer. Hence $n^{2}$ is even, which contradicts the assumption that $n^{2}$ is odd.

This tells us two things:

  1. The logical statement "$n^{2}$ is odd and $n$ is even" is a false statement.
  2. The logical statement "$n$ is even implies $n^{2}$ is even" is a true statement. This is the contrapositive ($\neg q\Rightarrow\neg p$) of the original statement, which always has the same truth value as the original statement.
$\endgroup$
4
  • 2
    $\begingroup$ The proof doesn't look correct to me! The OP proved the inverse implication! I know all Americans are humans, so I can infer that all humans are Americans?? $\endgroup$ Commented Jan 24, 2017 at 7:32
  • $\begingroup$ @NeedForHelp That is the converse, not the contrapositive. The contrapositive would be "if X is not human, then X is not American". The contrapositive of a true statement is true, but there's no guaranteeing that the converse is. $\endgroup$ Commented Jan 24, 2017 at 7:44
  • $\begingroup$ @ChrisHayes: Read the question carefully. The asker proved the wrong thing. $\endgroup$
    – user21820
    Commented Jan 24, 2017 at 7:45
  • 1
    $\begingroup$ @ChrisHayes OK, I meant converse and not inverse. Sorry my first language is not English. In any case the OP proved the converse which, as you said, doesn't guarantee that the statement he wants to prove is true. $\endgroup$ Commented Jan 24, 2017 at 7:46
0
$\begingroup$

The contrapositive of the original statement i.e. "If $n$ is even the $n^2$ is even" is easy to prove.

Let $n=2k$, $k\in\mathbb Z$ then $n^2=(2k)^2=2(2k^2)$ is even.

$\endgroup$
2
  • 1
    $\begingroup$ It is even easier when you have three other answers already there with the same argument. Also, how does this answer the question "Not sure if this was the efficient/**correct** way to prove this [...]". The OP proved the inverse of the implication... $\endgroup$ Commented Jan 24, 2017 at 7:22
  • $\begingroup$ @NeedForHelp: You are absolutely right. $\endgroup$
    – user21820
    Commented Jan 24, 2017 at 7:45
0
$\begingroup$

Last night I read this as a perfectly acceptable claim, but, as has been pointed out, your negation was not simply a "harder case" but instead the converse. Apologies! Your proof happened to work here because the stronger relationship (i.e. $\iff$)

A couple of things to note though. For a proof by contradiction would simply need to state that: there exists some $n^2$ which is odd, which has an even $n$ (perhaps phrased better: Suppose that you have $n^2$ which is odd for a corresponding $n$ even). With this in mind, consider the following direct proof by contradiction.

Assume that for some $n^2$ which is odd, we have $n = 2k$.

\begin{align} n^2 &= n\cdot n\\ &= (2k)(2k)\\ &= 2(2k^2) \\ 2k^2 &\in \mathbb{Z} \ \ \ \ \text{call it q} \\ n^2 &= 2q \implies 2 | n^2 \end{align}

and so we have reached a contradiction, so our assumption must be incorrect!

I do want to stress that, as with most propositions, there are multiple ways in which to prove this statement, as has been pointed out using the contrapositive is the most efficient way of proving it, but as the exercise asked to use a contradiction method, the above would work!

$\endgroup$

You must log in to answer this question.

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