Mixing
Covering the Euclidean plane with constructible lines and circles
Clash Royale CLAN TAG#URR8PPP
up vote
19
down vote
favorite
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 $mathbbRtimes mathbbR$ because only $mathbbQ^sqrttimes mathbbQ^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 $mathbbQ^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 $mathbbQ^textalg$ 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
$mathbbR^2$ might be "finitely coverable" in the sense that for any
given point $p in mathbbR^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!)
This is after two steps:
This it how it looks like after only two steps when starting with five points $0, 1, -1, i, -i$.
[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:
For the sake of completeness:
This is where the two points $0$, $1$ started off:
And this is where the five points $0$, $1$, $i$, $-1$, $-i$ started off:
elementary-set-theory euclidean-geometry
asked 2 days ago
Hans Stricker
4,49313676
 |Â
show 3 more comments
up vote
19
down vote
favorite
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 $mathbbRtimes mathbbR$ because only $mathbbQ^sqrttimes mathbbQ^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 $mathbbQ^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 $mathbbQ^textalg$ 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
$mathbbR^2$ might be "finitely coverable" in the sense that for any
given point $p in mathbbR^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!)
This is after two steps:
This it how it looks like after only two steps when starting with five points $0, 1, -1, i, -i$.
[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:
For the sake of completeness:
This is where the two points $0$, $1$ started off:
And this is where the five points $0$, $1$, $i$, $-1$, $-i$ started off:
elementary-set-theory euclidean-geometry
asked 2 days ago
Hans Stricker
4,49313676
Hurwitz complex continued fractions
– Ed Pegg
2 days ago
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.)
– Hans Stricker
2 days ago
1
Note that a line or a circle cover no area, so that your impressively filled picture contains a null fraction of the plane.
– Yves Daoust
2 days ago
1
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: $|mathbbR| = |mathbbR^2|$.
– Hans Stricker
2 days ago
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.
– Andrés E. Caicedo
2 days ago
 |Â
show 3 more comments
up vote
19
down vote
favorite
up vote
19
down vote
favorite
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 $mathbbRtimes mathbbR$ because only $mathbbQ^sqrttimes mathbbQ^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 $mathbbQ^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 $mathbbQ^textalg$ 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
$mathbbR^2$ might be "finitely coverable" in the sense that for any
given point $p in mathbbR^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!)
This is after two steps:
This it how it looks like after only two steps when starting with five points $0, 1, -1, i, -i$.
[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:
For the sake of completeness:
This is where the two points $0$, $1$ started off:
And this is where the five points $0$, $1$, $i$, $-1$, $-i$ started off:
elementary-set-theory euclidean-geometry
asked 2 days ago
Hans Stricker
4,49313676
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 $mathbbRtimes mathbbR$ because only $mathbbQ^sqrttimes mathbbQ^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 $mathbbQ^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 $mathbbQ^textalg$ 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
$mathbbR^2$ might be "finitely coverable" in the sense that for any
given point $p in mathbbR^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!)
This is after two steps:
This it how it looks like after only two steps when starting with five points $0, 1, -1, i, -i$.
[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:
For the sake of completeness:
This is where the two points $0$, $1$ started off:
And this is where the five points $0$, $1$, $i$, $-1$, $-i$ started off:
elementary-set-theory euclidean-geometry
elementary-set-theory euclidean-geometry
asked 2 days ago
Hans Stricker
4,49313676
asked 2 days ago
Hans Stricker
4,49313676
edited 2 days ago
asked 2 days ago
Hans Stricker
4,49313676
asked 2 days ago
Hans Stricker
4,49313676
asked 2 days ago
Hans Stricker
4,49313676
4,49313676
Hurwitz complex continued fractions
– Ed Pegg
2 days ago
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.)
– Hans Stricker
2 days ago
1
Note that a line or a circle cover no area, so that your impressively filled picture contains a null fraction of the plane.
– Yves Daoust
2 days ago
1
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: $|mathbbR| = |mathbbR^2|$.
– Hans Stricker
2 days ago
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.
– Andrés E. Caicedo
2 days ago
 |Â
show 3 more comments
Hurwitz complex continued fractions
– Ed Pegg
2 days ago
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.)
– Hans Stricker
2 days ago
1
Note that a line or a circle cover no area, so that your impressively filled picture contains a null fraction of the plane.
– Yves Daoust
2 days ago
1
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: $|mathbbR| = |mathbbR^2|$.
– Hans Stricker
2 days ago
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.
– Andrés E. Caicedo
2 days ago
Hurwitz complex continued fractions
– Ed Pegg
2 days ago
Hurwitz complex continued fractions
– Ed Pegg
2 days ago
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.)
– Hans Stricker
2 days ago
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.)
– Hans Stricker
2 days ago
1
1
Note that a line or a circle cover no area, so that your impressively filled picture contains a null fraction of the plane.
– Yves Daoust
2 days ago
Note that a line or a circle cover no area, so that your impressively filled picture contains a null fraction of the plane.
– Yves Daoust
2 days ago
1
1
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: $|mathbbR| = |mathbbR^2|$.
– Hans Stricker
2 days ago
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: $|mathbbR| = |mathbbR^2|$.
– Hans Stricker
2 days ago
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.
– Andrés E. Caicedo
2 days ago
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.
– Andrés E. Caicedo
2 days ago
 |Â
show 3 more comments
5 Answers
5
active
oldest
votes
up vote
30
down vote
accepted
It's the countable union of measure 0 sets, so its measure is 0.
edited yesterday
John Hughes
59.9k23987
answered 2 days ago
Acccumulation
5,7642616
The essence would be: Regardless of how fast a function $f: mathbb N rightarrow mathbb N $ grows: it remains countable?
– Hans Stricker
2 days ago
2
@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 $mathbbR^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"
– Brevan Ellefsen
2 days ago
@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 $mathbbN$ to $mathbbN$, it's $mathbbN$ to sets of subsets of $mathbbR^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. $|mathbbN|*|mathbbN|=|mathbbN|$.
– Acccumulation
2 days ago
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.
– Acccumulation
2 days ago
@HansStricker: See my answer for a concrete unfolding of this answer, in the case you are not familiar with basic measure theory.
– user21820
yesterday
 |Â
show 1 more comment
up vote
18
down vote
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.
answered 2 days ago
Micah
28.7k1361102
What about $(pi,0)$? (Restricting the question to the real line. At least $(pi,0)$ is not constructible in the narrower sense.)
– Hans Stricker
2 days ago
5
$pi$ and $0$ are not algebraically independent.
– Ethan Bolker
2 days ago
So the answer is just "No: Not for any given point $pinmathbbR^2$ there is a line or circle constructible in finitely many steps (starting from points $[0,0]$ and $[1,0]$) which $p$ lies on."?
– Hans Stricker
2 days ago
3
@HansStricker: Surely the whole real line, including $(pi,0)$, is constructible in your sense? It is the line through $(0,0)$ and $(1,0)$,
– TonyK
2 days ago
1
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."
– Hans Stricker
2 days ago
 |Â
show 4 more comments
up vote
10
down vote
Here's a geometric (as opposed to algebraic) argument.
Let $C$ be the set of points of $mathbbR^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 mathbbR^2$.
To see this, we'll define a family of sets $P_n$, for $n in mathbbN$, 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 mathbbN$, let $C_n$ be the set of points in $mathbbR^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 = bigcuplimits_n=0^infty C_n$$
It now suffices to prove that $C_n$ is nowhere-dense for each $n in mathbbN$, so that $C ne mathbbR^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 mathbbN$. 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 mathbbN$ 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$.
answered 2 days ago
Clive Newstead
48.3k471131
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"?
– Hans Stricker
2 days ago
2
This proof uses more properties of $mathbbR^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 $mathbbR^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 ;)
– Clive Newstead
2 days ago
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.
– Jack M
yesterday
add a comment |Â
up vote
4
down vote
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:
$
deflfrac#1#2largefrac#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 $lfrac8(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.
answered yesterday
user21820
36.2k440140
I'm utterly amazed!
– Hans Stricker
yesterday
1
@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.
– user21820
yesterday
Yes, it actually did, thank you.
– Hans Stricker
yesterday
add a comment |Â
up vote
1
down vote
This set is certainly dense in $mathbbR^2$. In other words $overlinemathbbQ^sqrt=mathbbR$. 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.
answered 2 days ago
cactus314
15.1k41862
Great hint, thank you.
– Hans Stricker
yesterday
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
30
down vote
accepted
It's the countable union of measure 0 sets, so its measure is 0.
edited yesterday
John Hughes
59.9k23987
answered 2 days ago
Acccumulation
5,7642616
The essence would be: Regardless of how fast a function $f: mathbb N rightarrow mathbb N $ grows: it remains countable?
– Hans Stricker
2 days ago
2
@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 $mathbbR^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"
– Brevan Ellefsen
2 days ago
@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 $mathbbN$ to $mathbbN$, it's $mathbbN$ to sets of subsets of $mathbbR^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. $|mathbbN|*|mathbbN|=|mathbbN|$.
– Acccumulation
2 days ago
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.
– Acccumulation
2 days ago
@HansStricker: See my answer for a concrete unfolding of this answer, in the case you are not familiar with basic measure theory.
– user21820
yesterday
 |Â
show 1 more comment
up vote
30
down vote
accepted
It's the countable union of measure 0 sets, so its measure is 0.
edited yesterday
John Hughes
59.9k23987
answered 2 days ago
Acccumulation
5,7642616
The essence would be: Regardless of how fast a function $f: mathbb N rightarrow mathbb N $ grows: it remains countable?
– Hans Stricker
2 days ago
2
@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 $mathbbR^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"
– Brevan Ellefsen
2 days ago
@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 $mathbbN$ to $mathbbN$, it's $mathbbN$ to sets of subsets of $mathbbR^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. $|mathbbN|*|mathbbN|=|mathbbN|$.
– Acccumulation
2 days ago
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.
– Acccumulation
2 days ago
@HansStricker: See my answer for a concrete unfolding of this answer, in the case you are not familiar with basic measure theory.
– user21820
yesterday
 |Â
show 1 more comment
up vote
30
down vote
accepted
up vote
30
down vote
accepted
It's the countable union of measure 0 sets, so its measure is 0.
edited yesterday
John Hughes
59.9k23987
answered 2 days ago
Acccumulation
5,7642616
It's the countable union of measure 0 sets, so its measure is 0.
edited yesterday
John Hughes
59.9k23987
answered 2 days ago
Acccumulation
5,7642616
edited yesterday
John Hughes
59.9k23987
edited yesterday
John Hughes
59.9k23987
edited yesterday
John Hughes
59.9k23987
59.9k23987
answered 2 days ago
Acccumulation
5,7642616
answered 2 days ago
Acccumulation
5,7642616
answered 2 days ago
Acccumulation
5,7642616
5,7642616
The essence would be: Regardless of how fast a function $f: mathbb N rightarrow mathbb N $ grows: it remains countable?
– Hans Stricker
2 days ago
2
@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 $mathbbR^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"
– Brevan Ellefsen
2 days ago
@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 $mathbbN$ to $mathbbN$, it's $mathbbN$ to sets of subsets of $mathbbR^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. $|mathbbN|*|mathbbN|=|mathbbN|$.
– Acccumulation
2 days ago
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.
– Acccumulation
2 days ago
@HansStricker: See my answer for a concrete unfolding of this answer, in the case you are not familiar with basic measure theory.
– user21820
yesterday
 |Â
show 1 more comment
The essence would be: Regardless of how fast a function $f: mathbb N rightarrow mathbb N $ grows: it remains countable?
– Hans Stricker
2 days ago
2
@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 $mathbbR^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"
– Brevan Ellefsen
2 days ago
@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 $mathbbN$ to $mathbbN$, it's $mathbbN$ to sets of subsets of $mathbbR^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. $|mathbbN|*|mathbbN|=|mathbbN|$.
– Acccumulation
2 days ago
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.
– Acccumulation
2 days ago
@HansStricker: See my answer for a concrete unfolding of this answer, in the case you are not familiar with basic measure theory.
– user21820
yesterday
The essence would be: Regardless of how fast a function $f: mathbb N rightarrow mathbb N $ grows: it remains countable?
– Hans Stricker
2 days ago
The essence would be: Regardless of how fast a function $f: mathbb N rightarrow mathbb N $ grows: it remains countable?
– Hans Stricker
2 days ago
2
2
@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 $mathbbR^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"
– Brevan Ellefsen
2 days ago
@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 $mathbbR^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"
– Brevan Ellefsen
2 days ago
@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 $mathbbN$ to $mathbbN$, it's $mathbbN$ to sets of subsets of $mathbbR^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. $|mathbbN|*|mathbbN|=|mathbbN|$.
– Acccumulation
2 days ago
@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 $mathbbN$ to $mathbbN$, it's $mathbbN$ to sets of subsets of $mathbbR^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. $|mathbbN|*|mathbbN|=|mathbbN|$.
– Acccumulation
2 days ago
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.
– Acccumulation
2 days ago
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.
– Acccumulation
2 days ago
@HansStricker: See my answer for a concrete unfolding of this answer, in the case you are not familiar with basic measure theory.
– user21820
yesterday
@HansStricker: See my answer for a concrete unfolding of this answer, in the case you are not familiar with basic measure theory.
– user21820
yesterday
 |Â
show 1 more comment
up vote
18
down vote
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.
answered 2 days ago
Micah
28.7k1361102
What about $(pi,0)$? (Restricting the question to the real line. At least $(pi,0)$ is not constructible in the narrower sense.)
– Hans Stricker
2 days ago
5
$pi$ and $0$ are not algebraically independent.
– Ethan Bolker
2 days ago
So the answer is just "No: Not for any given point $pinmathbbR^2$ there is a line or circle constructible in finitely many steps (starting from points $[0,0]$ and $[1,0]$) which $p$ lies on."?
– Hans Stricker
2 days ago
3
@HansStricker: Surely the whole real line, including $(pi,0)$, is constructible in your sense? It is the line through $(0,0)$ and $(1,0)$,
– TonyK
2 days ago
1
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."
– Hans Stricker
2 days ago
 |Â
show 4 more comments
up vote
18
down vote
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.
answered 2 days ago
Micah
28.7k1361102
What about $(pi,0)$? (Restricting the question to the real line. At least $(pi,0)$ is not constructible in the narrower sense.)
– Hans Stricker
2 days ago
5
$pi$ and $0$ are not algebraically independent.
– Ethan Bolker
2 days ago
So the answer is just "No: Not for any given point $pinmathbbR^2$ there is a line or circle constructible in finitely many steps (starting from points $[0,0]$ and $[1,0]$) which $p$ lies on."?
– Hans Stricker
2 days ago
3
@HansStricker: Surely the whole real line, including $(pi,0)$, is constructible in your sense? It is the line through $(0,0)$ and $(1,0)$,
– TonyK
2 days ago
1
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."
– Hans Stricker
2 days ago
 |Â
show 4 more comments
up vote
18
down vote
up vote
18
down vote
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.
answered 2 days ago
Micah
28.7k1361102
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.
answered 2 days ago
Micah
28.7k1361102
answered 2 days ago
Micah
28.7k1361102
answered 2 days ago
Micah
28.7k1361102
answered 2 days ago
Micah
28.7k1361102
28.7k1361102
What about $(pi,0)$? (Restricting the question to the real line. At least $(pi,0)$ is not constructible in the narrower sense.)
– Hans Stricker
2 days ago
5
$pi$ and $0$ are not algebraically independent.
– Ethan Bolker
2 days ago
So the answer is just "No: Not for any given point $pinmathbbR^2$ there is a line or circle constructible in finitely many steps (starting from points $[0,0]$ and $[1,0]$) which $p$ lies on."?
– Hans Stricker
2 days ago
3
@HansStricker: Surely the whole real line, including $(pi,0)$, is constructible in your sense? It is the line through $(0,0)$ and $(1,0)$,
– TonyK
2 days ago
1
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."
– Hans Stricker
2 days ago
 |Â
show 4 more comments
What about $(pi,0)$? (Restricting the question to the real line. At least $(pi,0)$ is not constructible in the narrower sense.)
– Hans Stricker
2 days ago
5
$pi$ and $0$ are not algebraically independent.
– Ethan Bolker
2 days ago
So the answer is just "No: Not for any given point $pinmathbbR^2$ there is a line or circle constructible in finitely many steps (starting from points $[0,0]$ and $[1,0]$) which $p$ lies on."?
– Hans Stricker
2 days ago
3
@HansStricker: Surely the whole real line, including $(pi,0)$, is constructible in your sense? It is the line through $(0,0)$ and $(1,0)$,
– TonyK
2 days ago
1
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."
– Hans Stricker
2 days ago
What about $(pi,0)$? (Restricting the question to the real line. At least $(pi,0)$ is not constructible in the narrower sense.)
– Hans Stricker
2 days ago
What about $(pi,0)$? (Restricting the question to the real line. At least $(pi,0)$ is not constructible in the narrower sense.)
– Hans Stricker
2 days ago
5
5
$pi$ and $0$ are not algebraically independent.
– Ethan Bolker
2 days ago
$pi$ and $0$ are not algebraically independent.
– Ethan Bolker
2 days ago
So the answer is just "No: Not for any given point $pinmathbbR^2$ there is a line or circle constructible in finitely many steps (starting from points $[0,0]$ and $[1,0]$) which $p$ lies on."?
– Hans Stricker
2 days ago
So the answer is just "No: Not for any given point $pinmathbbR^2$ there is a line or circle constructible in finitely many steps (starting from points $[0,0]$ and $[1,0]$) which $p$ lies on."?
– Hans Stricker
2 days ago
3
3
@HansStricker: Surely the whole real line, including $(pi,0)$, is constructible in your sense? It is the line through $(0,0)$ and $(1,0)$,
– TonyK
2 days ago
@HansStricker: Surely the whole real line, including $(pi,0)$, is constructible in your sense? It is the line through $(0,0)$ and $(1,0)$,
– TonyK
2 days ago
1
1
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."
– Hans Stricker
2 days ago
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."
– Hans Stricker
2 days ago
 |Â
show 4 more comments
up vote
10
down vote
Here's a geometric (as opposed to algebraic) argument.
Let $C$ be the set of points of $mathbbR^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 mathbbR^2$.
To see this, we'll define a family of sets $P_n$, for $n in mathbbN$, 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 mathbbN$, let $C_n$ be the set of points in $mathbbR^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 = bigcuplimits_n=0^infty C_n$$
It now suffices to prove that $C_n$ is nowhere-dense for each $n in mathbbN$, so that $C ne mathbbR^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 mathbbN$. 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 mathbbN$ 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$.
answered 2 days ago
Clive Newstead
48.3k471131
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"?
– Hans Stricker
2 days ago
2
This proof uses more properties of $mathbbR^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 $mathbbR^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 ;)
– Clive Newstead
2 days ago
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.
– Jack M
yesterday
add a comment |Â
up vote
10
down vote
Here's a geometric (as opposed to algebraic) argument.
Let $C$ be the set of points of $mathbbR^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 mathbbR^2$.
To see this, we'll define a family of sets $P_n$, for $n in mathbbN$, 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 mathbbN$, let $C_n$ be the set of points in $mathbbR^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 = bigcuplimits_n=0^infty C_n$$
It now suffices to prove that $C_n$ is nowhere-dense for each $n in mathbbN$, so that $C ne mathbbR^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 mathbbN$. 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 mathbbN$ 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$.
answered 2 days ago
Clive Newstead
48.3k471131
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"?
– Hans Stricker
2 days ago
2
This proof uses more properties of $mathbbR^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 $mathbbR^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 ;)
– Clive Newstead
2 days ago
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.
– Jack M
yesterday
add a comment |Â
up vote
10
down vote
up vote
10
down vote
Here's a geometric (as opposed to algebraic) argument.
Let $C$ be the set of points of $mathbbR^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 mathbbR^2$.
To see this, we'll define a family of sets $P_n$, for $n in mathbbN$, 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 mathbbN$, let $C_n$ be the set of points in $mathbbR^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 = bigcuplimits_n=0^infty C_n$$
It now suffices to prove that $C_n$ is nowhere-dense for each $n in mathbbN$, so that $C ne mathbbR^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 mathbbN$. 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 mathbbN$ 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$.
answered 2 days ago
Clive Newstead
48.3k471131
Here's a geometric (as opposed to algebraic) argument.
Let $C$ be the set of points of $mathbbR^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 mathbbR^2$.
To see this, we'll define a family of sets $P_n$, for $n in mathbbN$, 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 mathbbN$, let $C_n$ be the set of points in $mathbbR^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 = bigcuplimits_n=0^infty C_n$$
It now suffices to prove that $C_n$ is nowhere-dense for each $n in mathbbN$, so that $C ne mathbbR^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 mathbbN$. 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 mathbbN$ 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$.
answered 2 days ago
Clive Newstead
48.3k471131
edited 2 days ago
answered 2 days ago
Clive Newstead
48.3k471131
answered 2 days ago
Clive Newstead
48.3k471131
answered 2 days ago
Clive Newstead
48.3k471131
48.3k471131
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"?
– Hans Stricker
2 days ago
2
This proof uses more properties of $mathbbR^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 $mathbbR^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 ;)
– Clive Newstead
2 days ago
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.
– Jack M
yesterday
add a comment |Â
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"?
– Hans Stricker
2 days ago
2
This proof uses more properties of $mathbbR^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 $mathbbR^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 ;)
– Clive Newstead
2 days ago
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.
– Jack M
yesterday
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"?
– Hans Stricker
2 days ago
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"?
– Hans Stricker
2 days ago
2
2
This proof uses more properties of $mathbbR^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 $mathbbR^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 ;)
– Clive Newstead
2 days ago
This proof uses more properties of $mathbbR^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 $mathbbR^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 ;)
– Clive Newstead
2 days ago
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.
– Jack M
yesterday
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.
– Jack M
yesterday
add a comment |Â
up vote
4
down vote
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:
$
deflfrac#1#2largefrac#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 $lfrac8(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.
answered yesterday
user21820
36.2k440140
I'm utterly amazed!
– Hans Stricker
yesterday
1
@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.
– user21820
yesterday
Yes, it actually did, thank you.
– Hans Stricker
yesterday
add a comment |Â
up vote
4
down vote
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:
$
deflfrac#1#2largefrac#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 $lfrac8(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.
answered yesterday
user21820
36.2k440140
I'm utterly amazed!
– Hans Stricker
yesterday
1
@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.
– user21820
yesterday
Yes, it actually did, thank you.
– Hans Stricker
yesterday
add a comment |Â
up vote
4
down vote
up vote
4
down vote
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:
$
deflfrac#1#2largefrac#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 $lfrac8(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.
answered yesterday
user21820
36.2k440140
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:
$
deflfrac#1#2largefrac#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 $lfrac8(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.
answered yesterday
user21820
36.2k440140
answered yesterday
user21820
36.2k440140
answered yesterday
user21820
36.2k440140
answered yesterday
user21820
36.2k440140
36.2k440140
I'm utterly amazed!
– Hans Stricker
yesterday
1
@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.
– user21820
yesterday
Yes, it actually did, thank you.
– Hans Stricker
yesterday
add a comment |Â
I'm utterly amazed!
– Hans Stricker
yesterday
1
@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.
– user21820
yesterday
Yes, it actually did, thank you.
– Hans Stricker
yesterday
I'm utterly amazed!
– Hans Stricker
yesterday
I'm utterly amazed!
– Hans Stricker
yesterday
1
1
@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.
– user21820
yesterday
@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.
– user21820
yesterday
Yes, it actually did, thank you.
– Hans Stricker
yesterday
Yes, it actually did, thank you.
– Hans Stricker
yesterday
add a comment |Â
up vote
1
down vote
This set is certainly dense in $mathbbR^2$. In other words $overlinemathbbQ^sqrt=mathbbR$. 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.
answered 2 days ago
cactus314
15.1k41862
Great hint, thank you.
– Hans Stricker
yesterday
add a comment |Â
up vote
1
down vote
This set is certainly dense in $mathbbR^2$. In other words $overlinemathbbQ^sqrt=mathbbR$. 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.
answered 2 days ago
cactus314
15.1k41862
Great hint, thank you.
– Hans Stricker
yesterday
add a comment |Â
up vote
1
down vote
up vote
1
down vote
This set is certainly dense in $mathbbR^2$. In other words $overlinemathbbQ^sqrt=mathbbR$. 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.
answered 2 days ago
cactus314
15.1k41862
This set is certainly dense in $mathbbR^2$. In other words $overlinemathbbQ^sqrt=mathbbR$. 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.
answered 2 days ago
cactus314
15.1k41862
answered 2 days ago
cactus314
15.1k41862
answered 2 days ago
cactus314
15.1k41862
answered 2 days ago
cactus314
15.1k41862
15.1k41862
Great hint, thank you.
– Hans Stricker
yesterday
add a comment |Â
Great hint, thank you.
– Hans Stricker
yesterday
Great hint, thank you.
– Hans Stricker
yesterday
Great hint, thank you.
– Hans Stricker
yesterday
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2911971%2fcovering-the-euclidean-plane-with-constructible-lines-and-circles%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Hurwitz complex continued fractions
– Ed Pegg
2 days ago
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.)
– Hans Stricker
2 days ago
1
Note that a line or a circle cover no area, so that your impressively filled picture contains a null fraction of the plane.
– Yves Daoust
2 days ago
1
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: $|mathbbR| = |mathbbR^2|$.
– Hans Stricker
2 days ago
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.
– Andrés E. Caicedo
2 days ago