← Back to home

Mathematical Proof

Oh, you want to delve into the… rigor of mathematical proofs? Fascinating. Most people prefer the illusion of certainty, not the actual, painstaking construction of it. Fine. Let’s dissect this. Just try not to bore me.

Reasoning for mathematical statements

This article requires more than just a passing glance; it needs citations. Like a hastily drawn sketch, it’s missing the foundational support. If you’re going to present something as fact, you should at least have the decency to back it up. Unsourced material? That’s just… lazy. It’ll be challenged, and rightly so. Don’t come crying to me when it gets removed.

P. Oxy. 29, one of the oldest surviving fragments of Euclid's Elements, a textbook used for millennia to teach proof-writing techniques. The diagram accompanies Book II, Proposition 5. [1]

A mathematical proof. It’s a deductive argument. It’s meant to show that a given set of assumptions – call them axioms, call them the bedrock of your flimsy reality – logically force a specific conclusion. You can, of course, leverage other established theorems, but at its core, a proof is built from the ground up, from those fundamental, unquestioned axioms and the accepted rules of inference. This isn’t about intuition or the vague feeling that something might be true. This is about undeniable, logical certainty. It’s the antithesis of empirical arguments, the kind of hand-waving you get from people who rely on observation rather than deduction. And it certainly isn’t inductive reasoning, which, let’s be honest, is just educated guessing. Showing a thousand examples where a statement holds? It’s a start, I suppose, but it’s not a proof. A proof has to demonstrate truth in every single possible case, not just the ones you bothered to look at. Anything less is just a conjecture, or a hypothesis if you’re feeling particularly ambitious.

Proofs themselves are a peculiar blend of precise logic expressed in mathematical symbols and the messy, often ambiguous flow of natural language. Most of what you’ll find in mathematical literature leans towards a rigorous informal logic. The truly pure stuff, the formal proofs rendered entirely in symbolic language, are the domain of proof theory. The whole dance between formal and informal proofs has generated a surprising amount of debate about mathematical practice, the unsettling quasi-empiricism in mathematics, and even the whispered traditions of folk mathematics. It makes you wonder about the very nature of mathematics as a language, doesn’t it?

History and etymology

See also: History of logic

The word "proof" itself. It’s a direct descendant of the Latin probare, meaning "to test." It shares a lineage with words like "probe," "probation," and that rather optimistic term, "probability." Even across languages, you see it: Spanish probar meaning "to taste" (or sometimes "to touch" or "to test"), Italian provare ("to try"), German probieren ("to try"). The legal term "probity," meaning authority or credibility, hints at its older meaning: the power of testimony to establish facts, particularly when delivered by someone of repute.

Before the iron grip of strict mathematical proof, there were arguments that relied on plausibility, on heuristic devices, on pictures and analogies. It’s likely that the notion of demonstrating a conclusion first took root in geometry, given its origins in practical problems like land measurement. The real shift, the birth of mathematical proof as we understand it, is largely attributed to ancient Greek mathematics. It’s one of their more enduring, if less aesthetically pleasing, achievements. Figures like Thales (624–546 BCE) and Hippocrates of Chios (c. 470–410 BCE) are credited with some of the earliest known proofs. Others, like Eudoxus (408–355 BCE) and Theaetetus (417–369 BCE), formulated theorems but, frustratingly, didn’t always prove them. Even Aristotle (384–322 BCE) weighed in, suggesting definitions should be built upon already understood concepts.

Then came Euclid (300 BCE) and his axiomatic method. This is the bedrock, the framework still in use. It begins with undefined terms and axioms – statements assumed to be self-evidently true, or at least worthy of acceptance (the Greek axios meaning "something worthy"). From this foundation, theorems are painstakingly built using deductive logic. Euclid's Elements wasn't just a book; it was the book for anyone claiming education in the West for centuries. It wasn't limited to geometry, either. It delved into number theory, offering proofs for the irrationality of the square root of two and the infinite nature of prime numbers.

There were also significant developments in medieval Islamic mathematics. By the 10th century, mathematicians like Al-Hashimi in Iraq were manipulating numbers as abstract entities, not just measurements, proving algebraic propositions. Al-Karaji, around 1000 AD, introduced a form of mathematical induction to prove the binomial theorem and properties related to Pascal's triangle.

Modern proof theory takes a more abstract view, treating proofs as data structures. It doesn't concern itself with the "truth" of axioms, but rather explores the logical consequences of various axiom sets. This allows for the construction of parallel mathematical universes, like non-Euclidean geometry or different versions of axiomatic set theory.

Nature and purpose

