Constructible Points and Coverable Points

Given a set A of discrete points in the plane, draw all possible 
lines and circles (by Euclidean methods) based on the points of A 
and let A_1 denote the union of A and the new points formed by the 
intersections of those lines and circles.  Repeat this process on 
A_1 to generate the set A_2, and so on.  

If we let A consist of the two points with cartesian coordinates
(0,0) and (1,0), we can construct one line and two circles on
set A, yielding four new points, for a total of 6 distinct points
in set A_1.  How many distinct circles and lines can be constructed 
on the points of A_1, and how many distinct points are contained in 
A_2?  In general, how many distinct points are contained in A_k?  
Also, what is the density of the points in A_k?

Aside from these quantitative questions, it's interesting to consider 
the abstract pseudometric space of Euclidean proof/constructibility.  
We define the "distance" d(A,B) from set A to set B as the least 
integer k such that A_k contains B.  If no such integer exists then 
d(A,B) is said to be infinite.  Obviously d(A,B) = 0  if and only if
B is contained in A.  We also have the "triangle inequality"

             d(A,C)  < =  d(A,B) + d(B,C)

However, this measure is not commutative, i.e., d(A,B) is generally 
not equal to d(B,A).  This "directional asymmetry" seems to be a 
general characteristic of information spaces.  (For example, given
two primes you can find their product easily, but given their
product it's much harder to determine the two primes.)

A related question is whether, given only a straight-edge, a compass,
and two initial points on the plane, we can completely "cover" the 
plane.  In other words, is every point in the plane contained in at
least one line or circular arc constructible from two given points?
Notice that covering a point is not the same as constructing it.  A
constructible point is the intersection of TWO distinct constructible
lines or arcs, whereas each constructible line and arc contains 
infinitely many non-constructible points.  For example, if our two
initial points have cartesian coordinates (0,0) and (1,0) it's 
impossible to construct the point (2^(1/3),0), but nevertheless this
point is "covered" by the constructible line through the two given 
points.

Even though the cardinality of the coverable points is c (whereas the
cardinality of constructible points is aleph_0), there must exist 
infinitely many uncoverable points on the plane relative to any two
given points.  Suppose the contrary, i.e., that EVERY point was 
coverable from two given points.  It would follow that every point 
was coverable from ANY two (distinct) points.  Given two unrelated 
sets of initial points A1,A2 and B1,B2, let Q be a non-constructible
point relative to both of these sets.  On the assumption that evey 
point in the plane is coverable, there would be a finite sequence of
steps to construct the unique locus containing Q in system A, and a 
finite sequence of steps to construct the unique locus containing Q 
in system B.  Thus, assuming the locus that covers Q in system A is 
not the same locus that covers Q in system B, we would be able to 
construct any point Q in the plane by a finite sequence of steps from
four initial points.  This is clearly impossible, because the set of 
points of the plane has cardinality c whereas the set of points 
constructible from four given points has cardinality aleph_0.

The only escape from this argument would be if all but a countable
subset of the points covered by A were covered in system B *by exactly
the same locus*, which seems fairly implausible for arbitrary systems.

So, assuming the existence of uncoverable points relative to the 
initial set {(0,0),(1,0)}, how would we go about deciding whether a
particular point, such as (pi,e), was coverable?

Return to MathPages Main Menu