Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In a comment to this question, Tim Gowers remarked that using the axiom of choice, once 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.

share|improve this question
2  
    
Krzysztof Ciesielski proves it in the book "Set Theory for the Working Mathematician" –  Jason DeVito Apr 15 '10 at 16:53

5 Answers 5

up vote 3 down vote accepted

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

share|improve this answer
    
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 (Chatper 17, Section 2). In fact the following more general result by F. Bagemihl ("A theorem on intersections of precscribed cardinality", Annals of Math., 55 (1952), p. 34) holds:

Theorem: Suppose that every straight line $S$ lying in a plane is associated with cardinal number $m_S$ such that $2 \leq m \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.)

share|improve this answer

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.

share|improve this answer
    
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

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.

share|improve this answer
    
What, you don't believe in Jungian synchronicity? –  Gerry Myerson May 14 '10 at 7:15
    
Dear Gerry, I looked it up, I seem to believe in it. I have heard often enough of a certain mathematics topic being "in the air" meaning a variety of people were talking about it at roughly the same time. But the version with the word conspiracy tested better with the focus group. –  Will Jagy May 14 '10 at 18:43

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.