% 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}