|
Constructible Points and Coverable Points |
|
|
|
Given a set A0 of discrete points in the plane, draw all possible lines and circles (by Euclidean methods) based on the points of A0 and let A1 denote the union of A0 and the new points formed by the intersections of those lines and circles. Repeat this process on A1 to generate the set A2, and so on. If we let A0 consist of the two points with Cartesian coordinates (0,0) and (1,0), we can construct one line and two circles on set A0, yielding four new points, for a total of 6 distinct points in set A1. How many distinct circles and lines can be constructed on the points of A1, and how many distinct points are contained in A2? In general, how many distinct points are contained in Ak? |
|
|
|
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 (21/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 ﬡ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 pairs A0 and B0 of initial points, let Q be a non-constructible point relative to both of these sets. On the assumption that every point in the plane is coverable, there would be a finite sequence of steps to construct the unique locus containing Q in system A0, and a finite sequence of steps to construct the unique locus containing Q in system B0. Thus, assuming the locus that covers Q in system A0 is not the same locus that covers Q in system B0, 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 ﬡ0. The only escape from this argument would be if all but a countable subset of the points covered by A0 were covered in system B0 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 (π,e), was coverable? |
|
|
|
As an aside, it's also interesting to consider the abstract pseudo-metric 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 Ak 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" |
|
|
|
|
|
|
|
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.) |
|
|
