% LaTeX 2.09
\documentstyle[12pt]{article}

\input amssym.def
\input amssym
%% if amssym.def and amssym.tex are not available uncomment lines below
%\def\Bbb#1{{\bf #1}}
%\def\upharpoonright{|_}

\def\res{\upharpoonright}
\def\bairespace{\omega^{\omega}}
\def\cantorspace{2^{\omega}}
\def\setof{\;\;|\;\;}
\def\And{\wedge}
\def\proof{proof}
\def\qed{\nopagebreak\par\noindent\nopagebreak$\Box$\par}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\begin{document}

\begin{center}
{\LARGE Two remarks about analytic sets}
\footnote{in {\bf Lecture Notes in Mathematics},
Springer-Verlag, 1401(1989), 68-72.}
\end{center}

\begin{center}
Fons van Engelen\footnote{Research partially supported by the Netherlands
organization for the advancement of pure research}\\
Vr\"{y}e Universiteit\\
Subfaculteit Wiskunde\\
De Boeleaan 1081\\
1081 HV Amsterdam\\
The Netherlands\\
\mbox{ }\\
Kenneth Kunen\\
Department of Mathematics\\
University of Wisconsin\\
Madison, Wisconsin 53706\\
\mbox{ }\\
Arnold W. Miller\footnote{Research partially supported by NSF grant
MCS-8401711}\\
Department of Mathematics\\
University of Wisconsin\\
Madison, Wisconsin 53706\\
\end{center}

\centerline{Abstract}
\begin{quote}
   In this paper we give two results about analytic sets.  The first
   is a counterexample to a problem of Fremlin. We show that there
   exists $\omega_1$ compact subsets of a Borel set with the property
   that no $\sigma$-compact subset of the Borel set covers them.
   In the second section we prove that for any analytic subset A of
   the plane either A can be covered by countably many lines or
   A contains a perfect subset P which does not have three collinear
   points.
\end{quote}


In his book about Martin's Axiom \cite{fremlin} p. 61
 D. H. Fremlin shows that, assuming MA,
 for any analytic set X and set $A\subset X$
 of cardinality less than the continuum there exists a $\sigma$-compact
 set L such that $A\subset L\subset X$. ($\sigma$-compact means countable
 union of compact sets.)
  Here we show that
 the set $A$ cannot be replaced by a family of compact sets of cardinality
 $\omega_1$. This answers a question of Fremlin \cite{fremlin} p.67.

Let $\Bbb Q$ be the rationals and let $ E={\Bbb Q}^{\omega}$. E is a $\Pi^0_3$
set, or equivalently an $F_{\sigma\delta}$ set.
For each $\alpha<\omega_1$
let $C_{\alpha}$ be a compact subset of $\Bbb Q$ which is homeomorphic to
$\alpha+1$ and let $H_{\alpha}=C_{\alpha}^{\omega}$.

\begin{theorem}
There does not exists a $\sigma$-compact set L such that
for every $\alpha<\omega_1$, $H_{\alpha}\subset L\subset E$.
\end{theorem}

\begin{lemma}
For every compact set $K\subset \Bbb Q$ there exists $\alpha <\omega_1$
such that for all $\beta>\alpha$, $C_{\beta}\setminus K$ is nonempty.
\end{lemma}
\proof

This follows easily from a well-known theorem of Sierpi\'{n}ski
that every countable scattered space is isomorphic to an ordinal.
For simplicity we sketch a proof here.

Let $D(X)$ be the derivative operator, i.e. $D(X)$ is the set of
nonisolated points of X. Then let $D^{\alpha}(X)$ be the usual
$\alpha^{\mbox{th}}$ iterate of D, defined by induction as follows.

$$D^{\alpha+1}(X)=D(D^{\alpha}(X))$$
$$D^{\lambda}(X)=\cap_{\alpha<\lambda} D^{\alpha}(X)
  \mbox{ if $\lambda$ a limit ordinal} $$
 Define the
rank of any X (rank(X)) as the least $\alpha$ such that $D^{\alpha}(X)$ is
empty.

