(This puzzle is from Stan Wagon via @mary’s PhD advisor and requires some knowledge of transfinite set theory which is the funnest thing and if you don’t know where to begin with this problem we can instead talk about what the heck it even means to have infinities bigger than other infinities!)
The problem: How many non-intersecting (nesting is allowed) figure-8’s can you fit in the plane? Yes, the answer is infinity, but WHICH infinity?
Warm-up puzzles:
Show that you can fit uncountably many non-overlapping circles in the plane.
Show that you can only fit countably many non-overlapping disks in the plane.
The reason you can only fit countably many non-overlapping disks in the plane is that each disk necessarily covers a rational point (a point whose x and y coordinates are both rational.) There are only a countable number of such points, so any mapping of each disk to a rational point inside the disk in question (which is necessarily an injective mapping, because the disks don’t overlap) shows that there must be no more than a countable number of such disks.
This can be extended so show something similar in the case of the figure eights, and so they too must be limited to be no more than countable.
Create a mapping from each figure eight to a pair of rational points such that one of the points is “inside” each of the two loops of that figure eight. If we can prove this mapping is injective, then by similar logic to the disks, we’ll have proved that the amount of non-overlapping figure eights is countable.
Two different non-overlapping figure eights can take five configurations: The first can be “inside” the “left” loop of the second, inside the “right” loop of the second, the second can be inside the “left” or “right” loop of the first, or they can be both “outside” each other. Without loss of generality, in the first four cases one of them is “inside” one of the loops of the other, and so the smaller figure eight can’t be mapped to the same pair of rational points as the larger, as only one of the rational points that the larger pair is mapped to is inside the side of the figure eight in which the smaller figure eight is contained.
And, of course, in the fifth case, there is no way for either of the points to line up. Therefore the map is injective, and we have proven that there can no more than a countable number non-overlapping figure eights on the plane.
The only thing I know about cardinality of infinities is from an Automata Theory course, trying to talk about which languages can be enumerated by a TM. But I don’t remember why we cared…
Anyway, for the warm-up #1:
My understanding is that circles don’t have a width, so two circles can be arbitrarily close together without touching and that’s ok. So they can nest inside each other, with the “top” of each circle being at the “next” real number down from the outer one, and being just a tiny bit smaller in radius to compensate so it doesn’t run in to the outer one on the bottom. Then we have a number of circles equal to the number of points on the line from the center of the plane out to infinity, and this just the same as saying that a number line has uncountably many real numbers via the Cantor diagonal thing.
For number two (EDIT: disregard, I had the wrong definition of a “disk” as discussed below):
My understanding is that a disk is a circle with a finite width. If that’s so, then it reduces to the same number line question except we can enumerate all of the possible disks because the “next” disk’s top is defined by the width. So this is the same as saying that a number line as countably many natural numbers.
For the actual puzzle:
Does a figure 8 have a width? If yes, then it’s trivially the same as a disk isn’t it? If no, then the issue is that there’s spacing implied by the nesting restriction (that the inner 8 has to live entirely inside the top or bottom half of its parent). Put another way, there’s a restriction on the size of the nested 8 relative to the its parent, whereas an inner circle can have any radius smaller than its parent. However, I think this doesn’t matter because if we look only at the tops, there can be a new top of an 8 at every real number. The bottoms of those 8s are spaced out, but the tops are uncountably infinite just like the real numbers.
That said, we’re not really filling the plane with 8s by only making use of the top. The bottom of each 8 is empty and you can maybe nest more 8s inside the tops via rotation? However, I’m not familiar enough with the set theory here to know if there’s a relevant next cardinality we can get to here above uncountably infinite. Adding a finite multiple obviously does nothing for us, so I don’t see how the bottoms will be helpful to fill in because that only gives each parent two children instead of one. Even with some rotation tricks, I think we would have to achieve some non-finite amount of nesting at each level to say that there’s “more” of the 8s than real numbers? Otherwise each real maps to a finite set which doesn’t seem different to me.
@drtall: The answer to the first warm-up can be done in a way that is (in my opinion) much easier (and actually, I’m pretty sure that your way of doing it runs into the problem of there not being a “next” number down from any real number, which is actually an essential feature of the reals’ uncountablity (EDIT: never mind, it’s not so essential after all, but it’s still true in this case)):
Take the set of circles with radius r ∈ R+ (the positive real numbers), centered on the origin. There is a bijection between this set and R+, so this is an uncountable set. These circles also don’t intersect with one another, so this is an example of an uncountable set of non-intersecting circles.
Note that this is different from the second warm up. You can at most have a countable infinity of non-overlapping disks, as demonstrated above.
@zzq We came to a different conclusion, but I confess your argument is a little bit beyond my skills to critique. Maybe you would be kind enough to say why you think mine is wrong?
Ah, okay. And then the disk one is basically the same except you can’t select r from R, because the only valid radii are those where the width of the disk is excluded which means it’s the natural numbers with spacing w instead of spacing 1 and so it is countable just like the natural numbers?
For the second warm up, I see that you are mistaken in the definition of a disk. A disk is the region of all the points inside a given circle. (You can, if you want, distinguish an open disk (not including the surrounding circle) from a closed disk (which does include the points on the rim), but for our purposes that doesn’t matter.)
Replying here instead of editing because we’re both talking a lot
Is my solution wrong because I’ve created a hierarchy of sizes? Like, sure, I have a top of an 8 at every point on the real number line. But each 8 has a size, and there’s a countably infinite number of sizes available to me and on each “level” there’s a finite number of 8s corresponding to the “depth” of that level. As in, I showed one way you could try to enumerate it and that fails but there’s this other way to enumerate them that works so the whole thing is countable?
Create a mapping from your set of figure eights to the set of pairs of rational points (points in Q x Q, that is, points where both the x and the y coordinate are rational), such that the first of the pair is inside the “left” loop of the figure eight, and the second is inside the “right” loop.
I explained above why this is an injective mapping. And because we have an injective mapping into a countable set, all we need to do is enumerate that set (which in this case is (Q x Q) x (Q x Q)) and we’ll have enumerated your set of figure eights.
Enumerating (Q x Q) x (Q x Q) is trivial, as it’s really just an extension of enumerating Q itself.
With that new definition, I’m re-reading your OP and wondering:
Can you elaborate a little on why a disk must include a rational point? Naively I want to try to make a disk that only includes the point pi. It seems like I ought to be able to, but does it somehow extend from the definition of a circle having a non-zero radius? A circle’s radius can be arbitrarily small but not zero, so what we have to show is that there’s a rational point arbitrarily close to pi? I’m a little lost.
Got it. I understand your answer now, modulo my last question re the disk thing. That is:
I see how the disk-as-region-of-points is relevant because the figure 8 acts like a disk in that it captures two sets of points inside it. So I’m down to just wondering about how we know for sure there’s a rational point in there. (Sorry if this is all really dumb!)
Yes, it’s because a circle has non-zero radius, and the rationals are dense in the reals. (Likewise, Q x Q is dense in R x R.)
What it means for a set A to be dense in set B is that for each point in B, there is a point in A arbitrarily close to it. In other words, for each x in B, and for each epsilon greater than zero, there is a point in A within a distance of epsilon from x.
So if you have a disk centred on some point in R x R, there will be a point in Q x Q arbitrarily close to it. Whichever epsilon you pick for the radius of the disk, there will be a point in Q x Q within epsilon of the center, or in other words within the disk.
And yet rationals also have that feature and are countable!
Yes, but since they can be nested, the disk argument doesn’t work. And nested circles are uncountable so how can we be sure there isn’t a clever way to nest the figure-8’s to squeeze in an uncountable number of them? (Well, @zzq explained how!)
True. What I was thinking of when I wrote that was the other way around, that because of their unaccountability this is necessarily true for the reals. After thinking about it for a second, of course that’s wrong too: there are (non-standard) models of the natural numbers which are uncountable, after all. So never mind then.
Here’s my solution, which is the same as @zzq’s but I’m trying to avoid terms like “injective”!
Warmup 1:
This assumes you know Cantor’s diagonalization argument that there are more real numbers than natural numbers. Consider all the circles centered at the origin. None of them intersect each other but there’s one for every positive real number, so there are uncountably many of them!
Warmup 2:
First we need Cantor’s zigzag argument for why there are countably many fractions, or equivalently, countably many pairs of integers (a fraction is just a pair of integers). And if we know there are countably many pairs of integers then we can apply the zigzag argument recursively to see that there are countably many n-tuples of integers, for any finite n. In particular, there are countably many points in the plane with rational coordinates, because that’s just 4 integers (a/b, c/d).
With that established, proving that a set is countable means finding a function that maps every element of it to an element of a known-countable set (like points in the plane with rational coordinates) without anything in the known-countable set getting mapped to twice. It’s like pairing up every element of our set with a natural number, and having natural numbers left over is fine.
So with non-overlapping disks we just need to map every disk to a point with rational coordinates. (Thanks to @byorgey for pointing out that if you just say “pick a point in the disk” then you’re accidentally invoking the Axiom of Choice so let’s not do that! Aside: I’m so happy to be gradually grokking the axiom of choice finally!) Oh yeah, and rationals being dense in the reals tells us that any disk with finite radius must contain a point with rational coordinates. [1] Let’s say that we map each disk to the point (a/b,c/d) inside it that’s lexicographically smallest when you just list all 4 integers, (a,b,c,d).
So that’s it, every disk maps to a single element of a countable set. And since the disks don’t overlap, no point can get mapped to by two different disks! (Ok, fine, that’s what “injective” means.)
Figure-8’s:
(This was so hard to think of but so easy once you hear it (after those warmups!)!)
Remember how the set of all n-tuples of integers is still countable? (Just keep reapplying Cantor’s zigzag trick!) Well how about pairs of points on the plane with rational coordinates? ((a/b,c/d),(e/f,g/h)) The set of all of those is countable, so here’s the trick: map every figure-8 in the plane to a pair of rational coordinates like that. We can do the same as with disks to make sure we’re getting a unique point inside each loop of the figure-8. The other half of establishing that the mapping is injective is to make sure two different figure-8’s can’t map to the same pair of points. Well, try winding 2 different figure-8’s around the same 2 points without them intersecting. You can’t! QED
Footnote
[1] Proof that every circle contains a point with rational coordinates inside it:
You can slice the circle with a horizontal line and get 2 distinct real x-values.
Every point between those 2 numbers is inside the disk.
There exists a rational number between those 2 numbers (density of Q in R).
Make a vertical slice through that rational x-value.
That hits the circle in 2 distinct points.
Every point between those is also inside the circle.
There’s a rational number between those numbers (density of Q in R again).
Now we have a rational x-value and rational y-value inside the circle.
Eh, saying “try it, you can’t” isn’t really a proof, and that bit of the solution is actually the main place where there is a difference in the figure eight case from the disk case, so that’s actually the main part of the proof which kind of needs to be rigorous. But never mind, all that you need to do is enumerate the cases and point out in each case why they can’t share the same two points.
By the way, on an interesting but pendantic side note: you’re not really relying on the Axiom of Choice when the set in question is countable (such as Q), but just the Axiom of Countable Choice, which is a lot weaker. In fact, it’s so much weaker that it even seems trivial: if you know a set is countable, that means it has a bijection with N, so just pick the element that is mapped to 0 (or 1 or 5 or 53 or whatever number). But no, interestingly enough, you can’t just do that without countable choice. Why? Well, I just said to use the bijection to N that we know exists. But which bijection? There are, after all, an infinite amount of bijections between any countable set and N, and no intrinsic way to choose a “canonical” one. So we’re back to needing some AoC-like axiom in order to find a bijection to use in order to choose an element!
