NOTE: This article or section is (sadly) a serious treatment of the subject matter. Unlike most of RationalWiki, it lacks sarcasm, satire, or humor in general. \pagecolor{LimeGreen}\begin{align}3x-5y&=6\\2x+4y&=2\\x=? \; y&=?\end{align} This article/section deals with mathematical concepts appropriate for a student in mid to late high school.

Mathematical paradoxes are statements that run counter to one's intuition, sometimes in simple, playful ways, and sometimes in extremely esoteric and profound ways. It should perhaps come as no surprise that a field with as rich a history as mathematics should have many of them. They range from very simple, everyday common-sense issues, to advanced ones at the frontiers of mathematics. That is why this article has so many "expertise level" boxes above.

Perhaps the most well-known paradox is the Liar paradox:

 “”The statement below is true.
 “”The statement above is false.

These are sometimes written on two sides of a card ("The statement on the other side is true." / "The statement on the other side is false.") so that one can watch a person turn the card over and over.

The lesson of this one is clear: The fact that a sentence makes a statement doesn't mean that statement is true. (Of course, that's a good thing to be aware of in general.)

This paradox relates to several others, that are actually quite profound, such as the Gödel Incompleteness Theorem. This is because it goes to the heart of what it means for a sentence to "mean" something.

Consider the number described by the phrase

 “”The square root of thirty-six

Phrases can denote numbers clearly and unambiguously, can't they? Now consider this one

 “”The smallest natural number that cannot be described by a phrase shorter than one hundred letters

The number of phrases shorter than 100 letters is finite. In fact, it can't exceed 27100. (The 27 allows for the placement of spaces between words. Using larger character sets will increase the maximum possible numbers, for example, to 34100 with Russian Cyrillic alphabets) So the set of integers that can be described by such phrases must be finite. (It's actually much less than 27100—"Elementary, my dear Watson" does not denote a number.) But there are an infinite number of natural numbers (positive integers) so it's not hard to see that there must be a first number not in that set. But that number, whatever it is, has been correctly described by the phrase quoted above, which is shorter than 100 letters!

The lessons of this one are

• Arithmetic, even simple integer arithmetic, can be tricky.
• What it means for a phrase to "denote" a number is not well defined.

Once again, what it means for something to "mean" something can be very slippery.

Paradoxes of set theory

Mathematicians' attempts to formalize the subject in a really careful way have led to set theory, which can be an extremely advanced subject. But even a simple everyday notion of set theory leads to this paradox:

 “”The town barber, who is a man, shaves exactly every man in the town who does not shave himself.

So does the barber shave himself, or not?

The lesson of this is that what it means for something to be in a set is tricky, and what it means for a sentence to make a statement about set membership is tricky. Once again, "meaning" (also known as "semantics") comes into question.

A much more advanced paradox along these lines, perhaps the best known of all paradoxes, is the Russell paradox (Bertrand Russell, 1872–1970). When one formalizes mathematics in an incredibly careful way, as Russell, Whitehead and others did in the 1930s, everything is a set. Yes, every mathematical object is a set. And, for any yes/no question you could ask about things, those things for which the answer is "yes" comprise a set, as do those for which the answer is "no".

