11
$\begingroup$

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...

$\endgroup$
8
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Ross Millikan
    Commented Nov 2, 2011 at 0:21
  • 1
    $\begingroup$ The first thing you need is a rigorous definition of what qualifies as an "8-like symbol". $\endgroup$
    – hmakholm left over Monica
    Commented Nov 2, 2011 at 0:21
  • $\begingroup$ @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). $\endgroup$
    – hmakholm left over Monica
    Commented Nov 2, 2011 at 0:24
  • $\begingroup$ @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. $\endgroup$
    – Ross Millikan
    Commented Nov 2, 2011 at 0:29
  • $\begingroup$ @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. $\endgroup$
    – David Bevan
    Commented Nov 2, 2011 at 9:15

2 Answers 2

Reset to default
17
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – MathMathCookie
    Commented Nov 2, 2011 at 3:39
  • 1
    $\begingroup$ It means ordered pairs of ordered pairs, so a typical element would look like 4((p,q),(r,s)) $\endgroup$
    – Alex Youcis
    Commented Nov 2, 2011 at 3:41
  • $\begingroup$ 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. $\endgroup$
    – MathMathCookie
    Commented Nov 3, 2011 at 1:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alex Youcis
    Commented Nov 3, 2011 at 2:47
  • $\begingroup$ 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. $\endgroup$
    – David Bevan
    Commented Nov 3, 2011 at 8:26
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It does work for other figures :) $\endgroup$
    – Yuval Filmus
    Commented Nov 2, 2011 at 10:11
  • $\begingroup$ We cannot suppose such thing. We could have arbitrary small $8$s. $\endgroup$
    – richarddedekind
    Commented May 1, 2020 at 13:33
  • $\begingroup$ I expanded my answer a bit. The idea is that the union of countably many countable sets is countable. So there's absolutely no problem in supposing that all 8's have some minimal size. $\endgroup$
    – Yuval Filmus
    Commented May 1, 2020 at 16:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .