Real Numbers and Infinite Games, Part I

Georg Cantor

In this post I’d like to illustrate how one can use infinite games to prove theorems about the real numbers. I’ll begin with a game-theoretic proof that the set of real numbers is uncountable, following the exposition in this paper of mine. This will lead us somewhat unexpectedly into the realm of descriptive set theory, where we will discuss how games are used in cutting-edge explorations of the Axiom of Choice, the Continuum Hypothesis, and the foundations of second-order arithmetic. In a sequel post I will discuss how infinite games can be used to study Diophantine approximation, with applications to complex dynamics.

Countable versus uncountable infinities

When my daughter was 5 years old, she asked me if there is just one infinity. I proudly kissed her on the forehead and told her what an excellent question that was. I told her no, infinity comes in many different flavors. I pretty much left it at that, but since she’s 10 now, here are some more details for her. (The reader familiar with the basics of set theory can move on to the next section.) Continue reading →

The Pentagon Problem

In this post I’ll talk about another favorite recreational math puzzle, the (in)famous “Pentagon Problem”. First, though, I wanted to provide a solution to the Ghost Bugs problem from my last blog post. The puzzle is the following:

You are given four lines in a plane in general position (no two parallel, no three intersecting in a common point). On each line a ghost bug crawls at some constant velocity (possibly different for each bug). Being ghosts, if two bugs happen to cross paths they just continue crawling through each other uninterrupted. Suppose that five of the possible six meetings actually happen. Prove that the sixth does as well.

Here is the promised solution. The idea (like in Einstein’s theory of general relativity) is to add an extra dimension corresponding to time. We thus lift the problem out of the page and replace the four lines by the graph of the bugs’ positions as a function of time. Since each bug travels at a constant speed, each of the four resulting graphs $g_i$ is a straight line. By construction, two lines $g_i$ and $g_j$ intersect if and only if the corresponding bugs cross paths.

Suppose that every pair of bugs cross paths except possibly for bugs 3 and 4. Then the lines $g_1, g_2, g_3$ each intersect one another (in distinct points) and therefore they lie in a common plane. Since line $g_4$ intersects lines $g_1$ and $g_2$ in distinct points, it must lie in the same plane. The line $g_4$ cannot be parallel to $g_3$ , since their projections to the page (corresponding to forgetting the time dimension) intersect. Thus $g_3$ and $g_4$ must intersect, which means that bugs 3 and 4 do indeed cross paths.

Cool, huh? As I mentioned in my last post, I can still vividly remember how I felt in the AHA! moment when I discovered this solution more than 15 years ago.

Continue reading →

Beauty and explanation in mathematics

I just moved into a new house and haven’t had time to blog much lately. But I did want to advertise my friend Manya Raman-Sundström’s upcoming Workshop on Beauty and Explanation in Mathematics at Umeå University in Sweden: http://mathbeauty.wordpress.com/wbem/

The list of invited speakers includes Hendrik Lenstra, one of my graduate school teachers. (If you haven’t see it before, you should check out Lenstra’s lovely short article Profinite Fibonacci Numbers.) Continue reading →

Quadratic reciprocity and Zolotarev’s Lemma

I want to explain a beautiful proof of the Law of Quadratic Reciprocity from c. 1874 due to Egor Ivanovich Zolotarev (1847-1878). Some time ago I reformulated Zolotarev’s argument (as presented here) in terms of dealing cards and I posted a little note about it on my web page. After reading my write-up (which was unfortunately opaque in a couple of spots), Jerry Shurman was inspired to rework the argument and he came up with this elegant formulation which I think may be a “proof from the book”. The following exposition is my own take on Jerry’s argument. The proof requires some basic facts about permutations, all of which are proved in this handout.

Let $m$ and $n$ be odd relatively prime positive integers. You have a stack of $mn$ playing cards numbered 0 through $mn-1$ and you want to deal them onto the table in an $m \times n$ rectangular array. Consider the following three ways of doing this: