0
$\begingroup$

I'm not completely sure how to phrase my question, so bare with me.

First example:

If I would need to prove 'Suppose $n$ is integer, if $n$ is odd, then $n^2$ is odd' then a proof by contradiction would look something like this.

Suppose $n$ is integer, if $n$ is odd then $n^2$ is even.
Assume $n$ is odd, so $n=2a+1$.
Therefore $(2a+1)^2$ is even
And $4a^2+4a+1$ is even
Let $b=2a^2+2a$
Therefore $2b+1$ is even.
This is a contradiction.

So in this case you start from the hypothesis to (dis)proof the conclusion.

The confusion

My confusion is about when this is done the conclusion is used to deal with the hypothesis e.g.

Suppose n is integer, if n^2 is odd, then n is odd.

Proof by contrapositive

If proof by contrapositive would be used, you could rewrite this to: if n is even, then $n^2$ is even.

And this is pretty straight forward to prove since you can plug in the knowledge about $n$ (the hypotheses) into the $n^2$ (the conclusion)

But how can this be proved using contradiction?

I have looked at various resources and it seems that knowledge about the conclusion is plugged back into the hypotheses for example:

Proof by contradiction
Suppose $n$ is integer, if $n^2$ is odd, then $n$ is even.
Assume $n$ is even, then $n=2a$
Now plug this into $n^2$ is odd, then $(2a)^2$ is odd
Let $b$ is $2a^2$
And $(2a)^2$ can be simplified to
$2b$ is odd Which is a contradiction.

But this feels fishy. Normally you work from the hypothesis and to proof the conclusion. But it seems that in this case, the reverse is allowed.

Another example of my confusion: Suppose a is integer. If a^2 is even, then a is even. Proof by contradiction. Suppose a is integer. If a^2 is even, then a is odd. Since a is odd, then a=2c+1. Then a^2=(2c+1)^2=2(2c^2+2c)+1. So a^2 is odd, which is a contradiction.

In the above example you plug knowledge of the conclusion back into the hypothesis. Normally with direct proof you plug knowledge from the hypothesis into the conclusion. This is what is causing my confusion.

And Another example of my confusion:

Is the proof using contradiction for both these statements exactly the same?

1: Suppose n is integer. If n is odd, then n^2 is odd.

2: Suppose n is integer. If n^2 is odd, then n is odd.

