11

Let S be a set of pairwise disjoint 8-like symbols on the plane. (The 8s may be inside each other as well) Prove that S is at most countable.

Now I know you can "map" a set of disjoint intervals in R to a countable set (e.g. Q :rational numbers) and solve similar problems like this, but the fact that the 8s can go inside each other is hindering my progress with my conventional approach...

Andrés E. Caicedo
  • 79,201
MathMathCookie
  • 2,156
  • 1
    Intuitively the problem is the 8's can't pack against each other like line segments. There must be a small disk between them even if one is inside the other. In that disk must be an element of $\mathbb{Q \times Q}$. – Ross Millikan Nov 02 '11 at 00:21
  • 1
    The first thing you need is a rigorous definition of what qualifies as an "8-like symbol". – hmakholm left over Monica Nov 02 '11 at 00:21
  • @Ross, some subtlety will be needed, because there are uncountably many pairwise disjoint "0-like" curves in the plane (such as for example all concentric circles). – hmakholm left over Monica Nov 02 '11 at 00:24
  • @HenningMakholm: I agree. That is exactly why the gaps between are important and we need to define 8-like curves in a way that requires them. – Ross Millikan Nov 02 '11 at 00:29
  • @RossMillikan: The 8s can pack against each other (and even fill the plane) - e.g. 8s consisting of two rectangles. It's the "second o" that creates the "gaps" which prevent the concentric circle argument from working with 8s. – David Bevan Nov 02 '11 at 09:15
  • @DavidBevan Disjoint figure-eights cannot fill the plane. If the figure 8s consist of circles, any line will only intersect each figure 8 in finitely many points. If the figure 8s consist of rectangles, any circle will only intersect each figure 8 in finitely many points. Lines and circles are uncountable, but the plane only fits countably many figure 8s. – Marcel Besixdouze Jul 27 '14 at 05:36
  • I stand corrected. – David Bevan Sep 29 '14 at 14:41
  • I'm delighted to see this because I have a happy memory of one of the first serious mathematical discussions I ever had, around age 16 or so, of essentially this question; I wanted to prove that a set of pairwise-disjoint +-like symbols must be countable. – MJD May 01 '20 at 17:07

2 Answers2

16

Let $\mathcal{E}$ denote the set of all your figure eights. Then, define a map $f:\mathcal{E}\to\mathbb{Q}^2\times\mathbb{Q}^2$ by taking $E\in\mathcal{E}$ to a chosen pair of rational ordered pairs, one sitting inside each loop. Show that if two such figure eights were to have the same chosen ordered pair, they must interesect, which is impossible. Thus, $f$ is an injection and so $\mathcal{E}$ is countable.

Alex Youcis
  • 54,059
  • I am confused, but I don't know why :( First question: what does Q^2 x Q^2 denote? Q x Q denotes a "2-D pair" in the rationals right, so what does this mean? – MathMathCookie Nov 02 '11 at 03:39
  • 1
    It means ordered pairs of ordered pairs, so a typical element would look like 4((p,q),(r,s)) – Alex Youcis Nov 02 '11 at 03:41
  • Oh, I see. I still don't understand this part: "they must intersect, which is impossible" Could you write out more? Thank you so much. – MathMathCookie Nov 03 '11 at 01:41
  • 1
    Think about it, if you had two figure eights, $E$ and $E'$ which share a point in each of their loops. How could they do this and not intersect? I can't think of a simple analytical proof, but it's pretty clear by inspection. – Alex Youcis Nov 03 '11 at 02:47
  • If figure eight $A$ is inside a loop of figure eight $B$, $A$'s index points cannot include a point from the other loop of $B$. If $A$ and $B$ are external to each other, then they can have no index points in common. – David Bevan Nov 03 '11 at 08:26
0

Let us associate each 8 with its center. If two 8's have exactly the same size and are too close together, then they will intersect. The same holds even if they only have almost the same size. That is, there are some $\epsilon,\delta$ such that two nonintersecting 8's of size between $r$ and $(1+\epsilon)r$ cannot be $\delta r$-close (that is, their centers need to be at distance at least $\delta r$.

Let us denote by $S_r$ the set of 8's of size between $r$ and $(1+\epsilon)r$. The circles at radius $\delta r/3$ around the centers are disjoint, and so if we choose for each 8 in $S_r$ a rational point inside the circle at radius $\delta r/3$ around its center, then these rational points will be distinct. This shows that $S_r$ is countable.

The set of all 8's is the union of countably many sets of the form $S_r$ (for example, we can take $r = (1+\epsilon)^z$ for all integers $z$). Since the countable union of countable sets is countable, we conclude that the number of 8's is countable.

Yuval Filmus
  • 57,157