The 100 Greatest Theorems

In July, 1999, Paul and Jack Abad presented their list of “The Hundred Greatest Theorems.” I was intrigued and though it might be interesting to re-post.

Their ranking is based on the following criteria: “the place the theorem holds in the literature, the quality of the proof, and the unexpectedness of the result.”

The list is of course as arbitrary as the movie and book list, but the theorems here are all certainly worthy results.

1 The Irrationality of the Square Root of 2, Pythagoras and his school, 500 B.C.
2 Fundamental Theorem of Algebra, Karl Frederich Gauss, 1799
3 The Denumerability of the Rational Numbers, Georg Cantor, 1867
4 Pythagorean Theorem, Pythagoras and his school, 500 B.C.
5 Prime Number Theorem, Jacques Hadamard and Charles-Jean de la Vallee Poussin (separately), 1896
6 Godel’s Incompleteness Theorem, Kurt Godel, 1931
7 Law of Quadratic Reciprocity, Karl Frederich Gauss, 1801
8 The Impossibility of Trisecting the Angle and Doubling the Cube, Pierre Wantzel, 1837
9 The Area of a Circle, Archimedes, 225 B.C.
10 Euler’s Generalization of Fermat’s Little Theorem (Fermat’s Little Theorem), Leonhard Euler (Pierre de Fermat), 1760 (1640)
… (view the rest of the list)

Favorite Theorems: Cantor’s Theorem

This one is being added to my list just because of how slick the proof is. We finally proved it during Intermediate Analysis on Thursday. By the way, in case you turned glossy eyed at the sight of the following proof, I encourage you to scroll down to the end of this and read the story at the bottom. It is an interesting paradox, somewhat related to this proof.

Thm: (Cantor’s Theorem) For every set $A$, $\nexists$ a surjection of $A$ onto the set $\mathcal{P} (A)$, the power set of $A$.

For reference note that the power set of $A$, denoted $\mathcal{P}(A)$, is the set of all subsets of $A$. To call a mapping a surjection implies that it is “onto”. In other words, if $f:A\rightarrow B$, then $f$ is onto if and only if, for every element $b\in B, \ \ \exists \ a\in A \$ such that $f(a)=b$

Proof: For a contradiction we assume that there is a function, $\phi:A \rightarrow \mathcal{P}(A)$ that is onto. Let $a \in A$, which implies that $\phi(a) \subseteq A$. So then either, $a \in \phi(a)$ or $a \not \in \phi(a)$.
Let $D=\{ a\in A \ | \ a \not \in \phi(a) \}$. Now, because $D \subseteq A$ then there must be some $a_0 \in A$ such that $\phi(a_0)=D$.
So either (i) $a_0 \in D$ or (ii) $a_0 \not \in D$. But therein lies the problem. If (i) is true and $a_0 \in D$, then, by definition of $D$, $a_0 \not \in \phi(a_0) = D$ which is a contradition. If (ii) is true and $a_0 \not \in D$ then, by definition of $D$, $a_0 \in \phi(a_0) = D$ which is also a contradiction.
Thus, $\phi$ cannot be a surjection. $\Box$

It kind of reminds of those kinds of logical hurdles such as are inherent with such phrases as the “set of all sets”. For example, you might say that there is some set $U$ that is the set of all sets. Of course, since $U$ is a set, then it is an element of itself. So some sets are elements of themselves but clearly there are some sets that are not elements of themselves. For example, the set of all teacups, since elements of this set are teacups and not sets of teacups. Well, if you try to consider the set, $R$ of all sets that are not elements of themselves, you run into trouble. The trouble is that if $R$ is an element of $R$, then it is not an element of $R$. But if $R$ is not an element of $R$ then it is. Impossible.

Naive set theory leads to some interesting paradoxes. One particularly interesting example an applied form of Russell’s paradox (from KurzweilAI.net)

A judge is sentencing a man for a crime that he finds reprehensible and for which he wishes to mete out the most severe sentence. He tells the convicted man not only that he is sentenced to die, but that the sentence is to be carried out in a unique way. “The sentence is to be carried out no later than next Saturday. Furthermore, I want the sentence to be carried out in such a way that on the morning of your execution, you will not know for certain that you are going to be executed on that day. When we come for you, it will be a surprise.”

