The Tragedy of Infinite Tic-Tac-Toe

This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American

Last year, Moscow State University mathematician Olga Frolkina proved that you can fit only countably many nonintersecting Möbius strips in three-dimensional space. I wrote about her work and some generalizations for Quanta Magazine. 

If you haven’t encountered the idea of countable and uncountable infinities yet, they’re basically what they sound like. Mathematicians have shown that not all infinities are equal. One kind of infinity is the infinity you get when you start counting and never stop: 1, 2, 3, 4, …. This is called countable. Anything that you can put into a list with a first element, second element, and so on is countable. On the other hand, there’s no way to list the real numbers, or even just the real numbers between 0 and 1. Every list you make will be incomplete. (To see why, read this post by Yen Duong.) So the real numbers are uncountable. When you’ve experienced the abundance of the reals, countable infinity sounds a bit puny, to be honest. Only a puny infinity of Möbius strips fit into three-dimensional space.

While I was working on the Quanta article, Georgia Tech mathematician Dan Margalit told me about a similar question for letters in the plane. It’s not hard to fit countably many of any letter in the plane because you could just put them on an infinite grid, which is countable. But for some letters, you can put uncountably many copies in the plane if you’re clever. 

On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

The easiest example is O. There are a lot of different ways to put uncountably many O’s in the plane, but one way is to pick a circle of radius 1 and think about all the concentric circles that fit inside it. No two circles with the same center and different radii intersect each other, and there are uncountably many possible radii less than 1, so we’ve gotten up to uncountability, and we're done.

On the other hand, only countably many X’s fit in the plane. Hence, infinite tic-tac-toe games are stuck with countability because the X's hold the O's back. How do we know only countably many X's fit into the plane? First, we can quickly verify that we can’t just stick an X inside every one of our uncountably many O’s because the X’s would end up intersecting each other. But, as I wrote in the article about Möbius strips, that fact does not mean there is no more clever way to fit them in.

To see that it is impossible to embed uncountably many X’s in the plane, we harness the power of the rational numbers.

Probably the most important lesson I ever learned about countability, at least in terms of being able to show that certain sets were or were not countable, was that the rational numbers are countable. Unlike the whole numbers and some other countable sets, at first glance it is not obvious that the rationals are countable. There are just so many of them! There are an infinite number of rational numbers in any tiny interval on the real line, and at least when I first saw the question, I thought there must be “more” rationals than whole numbers. I spent quite a while trying to prove that the rationals were uncountable in a math class I was taking before another student presented a proof that they were, in fact, countable. Shifting my default way of thinking about countable sets from whole numbers, which are nicely spaced out and clearly have lots of room between them, to rational numbers, which are jumbled in everywhere but still somehow less plentiful than real numbers, was an important step in my mathematical development. One good strategy for showing that a set is countable is to find a way to set up a correspondence between the set and the rational numbers, and that's what we can do with X's.

Let's say we have a bunch of X’s in the plane.

For every X, we can find a small circle with a rational radius and a center that has rational coordinates so that the X sticks out of the circle at four points. Within each quadrant the X creates in the circle, we can find a point with rational coordinates.

So that’s 11 rational numbers associated to each X: one for the radius and two for each point with rational coordinates. As Bill Russell knows, 11 is a bit unwieldy. Luckily, as mathematicians, we don't need to do anything practical like wear them on our fingers. We just need to know they exist and that we could list them if we really had to.

When I spoke with him, Margalit called the circle and rational points a “template” for the X. (Note that every X has an infinite number of potential templates because if you jiggle one template a little bit, you can find another valid template.) Because these templates are defined by 11 rational numbers, there are only countably many of them in the plane. (We haven’t actually proved that in this post, but you can prove it for yourself if you want.) Therefore, if there are uncountably many X’s in the plane, infinitely many of them must have the same template because there just aren't enough distinct templates to go around. The last piece of the puzzle is to show that any two distinct X’s with the same template necessarily intersect each other. That’s not trivial to prove rigorously, but if you start drawing circles with X’s through them, I think you can convince yourself.

To tie a little bow on it, the fact that only countably many permissible X templates can sit in the plane without intersecting means we can only have countably many X’s.

I thought the proof was very cute when I heard it, but it also helped me develop some intuition about Möbius bands. Frolkina’s proof was not based on the same argument, but it made me more comfortable with thinking about how to even approach questions like this.

What about other letters? Can we fit uncountably many of them in the plane? Yes to C and (sans serif, like the font I used in the draft of this post, not the font in this version of the post) D. No to X and Y. Yes to V. No to Q; it's got an x-ish bit in the bottom right. I started developing some theories about what shapes could have uncountably many of their kindred sitting with them in the plane, and then I ran across Boston University math graduate student Sachi Hashimoto’s post about it, “Doodling Set Theory." She started thinking about the question when she was procrastinating on homework as an undergraduate and started thinking about a question she had seen: Can you embed uncountably many figure 8’s in the plane? “And if you’re really procrastinating on your homework, you just move on from there,” she joked.

She started doodling letters and other shapes, trying to figure out straightforward criteria to determine which shapes could be embedded uncountably many times in the plane and which couldn’t. She and a commenter on her blog came up with some conjectures as well but never found a watertight proof. When I talked with her about the question, she told me she had hoped I was about to tell her the answer once and for all. No such luck. “Every once in a while, I sit down and try to prove it,” she says, but as a computational number theorist, it’s not exactly her area of specialty. If you want to read her conjectures and start doodling set theory for yourself, check out her post. Update, March 8, 2019: Hashimoto and friends have continued their investigations into what shapes can be embedded in the plane uncountably many times. Check out her new post about it!

I talked to several mathematicians about embedding uncountably many letters or Möbius strips while I was working on the Quanta article and this post, and it was charming to see how much the question connected with mathematicians in some very different research areas. I’m not sure exactly what it is about it that is so broadly appealing to mathematicians, but I can recommend it as a conversation starter if you’re talking with mathematicians.

I think one appealing thing about it is that it plays with mathematical properties that can be thought of as notions of “smallness” and “largeness.” Without giving a rigorous definition, there’s some sense in which X’s must be “larger” than O’s because only countably many of them will fit in the plane. Likewise, in three-dimensional space, Möbius strips are “larger” than cylinders. But another notion of “largeness” and “smallness” is contractibility, whether a space can be shrunk down to a point without losing certain topological information. An O is not contractible. The hole is essential. But with an X, you can push the legs in and get a point. Once again, without giving a concrete definition, contractible spaces feel “smaller” than non-contractible ones. The hole lends some gravitas, perhaps. So in the case of letter embeddings, these different notions of smallness and largeness butt heads in a fun way.

Another way to think about the question is that it is telling us about the space we’re embedding objects in as much as the objects themselves. Three-dimensional space is “too small” for uncountably many Möbius strips, and the plane is too small for uncountably many X’s. With so many subtleties and angles on the question, as well as the fact that it seems like it should only take a few minutes’ thought to resolve, maybe it’s no surprise that mathematicians keep getting drawn in to it. If you’ve got something to procrastinate on (and who doesn’t?), I hope you can enjoy a letter-doodling diversion.