Reductio Ad Absurdum

Reductio ad absurdum

The painting Reductio ad absurdum by John Pettie, which graced the halls of the Royal Academy in 1884, serves as a rather dramatic, if slightly literal, visual representation of a potent logical tool. In the realm of logic, reductio ad absurdum – a phrase elegantly borrowed from Latin meaning "reduction to absurdity" – is a method of argument that seeks to establish the truth of a claim by demonstrating that the logical consequences of its negation would lead to a nonsensical or contradictory outcome. It’s also known by its equally Latin cousin, argumentum ad absurdum ("argument to absurdity"), or as an apagogical argument, and in the precise arena of mathematical proofs, it’s referred to as proof by contradiction. While it’s a workhorse in mathematical reasoning, it’s worth noting that not every philosophical faction within the philosophy of mathematics wholeheartedly embraces this particular brand of nonconstructive proof.

This argumentative form isn't some fleeting modern invention; its roots stretch back to the fertile intellectual soil of Ancient Greek philosophy. It has been a constant companion throughout history, finding its place in the rigorous proofs of mathematicians and the intricate debates of philosophers alike. In mathematics, the technique is quite literally called "proof by contradiction." Formal logic codifies this method with an axiom, often labeled RAA, for "reductio ad absurdum." This axiom is essentially the introduction rule for negation, as seen in negation introduction.

However, the utility of proof by contradiction extends beyond this formal definition. In a broader sense, it encompasses any argument that establishes a statement by reaching a contradiction, even if the initial assumption wasn't the direct negation of the statement being proven. In this more general guise, it’s also known as indirect proof or proof by assuming the opposite, and sometimes as reductio ad impossibile (reduction to the impossible).

The esteemed mathematician G. H. Hardy once described proof by contradiction as "one of a mathematician's finest weapons." He went on to elaborate, comparing it favorably to a chess gambit: "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game." This poetic comparison highlights the profound nature of this logical maneuver, suggesting it involves a greater, almost existential, stake.

Examples

The "absurd" conclusion that fuels a reductio ad absurdum argument can manifest in various forms, often playing on our common-sense understanding of the world or the fundamental rules of logic.

Consider the assertion that the Earth is flat. If we were to accept this premise, and also assume the Earth has a finite extent, then logically, we would expect people to eventually fall off its edge. The fact that we don't observe this, and indeed, our empirical evidence suggests otherwise, renders the flat Earth conclusion absurd.
Another example, this time from the mathematical realm, concerns the existence of a smallest positive rational number. If we were to hypothetically assume such a number, let’s call it q, exists, then q/2 would also be a rational number. Crucially, q/2 would be positive and, by definition, smaller than q. This directly contradicts our initial assumption that q was the smallest positive rational number. Therefore, we must conclude that no such smallest positive rational number exists. This is a classic mathematical proof by contradiction, also known as an indirect proof.

The first example leverages our sensory experience and common sense to highlight the absurdity of a proposition. The second, however, delves into the heart of mathematical rigor, demonstrating a logical contradiction where the denial of a premise leads to an impossible situation: the existence of a "smallest" number and yet simultaneously the existence of a number smaller than it.

A typical mathematical proof employing proof by contradiction unfolds in a structured manner:

Let P be the proposition we aim to prove.
We begin by assuming the negation of P, denoted as ¬P.
Our next step is to demonstrate that assuming ¬P inevitably leads to a falsehood. This is usually achieved by deriving two mutually contradictory statements, Q and ¬Q. This derivation relies on the fundamental law of noncontradiction.
Having reached a contradiction, we can confidently conclude that our initial assumption (¬P) must be false. Consequently, P must be true.

A particularly important subcategory of this technique is the existence proof by contradiction. To prove that an object with a certain property exists, we assume that all objects lack that property (or possess its negation) and then derive a contradiction.

Greek Philosophy

The reductio ad absurdum was a well-established tool within Greek philosophy. One of the earliest recorded instances appears in a satirical poem attributed to Xenophanes of Colophon (circa 570–475 BCE). Xenophanes, in his critique of Homer's anthropomorphic portrayal of the gods, noted that if horses and oxen possessed the capacity for artistic representation, they would depict their gods with equine and bovine features, respectively. Since the gods cannot simultaneously possess both human and animal forms, Xenophanes argued, attributing human-like flaws to them is also suspect. This, in essence, is a reductio argument: the assumption that gods have human faults leads to a contradiction when considering alternative, equally plausible, representations.

Greek mathematicians also wielded reductio ad absurdum to prove foundational propositions. Figures like Euclid of Alexandria (mid-4th – mid-3rd centuries BCE) and Archimedes of Syracuse (circa 287 – circa 212 BCE) are early exemplars of this practice.

The earlier dialogues of Plato (424–348 BCE), particularly those featuring Socrates, elevated the use of reductio arguments into a formal method of dialectic, known as the elenchus or the Socratic method. Typically, Socrates would engage an interlocutor who made a seemingly straightforward assertion. Through a series of carefully crafted questions and logical steps, drawing upon the interlocutor's own background assumptions, Socrates would guide them to admit that their initial assertion led to an absurd or contradictory conclusion. This forced the interlocutor to abandon their original position and often resulted in a state of aporia – a state of perplexity or uncertainty.

The elenctic refutation, as it functions in the Socratic dialogues, relies on a dichotomous thesis, one that can be divided into two mutually exclusive parts. Socrates would then proceed to demonstrate the falsity of the commonly held part by proving its negation, all while adhering to the law of non-contradiction. According to the scholar Gregory Vlastos, the Socratic method, when used for refutation, generally followed these steps:

Socrates' interlocutor posits a thesis, for instance, "Courage is endurance of the soul." Socrates, believing this to be false, targets it for refutation.
Socrates then elicits agreement from the interlocutor on additional premises, such as "Courage is a fine thing" and "Ignorant endurance is not a fine thing."
Through further reasoning, Socrates, with the interlocutor's assent, shows that these additional premises logically imply the negation of the original thesis, leading to the conclusion: "courage is not endurance of the soul."
Finally, Socrates declares that he has successfully demonstrated the falsity of the interlocutor's thesis and, by implication, the truth of its negation.

The technique also received significant attention from Aristotle (384–322 BCE). In his work Prior Analytics, he referred to it as demonstration to the impossible (in Ancient Greek: ἡ εἰς τὸ ἀδύνατον ἀπόδειξις, literally 'demonstration to the impossible', 62b).

Another pertinent example is the sorites paradox. This paradox presents a scenario where it's argued that if a million grains of sand constitute a heap, and removing a single grain from a heap still leaves it a heap, then by extension, even a single grain of sand, or no grains at all, should logically form a heap. The absurdity of this conclusion prompts scrutiny of the premise.

Buddhist Philosophy

A significant portion of Madhyamaka Buddhist philosophy is dedicated to demonstrating how various essentialist viewpoints collapse into absurd conclusions when subjected to reductio ad absurdum arguments. In Sanskrit, this method is known as prasaṅga, meaning "consequence." In the Mūlamadhyamakakārikā, Nāgārjuna employs reductio ad absurdum to dismantle theories of substance or inherent essence. He argues that phenomena, whether change, causality, or sense perception, are ultimately empty (śūnya) of any essential existence. Nāgārjuna's primary objective, as understood by many scholars, was to refute the essentialism espoused by certain Buddhist Abhidharma schools (notably the Vaibhasika), which posited theories of svabhāva (essential nature). He also targeted Hindu schools like Nyāya and Vaiśeṣika, which advocated for a theory of ontological substances (dravyatas).

Example from Nāgārjuna's Mūlamadhyamakakārikā

In chapter 13, verse 5, Nāgārjuna aims to illustrate the consequences that arise from the presumption of inherent existence. He posits that if a "young man" exists intrinsically, then he cannot grow old, because to do so would mean he is no longer a "young man." By attempting to separate the man from his defining characteristic (youth), we find that everything is subject to constant change. This leaves us with nothing beyond a conventionally assigned designation, highlighting the emptiness of inherent existence. The verse reads:

A thing itself does not change. Something different does not change. Because a young man does not grow old. And because an old man does not grow old either.

Nāgārjuna's point here is that if we assume things have an inherent, unchanging nature, we run into logical paradoxes. The "young man" cannot become old if his youth is an inherent, immutable quality. Conversely, an "old man" cannot be old if aging is a process of change that his inherent nature prevents. This forces us to question the very notion of inherent existence.