Then the lemma follows easily from the following facts:

\begin{enumerate}
 \item Every compact subset of $\Bbb Q$ has a countable rank.
 \item If $X\subset Y$ then $D(X)\subset D(Y)$.
 \item If $X\subset Y$ then  rank(X)$\leq$rank(Y).
 \item rank$(C_{\omega^{\alpha}+1})=\alpha+1$.
\end{enumerate}

\qed

To prove the Theorem let $L=\bigcup_{n\in\omega}L_{n}$ where
each $L_{n}$ is compact. Let $K_{n}\subset \Bbb Q$ be the projection
of $L_{n}$ onto the $n^{th}$ coordinate.  By the lemma
there exists $C_{\beta}$ which is not covered by any $K_{n}$.
 It follows that $H_{\beta}$ is not covered by L.
\qed

We don't know whether the theorem is true for $\Sigma^0_3$ sets
($G_{\delta\sigma}$) or even
for a set which is the union of a countable set and
a $\Pi^0_2$ ($G_{\delta}$).

Next we prove the following theorem:

\begin{theorem}
Suppose that A is an analytic subset of the plane, ${\Bbb R}^2$,
 which cannot be covered by
countably many lines.  Then there exists a perfect subset P of A
such that no three points of P are collinear.
\end{theorem}
\proof

A set is perfect iff it is homeomorphic to the Cantor space $\cantorspace$.
The proof we give is similar to the classical proof that uncountable
analytic sets must contain a perfect subset. A subset $A$ of a
complete separable space $X$
 is analytic iff there exists a closed set $C\subset \bairespace\times X$
 such that $A$ is the projection of $C$, i.e.

$$A=\mbox{p}(C)=\{y\in X\setof\exists x\in\bairespace\;(x,y)\in C\}$$
Every Borel subset of $X$ is analytic.

Let $A$ be analytic subset of the plane ${\Bbb R}^2$
 which cannot be covered by
countably many lines.
Let $S$ be the unit square $([0,1]\times [0,1])$ minus all lines of the
form $x=r$ or $y=r$ for r a rational number.  Without loss of generality
we may assume that $A$ is a subset of $S$. Since $S$ is a complete
separable space
there exists $C\subset \bairespace\times S$ a closed set such that
$A=p(C)$.

Give $S$ the basis $B_s$ for $s\in 4^{<\omega}$  described in
figure \ref{square}.
( $4^{<\omega}$ is the
set of finite sequences of elements
from $4=\{0,1,2,3\}$)


\begin{figure}
\unitlength=1.2mm
\begin{picture}(125,60)(0,120)

\put(10,155){\framebox(20,20){$B_{<0>}$}}
\put(30,155){\framebox(20,20){$B_{<1>}$}}
\put(30,135){\framebox(20,20){$B_{<2>}$}}
\put(10,135){\framebox(20,20){$B_{<3>}$}}
\put(10,130){\makebox(0,0){0}}
\put(5,135) {\makebox(0,0){0}}
\put(5,175) {\makebox(0,0){1}}
\put(50,130){\makebox(0,0){1}}

\put(65,155){\framebox(20,20)}
\put(85,155){\framebox(20,20)}
\put(85,135){\framebox(20,20)}
\put(65,135){\framebox(20,20)}

\put(85,165) {\framebox(10,10){$B_{<1,0>}$}}
\put(95,165) {\framebox(10,10){$B_{<1,1>}$}}
\put(95,155) {\framebox(10,10){$B_{<1,2>}$}}
\put(85,155) {\framebox(10,10){$B_{<1,3>}$}}

\put(60,175){\makebox(0,0){1}}
\put(60,135){\makebox(0,0){0}}
\put(65,130){\makebox(0,0){0}}
\put(105,130){\makebox(0,0){1}}


\end{picture}
\caption{$B_s$ for $s\in 4^{<\omega}$\label{square}}
\end{figure}


