Subset of the plane that intersects every line exactly twice

Question

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.

Answer 1

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$.

Answer 2

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 \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.)

Answer 3

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.

Answer 4

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$.

A pdf version is available here (Wayback Machine).

Answer 5

An article on almost exactly this question appears in the current M.A.A. Monthly, volume 117, number 5, May 2010, pages 414-423, Alexander B. Kharazishvili and Tengiz Sh. Tetunashvili, "On Some Coverings of the Euclidean Plane with Pairwise Congruent Circles." I'm not so sure this available for free online, the A.M.S. does that but I'm not sure about the M.A.A.

I've got to say, this is at least the third time that I have put in a comment or answer that says "It's funny, related material appears in the current issue of this journal." I believe this points to a widespread conspiracy.