If one is given free rein to do anything at all in set theory, a set could contain itself. (Though most sets don't.) The Russell paradox concerns

• The set of all sets which do not contain themselves.

Obviously, there's a problem with this. Does this set contain itself, or not? The lessons are

• Set theory is really very complicated.
• We can't allow set theorists free rein to do just anything.

Mathematicians have created the Zermelo-Fraenkel axioms to formalize set theory so that these problems won't arise.

Mathematicians of the 1930s attempted to formalize logic itself very rigorously, that is, what it means to "prove" a "theorem". Given how hard it is to ascribe "meaning" to "meaning", it isn't surprising that an amazing problem arose: the Gödel Incompleteness Theorem.

First, mathematicians had to establish in a very rigorous and profound way what it means for a proposition to be "true" or "false", and what it means for something to be a "valid proof" of such a thing. Once that was done, the "Holy Grail" of logic came into view: Can we say that, for every proposition whose truth or falsity is well defined, that either

• It is true, and there is a proof that it is true.

or

• It is false, and there is a proof that it is false. ?

The search for this "Holy Grail" is not new. In the 1600s, Gottfried Wilhelm Leibniz expressed a desire to be able to answer any question (mathematical or otherwise!) by logical analysis, deduction, and calculation.

It was not to be. The Gödel Incompleteness Theorem says that it is not possible to formulate consistent laws of logic such that, for every well-formed statement, there is either a proof that it is true or a proof that it is false.

This theorem is related to a theorem of computer science: Even under an ideal formulation of what a computer can do, it is not possible for a computer program to be able to examine every other computer program and say with certainty whether any given program will halt or go on forever. This is known as the "halting problem".

Paradoxes of analysis and measure theory

When one has studied advanced analysis (that is, calculus), topology, and, especially, measure theory, one can see many paradoxical things. Some of these involve the Cantor set and Cantor function. The Cantor set (briefly defined as those real numbers between 0 and 1 whose representation in base 3 contains only 0's and 2's) is an uncountable set of measure zero. While not paradoxical in itself, it is a rather unexpected result. The Cantor function is a function such that f(0) = 0, f(1) = 1, f is continuous everywhere, and f is differentiable, with derivative zero, "almost everywhere", that is, except on a set of measure zero. This would violate the Mean Value Theorem if that theorem actually applied.

The lesson here is that one's intuition about what things should look like can be very misleading at advanced levels.

Measure theory provides some interesting paradoxes. By the time one has studied advanced calculus and topology, one has seen many very strange sets. Measure theory attempts to assign a "geometrical size" to sets. Of course, we want the measure of a simple set to match our intuition—in one dimension the interval [-4, 5] should have a measure of 9. In two dimensions, the set of all points with $x^2 + y^2 \le 1$ is the unit circle and has measure $\pi$, and so on. We want the measure of the union of non-overlapping sets to be the sum of those sets' measures, and so on. Lebesgue measure (rhymes with vague; and the s is silent) is the accepted theory of measure. It is compatible with common intuition for sets that fall under common intuition. But not all sets are Lebesgue-measurable.

In addition to the seemingly paradoxical existence of non-Lebesgue-measurable sets, there are some more serious paradoxes. Perhaps the most famous is the Banach-Tarski paradox. This says that a sphere in 3 dimensions can be divided into a finite number of subsets (specifically, 5) which, without changing their shapes or sizes, can be reassembled into two spheres, each identical to the original one. This of course violates everything we thought we knew about what "measure" is supposed to mean. The way the paradox gets away with this trick is that the sets are not measurable.

The lesson here is that, when dealing with complicated sets such as may arise in advanced analysis, geometrical intuition can fail badly. And that non-measurable sets (a price one must pay for advanced analysis and topology) are particularly suspect.

The axiom of choice

The axiom of choice (AC) is fairly easy to state at a simple level, but actually very advanced to understand properly. At a superficial level, there doesn't seem to be anything harmful about it (making a choice isn't controversial—proofs say things like "let x be a number < y" all the time, and handling infinities of such things shouldn't be harmful, should it?) In fact the vast majority of mathematical theorems don't require this choice in its infinite form.

Mathematicians have been concerned about it for some time, wondering whether it can be proven from the axioms of Zermelo-Fraenkel (ZF) set theory. In 1962 it was shown to be independent of ZF, and the axiom system of ZF with the additional assumption of the axiom of choice is called ZFC.

Many mathematicians generally prefer proofs that do not require AC, on the grounds that such proofs are more "clean". But others are not concerned about this, and find that the greater elegance and generality that it provides in statements and proofs of theorems is worth it. For example, with AC, we have the extremely simple theorem "every vector space has a basis". Without AC, the theorem has various messy qualifications on it. Now does this mean that there are vector spaces that "shouldn't" have bases, and that AC was wrong in giving them bases? In practice, it doesn't matter. No use of AC leads to results that are "wrong" in practice.

The axiom of choice is used in the construction of non-Lebesgue-measurable sets, such as the ones in the Banach-Tarski paradox. Does this mean that AC makes the paradox happen? No. The paradox doesn't actually "happen" in any constructive sense. You can't actually carve up a sphere in the required way in practice, with or without AC. Even without AC, Lebesgue meaure theory allows for the existence, on an abstract level, of non-measurable sets, and hence it potentiates the Banach-Tarski paradox. It just doesn't say how to produce those sets. AC says how to produce them, but in a totally abstract way.

The lesson here is that what you can't see can be extremely annoying mystifying.