Indirect Proof

In the world of mathematics, we must prove something is true before we call it a theorem. There are many types of proof, and one example is "indirect proof." But what does this mean? How can proof be indirect? Let's find out:

Indirect proof, explained

If we want to prove that a theorem is correct, we have a few options. One is to show that the conclusion is true, and we do this by starting with our given information and building a proof from there. This is called "direct proof."

On the other hand, indirect proof involves the opposite. We use logic to prove that all other possibilities cannot be true -- leaving us with the hypothesis as the only viable solution.

Proof by contradiction

Proof by contradiction is a powerful method of proving statements in mathematics and logic. The method involves assuming the negation of the statement you want to prove and then showing that this assumption leads to a contradiction, which means that the original statement must be true.

Let's work with a basic conditional statement:

"If p, then q."

To perform a proof by contradiction, we assume the opposite of what we want to prove. In this case, we assume "p and not q."

For example, consider the statement:

"If a person is fluent in English, then they can attend an English-speaking school."

To prove this by contradiction, we assume the opposite:

"A person is fluent in English, and they cannot attend an English-speaking school."

Now, we try to find a contradiction under this assumption. If a person is fluent in English, there should be no reason for them not to attend an English-speaking school, assuming there are no other barriers. Since our assumption doesn't make logical sense, we can conclude that the original statement is true.

Proof by contradiction can be used to prove more complex mathematical statements as well. In everyday conversations, indirect proofs can be used as thought experiments to challenge assumptions:

"Assuming for a moment that two squares are not similar figures.."
"Let's say for argument's sake that a right angle does not contain 90 degrees.."
"If the Pythagorean theorem is false, then.."

These starting points are based on assuming the opposite of what we suspect is true. Proof by contradiction can be an effective way to prove statements when direct proof is difficult or impossible.

An example of proof by contradiction

We already know that there are an infinite number of prime numbers. But how exactly do we prove that this is true? If we tried to count all of the prime numbers, we would never get the proof that we need -- even after millions of years.

We can prove that there are an infinite number of prime numbers using a proof by contradiction:

Suppose there is a finite number of prime numbers, and we have a list of all prime numbers:

p_{1}, p_{2}, ..., p_{n}

Now, we form a new number q:

q = p_{1} \times p_{2} \times ... \times p_{n} + 1

We know that q is greater than all the prime numbers in our list since it is a product of all the primes plus 1.

Now, q can either be prime or composite.

If q is prime, then it is a new prime number not in our original list, which contradicts our assumption that we have listed all the prime numbers.

If q is composite, then it must have at least one prime factor. However, q cannot be divisible by any prime number in our list, as it would result in a remainder of 1. This means q has a prime factor not in our list, which again contradicts our assumption.

In either case, our assumption that there are a finite number of prime numbers is contradicted. Therefore, there must be an infinite number of prime numbers.

Topics related to the Indirect Proof

Inductive Reasoning

Counter Example

Symbolic Logic

Flashcards covering the Indirect Proof

Symbolic Logic Flashcards

Introduction to Proofs Flashcards

Practice tests covering the Indirect Proof

Introduction to Proofs Practice Tests

Help your student wrap their mind around indirect proofs

It's easy to feel a little lost when covering symbolic logic and indirect proofs. Give your student a little extra help outside of class by contacting Varsity Tutors today. We carefully vet and interview each tutor before they work with students. These educational professionals can personalize lesson plans based on your student's goals, learning style, and ability level. Reach out today to get started.