When the judge finishes describing his unusual sentence, the condemned man seems surprisingly pleased and replies, “Well, that’s great judge. I am greatly relieved.” To this the judge says, “I don’t understand. How can you be relieved?”

The man replies, “Well, your honor, in order for your sentence to be carried out, I could not be executed on Saturday.” “Why is that?’ asks the judge. “Since the sentence must be carried out by Saturday, if we actually get to Saturday, I will know for certain that I am to be executed on that day, and thus it would not be a surprise.”

“I suppose you are right,” responds the judge. “You cannot be executed on Saturday. I still do not see why you are relieved.” “Well,” says the prisoner, “if we have definitely ruled out Saturday, then I cannot be executed on Friday either.”

“Why is that?” asks the judge. “We have agreed that I definitely cannot be executed on Saturday. Therefore, Friday is the last day I can be executed. Thus, if Friday rolls around, I will definitely know that I am to be executed on that day, and therefore it would not be a surprise. So I cannot be executed on Friday.” “I see,” says the judge.

“Thus the last day I can be executed would be Thursday. But if Thursday rolls around, I would know I had to be executed on that day, and thus it would not be a surprise. So Thursday is out. By the same reasoning we can eliminate Wednesday, Tuesday, Monday, and today.”

The judge scratches his head as the confident prisoner is led back to his cell. On Thursday, the prisoner is taken to be executed. He is very surprised. So the judge’s orders are successfully carried out.

Favorite Theorem #6: Pigeonhole Principle

In doing do preparatory reading for classes next term, I stumbled across this little interestingly named gem of a theorem. It is one that is frequently used in combinatorial analysis. It will also come in handy in our introductory Analysis class.

The reason for its name is that it can be used to say that if $m$ pigeons are put into $b$ pigeon holes and if $m>n$ the at least two pigeons must share one of the pigeonholes. To you non-mathematicians that see that as utterly obvious, just know that in the field of mathematics even the obvious concepts still need to be verified through rigorous proof.

So here it is, the pigeonhole principle:

Thm: Let $m,n \in \mathbb{N}$ with $m>n$. Then there does not exist an injection from $N_m$ to $N_n$.

