Introduction to Proof by Contradiction

Introduction to Proof by Contradiction

One of the most powerful techniques in mathematical proof is the method of proof by contradiction. This method, also known as reductio ad absurdum, is based on the principle that to prove a statement, one can assume the opposite of the statement, and then show that this assumption leads to an impossible or contradictory conclusion. This impossibility then implies that the original statement must be true.

Fundamentals of Proof by Contradiction

Let's delve into the basics of how contradiction is utilized in mathematical proofs. The outline of a proof by contradiction follows these simple steps:

Assume the statement we want to prove is false. Apply logical operations and derive further implications based on this assumption. Show that the derived statement or a derived group of statements cannot be true (i.e., it leads to a contradiction). Conclude that since the assumption of the negation of the statement leads to a contradiction, the original statement must be true.

The beauty of this technique lies in its flexibility and versatility. It can be applied to various types of mathematical proofs, from geometry to number theory and beyond.

Practical Example: Proof that √2 is Irrational

To illustrate the method, let's consider the classic example of proving that the square root of 2 is irrational.

Step 1: Assume the Statement is False

Assume, for the sake of contradiction, that √2 is rational. This means that √2 can be expressed as a fraction of two integers, say a/b, where a and b are integers with no common factors other than 1 (i.e., a and b are in their simplest form).

Step 2: Derive Further Implications

Substitute √2 with a/b:

[ (frac{a}{b})^2 2 ]

Then,

[ frac{a^2}{b^2} 2 ]

Which simplifies to:

[ a^2 2b^2 ]

This equation tells us that a2 is an even number, since it is equal to 2 times another integer (b2). Therefore, a must also be even (since the square of an odd number is odd).

Let a 2k, where k is an integer. Substitute a 2k into the equation a2 2b2 and you get:

[ (2k)^2 2b^2 ]

[ 4k^2 2b^2 ]

[ 2k^2 b^2 ]

Now, b2 is also even, which means b must be even.

So, both a and b are even, which contradicts our initial assumption that a and b have no common factors other than 1 (since they are both even, they share the factor of 2).

Step 3: Identify the Contradiction

This contradiction means that our assumption of √2 being rational must be incorrect. Consequently, √2 must be irrational.

Step 4: Conclusion

Therefore, by the method of contradiction, we have proven that √2 is irrational.

Application of Proof by Contradiction

Proof by contradiction is not limited to irrational numbers but can also be used in various areas of mathematics, including number theory, geometry, and set theory. Here are a few more examples of how contradiction can be applied:

Example 1: Proving that a Triangle with Three Right Angles Cannot Exist

Assume a triangle can have three right angles. Since the sum of the angles in a triangle is 180 degrees, having three right angles would imply:

[ 90 90 90 270 ]

This is a contradiction, as the sum should be 180 degrees. Therefore, a triangle cannot have three right angles.

Example 2: Proving a Formula in Number Theory

In number theory, one might want to prove that for any integer n, if n2 is even, then n must also be even. Assume n2 is even but n is odd. Then, n can be written as 2k 1 for some integer k. Substituting this into n2 yields:

[ (2k 1)^2 4k^2 4k 1 2(2k^2 2k) 1 ]

This shows that n2 is of the form 2m 1, where m (2k^2 2k), which means it is odd. This is a contradiction, as n2 was assumed to be even. Therefore, n must be even.

Conclusion

Proof by contradiction is a versatile and powerful method in mathematical logic. By assuming the opposite of what you want to prove and showing that this assumption leads to a contradiction, you validate the truth of your original statement. This method is not only elegant but also fundamental in the field of mathematics, providing a way to tackle complex problems and explore new mathematical territories.

By understanding and mastering the technique of proof by contradiction, mathematicians and students can solve a wide range of problems and deepen their understanding of mathematical concepts. Whether it's proving properties of numbers, geometric shapes, or more abstract concepts, contradiction plays a crucial role.