Proof by Contradiction at Five Levels

Let’s explain “Proof by Contradiction” in five different levels of complexity.

1. Child:

Imagine you’ve lost your favorite toy and you think it’s under your bed, but you’re not sure. One way to find out is by first saying “Let’s pretend the toy is NOT under the bed.” Then you start to look everywhere else in the room, but you can’t find the toy. You’ve looked absolutely everywhere else and the toy is nowhere to be found. So, because it’s not anywhere else, it must be under your bed! That’s a bit like how “proof by contradiction” works. We first say something is not true, and then we show that this leads to something silly or impossible.

2. Teenager:

“Proof by contradiction” is like trying to prove someone wrong by showing that what they’re saying leads to something absurd or impossible. Imagine you’re debating with a friend, and they claim that every single Marvel movie is bad. You can prove them wrong (using a method similar to proof by contradiction) by showing them at least one Marvel movie that is really good and popular. So their statement leads to an absurd conclusion (that a good and popular movie is bad), hence their original statement must be wrong.

3. Undergrad majoring in Computer Science:

“Proof by contradiction” (also known as reductio ad absurdum) is a common mathematical and logical technique. In computer science, we often use it to prove properties of algorithms or systems. The process involves assuming the opposite of what you want to prove, and then demonstrating that this assumption leads to a contradiction. This proves that the original statement must be true. For example, suppose you want to prove that a certain algorithm will always sort a list in increasing order. You might start by assuming the opposite - that there’s a list it can’t sort properly - then showing that this leads to a contradiction with how the algorithm works.

4. Grad student:

As you delve deeper into theoretical computer science, “proof by contradiction” becomes a critical tool for your research. For example, one of the most famous proofs by contradiction is the proof that there is no largest prime number. By assuming that there is a largest prime number, and then showing that you can always find a prime number that is bigger, we reach a contradiction. This contradiction proves that the assumption (that there is a largest prime number) is false, hence there is no largest prime number. Similar techniques can be applied to reason about the limits of computability, complexity theory, and more.

5. Colleague:

In formal logic and computer science, proof by contradiction is an indispensable method for establishing the validity of a proposition, particularly in the context of completeness and decidability issues. The premise involves assuming the negation of a proposition and then demonstrating that this leads to an inconsistency or contradiction, thereby establishing the truth of the original proposition. It’s fundamental in proofs concerning the halting problem, Gödel’s incompleteness theorems, the existence of non-computable real numbers, and various results in complexity theory, among other areas. It’s worth noting that while proof by contradiction is generally accepted in classical logic, it’s not valid in all logical systems, such as intuitionistic logic.

Counter Example

Proof by contradiction and counterexamples are two related but distinct tools used in mathematical reasoning and computer science.

In a proof by contradiction (also known as reductio ad absurdum), you start by assuming the opposite of what you’re trying to prove. Then you proceed logically from this assumption and try to arrive at a contradiction, something that you know is false. If you can do this, you’ve proven that your initial assumption (the opposite of what you’re trying to prove) must be false, and therefore what you’re trying to prove must be true.

On the other hand, a counterexample is a specific instance that disproves a statement. If you claim that a certain property holds for all elements of a set, finding just one element for which the property does not hold serves as a counterexample, proving your statement false.

So how are they related?

In the context of proof by contradiction, a counterexample can be used to demonstrate the contradiction. For instance, if we assume a proposition to be true for all elements in a set, and we are able to find an element (counterexample) that contradicts this assumption, we’ve used a counterexample to complete a proof by contradiction. Therefore, we can say that a counterexample is a powerful tool used in proofs by contradiction to help reveal contradictions.

Concept Breakdown

The method of Proof by Contradiction, also known as “reductio ad absurdum,” is a common form of argument in mathematics and computer science. It has a few fundamental components:

1. Assumption: You begin by assuming the opposite of what you are trying to prove. This is often referred to as the “negation” of your hypothesis.

2. Logical Deduction: Using known facts, rules, axioms, or previously proven statements, you deduce new statements from your initial assumption.

3. Contradiction: You arrive at a contradiction, which is a statement that contradicts either a known fact or the initial assumption itself.

4. Conclusion: Because of the contradiction, you conclude that the initial assumption (the opposite of what you were trying to prove) must be false. Therefore, the original hypothesis you were trying to prove must be true.

This is a powerful and widely used method in many fields because it allows you to prove a statement by demonstrating that its opposite leads to an absurd or impossible conclusion.

Here is an example of proof by contradiction:

Suppose you want to prove that √2 is irrational.

Assumption: Assume the opposite, i.e., √2 is rational. This means it can be expressed as a ratio of two integers, say p/q where p and q have no common factors other than 1 (i.e., they are coprime).

Logical Deduction: If √2 = p/q, then squaring both sides we get 2 = p²/q², or p² = 2q². This implies that p² is even, and therefore p must be even (because only even numbers have even squares). So, we can write p = 2k for some integer k. Substituting p in our equation, we get (2k)² = 2q², or 4k² = 2q², or q² = 2k². Now, this implies that q² is even and hence q is also even.

Contradiction: We’ve now deduced that both p and q are even, which contradicts our initial assumption that p and q have no common factors. We’ve reached an absurdity.

Conclusion: Therefore, our initial assumption that √2 is rational must be incorrect. Hence, √2 is irrational.