23
$\begingroup$

It is a well-known fact that the set of points which are finitely constructible with straightedge and compass (starting with two points $0$ and $1$) doesn't cover the Euclidean plane $\mathbb{R}\times \mathbb{R}$ because only $\mathbb{Q}^{\sqrt{}}\times \mathbb{Q}^{\sqrt{}}$ is finitely constructible (which is a countable set).

[Side question 1: What is the official name (and symbol) for the set which I call $\mathbb{Q}^{\sqrt{}}$, i.e. the set of those numbers that can be defined by addition, substraction, multiplication, division and taking the square root alone (starting from $0$ and $1$). Note that the set of algebraic numbers $\mathbb{Q}^\text{alg}$ allows for taking arbitrary roots.]

But in the process of constructing points with straightedge and compass a lot of other points are "created", just by drawing the allowed lines and circles that are needed to take intersections (allowed = defined by previously constructed points). Only those points count as constructed that are intersections of such constructed lines and circles with other constructed lines and circles. But the other ones at least have been drawn.

My question is:

Does it make sense to ask – and how can it be proved or disproved – whether $\mathbb{R}^2$ might be "finitely coverable" in the sense that for any given point $p \in \mathbb{R}^2$ there is a line or circle constructible in finitely many steps (starting from points $[0,0]$ and $[1,0]$) which $p$ lies on?

The question and answer is not trivial at first glance (at least not for me), because the number of constructed points grows so incredibly fast, and the number of constructed lines and circles grows even faster (roughly quadratically, because each pair of new points gives – roughly – one new line and two new circles).

[Side question 2: Can a rough estimate of the growth rate of the numbers of points, lines and circles be given, when starting with $n$ points in general or regular position?]


To give a little visual sugar to my question: These are the constructible points, lines and circles after only three steps (starting with two points $0$ (red) and $1$ (orange)). (Each intersection of a line or circle with a line or circle is a constructed point – and there are myriads of them, after only three steps!)

enter image description here

This is after two steps:

enter image description here

This it how it looks like after only two steps when starting with five points $0, 1, -1, i, -i$.

enter image description here

[Side question 3: What might the little (and internally structured) white cross in the middle (around $(0,0)$ (red)) "mean"?]

This is after one step:

enter image description here


For the sake of completeness:

This is where the two points $0$, $1$ started off:

enter image description here

And this is where the five points $0$, $1$, $i$, $-1$, $-i$ started off:

enter image description here

$\endgroup$
  • $\begingroup$ Hurwitz complex continued fractions $\endgroup$ – Ed Pegg Sep 10 '18 at 14:48
  • $\begingroup$ How would this answer my question? Is it obvious (at least for you)? (I've read, that "the Hurwitz complex continued fraction algorithm generates Gaussian rational approximations to an arbitrary complex number", but it's not obvious for me how this does answer my question.) $\endgroup$ – Hans-Peter Stricker Sep 10 '18 at 14:52
  • 2
    $\begingroup$ Note that a line or a circle cover no area, so that your impressively filled picture contains a null fraction of the plane. $\endgroup$ – Yves Daoust Sep 10 '18 at 15:39
  • 1
    $\begingroup$ That's what (in my understanding) even Cantor was astonished of: That there might be something one-dimensional (like a "line" and covering no area) that covered the two-dimensional plane: $|\mathbb{R}| = |\mathbb{R}^2|$. $\endgroup$ – Hans-Peter Stricker Sep 10 '18 at 15:43
  • $\begingroup$ This is not really set theory, Hans. If you feel such a tag is needed, the appropriate one is elementary-set-theory. Please do not add back the other one. $\endgroup$ – Andrés E. Caicedo Sep 10 '18 at 20:32
30
$\begingroup$