Modern Philosophy

Contemporary philosophers continue to employ reductio ad absurdum in their scholarly endeavors. Notable examples include:

Lewis White Beck, who utilized the argument in his critique of mechanism in his 1974 work, The Actor and the Spectator.
Robert L. Holmes, who applied reductio ad absurdum to challenge deterrence theory from a deontological perspective, specifically concerning the prima facie presumption against killing innocent life, in his 1989 book, On War and Morality.

Principle of Non-Contradiction

Aristotle provided a crucial clarification of the link between contradiction and falsity through his principle of non-contradiction. This principle asserts that a proposition cannot be simultaneously true and false. In formal terms, a proposition Q and its negation ¬Q cannot both hold true. Consequently, if a premise logically leads to both Q and ¬Q, it must be that the premise itself is false. This deduction, known as indirect proof or proof by contradiction, forms the bedrock of reductio ad absurdum arguments in fields like logic and mathematics.

Formalization

The principle can be formally expressed in propositional logic as the formula ¬¬P ⇒ P, which is logically equivalent to (¬P ⇒ ⊥) ⇒ P. This translates to: "If assuming P to be false leads to a falsehood (⊥), then P must be true."

In the system of natural deduction, this principle is embodied in the rule of inference:

\cfrac{\vdash \lnot \lnot P}{\vdash P}

This reads: "If we have proven ¬¬P (double negation), then we can conclude P."

In sequent calculus, the principle is represented by the sequent:

\Gamma, \lnot \lnot P \vdash P, \Delta

This signifies that if the hypotheses Γ and ¬¬P are assumed, then the conclusion P or Δ can be derived.

Justification

In classical logic, the validity of ¬¬P ⇒ P can be readily confirmed by examining its truth table, where it consistently evaluates to True, making it a tautology:

P	¬P	¬¬P	¬¬P ⇒ P
T	F	T	T
F	T	F	T

Another method of justification involves deriving it from the law of the excluded middle. Assuming ¬¬P, we want to prove P. The law of excluded middle states that either P is true or ¬P is true.

If P is true, then we have successfully established P.
If ¬P is true, then applying the law of noncontradiction to ¬P and the assumed ¬¬P yields a falsehood. The principle of explosion then allows us to conclude P from a falsehood.

In both cases, P is established. Conversely, proof by contradiction can be used to derive the law of excluded middle itself, demonstrating their deep connection.

In the context of classical sequent calculus LK, proof by contradiction can be derived from the inference rules governing negation:

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

This sequence of inference rules shows how ¬¬P ⇒ P can be derived within the system.

Relationship with Other Proof Techniques

Refutation by Contradiction

Proof by contradiction shares a close kinship with refutation by contradiction, also known as proof of negation. The latter establishes ¬P as follows:

The proposition to be proved is ¬P.
Assume P.
Derive a falsehood.
Conclude ¬P.

In contrast, proof by contradiction proceeds as outlined earlier:

The proposition to be proved is P.
Assume ¬P.
Derive a falsehood.
Conclude P.

Formally, these are distinct. Refutation by contradiction is specifically applied when proving a negated statement, whereas proof by contradiction can be used for any proposition. However, in classical logic, where P and ¬¬P are considered interchangeable, this distinction often becomes blurred. Consequently, in standard mathematical practice, both methods are frequently referred to simply as "proof by contradiction."

Proof by Contradiction in Intuitionistic Logic

In intuitionistic logic, the principle of proof by contradiction is not universally accepted as valid, though certain specific instances can be derived. However, proof of negation and the law of non-contradiction remain intuitionistically valid.

The Brouwer–Heyting–Kolmogorov interpretation of logical systems offers insight into the intuitionistic view. According to this interpretation, a proof by contradiction is valid only if there exists a method to establish that a proposition is false, which then implies there is a method to establish that the proposition is true. However, this interpretation faces challenges when "method" is equated with algorithm. If this were the case, it could lead to the ability to solve the Halting problem. For instance, consider the statement H(M), asserting that a Turing machine M halts or does not halt. Its negation, ¬H(M), would mean "M neither halts nor does not halt," which is a contradiction by the intuitionistically valid law of non-contradiction. If proof by contradiction were universally valid in intuitionistic logic, we could derive an algorithm to decide whether any given Turing machine halts, thus violating the intuitionistically proven non-solvability of the Halting problem.

A proposition P that satisfies ¬¬P ⇒ P is termed ¬¬-stable. In intuitionistic logic, proof by contradiction is generally restricted to such ¬¬-stable propositions. Decidable propositions, those satisfying P ∨ ¬P, are a prime example of ¬¬-stable propositions. The proof demonstrating that the law of excluded middle implies proof by contradiction can be adapted to show that any decidable proposition is ¬¬-stable. Statements verifiable by direct computation, such as "n is prime" or "a divides b," are typical examples of decidable propositions.

Examples of Proofs by Contradiction

Euclid's Elements

An early and elegant instance of proof by contradiction can be found in Euclid's Elements, specifically in Book 1, Proposition 6:

"If in a triangle two angles equal one another, then the sides opposite the equal angles also equal one another."

Euclid's proof proceeds by assuming the opposite – that the sides are not equal – and then, through a series of logical steps, derives a contradiction, thereby establishing the truth of the original proposition. This strategy is employed in numerous other proofs within Euclid's Elements, including Book 7, Proposition 33, which deals with the properties of inscribed hexagons and decagons.

Hilbert's Nullstellensatz

David Hilbert provided an influential proof by contradiction for his famous Nullstellensatz. The theorem states:

"If polynomials $f_1, \ldots, f_k$ in $n$ indeterminates with complex coefficients have no common complex zeros, then there exist polynomials $g_1, \ldots, g_k$ such that $f_1g_1 + \ldots + f_k g_k = 1$ ."

Hilbert's proof method involved assuming that no such polynomials $g_1, \ldots, g_k$ exist and then demonstrating that this assumption leads to a contradiction.

Infinitude of Primes

Euclid's theorem, which asserts the infinitude of prime numbers, is a cornerstone of number theory. In Euclid's Elements, Book IX, Proposition 20, the theorem is stated as:

"Prime numbers are more than any assigned multitude of prime numbers."

Depending on the precise formalization of this statement, the standard proof can be presented as either a proof by contradiction or a refutation by contradiction. Let's examine it as a proof by contradiction.

To formally express Euclid's theorem as "for every natural number $n$ , there exists a prime number greater than $n$ ," we can employ proof by contradiction. Given any natural number $n$ , we aim to prove the existence of a prime larger than $n$ . We begin by supposing the contrary: that no such prime exists. This implies that all prime numbers are less than or equal to $n$ . We can then construct a list of all such primes: $p_1, \ldots, p_k$ . Let $P = p_1 \cdot \ldots \cdot p_k$ be the product of all these primes, and consider the number $Q = P + 1$ .

Now, $Q$ is demonstrably larger than any prime in our list. If $Q$ itself is prime, then we have found a prime larger than $n$ , contradicting our initial assumption. If $Q$ is not prime, it must have a prime factor, let's call it $p_i$ . This prime factor $p_i$ must be one of the primes in our original list, as we assumed that list contained all primes. However, if $p_i$ divides $P$ (by definition of $P$ ) and $p_i$ also divides $Q = P + 1$ , then $p_i$ must also divide their difference, $Q - P = 1$ . But 1 is not divisible by any prime number. This is a contradiction. Therefore, our initial supposition that no prime number exists greater than $n$ must be false. Hence, there must be a prime number larger than $n$ .

Examples of Refutations by Contradiction

The following examples are often referred to as proofs by contradiction, but they formally employ refutation by contradiction. This distinction is significant because refutation by contradiction is considered intuitionistically valid.

Infinitude of Primes (Alternative Formulation)

Let's revisit Euclid's theorem – Book IX, Proposition 20 – from a slightly different angle. Instead of asserting "for every $n$ , there is a prime greater than $n$ ", we can interpret the statement as "for any finite list of prime numbers, there exists a prime not on that list." This interpretation is arguably closer to Euclid's original phrasing and directly lends itself to refutation by contradiction.

