Within the mathematics community there exists a group of people who adhere to something called constructivism; the suspicion that, for whatever reason (safety, utility, comfort) mathematicians should adhere to using only constructive proofs.

While this is not necessarily a widely held view (many are antagonistic toward it because it seems to impose some rather strict limitations on what can actually be proven), it's worth looking in to!

We've already seen that proof-by-contradiction, a technique widely utilized in mathematical proofs, seems to be based on some shakey ground. This is because it is non-constructive; the proof itself does not tell us how to "build" the object that it claims exists.

Let's do an example. Suppose I want to prove that there exists two irrational numbers, call them a and b, such that a^b is rational. You might be unsure if such numbers actually exist.

We know that root(2) is irrational (the proof of that is quite easy, I can show you), and 2 is obviously rational. Consider root(2)^root(2).

If it's rational, then we're done. Huzzah!
If it's irrational, try again: say a is root(2)^root(2), and b is root(2). Do some simplification...

One of these must be rational!

But notice two things:
We don't actually know which of these is rational! and
We had to assume every number is rational, or irrational.

Growing off of this, there are all sorts of "Proofs" in mathematics that are actually non-constructive. Perhaps the most famous criminal is the Axiom of Choice.

The Axiom of Choice was formulated in 1904 buy one Ernst Zermelo (beardless, yet handsome visage pictured at right), but was by no means first used by him. Informally, it says:

Given any collection of bins containing at least one object each, it's possible to pick exactly one object from each bin, even if there are infinitely many bins and there's no "rule" for which object to pick.

Seems reasonable, right? Well, obviously, this isn't a proof, and there's no real "proof" for this; that's why it's an axiom. You either take it, and use it, or you don't.

Most mathematicians now-a-days use the axiom of choice with very little problem. But you see, it's not a proven statement, and some weird things can happen if you allow the axiom of choice.

For example, there's the Banach-Tarski Paradox.

A solid ball in 3-dimensional space can be split into a finite number of non-overlapping pieces, and can be put back together to make TWO identical copies of the original ball.

WTF, right?

But there are plenty of useful and important theorems that are only provable if you "take" the axiom of choice. So most mathematicians use it. Any proof using the axiom of choice becomes non-constructive, though.

Probably the most... forceful detractor of constructivism was David Hilbert, who said "Taking the principle 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."

Why is this important? Well, increasingly, the value of constructivism is being recognized on non-ideological grounds.

Say you're trying to use a computer system to, I don't know, prove that the software running in your airplane is "safe," or at least mathematically valid. There are indeed computer systems out there that will allow you to write, formally, "contracts" that describe the behavior of your system (assumptions). From those, you want to derive the conclusion that the system is coherent. If you use constructive logic, you can actually, definitively say that the system is safe. If you use non-constructive logic... well, it's hard to say.

That's kind of an initial overview. It's deeper than that, of course, but now you're at least introduced to it, and you know why negation kind of makes mathematicians get philosophical.
Allons-y! Back to CIS160 Page