Reductio ad absurdum

In logic, reductio ad absurdum (Latin for "reduction to absurdity") is a special way of proving something. It works by showing that if the opposite of what you want to prove were true, it would lead to something silly or impossible, called a contradiction. This method has been used for a very long time, starting with Ancient Greek philosophy, and is popular in math and philosophy.

In math, this method is often called a proof by contradiction. It is one way to show something is true without directly proving it. Instead, you assume the opposite is true and then show this leads to a problem. Famous mathematician G. H. Hardy liked this method very much, comparing it to a clever move in a chess gambit.

Even outside of strict math rules, this idea is used in many arguments. It can be called an indirect proof or proof by assuming the opposite. This way of thinking helps people understand big ideas by looking at what cannot be true.

Examples

A reductio ad absurdum argument shows something is true by proving that the opposite idea would lead to a silly or impossible result.

For example, we know the Earth isn’t flat because, if it were, people would fall off the edge. Another example is in math: there is no smallest positive rational number. If there were a smallest one, dividing it in half would give a smaller number, which contradicts our idea of the smallest number.

In math, this kind of proof works like this: we want to prove something is true, so we pretend it is false. Then we show that this false idea leads to two statements that can’t both be true at the same time. Because this doesn’t make sense, our original idea must be true.

Greek philosophy

Reductio ad absurdum was used a lot in Greek philosophy. One of the oldest examples is in a funny poem by Xenophanes of Colophon (around 570 – around 475 BCE). He talked about how humans think gods look like humans. But if horses or oxen could draw, they would draw gods looking like horses or oxen. Since gods can’t look like both, saying gods have human faults doesn’t make sense either.

Greek math experts like Euclid of Alexandria (mid-4th – mid-3rd centuries BCE) and Archimedes of Syracuse (around 287 – around 212 BCE) also used this way of proving things. In the talks of Plato (424–348 BCE) about Socrates, this method became a special way to talk and ask questions. Socrates would ask someone to say something that seemed simple. Then, by asking questions and using other ideas, he would show that what they said led to silly or impossible results. This made them change their mind.

The method was also important to Aristotle (384–322 BCE), especially in his book Prior Analytics. Another example is the sorites paradox, which asks if one million grains of sand make a heap, and if taking away one grain from a heap still leaves a heap, then even one grain (or none) could be a heap.

Buddhist philosophy

Much of Buddhist philosophy uses a special way of thinking called reductio ad absurdum to show that certain ideas do not make sense. This method is known as prasaṅga in Sanskrit. In a famous book called the Mūlamadhyamakakārikā, a thinker named Nāgārjuna used this method to explain that things like change and our senses do not have a fixed, unchanging nature.

For example, Nāgārjuna showed that if we say a "young man" truly exists on his own, it would mean he could never grow old. This helps us understand that many ideas we hold about things being fixed or unchanging do not hold up when we look closely.

Modern philosophy

Some modern thinkers have used the idea of reductio ad absurdum in their work.

Lewis White Beck used it when he talked about mechanism philosophy in his book The Actor and the Spectator from 1974.

Robert L. Holmes used this way of thinking to talk about deterrence theory in his book On War and Morality from 1989. He talked about why it is wrong to think that stopping wars by threatening to start wars is a good idea.

Relation to the principle of non-contradiction

Aristotle explained how being wrong works using his principle of non-contradiction. This idea says that something cannot be true and not true at the same time. For example, if we say "It is raining" and also "It is not raining" at the same time, one of these must be wrong. In math, people use this idea to show when an idea does not make sense by finding a mistake where both something and its opposite seem true. This helps prove that some ideas are false.

Formalization

The idea behind this method can be shown using simple logic. If saying something is not true leads to a wrong result, then that something must be true.

In logic rules, this looks like a special way to show a point. If we can prove that the idea of something not being true leads to a problem, then we can say that idea is true.

This idea is used in different logic systems to help make strong arguments.

Justification

In classical logic, this idea can be supported by looking at the truth table for the statement ¬¬P ⇒ P, which shows it is always true:

Another way to support this idea is by using the law of the excluded middle. We start by assuming ¬¬P and try to show P. According to the law of excluded middle, P is either true or false:

1. If P is true, then P is true.
2. If ¬P is true, we find a problem by using the law of noncontradiction with ¬P and ¬¬P. Then, the principle of explosion helps us say P is true.

Either way, we show P is true. It also works the other way around—proof by contradiction can help show the law of excluded middle is true.

In classical sequent calculus LK, proof by contradiction comes from the inference rules for negation:

!{\displaystyle {\cfrac {{\cfrac {{\cfrac {\ }{\Gamma ,P\vdash P,\Delta }}\;(I)}{\Gamma ,\vdash \lnot P,P,\Delta }}\;({\lnot }R)}{\Gamma ,\lnot \lnot P\vdash P,\Delta }}\;({\lnot }L)}

Relationship with other proof techniques

Proof by contradiction is like a special way to show something is true by assuming the opposite and finding a problem with it. In refutation by contradiction, we start by wanting to prove that something is not true. We assume it is true, find a problem, and conclude it must not be true.

In proof by contradiction, we want to prove something is true. We assume it is not true, find a problem with this idea, and conclude it must be true. Even though these methods seem similar, they are used in slightly different ways. In everyday math, people often use both methods interchangeably.

Proof by contradiction in intuitionistic logic

In intuitionistic logic, proof by contradiction isn’t usually accepted. However, some special cases can still be used. Two important ideas in this type of logic are proof of negation and the principle of noncontradiction, which both work well.

One way to understand proof by contradiction in intuitionistic logic is to think about whether we can prove a statement is true or false. If we can’t find a way to show a statement is false, maybe we can show it’s true. But this idea can lead to problems, like trying to solve things that are impossible to figure out, such as knowing if a computer program will ever stop running.

Some statements can still use proof by contradiction if they are “decidable,” meaning we can check them directly, like whether a number is prime or if one number divides another.

Examples of proofs by contradiction

Euclid's Elements

One of the oldest examples of this type of proof is found in Euclid's Elements, where he shows that if two angles in a triangle are the same, the sides opposite those angles must also be the same length. He starts by assuming the opposite sides are not equal and shows this leads to a problem.

Hilbert's Nullstellensatz

David Hilbert used this method to prove an important idea called the Nullstellensatz. He assumed the opposite of what he wanted to show and found that this also led to a problem.

Infinitude of primes

Euclid's theorem tells us there are more prime numbers than we can count. One way to show this is by assuming there is a largest prime number, then creating a new number that must be divisible by a prime but cannot be — another problem this method helps to find.

Examples of refutations by contradiction

These examples show how we can prove something by assuming the opposite and showing it leads to a problem.

One example is about prime numbers. We can show there are more prime numbers than any list we make by assuming we have all the primes and finding a new one that isn’t on the list. This shows our original idea cannot be right.

Another example is about the square root of 2. We can show it cannot be written as a simple fraction by assuming it can be and finding a problem with that idea.

A third example is about proof by infinite descent. We assume there is a smallest object with a certain property and then show we can find an even smaller one, which is a problem.

Finally, there is an example from set theory called Russell’s paradox, which shows a certain idea about sets cannot be true by showing it leads to a problem.

Euclid's theorem Euclid's proof prime factor proof that the square root of 2 is irrational √2 lowest terms integers even Proof by infinite descent Russell's paradox

Notation

Some proofs that show something cannot be true end with the words "Contradiction!".

Long ago, two people named Isaac Barrow and Baermann used the words Q.E.A., short for "quod est absurdum" ("which is absurd"), similar to the words Q.E.D. that people use today. But almost no one uses Q.E.A. anymore.

Today, people sometimes draw special symbols to show a contradiction. One symbol looks like a lightning bolt pointing down. Other symbols can look like two arrows pointing in opposite directions, arrows with a line through them, a special kind of hash mark, or even a symbol that looks like a reference mark or two X’s together.

Automated theorem proving

In automated theorem proving, a method called resolution, shown as resolution, uses proof by contradiction. This means the prover assumes the given facts and the opposite of the statement we want to prove. Then, it tries to find a mistake or problem in these assumptions. If it finds one, it helps prove the original statement is true.