Given any finite list of prime numbers $p_1, \ldots, p_n$ , we aim to show that at least one additional prime number, not present in this list, must exist. Let $P = p_1 \cdot p_2 \cdots p_n$ be the product of all the primes in the given list. Now, consider the number $P + 1$ . Let $p$ be any prime factor of $P + 1$ . We claim that this prime factor $p$ cannot be any of the primes $p_1, \ldots, p_n$ in our original list.

Suppose, for the sake of contradiction (this is the refutation step), that $p$ is in the list, say $p = p_i$ for some $i$ . Then $p_i$ divides $P$ (since $P$ is the product of all primes in the list, including $p_i$ ). Also, by definition, $p_i$ divides $P + 1$ . If a number divides two other numbers, it must also divide their difference. Therefore, $p_i$ must divide $(P + 1) - P = 1$ . However, no prime number can divide 1. This is a contradiction. Thus, our supposition that $p$ is in the list must be false. This means $p$ is a prime number not found in the original list $p_1, \ldots, p_n$ . Hence, there is always a prime number beyond any given finite list of primes.

Irrationality of the Square Root of 2

The classic proof that the square root of 2 is irrational is a quintessential example of refutation by contradiction. The proof begins by assuming the opposite of what we want to prove: that $\sqrt{2}$ is rational. This means we assume there exist natural numbers $a$ and $b$ such that $a/b = \sqrt{2}$ . From this assumption, we derive a contradiction, thus proving that $\sqrt{2}$ must be irrational.

The proof proceeds by showing that if $\sqrt{2}$ can be expressed as a fraction $a/b$ , then it can be expressed as a fraction $c/d$ where both $c$ and $d$ are odd numbers. Squaring both sides of $a/b = \sqrt{2}$ gives $a^2/b^2 = 2$ , or $a^2 = 2b^2$ . This implies $a^2$ is an even number, and therefore $a$ must also be even. If $a$ is even, we can write $a = 2k$ for some integer $k$ . Substituting this back into the equation gives $(2k)^2 = 2b^2$ , which simplifies to $4k^2 = 2b^2$ , or $2k^2 = b^2$ . This means $b^2$ is also an even number, and therefore $b$ must be even as well. So, we have concluded that both $a$ and $b$ are even. This contradicts the initial condition that the fraction $a/b$ was in its simplest form (where $a$ and $b$ share no common factors, meaning they cannot both be even). Since the assumption that $\sqrt{2}$ is rational leads to a contradiction, it must be irrational.

Proof by Infinite Descent

Proof by infinite descent is a specific type of proof that relies on refutation by contradiction. It works by assuming that a smallest object with a particular property exists, and then demonstrating that an even smaller object with the same property must also exist. This creates an infinite sequence of ever-smaller objects, which is impossible for objects that must be positive and discrete (like integers). This leads to a contradiction, proving that no such smallest object can exist.

A common illustration of this is the proof that there is no smallest positive rational number. We assume there is such a smallest positive rational number, $q$ . However, the number $q/2$ is also a positive rational number, and it is clearly smaller than $q$ . This contradicts the assumption that $q$ was the smallest. Therefore, no smallest positive rational number exists. This is essentially a refutation by contradiction.

Russell's Paradox

Russell's paradox, famously formulated in set theory as "there is no set whose elements are precisely those sets that do not contain themselves," is typically proven using refutation by contradiction. The proof involves assuming such a set exists and then showing that this assumption leads to a contradiction regarding whether the set contains itself.

Notation

Proofs by contradiction sometimes conclude with the emphatic word "Contradiction!". Historically, notations like Q.E.A. (for quod est absurdum, "which is absurd"), similar to the ubiquitous Q.E.D., were used by figures like Isaac Barrow and Baermann, though these are not common today. Visual symbols for contradictions have also been employed, such as a downward zigzag arrow (↯) or pairs of opposing arrows (→← or ⇒⇐). Some texts use a stylized hash symbol (⨳) or a reference mark (※), while others might use a double-strike 'x' (×!!×).

Automated Theorem Proving

In the field of automated theorem proving, the method of resolution is fundamentally based on proof by contradiction. To demonstrate that a given statement logically follows from a set of hypotheses, an automated prover typically assumes the hypotheses along with the negation of the statement. The prover then attempts to derive a contradiction from this combined set of assumptions.