It's the countable union of measure 0 sets, so its measure is 0.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The essence would be: Regardless of how fast a function $f: \mathbb {N} \rightarrow \mathbb {N} $ grows: it remains countable? $\endgroup$ – Hans-Peter Stricker Sep 10 '18 at 18:13
  • 2
    $\begingroup$ @HansStricker countability and measure differ a bit. Note that any line or circle have uncountably many points, but are sets of measure zero when considered as subsets of $\mathbb{R}^2$. Since we can index each step of your algorithm using the naturals in the obvious way (step one, step two, etc. as you do in your post) the algorithm can generate at most countably many circles and lines. Since the countable union of sets of measure zero has measure zero, so must your set of "drawn" points. Since the plane has measure $> 0$ we conclude not all points can be "drawn" $\endgroup$ – Brevan Ellefsen Sep 10 '18 at 21:58
  • $\begingroup$ @HansStricker It's not really correct usage to ask whether a function is countable. And it's not clear what function you're talking about. if you mean the function from Step n to the set of circles and lines at Step n, that not $\mathbb{N}$ to $\mathbb{N}$, it's $\mathbb{N}$ to sets of subsets of $\mathbb{R}^2$. So for each natural number, we have a set of sets, and each such set of subsets is countable (finite, in fact). The union of a countable number of countable sets is a countable number of sets. $|\mathbb{N}|*|\mathbb{N}|=|\mathbb{N}|$. $\endgroup$ – Acccumulation Sep 10 '18 at 22:22
  • $\begingroup$ Since each step has finite number of elements, we can simple count off all the elements from the first step. Then we can count off all the elements of the second step, starting at one more than whatever number we left off at the first step. Then we can go to the third step. For each element, we will eventually get to that element and give it a number. $\endgroup$ – Acccumulation Sep 10 '18 at 22:22
  • $\begingroup$ @HansStricker: See my answer for a concrete unfolding of this answer, in the case you are not familiar with basic measure theory. $\endgroup$ – user21820 Sep 11 '18 at 8:15
19
$\begingroup$

The equation for any such constructible line or circle will have algebraic coefficients. So if $x$ and $y$ are algebraically independent (say, $x=\pi$, $y=e^{\pi}$), then $(x,y)$ cannot be drawn in this way.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What about $(\pi,0)$? (Restricting the question to the real line. At least $(\pi,0)$ is not constructible in the narrower sense.) $\endgroup$ – Hans-Peter Stricker Sep 10 '18 at 14:56
  • 6
    $\begingroup$ $\pi$ and $0$ are not algebraically independent. $\endgroup$ – Ethan Bolker Sep 10 '18 at 15:12
  • $\begingroup$ So the answer is just "No: Not for any given point $p\in\mathbb{R}^2$ there is a line or circle constructible in finitely many steps (starting from points $[0,0]$ and $[1,0]$) which $p$ lies on."? $\endgroup$ – Hans-Peter Stricker Sep 10 '18 at 15:19
  • 3
    $\begingroup$ @HansStricker: Surely the whole real line, including $(\pi,0)$, is constructible in your sense? It is the line through $(0,0)$ and $(1,0)$, $\endgroup$ – TonyK Sep 10 '18 at 15:20
  • 1
    $\begingroup$ Cantor once said: "I see it, but I don't believe it." I have to say: "I (must) believe it, but I don't see it." $\endgroup$ – Hans-Peter Stricker Sep 10 '18 at 15:24
11
$\begingroup$

Here's a geometric (as opposed to algebraic) argument.

Let $C$ be the set of points of $\mathbb{R}^2$ which lie either on a line through two constructible points or on a circle with a radius whose endpoints are constructible, where by 'constructible' I mean constructible from a fixed finite set of points by ruler-and-compass constructions in a finite number of steps.

We will prove that $C \ne \mathbb{R}^2$.

To see this, we'll define a family of sets $P_n$, for $n \in \mathbb{N}$, inductively as follows:

  • Let $P_0$ be the (finite) set of points you start with;
  • With $P_n$ defined, let $P_{n+1}$ be the set of points lying at an intersection of two (non-coinciding) lines or circle defined from $P_n$, where a 'line defined from $P_n$' means one passing through two distinct elements of $P_n$, and a 'circle defined from $P_n$' means one with a radius whose endpoints are distinct elements of $P_n$.

Next, for each $n \in \mathbb{N}$, let $C_n$ be the set of points in $\mathbb{R}^2$ which lie on a line or circle defined from $P_n$.

We obtain the set $C$ as the union of all of the sets $C_n$: $$C = \bigcup\limits_{n=0}^{\infty} C_n$$

It now suffices to prove that $C_n$ is nowhere-dense for each $n \in \mathbb{N}$, so that $C \ne \mathbb{R}^2$ by the Baire category theorem (see BCT3 here).

