Games
Problems
Go Pro!

Proof by Contradiction

Reference > Mathematics > Introduction to Proofs
 

Proof by contradiction is a very interesting form of proof, in which we make an assumption (usually we're not allowed to make assumptions when doing proofs) and use the assumption to arrive at a contradiction. Once we have a contradiction, we know that the assumption can't be true. Let's take a look at an example.

Prove: No proper divisors of an integer are more than half of that integer.

Proper divisors are numbers that are less than the number itself. For example, the proper divisors of 12 are 1, 2, 3, 4, and 6. There are no proper divisors of 12 that are bigger than 6.  It makes sense, doesn't it? But how do we prove it?

We assume the opposite, and create a contradiction.

STATEMENT                                                    REASON
1. Let k be a divisor of n such that 
n
2
< k < n Assumption 2. n < 2k < 2n Multiplicative property of inequality (x2) 3. There exists a positive integer j such that kj = n Definition of a divisor 4. kj < 2k and 2k < 2kj Substitution property of inequality 5. j < 2 and 2 < 2j Division property of inequality (/k) 6. j < 2 and 1 < j Division property of inequality (/2)

Line 6 states that j is between 1 and 2, but there are no integers between 1 and 2, which violates statement 3, leading to a contradiction.

Since we've generated a contradiction, we can conclude that our assumption in statement 1 is invalid. Thus, no proper divisors of an integer are more than half of that integer.

Questions

1.
Prove by contradiction: If x is even, x2 is a multiple of 4
2.
Prove by contradiction: If x and y are both even, their sum is even.
Assign this reference page
Click here to assign this reference page to your students.
Transitive Property in ProofsTransitive Property in Proofs
Lemmas, If and Only If TheoremsLemmas, If and Only If Theorems
 

Blogs on This Site

Reviews and book lists - books we love!
The site administrator fields questions from visitors.
Like us on Facebook to get updates about new resources
Home
Pro Membership
About
Privacy