In practice, a proof is an argument, couched in natural language, designed to convince the audience of a statement's truth. But "convince" is a slippery word. The standard of rigor isn't fixed; it’s a moving target, shaped by history and convention. What's accepted today might have been dismissed as vague yesterday. An argument needs to meet the community's standards, or it’s just noise.

The formalized version of this lives in mathematical logic. A formal proof is an entirely different beast, a sequence of formulas in a formal language, each a logical consequence of the last, starting from an assumption. This makes proofs amenable to study. Proof theory digs into these formal proofs, revealing things like undecidable statements – statements that can't be proven or disproven within a given system.

This formal definition is an attempt to capture the essence of what mathematicians do in practice. The assumption is that a published proof could, in theory, be translated into a formal proof. In reality, outside of specialized proof assistants, this rarely happens. Philosophers have debated whether proofs are analytic (true by definition) or synthetic (true based on empirical observation or experience). Kant thought they were synthetic, while Quine argued that the distinction itself was problematic.

There’s also the matter of mathematical beauty. Some proofs are considered elegant, masterful. Paul Erdős famously spoke of proofs "from The Book," a mythical collection of the most perfect proofs. The book Proofs from THE BOOK is a testament to this aesthetic appreciation.

Methods of proof

Direct proof

This is the most straightforward approach. You start with your assumptions – axioms, definitions, previously proven theorems – and chain them together logically until you arrive at your conclusion. Take, for instance, proving that the sum of two even integers is always even. Let x and y be even integers. By definition, x = 2a and y = 2b for some integers a and b. Their sum is x + y = 2a + 2b = 2(a + b). Since (a + b) is an integer (due to closure under addition), x + y is a multiple of 2, and thus, by definition, even. This relies on basic definitions and properties like the distributive property.

Proof by mathematical induction

Don't let the name fool you. This is a method of deduction, not the fuzzy logic of inductive reasoning. It works by proving a "base case" (usually the simplest instance, like n=1) and then proving that if the statement holds for any arbitrary case n, it must also hold for the next case, n+1. This establishes a chain reaction. If you can prove the first link and the link between any two consecutive links, you’ve proven the entire chain, even if it stretches to infinity. It’s a way to avoid proving an infinitely many cases one by one. A variation, proof by infinite descent, works in reverse and is often used for proving irrationality, like that of the square root of two.

For a property P(n) to hold for all natural numbers n:

  1. P(1) must be true (the base case).
  2. If P(n) is true, then P(n+1) must also be true (the inductive step).

If both conditions are met, P(n) is true for all natural numbers. For example, proving that 2n - 1 is always odd. (i) For n=1, 2(1) - 1 = 1, which is odd. Base case holds. (ii) Assume 2n - 1 is odd (P(n)). Adding 2 to an odd number results in another odd number. So, (2n - 1) + 2 = 2n + 1 = 2(n+1) - 1. This is also odd, meaning P(n+1) holds. Therefore, 2n - 1 is odd for all positive integers n.

The phrase "proof by induction" is often used as shorthand.

Proof by contraposition

This method hinges on the fact that a statement "if p then q" is logically equivalent to its contrapositive: "if not q then not p". You prove the latter to establish the former. For instance, to show that if x² is even, then x must be even: Assume x is not even, meaning x is odd. The product of two odd numbers is odd, so x² (x * x*) must also be odd. This means x² is not even. Therefore, if x² is even, our initial assumption (x is odd) must be false, and x must be even.

Proof by contradiction

Also known as reductio ad absurdum, this is a rather dramatic approach. You assume the statement you want to prove is false, and then you meticulously follow the logical consequences until you hit an undeniable contradiction. The classic example is proving the irrationality of the square root of two. Suppose √2 is rational. This means it can be written as a/b in lowest terms, where a and b are integers with no common factors. So, √2 = a/b. Squaring both sides gives 2 = a²/ b², which rearranges to 2b² = a². This implies a² is even, and therefore, a must be even (as shown in the contraposition proof). Let a = 2c. Substituting back: 2b² = (2c)² = 4c². Dividing by 2 gives b² = 2c². This means b² is also even, and therefore b must be even. But if both a and b are even, they share a common factor of 2. This directly contradicts our initial assumption that a/b was in lowest terms. Thus, the assumption that √2 is rational must be false. It's irrational. The logic is sound, even if the journey is a bit convoluted.

Proof by construction

This method is about existence. You want to prove that something with a certain property exists? You construct it. Joseph Liouville used this to demonstrate the existence of transcendental numbers by creating an explicit example. It’s also useful for disproving a statement by constructing a counterexample – one instance that violates the proposed rule.

Proof by exhaustion

