We can write a computer program that will successively print out the digits of the decimal expansion of Pi. We can also write one that will list the digits of the decimal expansion of the square root of 2. Similarly, there are computer programs that...

Continue reading...# other

# Ordinal Numbers

One of the most useful properties of the whole numbers is that every non-empty subset has a least element; this allows us to begin a process of “counting” by successively choosing least elements: 0, 1, 2, 3, 4, … Any (totally) ordered set which has...

Continue reading...# All Horses are the Same Color

If you know how to prove things by induction, then here is an amazing fact: Theorem. All horses are the same color. Proof. We’ll induct on the number of horses. Base case: 1 horse. Clearly with just 1 horse, all horses have the same color....

Continue reading...# Continuum Hypothesis

We have seen in the Fun Fact Cantor Diagonalization that the real numbers (the “continuum”) cannot be placed in 1-1 correspondence with the rational numbers. So they form an infinite set of a different “size” than the rationals, which are countable. It is not hard to show that...

Continue reading...# Equidecomposability

Two sets A and B are said to be equidecomposable if you can partition set A into a finite number of subsets and reassemble them (by rigid motions only) to form set B. Let A be a unit circle, and let B be a unit circle with...

Continue reading...# Envy-free Cake Division

Say you and a friend wish to share a cake. What is a “fair” way to split it? Probably you know this solution: one cuts, the other chooses. This is called a fair division algorithm, because by playing a good strategy, each player can guarantee she gets...

Continue reading...# Banach-Tarski Paradox

Did you know that it is possible to cut a solid ball into 5 pieces, and by re-assembling them, using rigid motions only, form TWO solid balls, EACH THE SAME SIZE AND SHAPE as the original? This theorem is known as the Banach-Tarski paradox. So why...

Continue reading...# Sierpinski-Mazurkiewicz Paradox

If you’ve seen the Banach-Tarski paradox, you know that it is possible to cut a solid 3-dimensional ball into 5 pieces and reassemble the pieces using only rigid motions to form two solid balls each the same size as the original. The construction depends on the Axiom...

Continue reading...# Arrow’s Impossibility Theorem

Elections are democracy in action. People go to polls and express their preferences, and somehow we must aggregate the preferences of many individuals to make a joint decision. So the choice of voting method is very important. Is there an ideal voting method? According a...

Continue reading...# All Numbers are Interesting

There are clearly many interesting whole numbers. For instance, 2 is the only even prime number, 3 is the first odd prime, 6 is a perfect number (the sum of the proper divisors is the number itself), etc. But did you know that all whole...

Continue reading...