For $y\in S$ define $y\res n=s$ iff $y\in B_s$ for s of length n and
for $x\in\bairespace$ let $x\res n$ be the restriction of x to the
set $n=\{0,1,2,\ldots,n-1\}$.
Let
 $$T=\{(x\res n,y\res n)\setof (x,y)\in C\}$$
 Then
$$C=[T]=\{(x,y)\setof \forall n\; (x\res n,y\res n)\in T\}$$
and
$$A=\mbox{p}[T]$$
For any $(s,t)\in T$ define
$$T_{(s,t)}=\{(\hat{s},\hat{t})\in T\setof (\hat{s}\subset s\And
 \hat{t}\subset t)
\mbox{ or } (s\subset \hat{s}\And t\subset \hat{t})\}$$
Let
$$T'=\{(s,t)\in T\setof \mbox{p}[T_{(s,t)}]\mbox{ cannot be covered by
countably many lines }\}$$

\begin{lemma}
For any $(s,t)\in T'$ p$[T'_{(s,t)}]$ cannot be covered by
countably many lines, where $T'_{(s,t)}=T_{(s,t)}\cap T'$.
\end{lemma}
\proof

 By definition p$[T_{(s,t)}]$ cannot be covered by countably
many lines.  For any x in p$[T_{(s,t)}]$ but not in p$[T'_{(s,t)}]$
there must be some $(\hat{s},\hat{t})$ in $T_{(s,t)}$
 but not in $T'_{(s,t)}$ such that x is in p$[T_{(\hat{s},\hat{t})}]$.
Since each such p$[T_{(\hat{s},\hat{t})}]$ can be covered by countably
many lines, p$[T'_{(s,t)}]$ cannot be covered by countably many lines.
\qed

\begin{lemma}(Split and shrink)
Suppose $(s_i,t_i)\in T'$ for $i=0,1,2,\ldots,n$ are given with the
properties that for $i\neq j$ $B_{t_i}$ is disjoint from $B_{t_j}$
and no line meets three or more of the $B_{t_j}$'s.
Then there exists $(\hat{s_i},\hat{t_i})\in T'$ for $i=1,2,\ldots,n$
with $(\hat{s_i},\hat{t_i})\supset (s_i,t_i)$ and
$(s_0^j,t_0^j)\in T'$ for $j=0,1$ with
$(s_0^j,t_0^j)\supset (s_0,t_0)$ and
$B_{t_0^0}$ disjoint from $B_{t^1_0}$ and
no line meets three or more of the
$$ B_{t_0^0}, B_{t_0^1},B_{\hat{t_1}},B_{\hat{t_2}},
B_{\hat{t_3}},\ldots,B_{\hat{t_n}},$$
\end{lemma}
\proof

  Since p$[T'_{(s_0,t_0)}]$ cannot be covered by countably
many lines we can find distinct elements of it $x_0,x_1$.  Let $l$ be the
line containing $x_0$ and $x_1$. Since this line cannot cover
p$[T'_{(s_i,t_i)}]$ for $i=1,2,\ldots, n$ we can find
$(\hat{s_i},\hat{t_i})\supset (s_i,t_i)$ with each $B_{\hat{t_i}}$
a positive
distance from the line $l$. Now choose $(s_0^j,t_0^j)\supset (s_0,t_0)$
in $T'$
with $B_{t_0^j}$ a small enough neighborhood of $x_j$ so as ensure that
no line meets three or more of these squares.  See figure \ref{split}.
\qed

% \input{split}

\setlength{\unitlength}{1mm}

\begin{figure}
\begin{picture}(130,90)(0,90)

\put(5,120){\framebox(45,45)}
\put(45,175){$B_{t_0}$}
\put(0,175){\line(1,-1){90}}

\put(20,150){\framebox(5,5){\circle*{2}}}
\put(26,156){$x_0$}
\put(35,155){$B_{t_0^0}$}

\put(35,135){\framebox(5,5){\circle*{2}}}
\put(41,141){$x_1$}
\put(37,127){$B_{t_0^1}$}

\put(65,100){\framebox(30,30)}
\put(80,115){\framebox(5,5)}
\put(74,132){$B_{t_k}$}
\put(85,107){$B_{\hat{t_k}}$}


\end{picture}
\caption{Split and shrink lemma \label{split}}
\end{figure}


\begin{lemma}
Suppose $(s_i,t_i)\in T'$ for $i=0,1,2,\ldots,n$ are given with the
properties that for $i\neq j$ $B_{t_i}$ is disjoint from $B_{t_j}$
and no line meets three or more of the $B_{t_j}$'s.
Then there exists $(s_i^j,t_i^j)\in T'$ for $i=0,1,2,\ldots,n$
and $j=0,1$
with $(s_i^j,t_i^j)\supset (s_i,t_i)$ and
$B_{t_i^0}$ disjoint from $B_{t^1_i}$ and
no line meets three or more of the
$B_{t_i^j}$  for $i=0,1,2,\ldots,n$ and $j=0,1$.
\end{lemma}
\proof

  Apply the split and shrink lemma iteratively $n+1$ times.
\qed

To prove the theorem construct a subtree $T^*\subset T'$ with the
property that p$[T^*]=P$ is perfect and for every $n\in\omega$
no line meets three or more of
the $B_t$ with $(s,t)\in T^*$ for some s and t of length n.
Then $P$ is a perfect subset of $A$ which does not contain three collinear
points.
\qed



One of our original interests
in this problem was the following corollary:

\begin{corollary}
Suppose that $A$ is an analytic subset of the plane and $\cal L$
is a family of
fewer than continuum many lines such that $\cal L$ covers $A$.
 Then $A$ is covered
by a countable subfamily of lines from $\cal L$.
\end{corollary}
\proof

If $A$ contains a perfect set with no three points collinear then $A$ could
not be covered by $\cal L$, since perfect sets have the cardinality of the
continuum.  Hence we may assume that $A$ is covered by countably many
lines. Suppose:

$$A\subset\bigcup\{l_n\setof n\in\omega\}$$

If $l$ is any line such that
$l\cap A$ is uncountable, then $l$ is in $\cal L$.  This is because
$l\cap A$ is an analytic set, hence has cardinality the continuum,
but every line in $\cal L$ meets $l$ in at most one point,
so $l\cap A$ could
not be covered by $\cal L$.

So $A$ is covered by the $l_n$ which are in $\cal L$ plus at most countably many
more lines in $\cal L$ which cover the points in $A$
such that $l_n\cap A$ is
countable.

\qed

Note that if V=L then there exists an uncountable coanalytic subset
of the line which
contains no perfect subsets.  If this set is arranged around a circle then
we see that the theorem cannot be generalized to include coanalytic sets.

However Dougherty, Jackson, and Kechris have proved the following result:

\begin{theorem}
Suppose the axiom of determinacy and V=L[R] is true.  Then  every
subset of the plane  either  can be covered by countably many lines
or  contains a perfect subset $P$ with no three points collinear.
\end{theorem}

Their proof uses a technique of Harrington
(see Kechris and Martin \cite{kechris})
to prove Silver's theorem
that every coanalytic equivalence relation with uncountably many
equivalence classes contains a perfect set of inequivalent points.
They generalize this result and our result.

Is it true in Solovay's model \cite{solovay} that  every
subset of the plane  either  can be covered by countably many lines
or  contains a perfect subset $P$ with no three points collinear?

% \input{bib}

\begin{thebibliography}{99}

\bibitem{kechris}
A. S. Kechris and D. A. Martin, Infinite games and effective
descriptive set theory, in {\bf Analytic Sets}, ed. by C. A. Rogers
et al, Academic Press, (1980), 404-470.

\bibitem{fremlin}
D. H. Fremlin, {\bf Consequences of Martin's Axiom}, Cambridge University
Press, (1984).

\bibitem{solovay}
R.Solovay,
A model of set-theory in which every set of reals is Lebesgue
measurable, Annals of Mathematics, 92(1970), 1-56.

\end{thebibliography}

\end{document}