(Note: $\mathbb{N}$, is the set of natural numbers, and for some $k\in \mathbb{N}$, $\mathbb{N}_k$ is the set of all natural numbers less than $k$

The only proof I’ve some up with is similar to the one that appears in Bartle and Sherbert’s Intro. to Real Analysis. It is below. If you have a more elegant argument, please share.

Proof:
Let’s use mathematical induction. If $n=1$ and if $f$ is any map of $\mathbb{N}_m \ (m>1)$ into $\mathbb{N}_1$ then it is clear that $f(1) = f(2) = \cdots = f(m)=1$ so that $f$ is not 1-1, and thus, not injective.
Now, assume that for some $k>1$, we have that there is no injective map from $\mathbb{N}_m$ to $\mathbb{N}_k$ when $m>k$. Let $f$ be a function that maps $\mathbb{N}_m$ to $\mathbb{N}_{k+1}$. Consider two cases: either the image of $g$ is a subset of $\mathbb{N}_k$ or it is not.
Case 1: If $g(\mathbb{N}_m) \subseteq \mathbb{N_k}$ then we can consider $g$ as simply a map from $\mathbb{N}_m$ to $\mathbb{N}_k$ and by the induction hypothesis, it cannot be injective.
Case 2: Suppose that $g(\mathbb{N}_m)$ is not contained in $\mathbb{N}_k$. If more than one element in $\mathbb{N}_m$ maps to $k+1$, then $g$ is not an injection. Therefore, we assume that there is a single element $p\in \mathbb{N}_m$ such that $g(p)=k+1$. Define
$h (q) = \left\{ \begin{array}{ll}g(q) & \mathrm{if } \ q=1,\ldots,p-1\\ g(q+1) & \mathrm{if } \ q=p, \ldots, m-1 \end{array}\right.$
Now, since $h:\mathbb{N}_{m-1} \rightarrow \mathbb{N}_k$, the induction hypothesis applies and $h$ is not injective. It is then easy to see that $g$ is not injective.
Q.E.D.

Interestingly this can prove that if two different people count the same set of objects, they will get the same number (assuming they count correctly). Stated mathematically:

Thm: $S$ is a finite set $\Rightarrow \ \exists ! \ \ n \in \mathbb{N}$ such that $\exists$ a bijection from $\mathbb{N}_n$ to $S$.

Four Color Problem

Some of you may know of a theorem called the Four Color Theorem. Many of you may not. It has the distinction of being the first major theorem to be proved using a computer. And thus, to many mathematicians the proof is not accepted since faith must be placed in the computer for the result and there is a complete lack of elegance to the proof. After all, “a good mathematical proof is like a poem . . . this [proof] is a telephone directory!” – Wikipedia

The theorem states that any plane separated into regions, such as a map of countries or states, can be colored with only four colors, such that no adjacent regions have the same color. Now, if you accept this a fact (which you most certainly should), that still leaves open the question of how to perform the coloring. Sure, a coloring using only four colors exists but finding it is another matter. Try it for yourself:

Puzzle Japan > Miscellaneous Page > Four Color Problem

HT: Think Again!

Pythagorean Triples

Scatterplot of first pythagorean triples inside 4500

I had the pleasure of filling in for a colleague in her Discrete Structure class, which is basically our introduction to proof class. Currently they are covering some introductory concepts from Number Theory. One of my favorite results had been covered in the class just before I needed to fill in: The Euclidean Algorithm. Anyways, toward the end of class we introduced the concept of Pythagorean Triples.

Def: An ordered triple, $(a,\ b,\ c)$ of positive integers such that $a^2 + b^2 = c^2$ is called a pythagorean triple.

EX: (3, 4, 5)
EX: (6, 8, 10)
EX: (9, 12, 15)
EX: (5, 12, 13)

Notice that the first three examples are of the same “type.” That is, the second and the third are multiples of the first. In fact, we could state the following theorem.

Thm: If $(a,\ b,\ c)$ is a Pythagorean triple then for any positive integer $k$, $(ka,\ kb,\ kc)$ is also a Pythagorean triple.

Now, the last of my examples is fundamentally different from the other three. In fact, we could create a new definition.

Def: If the greatest common divisor of the pythagorean triple $(a,\ b,\ c)$ is $1$, then it is called a primitive pythagorean triple. (In other words, if they have no common factors it is a primitive pythagorean triple)

I left the class with an question and recommended that if they were interested they should do a little research to find the answer.

Question: How many primitive pythagorean triples are there? That is, are there infinitely many or only some finite number of them?

Pass the napkins

The Wobbly Table Theorem

There’s a theorem I have recently come across that is much along the same lines as the Pancake Theorem or the Ham Sandwich Theorem. It’s called the Wobbly Table Theorem (by some). Basically it states that if you’re at a four legged table that does rest evenly on the floor due the fact that floor is slightly uneven, you can rotate the table around until eventually all four legs will rest on the ground. The proof of this fact depends on one of my favorite theorems. I used to have a series of Favorite Theorems, but it is faded into oblivion. This post will hopefully bring back those theorems. Perhaps tomorrow you can expect one on this: The Intermediate Value Theorem.

At any rate, here are a couple of references on the Wobbly Table Theorem. I’m not completely satisfied with the proofs I’ve found here. When I have time, I’ll come back and explain why.

Hairy Theorem

This one’s a new one for me. It is definitely intuitive but I would have never thought of name for it!

You cannot comb a hairy ball.

The Hairy Ball Theorem states that if you take a ball that is evenly covered with hairs, no matter how you comb the ball, there must be a part somewhere. In other words, the orientation of the hairs must be discontinuous. Compare this to a hairy cylinder which you could comb all the hairs in on direction around the outside of the cylinder with no part. Sorry, I have no picture of a hairy cylinder.

To think of the theorem in another way, let the hairs represent the velocity of the wind blowing across the surface of the Earth. Then, if the wind velocity is continuous, there must be a point where the wind speed is zero.

Koosh!