One Puzzle with Two Totally Different Solutions

Peter Winkler‘s excellent book Mathematical Puzzles: A Connoisseur’s Collection has in it the problem of finding a partition of \mathbb{R}^3 into disjoint non-trivial circles. (Here “non-trivial” means “not a point.”) Winkler gives a very clever solution which is purely geometric.

Later, I read the same problem in Krzysztof Ciesielski‘s excellent book Set Theory for the Working Mathematician. In that book Ciesielski gives an almost purely set-theoretic solution.

I’ll discuss both solutions below.  (Don’t read on yet if you want to think about the puzzle first.)

Geometric Solution: First observe that you can partition a 2-sphere (e.g., \{(x,y,z) \mid x^2 + y^2 + z^2 = 1\}) minus two points into disjoint circles. The easiest way to see this is to see that you can do it if you remove the north and south poles from the sphere by taking the circles to be the lines of latitude. Then observe that you can drag the two holes at the two poles to any other two locations on the sphere you want and allow the circles to follow. (For example, say that the two holes are still on different hemispheres. Then the circles will still radiate out from the holes, but their centers will gradually become closer and closer to the north or south pole, depending on the hemisphere that the hole is in.)

Given that, the partition of \mathbb{R}^3 is as follows: The first circles in the partition will be those in the xy-plane with center (x,0,0) where x\cong 1\text{ (mod }4) and with radius 1. Now notice that every 2-sphere centered at the origin meets these circles in exactly two points. Thus we may complete the partition by taking a partition of each of these 2-spheres into circles separately.

There is another (probably much better) explanation of this solution at cut-the-knot.

Set-theoretic solution: Let \alpha be the first ordinal of cardinality 2^{\aleph_0} = |\mathbb{R}| = |\mathbb{R}^3|. Pick a well-ordering \{w_\beta\}_{\beta < \alpha} of \mathbb{R}^3 of length \alpha. We will build the partition of \mathbb{R}^3 by transfinite recursion along \{w_\beta\}. At each step \beta, we will define a circle C_\beta such that w_\beta\in C_\beta and C_\beta\cap C_\gamma = \emptyset for \gamma < \beta if C_\beta\ne C_\gamma. Hopefully, it’s clear that this suffices.

Here’s what to do at step \beta. First of all, if w_\beta is in some C_\gamma where \gamma < \beta then let C_\beta = C_\gamma and stop. Otherwise, pick a plane P passing through w_\beta which is not coplanar with any C_\gamma for \gamma < \beta. This is possible since there are 2^{\aleph_0} planes through w_\beta but only |\beta|< 2^{\aleph_0} circles C_\gamma.

Now, each circle C_\gamma intersects P in at most 2 points. Since there are 2^{\aleph_0} circles in P containing w_\beta but only |\beta|< 2^{\aleph_0} circles C_\gamma there must be a circle in P which contains w_\beta and is disjoint from each C_\gamma for \gamma<\beta. Let this circle be C_\beta. This completes the proof.

About these ads

4 Comments

Filed under Ordinals, Puzzles, Set Theory

4 responses to “One Puzzle with Two Totally Different Solutions

  1. This is a fun observation! The set-theoretic solution gives a hint to the obvious follow-up question: Why 3? I don’t see how to get that information from the (very clever) geometric solution. It seems odd that the non-constructive solution gives more information than the constructive one. Perhaps the geometric solution is too clever?

  2. mkoconnor

    Great observation, I hadn’t thought of that. It did occur to me that the set-theoretic solution gives the extra information that any family of \kappa disjoint circles can be extended to a partition when \kappa < 2^{\aleph_0}. The problem of getting a geometric solution even for \kappa = \omega or \kappa finite seems like it’s probably very hard.

  3. Gauster

    Indeed…and what is even more surprising, if I got it right, is that it’s even possible to have all circles to be the same size with the second construction. And here the geometric solution seems impossible.

  4. Wojowu

    Unfortunatelly, this proof uses axiom of choice. Without it, we can’t prove that space (or any other continuum) is well-orderable

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s