Proof by ContradictionReference > 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< 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)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.