Mazurkiewicz's Theorem on 2-Point Sets

Does there exist a subset of the plane such that every straight line intersects the set at exactly two points?

(Remark. A set that intersects every line of the plane in exactly n points is called an n-point set or sometimes a Mazurkiewicz set. A 1-point set is clearly impossible; this question asks whether 2-point sets exist.)

Need a hint? Click here.

Click here for the complete solution.

Hint 1

The answer is Yes, although it's hard to visualize such a set. This result was proved by Stefan Mazurkiewicz in 1914, and we will show his proof. In this article we will show how to construct the set using transfinite recursion. Surprisingly the construction uses almost no facts about geometry or the plane, but it does use some facts about transfinite numbers, so you should be familiar with those. (Most books on set theory discuss this topic.)

Let's practice on a simpler version of the problem before we take a leap into the transfinite. Suppose we are given a finite collection of straight lines in the plane, L_1, ..., L_N. Describe a method for generating a set of points in the plane such that (1) each line of this collection intersects exactly two members of the set, and (2) any line in the plane intersects at most two members of the set. An easy way to do this would be to draw a very large circle, large enough that every line intersects it; but this method does not generalize well, so think of some other method where you select the points one at a time.

Hint 2

The set of points can be defined in a simple way by induction. We will define the sequence of points y_1, y_2, .... We'll also define the sets A_2, A_3, ... by A_k = \{y_1, y_2, ..., y_{k-1} \}. We write A for the set of all y_k.

• Define y_1 as any point of L_1.
• Having defined y_1, ..., y_{k-1}, define y_k as follows. If all the L_i intersect A_k in at least two points, we are finished. Otherwise, pick the smallest i such that L_i intersects A_k in fewer than two points. Choose y_k as any point of L_i that is not already in A_k and that is not co-linear with any two points of A_k.

By construction, no three points of any A_k are co-linear, so no line in the plane intersects A in more than two points. The construction clearly terminates after at most 2N steps, because each step adds a point and there are at most 2 points per line.

Note that this construction gradually works its way up through the lines. In general we add two points on each line, then step to the next-numbered line, and in the general case we end up with a set containing 2N points. It's possible that the final set may be smaller; it may happen that a point chosen from one line also occurs in a later line, so when we get to the later line we don't have to add two points.

Now we have to make the leap to transfinite numbers. Our constructions works well for a finite collection of lines; how can we extend it to the collection of all lines of the plane?

The Rest of the Solution

We can actually use the same construction in a transfinite recursion that will step through all lines of the plane! But we have to define the recursive step with a little more care to ensure that all lines get used.

We'll write c for the cardinality of the continuum; that is, the transfinite cardinal for the real line. This is also the cardinality of points of the plane, and the cardinality of the straight lines in the plane (each straight line is determined by two points). We'll also write O_c for the first transfinite ordinal that has cardinality c (there is a first one because the ordinals are well-ordered). The collection of all straight lines in the plane has cardinality c and therefore can be put in a one-to-one correspondence with O_c. This establishes a well-ordering of this collection, so we can refer to individual lines by indexing them:

Note that this choice of indexing has the special property that any initial segment \{L_i | i < d\} where d < c has a smaller cardinality than c, even though the whole collection of lines has cardinality c, because O_c is the smallest ordinal with cardinality c. In the same way we can index all the points of the plane: {x_i} where i < c.

Now our construction of the y_k and A_k is almost the same as before. The transfinite recursion step is that, having defined all y_i for i < k where k < c is an ordinal number, we define y_k as before, except that to make the recursion well-defined, we always choose the first suitable point on the line (using the ordering on x_i).

In this infinite case we need an argument to show that there always exists a line L_i that works, and we need a new argument to show that all lines intersect A in at least two points (as before, by construction they intersect A_k in at most two points).

It's easy to see that we won't run out of lines. For any k, A_k has cardinality less than c (k is an initial segment of O_c), and each line contains at most two y_i , so the number of lines that intersect A_k also has cardinality less that c.

Showing that each line intersects at least two points of A is more subtle, but it is the same idea as the finite case: We are gradually working through the lines in order, adding two points per line, so if some line has fewer than two points, this means the process has stalled somehow, and we'll show this is impossible. To make this argument precise, let's assume there are lines intersecting A in fewer than two points. Then there is a first such line, call it L_r. We observe that A has cardinality c, because it has an element y_i for each i < c. The set of lines

has cardinality less than c, and each contains at most two elements of A, so there are elements of A not in any line of this set. Using the ordering of the y_i (not the ordering of the x_i) let y_m be the first such point. We know y_m is not in A_m, because it is added to A_m to form A_{m+1}. Let L_s be the line that we use when selecting y_m , so that y_m is in L_s. We will now derive a contradiction by considering where the ordinal s is relative to r. We know s > r is impossible, because L_r intersects A in fewer than two points and so in particular intersects A_m in fewer than two points, meaning that we could not have picked the later L_s to select y_m from. We also know that s \le r is impossible, because L_s would be a line of the collection G, but we chose y_m so that it is not in any line of that collection. Therefore we have a contradiction, and there is no such line as L_r.

Well-Ordering, The Axiom of Choice, and Zorn's Lemma

Mazurkiewicz's proof is a rare instance of transfinite induction being used to prove some result outside of set theory (his theorem is considered to be topology). Relative to the Zermelo-Fraenkel axioms for set theory, there are three results that are equivalent (in the sense that any one can be proved easily from any other):

• The Well-Ordering Principle: Any set can be well-ordered (that is, given a total order such that any subset has a minimum).
• The Axiom of Choice: Any collection of sets has a choice function; that is, a function that maps each set to an element of that set. Informally this says we can always write "pick an element from each set" even for infinite collections.
• Zorn's Lemma: If every totally-ordered subset of an ordered set has an upper bound in the set, then there is a maximal element in the set.

In mathematics in general (outside of set theory) Zorn's Lemma is the most commonly used of these three results. One example of its use is Tychonoff's Theorem that the cartesian product of any collection of compact topological spaces (even an infinite collection) is itself compact.

References

• Sam's original question is here.
• Mazurkiewicz's original proof was published in Polish in 1914; we follow the French translation that was published in his collected works in 1969. "Sur un ensemble plan qui a avec chaque droite deux et seulement deux points communs", in: Travaux de Topologie et ses Applications by Stefan Mazurkiewicz, edited by Karol Borsuk et al., PWN, 1969.
• Waclaw Sierpinski, Cardinal and Ordinal Numbers, 2nd edition revised, PWN, 1965. Chapter XVII, Section 2, "Plane set having exactly two points in common with every line", pp. 449-450. Another exposition of Mazurkiewicz's proof.
• Paul R. Halmos, Naive Set Theory, Springer reprint, 1974. A good book on set theory; includes everything you need to know to understand Mazurkiewicz's proof.
• Patrick Suppes, Axiomatic Set Theory, Van Nostrand, 1960. Another good book on set theory, based on the Zermelo-Fraenkel axioms. It has an especially thorough discussion of transfinite induction and recursion (Chapter 7).
• Tychonoff's Theorem is proved in most books on abstract analysis, for example: Avner Friedman, Foundations of Modern Analysis, Dover reprint, 1982, section 4.11.