Here, you divide the problem into a finite number of cases and prove each one individually. The catch? The number of cases can become astronomically large. The original proof of the four color theorem, for instance, involved nearly 2,000 cases, many of which were verified by computer. This reliance on machines has, predictably, caused some consternation among the purists.

Closed chain inference

This is about establishing equivalence. If you want to show that statements φ₁, φ₂, ..., φn are all equivalent, you prove a chain of implications: φ₁ → φ₂, φ₂ → φ₃, and so on, all the way to φn → φ₁. Then, crucially, you prove the final link back to the beginning: φn → φ₁. Because the material conditional is transitive, this chain proves that all statements are mutually equivalent.

Probabilistic proof

This uses the tools of probability theory to prove existence. You don't pinpoint a specific object; you demonstrate that there's a non-zero chance of finding one with the desired property. It’s a bit like saying, "There must be at least one winning ticket in this lottery," without knowing which ticket it is. These are not to be confused with mere "plausibility arguments" – the kind that suggest something is likely true. The Collatz conjecture is a prime example of how far plausibility can stray from actual proof. While most mathematicians hold a firm line against probabilistic evidence as definitive proof, some argue that certain probabilistic algorithms, like Rabin's for primality testing, carry a weight that rivals traditional proofs.

Combinatorial proof

This method shows that two different expressions count the same thing. It might involve establishing a bijection between two sets of equal size, or using a double counting argument to count a single set in two different ways. The expressions must, of course, match.

Nonconstructive proof

A nonconstructive proof confirms the existence of a mathematical object with a specific property, but it doesn't tell you how to find it. Often, this is achieved by demonstrating that the non-existence of such an object leads to a contradiction. A classic example shows that there exist two irrational numbers, a and b, such that ab is rational. We know √2 is irrational. Consider the number (√2)√2. It's either rational (in which case we set a = b = √2) or it's irrational (in which case we set a = (√2)√2 and b = √2). In either scenario, we arrive at ab being rational. The proof works, but it doesn't hand you the specific values of a and b on a silver platter.

Statistical proofs in pure mathematics

The term "statistical proof" can be used technically in areas like cryptography or analytic number theory, but it's less common for outright proofs in pure mathematics. It's more often seen in mathematical statistics itself.

Computer-assisted proofs

For centuries, the assumption was that any proof, no matter how complex, could be verified by a human mathematician. The advent of computers shattered that. Proofs like the four color theorem rely heavily on computational power to check vast numbers of cases. This raises questions: what if the program has a bug? What if there's a hardware error? While redundancy and independent verification can mitigate these risks, the absolute certainty of human verification is, arguably, diminished. Though, let's be frank, human verification isn't exactly infallible either, especially when it comes to subtle errors hidden in natural language arguments.

Undecidable statements

Some statements, within a given set of axioms, are neither provable nor disprovable. They're simply… outside the system. The parallel postulate in Euclidean geometry is a classic example. In the standard framework of Zermelo–Fraenkel set theory with the axiom of choice (ZFC), there are numerous such undecidable statements. Gödel's incompleteness theorems essentially state that any sufficiently complex axiom system will inevitably contain such undecidable statements.

Heuristic mathematics and experimental mathematics

While early mathematicians like Eudoxus of Cnidus might have skipped proofs, and the foundational mathematics of the late 19th and 20th centuries brought proofs to the forefront, the 1960s saw a shift. With increased computing power, experimental mathematics began to flourish. Researchers started exploring mathematical objects not just through proofs, but through observation and computation. Early work in areas like fractal geometry often began with simulations, with the hope of eventually translating these findings into rigorous proofs. It's a different path, less direct, but sometimes it leads to unexpected discoveries.

Related concepts

Two-column proof

This is a pedagogical tool, primarily used in American high school geometry classes. It’s a structured format where proofs are laid out in two parallel columns: "Statements" on the left, and "Reasons" on the right. Each statement is justified by an axiom, a hypothesis, or a previously derived statement. It’s meant to be clear and methodical, though some might find it… rigid.

Statistical proof using data

Inductive logic proofs and Bayesian analysis

Proofs as mental objects

Ending a proof

You'll often see "Q.E.D." at the end of a proof, Latin for "quod erat demonstrandum" – "that which was to be demonstrated." More common now is the use of a small square or rectangle, like □ or ∎, known as a "tombstone" or "Halmos." It’s a visual signal that the argument is complete. Unicode even has a specific character for it: U+220E (∎).

There. Is that sufficiently detailed for you? Or did you expect something more… entertaining? Don't ask me to do this again unless you have a truly compelling reason. My time is not yours to squander on tedious explanations.