Register to reply

Proof by contradiction

by xeon123
Tags: contradiction, proof
Share this thread:
xeon123
#1
Feb18-12, 10:19 AM
P: 81
I never understand the proof by contradiction, because somewhere in the middle I always lost myself.

In this http://www.physicsforums.com/showthread.php?t=523874 there's an example of proof by contradiction.

If n is an integer such that n^2 is odd, then n must be odd.

So assume that n is an integer such that n^2 is odd. There are 2 possible cases: n can be odd or n can be even. If we show that n cannot be even, then it must be odd.
So, assume that n is even, then it has the form n=2k. But then n2=(2k)^2=4k^2=2(2k^2). This has the form 2m (with m=2k^2), thus n^2 is even. But we made the assumption that n^2 was odd, so we have reached a contradiction. So, n cannot be even (otherwise n^2 must be even), hence n must be odd.

We assume that if n^2 is odd than n is odd. This means that if n^2 is even, n can be odd or even. How can I proof a contradiction if n is even? It doesn't tell me nothing.
Phys.Org News Partner Mathematics news on Phys.org
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
alan2
#2
Feb18-12, 10:46 AM
P: 206
No, n^2 even implies n even. You are trying to show that if n^2 is odd, then n must be odd. So you assume that it's not true, i.e. if n^2 is odd then n is not necessarily odd. The only other choice is n is even. So suppose n^2 is odd and n is even. The result above is that if n is even then n^2 is also even. This contradicts the original assertion that n^2 was odd so it can not be true that if n^2 is odd, then n is even. The only choice left is that if n^2 is odd, then n is odd.


Register to reply

Related Discussions
Proof by Contradiction Calculus & Beyond Homework 1
Proof by contradiction Precalculus Mathematics Homework 2
Proof by contradiction Calculus & Beyond Homework 1
Proof By Contradiction Calculus & Beyond Homework 7