To prove this, it suffices to prove that $P_n$ is finite for each $n \in \mathbb{N}$. Indeed, each line and circle defined from $P_n$ is determined by two elements of $P_n$, so that if $P_n$ is finite, then $C_n$ is a finite union of lines and circles. Since lines and circles are nowhere-dense, it follows that $C_n$ is a finite union of nowhere-dense sets, so is itself nowhere-dense.

Finally, proving $P_n$ is finite for each $n \in \mathbb{N}$ is an easy induction on $n$. Indeed, $P_0$ is finite by assumption, and if $P_n$ is finite, then $P_{n+1}$ is finite since two non-coinciding lines or circles may only intersect at $0$, $1$ or $2$ points, and there are only finitely many lines and circles definable from $P_n$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot. Would you agree that this proof (that the constructible lines and circles don't cover the plane) is "harder to understand (or to believe)" than the proof that the constructible points don't cover the plane? "Polynomially harder" or "exponentially harder"? $\endgroup$ – Hans-Peter Stricker Sep 10 '18 at 16:02
  • 2
    $\begingroup$ This proof uses more properties of $\mathbb{R}^2$ (e.g. completeness) than the proof that the set of constructible points doesn't cover the plane. It can be proved fairly easily that the set of constructible points is countable, and therefore can't cover $\mathbb{R}^2$ since the latter is uncountable; however, a single line or circle is already uncountable, so you can't reason purely about cardinalities to prove this result. Whether you believe it or not is up to you ;) $\endgroup$ – Clive Newstead Sep 10 '18 at 16:10
  • $\begingroup$ This seems a little longer than it needs to be. There are countably many constructible points, therefore countably many constructible lines and constructible circles. Circles and lines are meagre sets. $\endgroup$ – Jack M Sep 11 '18 at 9:30
4
$\begingroup$

Acccumulation's answer is really the fundamental one, namely it boils down the the fact that measure zero sets are closed under countable union. But here is a concrete unfolding of that fact applied to this problem: $ \def\lfrac#1#2{{\large\frac{#1}{#2}}} $


Fix an enumeration of your collection of lines and circles. We shall show that we can cover the $k$-th curve by a countable collection of squares with total area at most $2^{-k}$, which would imply that your entire collection can be covered by a countable collection of squares with total area at most $1$, and hence your collection does not cover the plane because the plane cannot be covered by any countable collection of squares with finite total area.

First note that each line can be divided into countably many finite-length segments. Next note that any circle or line segment can be covered by finitely many squares with total area $ε$, for any real $ε > 0$. This is very easy for a line segment. To convince yourself concretely that it is true for a circle, impose a Cartesian plane with origin at the centre of the circle, and overlay a square grid with grid spacing $1/n$. Then in each quadrant the circle is monotonic in both coordinates and hence passes through (the interior of) at most $2(rn+1)$ squares, where $r$ is the radius of the circle. Thus the circle passes through squares with total area at most $\lfrac{8(rn+1)}{n^2}$, which can be made smaller than $ε$ for sufficiently large $n$.


To rigorously prove that the plane cannot be covered by any countable collection of squares with finite total area, one would have to at least introduce the notion of area of a union of a countable collection of squares, which can be done in a few ways, such as via the Riemann integral. It would then be obvious that the area of a countable union of squares is at most the sum of their areas.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm utterly amazed! $\endgroup$ – Hans-Peter Stricker Sep 11 '18 at 8:28
  • 1
    $\begingroup$ @HansStricker: Thank you! Does this explanation satisfy your curiosity in the sense of convincing you that the points covered by your collection of lines and circles are really quite 'little' compared to the rest of the plane? It's hard to get at first glance, but it's the same kind of thing as why the rationals are dense in the reals but have measure zero. $\endgroup$ – user21820 Sep 11 '18 at 8:31
  • $\begingroup$ Yes, it actually did, thank you. $\endgroup$ – Hans-Peter Stricker Sep 11 '18 at 8:35
2
$\begingroup$

This set is certainly dense in $\mathbb{R}^2$. In other words $\overline{\mathbb{Q}^{\sqrt{}}}=\mathbb{R}$. There's an area called Diophantine Approximation where one might ask how close we can get to real number with lines and circles. Also consider complexity theory.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.