# Subset of the plane that intersects every line exactly twice

In a comment to this question, Tim Gowers remarked that using the axiom of choice, one can show that there exists a subset of the plane that intersects every line exactly twice (although it has yet to be shown that choice is required).

Unfortunately, I haven't been able to track down a reference, so if someone could link me to the original result (or provide a short proof) that would be great. I have roughly worked out a proof for myself, and I'd like to check it against the literature.

• mathnerds.com/best/Mazurkiewicz/solution.aspx – t3suji Apr 15 '10 at 16:36
• Krzysztof Ciesielski proves it in the book "Set Theory for the Working Mathematician" – Jason DeVito Apr 15 '10 at 16:53
• Problem 12.7 in Komjáth, Totik: Problems and Theorems in Classical Set Theory. The problem is formulated on p. 60, the solution is given on p. 287. – Martin Sleziak Oct 24 '14 at 14:38

By AC, choose a cardinal well-ordering of the lines in in the plane and any well-ordering of all the points.

We proceed by transfinite induction.

Suppose $A_l$ is a set of points, no three colinear, and let $B_l$ be the set of lines spanned by points of $A_l$, and let $C_l=\cup B_l$. Suppose further that $l'\prec l$ implies $l'\in B_l$. Note that $|A_l| \leq |B_l| < |l|$, so that $$|C_l\cap l| = |\cup_{l'\in B_l} l\cap l'| < |l| .$$

• If $l\in B_l$, let $A_{Sl} = A_l$.
• If $a\in l \cap A_l$, take the minimal point $b\in l\backslash C_l$ and let $A_{Sl} = A_l\cup \{b\}$.
• If $A_l\cap l = \emptyset$, take the minimal two points $a,b\in l\backslash C_l$, and let $A_{Sl}=A_l\cup\{a,b\}$.
• Otherwise if $l'\$ is a limit ordinal, let $A_{l'} = \bigcup_{l\prec l'} A_l$.

It is easy to check that $A_{l'}$ has no three points colinear --- they'd have to all be in some $A_l$ for $l\prec l'$. The final union $\bigcup_l A_l$ has exactly two points on each line $l$.

• Thanks some guy on the street! This is essentially isomorphic (although cleaner) to what I thrashed out, so I'm pleased that I can still do some basic set theory. Thanks also to Jason and t3suji for the links in the comments. – Tony Huynh Apr 15 '10 at 17:10
• oh, nice! and reciprocally, I'm sure. The trick, of course, is the cardinal ordering --- which is why we can be sure that $l$ still has lots of points to choose from. – some guy on the street Apr 15 '10 at 17:13
• Another thing is --- for stylistic reasons --- I like to get all the choices out of the way at the beginning. It makes the induction closer to the style of oracular programming, even if the program takes a very long time to run! – some guy on the street Apr 15 '10 at 17:16

This theorem is originally to S. Mazurkiewicz. In Sierpinski's book "Cardinal and Ordinal Numbers", the theorem is proved on page 449 (Chapter 17, Section 2). In fact the following more general result by F. Bagemihl ("A theorem on intersections of prescribed cardinality", Annals of Math., 55 (1952), p. 34, jstor) holds:

Theorem: Suppose that every straight line $S$ lying in a plane is associated with cardinal number $m_S$ such that $2 \leq m_S \leq 2^{\aleph_0}$. Then there exists a plane set $Q$ such that the cardinality of $Q \cap S$ is $m_S$ for every straight line $S$ in the plane.

(I am mentioning Sierpinski's book because it might be more easily available than 1952 issues of Annals of Mathematics.)

It's still an open problem whether there exists a Borel set that is a 2-point set (or $n$-point set for that matter). There is a PhD-thesis from my alma mater (Free University Amsterdam) by K.Bouhjar (under Jan van Mill) (2002) called "On the structure of N-point sets". This has some more info on sets like this. One result is that no $n$-point set in the plane can be $\sigma$-compact.

• If my memory serves, it's open even for G_delta sets (but known that they cannot be F_sigma sets). – gowers Apr 19 '10 at 17:59

Here is a minor variation of the proof.

We show that there is a subset $Z$ of $\mathbb R^2$ which intersects each line exactly twice.

We define the ordinals in such a way that each ordinal $a$ is the set of those ordinals $< a$. For any set $S$ we write $|S|$ for the least ordinal equipotent to $S$, and call it the cardinality of $S$. Let $c$ (for continuum) be the cardinality of $\mathbb R$. For any subset $S$ of $\mathbb R^2$ we denote by $\langle S\rangle$ the set of lines generated by $S$ (a line being generated by $S$ if it has at least two points in common with $S$). Let $d\mapsto L_d$ be a bijection from $c$ onto the set of lines in $\mathbb R^2$.

For each $d\in c$ we define $Z_d\subset\mathbb R^2$, $f(d)\in c$, and $z_d\in\mathbb R^2$, as follows. Let $z_0$ be any point of $L_0$, put $f(0)=0$, and let $Z_0$ be the empty set. Now assume $0< d< c$, and $f(e), z_e$ already defined for $e < d$. Put $Z_d:=$ {$z_e\ |\ e< d$}. As $|\langle Z_d\rangle|< c$ (because $|Z_d|< c$), there is a least $f(d)$ in $c$ such that $L_{f(d)}\notin\langle Z_d\rangle$. Let $z_d$ be any point of the set

$$L_{f(d)}-(Z_d\cup(\cup\langle Z_d\rangle)),$$

which is easily seen to be nonempty.

Let $Z$ be the union of the $Z_d$ and $L$ any line in $\mathbb R^2$. We claim $|L \cap Z|=2$, that is, $Z$ is the sought-for subset of $\mathbb R^2$. To prove $|L\cap Z|\le2\ (*)$ we assume by contradiction that there are $g< h< i$ in $c$ such that $z_g,z_h,z_i\in L\cap Z$. We have $z_g,z_h\in Z_i$ by definition of $Z_i$, and thus $L\in\langle Z_i\rangle$, contradicting the definition of $z_i$. To prove $|L\cap Z|\ge2$ we assume by contradiction $|L\cap Z|< 2$. Put $L=L_d$ and let $g$ be in $c$. The inequality $|L_d\cap Z_g|<2$ implies $L_d\notin\langle Z_g\rangle$, and thus $f(g)\le d$ by minimality of $f(g)$. This shows that $Z$ is contained into the union of the $L_e$ such that $e\le d$. As $|L_e\cap Z|\le2$ by $(*)$, we get $|Z|\le2|d|+2< c$, contradicting the obvious equality $|Z|=c$.