$\endgroup$
  • 1
    $\begingroup$ Not sure I follow. The statements "$n$ odd $\implies n^2$ odd" and "$n^2$ odd $\implies n$ odd" are not equivalent. $\endgroup$ – lulu Nov 28 '17 at 13:53
  • $\begingroup$ You are right. A negation is needed on the second one. $\endgroup$ – user370967 Nov 28 '17 at 13:54
  • $\begingroup$ @lulu yes, they are not equivalent. They are 2 different examples of proofs, but help to clarify where my problem is. $\endgroup$ – pveentjer Nov 28 '17 at 13:56
  • 1
    $\begingroup$ Well...I don't see the first proof as being a "proof by contradiction". Rather, it is a (perfectly valid) proof by explicit computation: $(2a+1)^2=4a^2+4a+1=2\times(2a+2)+1$ is odd. End of proof. $\endgroup$ – lulu Nov 28 '17 at 14:01
  • $\begingroup$ Typo: left off the multiplicative factor of $a$ in my expression (doesn't change the argument). $\endgroup$ – lulu Nov 28 '17 at 14:10
1
$\begingroup$

I think, we have to go back using logical symbols. If $A$ and $B$ are statements (like "$n$ is even" or "$n^2$ is odd") which is either true or false.

$A\vee B$ means "$A$ or $B$"

$A\wedge B$ means "$A$ and $B$"

$\neg A$ means "not $A$"

The implication $A\Rightarrow B$ is defined as $\neg A\vee B$ and has the meaning "If $A$, then $B$".

Suppose $\neg(A\Rightarrow B)$ is true. If you get a contradiction, then you deduce that $\neg(R\Rightarrow B)$ is false hence $A\Rightarrow B$ is true. This is called proof by contradition. But be careful: $ \neg(A\Rightarrow B) $ is equivalent to $A\wedge \neg B$.

On the other hand you can show that $A\Rightarrow B$ is equivalent to $\neg B\Rightarrow \neg A$, which is called the contraposition. So if you prove that the contraposition is true, than your original statement is true too.

Let us go to your example:

Proof by contraposition to "If $n$ is odd, then $n^2$ is odd."

Suppose $n$ is odd and $n^2$ is even. Then there exists integer $k,m$ such that $n=2k+1$ and $n^2=2m$. We get $$ 2m=n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1 $$ which is a contradition since the LHS is even while the RHS is odd.

Using proof of contraposition to "If $n^2$ even, then $n$ is even".

The contrapostion is: "If $n$ is odd, then $n^2$ is odd", which we proved by contradiction above.

And Another example of my confusion:

Is the proof using contradiction for both these statements exactly the same?

1: Suppose n is integer. If n is odd, then n^2 is odd.

2: Suppose n is integer. If n^2 is odd, then n is odd.

First, we suppose the negation of the statement is true, which is

1': Suppose $n$ is odd and $n^2$ is even.

2': Suppose $n^2$ is odd and $n$ is even.

Since $1$ and $2$ are different (not equivalent) statements, so $1'$ and $2'$ are.

But in fact, you will produce the same contradiction in both cases with the same idea/way. But if you suppose $1'$ you conclude $1$ and if you suppose $2'$ you conclude $2$.

$1$ and $2$ together means:

$n$ is odd if and only if $n^2$ is odd.

This case is a little bit special, since you can use the same arguments for both directions. That is not always natural. Normally you need totally different ways to prove an equivalence.

$\endgroup$
  • $\begingroup$ Ok. And now proof 'if n^2 is odd, then n is odd' using contradiction. See page 115 from 'Book of Proof' people.vcu.edu/~rhammack/BookOfProof/Contradict.pdf. $\endgroup$ – pveentjer Nov 28 '17 at 14:30
  • $\begingroup$ They did the same as me. If you like to proof "If $n^2$ is odd, then $n$ is odd" you have to consider the negation which is "$n^2$ is odd and $n$ is even" and produce a contradiction. $\endgroup$ – Mundron Schmidt Nov 28 '17 at 14:37
  • $\begingroup$ You agree that for this proof, knowledge from the conclusion is plugged back into the hypothesis? Normally with direct proofs you plug knowledge from the hypothesis in the conclusion. This reverse behavior for the above contradiction proof is the source of my confusion.. $\endgroup$ – pveentjer Nov 28 '17 at 14:39
  • $\begingroup$ If you do a proof by contradiction, you have to drop the idea of "conclude one statement from the other". You suppose that the hypothesis AND the negation of the conclusion are given. You have both statements and combine them to a contradiction. $\endgroup$ – Mundron Schmidt Nov 28 '17 at 14:47
  • $\begingroup$ So the proof by contradiction for A->B, or B->A would be the same? See the last example of my opening post. edit Not the same because either you get 'A and not B' or 'B and not A' as base for the contradictions. $\endgroup$ – pveentjer Nov 30 '17 at 14:27
0
$\begingroup$

Afters studying the topic some more, I have gained some deeper insights.

So imagine the statement S needs to be proved by contradiction, then

~S->(r/\ ~r)

So in other words, the negation of S would lead to some contradiction where r is both true and false. Since the contradiction is always false, the only way to make this statement true, is ~S is false. Since ~S is false, S must be true.

Assume that S is defined as some implication:

p1/\p2/\.../\pn->q

If we plug this into a proof by contradiction we would get:

~(p1/\p2/\.../\pn->q)->(px/\~px)

Where px is one of the contradicting premises. If we clean this up a bit:

~(~(p1/\p2/\.../\pn)\/q)->(px/\~px) (Implication conversion law)

~(~p1\/~p2\/...\/~pn\/q)->(px/\~px) (de Morgan)

(~~p1/\~~p2/\.../\~~pn/\~q)->(px/\~px) (de Morgan)

(p1/\p2/\.../\pn/\~q)->(px/\~px) (Double negation law)

To answer my own question, there is no more implication between the premises and the conclusion and therefor knowledge of the conclusion can be plugged into the premise or vice versa

$\endgroup$

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.