Something from nothing?

"You can take it or leave it" is a phrase we use purely for effect. It's obvious that the person we're talking to is either going to take it or leave it — what else can they do? — so in terms of information content, the phrase is useless. It's an example of a logical tautology: something that is always true, no matter the circumstance. That's probably why the phrase is so annoying.

Proving things non-cnostructively is a bit like pulling a rabbit out of a hat.

Curiously, mathematicians frequently draw meaning from such vacuous tautologies. The phrase above is of the form P OR NOT P, where P is some statement ("you can take it") and NOT P is its negation ("you can not take it"="you can leave it"). According to the classical rules of logic, such a statement is always true — put differently, if P is true then NOT P is false and vice versa.

This so-called law of the excluded middle allows mathematicians to perform logical magic. Suppose you want to show that some statement P is true. If you can show that NOT P is definitely false, then P has no choice but being true and you're done. You have proved the statement P without necessarily getting your hands dirty with the details of P. The technique is called a proof by contradiction, or reductio ad absurdum to use the Latin description.

If this sounds confusing, here is an example. A prime number is a natural number that is only divisible by itself and 1. The first few primes are 2, 3, 5, and 7. The primes are like building blocks for all the natural numbers, because every natural number that is not itself a prime can be written as a product of primes in a unique way. For example, 24 = 2x2x2x3.

We are going to prove that there are infinitely many prime numbers using a proof by contradiction. Suppose there are only finitely many and label them $p_1$ , $p_2$ , $p_3$ , up to $p_ n$ . Now consider the number

$p=p_1p_2...p_ n+1.$

Because it’s different from all the $p_1$ up to $p_ n$ , and these are all the primes there are, it cannot itself be a prime. But then, as we have noted above, it must be a product of primes. This means that one of our $p_1$ up to $p_ n$ must divide it. But since the $p_1$ up to $p_ n$ divide $p-1=p_1p_2...p_ n$ , they can’t possibly divide $p$ as well. This is a contradiction. Hence, the statement that there are only finitely many primes is false. Therefore, its negation, that there are infinitely many primes must be true. Here the statement P is "there are infinitely many primes" and NOT P is "there are finitely many primes".

Depending on your preference, you might find this an elegant argument, or you might feel a little cheated. OK, so there are infinitely many primes, but what are they? How do you find them? Our proof is an example of a non-constructive proof, which shows that something exists without actually constructing it.

Mathematics, as it is accepted by most people, relies heavily on non-constructive proofs and proofs by contradiction. As the famous mathematician David Hilbert remarked in 1928, "Taking the law of the excluded middle from the mathematician would be the same, say, as proscribing the telescope to the astronomer or to the boxer the use of his fists."

Should all of mathematics be explicitly constructed?

Some people believe, however, that logically such proofs live on thin ice. The proofs purport to show that something exists (or is true) by showing that it can't possibly not exist (or be false). Is that really as convincing as proving that it exists by actually constructing it? A school of thought called constructivism believes that it isn't, and that we should only deal with mathematical objects that we can get our heads around in a concrete way. There should be a recipe, an algorithm, for calculating all the properties of the object in question. To borrow a phrase from the US mathematician Errett Bishop, everything in mathematics should have "numerical meaning".

Constructivists reject the law of the excluded middle. To them, a statement of the form P OR NOT P is only true when we know for certain that one of P or NOT P is true. Until we have proved, constructively, that there are infinitely many primes or that there are finitely many primes, the statement "either there are infinitely many primes or finitely many primes" means nothing, and we certainly can't base a proof on it.

What does this constructivist stance mean for mathematics as whole? Our prime number proof from above can quite easily be saved: there’s a version that isn’t based on contradiction. Given any finite list of prime numbers label them $p_1$ , $p_2$ , $p_3$ , up to $p_ n$ . Form the number

$p=p_1p_2...p_ n+1$

and find all its prime factors (if $p$ is itself a prime, then it’s the only number in its prime factorisation). The primes $p_1$ , $p_2$ , $p_3$ , up to $p_ n$ cannot appear in the prime factorisation of $p$ because they divide $p-1$ and therefore don’t divide $p.$ Thus, the prime factorisation of $p$ provides us with at least one prime not on the original list. You can now repeat the process including the new prime(s) in your list to find yet more new prime(s). And so on. In this way, you can generate infinitely many primes.

Can all proofs in mathematics be rewritten in a constructive way so easily? We examine this question, as well as the ins and outs of constructivism, in this article.

About this article

Marianne Freiberger is Editor of Plus.

This article is part of our Who's watching? The physics of observers project, run in collaboration with FQXi. Click here to see more articles about constructivism.

Something from nothing?

About this article

Comments

Small mistake

Oh dear, thanks for pointing

Typo