% LaTeX 2.09
\newcommand{\cross}{\times}
\newcommand{\intersect}{\cap}
\newcommand{\forces}{\mid\vdash}
\newcommand{\infsets}{[\omega]^{\omega}}
\newcommand{\finsets}{[\omega]^{< \omega}}
\newcommand{\infsubsets}[1]{ [#1]^{\omega} }
\newcommand{\union}{\cup}
\newcommand{\setof}{\;\;|\;\;}
\newcommand{\cantorspace}{2^{\omega}}
\newcommand{\qed}{\nopagebreak\par\noindent\nopagebreak$\Box$\par}
\newcommand{\implies}{\rightarrow}
\newcommand{\turingequiv}{\equiv_T}
\newcommand{\turingred}{\preceq_T}
\newcommand{\finsubsets}[1]{[#1]^{<\omega}}
\newcommand{\bairespace}{\omega^{\omega}}
\newcommand{\Intersect}{\bigcap}
\newcommand{\res}{\uparrow}
\newcommand{\underset}[2]{\begin{array}{c} {#1}\\{\scriptstyle #2}
                            \end{array}}

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

\documentstyle[12pt]{article}
\begin{document}



\begin{titlepage}
\begin{center}
{\bf\Large Infinite Combinatorics and Definability}
\footnote{in Annals of Pure and Applied Mathematical Logic,
41(1989), 179-203.}
\end{center}
\vspace{1 in}
\begin{flushright}
Arnold W. Miller\footnote{Partially supported by NSF grant MCS-8401711.}
\\Department of Mathematics\\University of Wisconsin\\Madison, WI 53706
\\ July 22, 1986
\\ revised January 20,1987
\\ final version \today
\end{flushright}
\vspace{1 in}
\begin{center}
{\bf Abstract}
\end{center}
\begin{quotation}
 The topic of this paper is Borel versions of infinite combinatorial
 theorems.  For example it is shown that there cannot be a Borel
 subset of $\infsets$ which is a maximal independent family.
 A Borel version of the delta systems lemma is proved.
 We prove a parameterized version of the Galvin-Prikry Theorem.  We
 show that it is consistent that any $\omega_2$ cover of reals by
 Borel sets has an $\omega_1$ subcover. We show that if
 V=L then there are $\Pi^1_1$ Hamel bases, maximal almost disjoint families,
 and maximal independent families.

\end{quotation}
\end{titlepage}
\section{Introduction}
Notation and background for reading this paper is in section \ref{nota}.

Section \ref{para} is concerned with the Galvin-Prikry Theorem.
This theorem says that for any Borel set $B\subset\infsets$ there
exists a set $H\in\infsets$ such that either $\infsubsets{H}\subset B$
or $\infsubsets{H}\intersect B = \emptyset$. Answering a question of
D. Mauldin we prove:
\begin{quote}
 If $B\subset \cantorspace \cross \infsets$  is Borel,
then there exists $ C\subset \cantorspace$ perfect and $X\in \infsets $
such that $C\cross \infsubsets {X} \subset B$ or
 $( C\cross \infsubsets {X} ) \intersect B = \emptyset$.
\end{quote}
Section \ref{inte} is concerned with a question of D. Fremlin.
We prove that:
\begin{quote} It is consistent that
the continuum is $\omega_3$ and for
every family F of Borel sets of size $\omega_2$ if F has empty intersection
then some subfamily of F of size $\leq\omega_1$ has empty intersection.
Equivalently by taking complements, if $R=\union F$ then for some
 $G\subset F$ of cardinality $\omega_1$, $R=\union G$.
\end{quote}

The remaining sections are about finding
Borel versions of various combinatorial theorems. Probably the first result
along this line is a theorem of Sierpi\'{n}ski
1938 \cite{sierpinski2} that any nontrivial
ultrafilter on $\omega$ when considered as a subset of $\cantorspace$ cannot
be Borel.  Talagrand 1980 \cite{talagrand} pursues this.
Mathias 1977 \cite{mathias} shows that a maximal almost disjoint
family in $\infsets$
cannot be $\Sigma^1_1$.  Jones 1942 \cite{jones} shows that a
Hamel basis cannot be $\Sigma^1_1$. This was done earlier by
Sierpi\'{n}ski 1920 \cite{sierpinski1}.

Another Borelized version of
a combinatorial theorem is an unpublished result of
Galvin (1968) \cite{galvin2}.
 Namely,
for any Borel partition of the two element sets of reals into finitely
many pieces there exists a perfect set all of whose two element subsets
are in the same piece of the partition.
Later Silver noticed that using a result of Mycielski (1964)
\cite{mycielski1} it can be reduced to clopen partitions
and that in fact works for any Baire partition (or measurable partitions
Mycielski (1967) \cite{mycielski2}).
Galvin extended his result to three tuples and
Blass (1981) \cite{blass} extended it to arbitrary n-tuples.



Friedman and Shelah
(see Shelah 1984 \cite{shelahsouslin})
proved that no Borel linear order can be a Souslin line as well as
many other results about Borel partial orders ( see also
Harrington-Shelah 1982 \cite{harrington}).
Harrington, Marker, and Shelah (1988) \cite{harr}
have proved a Borel version of Dilworth's Theorem.
Martin 1981 \cite{martin} proves a theorem of Eggleston about
subsets of the plane of positive measure using
forcing and absoluteness.  Komj\'{a}th 1984 \cite{komjath2} proves
and improves a result of Laczkovich about sequences of Borel
sets using similar ideas.
In section \ref{delt} we give a proof of a Borel version of the delta
system lemma:
\begin{quote}
If $B \subset \cantorspace \cross \cantorspace $ is any Borel set all of
whose cross sections are finite, then there exists a perfect set
$C \subset \cantorspace$ with the property that
$\{B_t \setof t\in C\}$ is a delta system.
\end{quote}
We also consider weak delta systems of families of countable
sets.

In section \ref{stro} we give some counterexamples to Borel versions
of combinatorial theorems about families of strongly almost disjoint
families.

In section \ref{simi} we show that for any convergent sequence of
real numbers it is possible to partition the real line into two
pieces so that neither piece contains a sequence which is similar
to the given sequence.

In section \ref{twopt} we show that if V=L then there exists a
$\Pi^1_1$ subset of the plane that meets every line in exactly two
 points. In section \ref{maxi} we show there is a $\Pi^1_1$ maximal
 almost disjoint family of subsets of $\omega$.
 In section \ref{hame} we show that if V=L then there is
 a $\Pi^1_1$ Hamel basis.
  We also give a category
 proof of Jones' Theorem  that no Hamel basis can be $\Sigma^1_1$.

   In section \ref{mixa} we show that
 maximal independent families cannot be $\Sigma^1_1$ but if V=L then
 there are ones which are $\Pi^1_1$.






\section{Parameterized Galvin Prikry Theorem}
\label{para}

The following theorem answers a question of D. Mauldin.  It is a sort of
parameterized Galvin-Prikry Theorem  1973 \cite{galvin-prikry}.

\begin{theorem}
 If $B\subset \cantorspace \cross \infsets$  is Borel,
then there exists $ C\subset \cantorspace$ perfect and $X\in \infsets $
such that $C\cross \infsubsets {X} \subset B$ or
 $( C\cross \infsubsets {X} ) \intersect B = \emptyset$.
\label{PGP}
\end{theorem}

The proof will broken down into several lemmas.

\begin{lemma}
If U is a Ramsey ultrafilter in a model M of $ZFC^*$ and t is Sacks perfect
set forcing generic over M and
$$ U^*=\{X\in\infsets \intersect M[t] \setof \exists Y\in U \;\;
   Y\subset X\}$$
then
$$ M[t]\models U^* {\;\rm\;is\;a\;Ramsey\;ultrafilter} $$
\label{BL}
\end{lemma}
proof: see Baumgartner-Laver 1979 \cite{baumgartner-laver}
Theorem 4.4 p 280.\qed
If U is a Ramsey ultrafilter then define
$$ P_U =\{(s,X)\setof s\in \finsets , X\in U,\mbox{ and max(s) $<$ min(X) }\}$$
ordered by
 $(s,X)\leq (t,Y)$ iff $s\supset t, X\subset Y$ and
$s\setminus t \subset Y$.

The next lemma says that any statement can be decided without extended the
finite part of the condition.

\begin{lemma}
If $\theta$ is any sentence and $(s,X)\in P_U$ then there exists
$Y\in U\intersect \infsubsets{X}$ such that either
$(s,Y)\forces\theta$ or $(s,Y)\forces\neg\theta$
\label{MA1}
\end{lemma}
proof: see Mathias 1977 \cite{mathias} Prop 2.9 p 74. \qed


For G a $P_U$ filter define $Z_G=\;\union \{ s \setof \exists X \; (s,X)\in G\}$
.
Conversely given $Y\in \infsets$
define $G_Y = \{(s,X)\in P_U \setof s \subset Y \subset X\union s \}$.
It is well known that G and Z are definable from each other.  Z is
called a Mathias real.  The next lemma says that every infinite
subset of a Mathias real is Mathias.

\begin{lemma}
If G is $P_U$ generic over M then for every $Y\in\infsubsets{Z_G}$
$G_Y$ is $P_U$ generic over M.
\label{MA2}
\end{lemma}
proof: see Mathias 1977 \cite{mathias} Corollary 2.5 p. 73.\qed
\begin{lemma}
For any perfect set p and infinite $Y\subset\omega$ in M
there exists a perfect set $ C\subset p$ and $X\in \infsubsets{Y}$
such that for every $t\in C$ and $Z \in \infsubsets{X}$
(t,Z) is $ S\cross P_U$ generic over M.
\label{prod}
\end{lemma}
proof:  Construct C  perfect and $X\in\infsets$ such that for every
$t\in C$ $(t,X)$ is $S\cross P_U$ generic over M.
This is easy to do since M is countable.  By the product lemma
for any $t\in C$ we have that X is $P_U$ generic over $M[t]$.
But $P_U$ is a dense subset of $P_{U^*}$ and so X is $P_{U^*}$ generic
over $M[t]$.  By Lemma \ref{BL}  $U^*$ is a Ramsey ultrafilter in $M[t]$ and
by Lemma \ref{MA2}  any $Z\in\infsubsets{X}$ is $P_{U^*}$ generic over
$M[t]$.  Since $P_U$ is dense in $P_{U^*}$ Z is $P_{U}$ generic over
$M[t]$ and so $(t,Z)$ is $S\cross P_U$ generic over M.
\qed

proof of Theorem {\ref{PGP}}:  Let M be a countable
standard model of
a sufficiently large finite fragment of the
theory {ZFC + CH} and containing a code for the Borel set B.
Let S be Sacks perfect set forcing and let t be S generic over M.
By Lemma {\ref{BL}} and Lemma {\ref{MA1}} either:
$$ M[t]\models \exists A\in U^*\;\; (\emptyset,A)\forces Z\in B_t$$
or
$$ M[t]\models \exists A\in U^*\;\; (\emptyset,A)\forces Z\notin B_t$$
where Z is Mathias over M[t].  Assume the first case since the argument
is symmetric.  Hence working in M  there exists p $\in S$ and $Y\in U$
 such that
$$ p\forces_{S} `` \;\;
(\emptyset,Y)\forces_{P_{U^*}} Z\in B_t \mbox{''}$$
Note that by Lemma {\ref{BL}}  $P_U$ is a dense subset of $P_{U^*}$ and
hence $S\cross P_U$ is a dense subset of the iteration $S \ast P_{U^*}$.
It follows that
$$ (p,(\emptyset,Y))\forces_{S\cross P_U} Z\in B_t$$
Since B is Borel and hence absolute we have
$$ C\cross\infsubsets{X} \subset B$$
where C and X are gotten by applying Lemma 2.5.
\qed


 Since we are only using the absoluteness of Borel predicates
the same proof gives a parameterized version of Silver's 1970 Theorem
 {\cite{silver}} that $\Sigma^1_1$ are Ramsey.  Is there a parameterized
 Ellentuck 1974 Theorem? (\cite{ellentuck}).  More specifically consider the
 $\sigma$-algebra of all sets
   $A \subset \cantorspace \cross \infsets$ with the
 property that for every perfect set $C \subset\cantorspace $ and
 $(s,X)$ there exists a perfect set $D\subset C$ and a $Y\in\infsubsets{X}$
such that
$$ D\cross [s,Y] \subset A {\rm \;\; or\;\; }  D\cross [s,Y] \intersect
 A = \emptyset $$
where $[s,Y]=\{ Z\in\infsets \setof s\subset Z \subset Y\union s \}$.
Can we characterize this family of sets in terms of the Baire property
in the Ramsey topology and perhaps the ideal of $(s_0)$ sets?
(A set of reals X has property $(s_0)$ if for every perfect set P there
 exists a perfect set $Q\subset P$ which is disjoint from X,
 see A.Miller 1984 section 5 \cite{survey} and
 Marczewski 1935 \cite{marczewski}.)

The following corollary  which is a result of Mazurkiewicz (1932)
\cite{mazurkiewicz2}
was pointed out to me by D.Mauldin and R.Pol.
\begin{corollary}
  Suppose $<f_n :\cantorspace\mapsto\cantorspace\setof n\in\omega>$
  is a sequence of Borel functions.  Then there exists a perfect set
  $P\subset\cantorspace$ and a subsequence
  $<f_{k_n} :\cantorspace\mapsto\cantorspace\setof n\in\omega>$
  which is pointwise convergent on every point in P.
\end{corollary}
proof: Consider
$$ B=\{(x,M)\setof<f_n(x) \setof n\in M>
\mbox{converges}\}\subset\cantorspace\cross\infsets$$
\qed

{\bf Examples}\par
\begin{enumerate}
\item
Define $B\subset\infsets\cross\infsets$ by
$(X,Y)\in B$ iff $min(X)<min(Y)$.  Then there cannot be $M,N\in\infsets$
such that $\infsubsets{M}\cross\infsubsets{N}$ is either contained in or
disjoint from B.
\item
(D.Mauldin) Let
$$B=\{(x,M)\setof x\res M\;constant\}\subset\cantorspace\cross\infsets$$
It is easy to see that this example shows that the perfect set C in
Theorem \ref{PGP} cannot in general be of positive measure.
Mauldin also has an example of a uniformly bounded sequence of continuous
functions on $[0,1]$ such that no subsequence converges pointwise
on a set of positive measure.
\item
It is easy to generalize Theorem \ref{PGP} to the case of
Borel subsets of $((2^{\omega})^{\omega})\cross \infsets$ by using
Laver's \cite{laver} infinite version of the Halpern-L\"{a}uchli Theorem.

\end{enumerate}

In an earlier version of this paper I remarked that
it would be interesting to have a proof
of Theorem \ref{PGP} that did not use forcing and
absoluteness.  Todor\v{c}evi\'{c} wrote back that in fact he proved Theorem
\ref{PGP} several years ago with the following proof:
\begin{quotation}
 Assume first that $B\subset\cantorspace\cross\infsets$ is clopen.  Pick
 recursively $\{(x_{\alpha},A_{\alpha})\setof \alpha<\omega_1\}$ such
 that the $x_{\alpha}$'s are distinct elements of $\cantorspace$,
 $A_{\alpha}\in\infsets$,  $A_{\alpha}\subset^* A_{\beta}$ for $\beta<\alpha$,
 and for all $\alpha<\omega_1$
 $$\{x_{\alpha}\}\cross \infsubsets{A_{\alpha}}\subset B \mbox{ or }
 \{x_{\alpha}\}\cross \infsubsets{A_{\alpha}}\intersect B=\emptyset $$
 Find $X\subset\omega_1$ and $A\in\infsets$ such that the order type of
 $\{x_{\alpha}\setof\alpha\in X\}$ is the
 same as the rationals and either for every
 $\alpha\in X$
 $$ \{x_{\alpha}\}\cross \infsubsets{A_{\alpha}}\subset B$$
 or for every $\alpha\in X$
 $$ \{x_{\alpha}\}\cross \infsubsets{A_{\alpha}}\intersect B=\emptyset $$
 and also
 $$A\subset\Intersect_{\alpha\in X} A_{\alpha}$$
 (A and X can be obtained by an argument similar to the proof of
 Lemma 3.1.1 of \cite{von-miller-steel}.)
 Let P be the closure of $\{x_{\alpha}\setof\alpha\in X\}$. Then P and A work.
 The proof when B is closed is almost the same.  The obvious induction on the
 Borel rank reduces the general case to the clopen case.
\end{quotation}




\section{Intersections of Borel Sets}
\label{inte}

In this section we answer a question of D.H.Fremlin. We show
that it is consistent that for
every family F of Borel sets of size $\omega_2$, if F has empty intersection
then some subfamily of F of size $\leq\omega_1$ has empty intersection.
Note that the Hausdorff gap 1934 (\cite{hausdorff})
 shows that there is a family of Borel sets
of size $\omega_1$ with empty intersection but every countable subfamily
has nonempty intersection.
In  Fremlin-Jasi\'{n}ski \cite{fremlin-jasinski}
it is shown that MA + not CH implies this is false.
They show that the complement of any set of reals of cardinality $\omega_2$
is the union of $\omega_2$ Borel sets.  The argument we use is the same as
used by Harrington (see Corollary \ref{harringtonmad}) in unpublished work.
\begin{theorem}\label{intborel}
Suppose M is a countable standard model of ZFC + CH and $P = FIN(\omega_3^M)$
($FIN(\kappa)$ is the usual
partial order for adding $\kappa$ Cohen reals
to M.)
Then for any G P-generic over M, in M[G] for
every family F of Borel sets of size $\omega_2$, if F has empty intersection
then some subfamily of F of size $\leq\omega_1$ has empty intersection.
Equivalently by taking complements, if $R=\union F$ then for some
 $G\subset F$ of cardinality $\omega_1$, $R=\union G$.
\end{theorem}
The proof will require the following well-known lemma.
\begin{lemma}
 Suppose M and N are standard models of $ZFC^*$, $j:M\mapsto N$ is an
 elementary embedding,  and $\kappa$ is the first ordinal moved,
 P a partial order in M, $j(P)=Q$,
 G is P-generic over N and $H=j^{-1}(G)$.
 If  P has $\kappa-c.c.$ in M then
 H is Q-generic over M and
 if $j^*:M[H]\mapsto N[G]$ is defined by $j^*(\tau^{H})=(j(\tau))^{G}$ then
 $j^*$  is well-defined and an elementary embedding.
\end{lemma}
proof:
If $A\subset Q$ is a maximal antichain in M, then since
Q has the $\kappa-c.c.$, $j(A)=j``A$ is a maximal antichain in P which is
in N, hence H is Q-generic over M.
\par\noindent Well-defined:  Suppose $\tau^H=\sigma^H$. Then there exists
 $p\in H$ such that $$M\models``p\forces \tau=\sigma\mbox{''}$$ but then
 $$N\models``j(p)\forces \tau=\sigma\mbox{''}$$
\par\noindent Elementarity:  We use the Tarski-Vaught criterion.
 Suppose $$N[G]\models \exists x\;\theta(x,j(\tau)^G)$$
 then there exists $p\in H$ such that either
 $$M\models\;p\forces \exists x\;\theta(x,\tau)$$
 or
 $$M\models\;p\forces \neg\exists x\;\theta(x,\tau)$$
 But the latter cannot happen because then
 $$N\models\;j(p)\forces \neg\exists x\;\theta(x,j(\tau))$$
 and $j(p)\in G$.  Hence there exist $\sigma\in M$ such that
 $$M\models\;p\forces \;\theta(\sigma,\tau)$$
 so
 $$N\models\;j(p)\forces \;\theta(j(\sigma),j(\tau))$$
 and $j(p)\in G$ so
 $$N[G]\models \theta(j(\sigma)^G),j(\tau)^G)$$
\qed

\noindent proof of Theorem \ref{intborel}:
Let $M_{\lambda}$ be $H_{\lambda}$ in M for some sufficiently large cardinal $\lambda$.
($H_{\lambda}$ is set of all sets whose transitive closure has cardinality
less than ${\lambda}$)
 Let $G:\omega_3\mapsto2$
 be FIN($\omega_3$)-generic over M and suppose
 $$ M[G]\models R=\union\{B_{\alpha}\setof \alpha<\omega_2\},
 \;each\;B_{\alpha}\;Borel$$
 Choose $\Sigma\in M$ so that
 $$<B_{\alpha}\setof \alpha<\omega_2>\in M_{\lambda}[G\res \Sigma]$$
Working in M find a transitive set N and embedding j such that
\begin{enumerate}
\item $|N|=\omega_1.$
\item $N^{\omega}\subset N$.
\item $j:N\mapsto M_{\lambda}$ is an elementary embedding.
\item $\beta=\omega_2\intersect N$ is an ordinal
and hence $j(\beta)=\omega_2$.
\item $\Sigma$ is in the range of j and let $j(\Sigma_0)=\Sigma$.
\end{enumerate}
Note that  $j(FIN(\Sigma_0))=FIN(\Sigma)$ and so if we let
$G_0$ be defined by $G_0(\alpha)=G(j(\alpha))$, then by the lemma
$$ j^*:N[G_0]\mapsto M_{\lambda}[G\res \Sigma]$$
is an elementary embedding.  Since $j^*$ is the identity on the reals
$j(B_{\alpha})=B_{\alpha}$.  Clearly
$$ M_{\lambda}[G\res \Sigma]\models``1\forces_{FIN(\omega)}
 R=\union\{B_{\alpha}\setof \alpha<\omega_2\}\mbox{''}$$
So by elementarity
$$ N[G_0]\models``1\forces_{FIN(\omega)}
 R=\union\{B_{\alpha}\setof \alpha<\beta\}\mbox{''}$$
It suffices to show that for every $x\in R^{M[G]}$ there exists
K $FIN(\omega)$-generic over $N[G_0]$ such that $x\in N[G_0][K]$, since
then there exists $\alpha<\beta$ such that $N[G_0][K]\models
x\in B_{\alpha}$ and thus by Borel absoluteness $x\in B_{\alpha}$.
This follows from knowing $M\models N^{\omega}\subset N$.
In more detail suppose  $\tau\in M$ is a name for x where:
$$\Gamma\in [\omega_2]^{\omega}\intersect M$$
$$y=G\res (j``\Sigma_0\intersect\Gamma)$$
$$z=G\res (\Gamma\setminus j``\Sigma_0)$$
$$x=\tau(y,z)$$
Working in M we can find a name $\tau^*(u,v)\in N$,
 $z^*\; FIN(\omega)$-generic over
$N[G_0]$ ( or rather a name for $z^*$ ), such that
$$ x=\tau^*(G_0\res j^{-1}(\Gamma),z^*)$$
Note that $j^*$ maps $G_0\res j^{-1}(\Gamma)$ to
$G\res (j``\Sigma_0\intersect \Gamma)$.\qed

Fremlin notes that it is easy to generalize the theorem to adding any
number $\kappa\geq\omega_3$ Cohen reals to M.
\begin{corollary} \label{harringtonmad}
(Harrington\footnote{The referee remarks that this result is folklore,
and was known when Harrington was in knee pants.  I first heard of it
from Harrington.})
In the Cohen real model there are no mad families of cardinality
$\kappa$ where $\omega_1<\kappa<c$.
\end{corollary}
proof:  For $X\in\infsets$ consider the Borel set
$$ B_X=\{Y\in\infsets\setof X\intersect Y\;infinite\}$$
If M is a mad then $R=\union\{B_X\setof X\in M\}$.\qed
There are mad families of cardinality $\omega_1$
(see Kunen \cite{kunen} chapter 8 Theorem 2.3 p.256 ) in the
Cohen real model.  If we start with MA + $c=\omega_2$ and add
$\omega_4$ random reals, then we get a model where there
are MAD's of size $\omega_2$ and $\omega_4$, but none of size
$\omega_1$ or $\omega_3$.


\section{Delta Systems Lemma}
\label{delt}

A delta system is a family of sets F such that there is a  R
( called the root ) with the
property that for every two distinct elements A and B of F,
 $A\intersect B = R$.
The classical delta systems lemma says that every uncountable
family of finite sets contains an uncountable delta system.
The following theorem is a definable version of this.

\begin{theorem}
If $B \subset \cantorspace \cross \cantorspace $ is any Borel set all of
whose cross sections are finite, then there exists a perfect set
$C \subset \cantorspace$ with the property that
$\{B_t \setof t\in C\}$ is a delta system.
\label{delta}
\end{theorem}

We will use the following lemma.

\begin{lemma}
Suppose P is a partial order in a model M then for any G and H such that
$G\cross H$ is $P \cross P$ generic over M
$$ M[G] \intersect M[H] = M$$
\label{intersect}
\end{lemma}
proof:  see Solovay 1970 \cite{solovay} Lemma 2.5 p.13 \qed
\noindent proof of Theorem {\ref{delta}}: Let M be a countable standard
model of $ZFC^*$ which contains a code for the
Borel set B.$\;$ Let P be the usual partial order for forcing a Cohen real,
i.\ e.\  $ P=2^{<\omega}$.  Let $x \in\cantorspace$ be P-generic over M.
Suppose $R= B_x \intersect M$ and let $p\in P$ be such that
$$p\forces B_x \intersect M=R$$

 Let C be a perfect set of elements of $\cantorspace$ such
that for every $x\in C$, $p\subset x$ and
for any two distinct elements of $x,y\in C$ we have that
(x,y) is $P\cross P$ generic over M (hence each $x\in C$ is P generic
over M).
It follows by absoluteness and Lemma {\ref{intersect}} that for any two
elements x and y of C we have $ B_x \intersect B_y = R $.
\qed

Todor\v{c}evi\'{c} remarks that Theorem \ref{delta} can also be proved using
Galvin's perfect partition theorem mentioned in the introduction.
The proof is done in
the same standard way Ramsey's Theorem shows that  any infinite
$F\subset [\omega]^m$ contains an infinite $\Delta$-system.
R.Pol sent me a similar proof.

We now will generalize to the case of families of countable sets.
We call a family of countable sets  F a weak delta system iff there is
a countable set R such that for any two elements X and Y of F
$ X\intersect Y \subset R$.

\begin{theorem}
If $B \subset \cantorspace \cross \cantorspace $ is any Borel set all of
whose cross sections are countable, then there exists a perfect set
$C \subset \cantorspace$ with the property that
$\{B_t \setof t\in C\}$ is a weak delta system.
\end{theorem}
proof: The proof is the same except
we just use $R=M\intersect\cantorspace$ as
our weak root.  Note that $B_x \subset M[x]$ since otherwise
$$ M[x]\models B_x \;is\; uncountable$$ and since it is Borel
there would be
a perfect set P coded in M[x] such that
$$ M[x]\models P\subset B_x$$
and so by $\Pi^1_1$ absoluteness $B_x$ would really contain P.
\qed

Note that a weak delta system is the best we can hope to obtain since there
is a Borel parameterized family of almost disjoint sets, e.\ g.\ let
$$\{ x_s \setof s\in 2^{<\omega}\}\subset \cantorspace$$
and define $B\subset\cantorspace\cross\cantorspace$ by
$$(t,x)\in B\;\; {\rm iff}\;\; \exists n \in \omega \;x= x_{t\res n}$$

The following result about weak delta systems is what we can say if
we drop the assumption of definability.

\begin{theorem}
Suppose $\kappa$ is any cardinal such that
 $\omega_1 < \kappa \leq \omega_{\omega}$ and F is a family of $\kappa$
many countable sets.  Then F contains a weak delta system of
cardinality $\kappa$.
If $\cantorspace < \omega_{\omega}$ then
this is false for $\kappa = \omega_{\omega+1}$.
\label{weakdelta}
\end{theorem}
 The following lemma is half of one of the standard proofs of the
usual delta lemma for families of countable sets.


\begin{lemma}
Let $\kappa > \omega_1 $ be a regular cardinal
and suppose  $F\subset \infsubsets{\kappa}$ has cardinality $\kappa$.
then there exists $ G \in [F]^{\kappa}$ and R of cardinality less
than $\kappa$ such that for every two $A,B \in G$ we have
 $A\intersect B \subset R$.
\label{halfdelta}
\end{lemma}
proof: Let $F=\{A_{\alpha} \setof \alpha < \kappa \}$ and define
 $$f(\alpha)=\sup ( A_{\alpha}\intersect \alpha )$$
 Since f is pressing down on all $\alpha$ of uncountable cofinality
there is a stationary set $S\subset \kappa$ and a $\gamma <\kappa$
such that for all $\alpha\in S$
$$  A_{\alpha}\intersect \alpha \subset \gamma$$
Since
$$ \{\alpha \setof \forall \beta < \alpha\;\; A_{\beta} \subset\alpha \}$$
is closed and unbounded in $\kappa$, we may assume for every
$\alpha,\beta\in S$ that $\alpha<\beta \implies A_{\alpha}\subset \beta$.
Hence $R=\gamma$ and $G=\{A_{\alpha} \setof \alpha \in S\}$ work.
\qed

\begin{lemma}
Suppose $\kappa > \omega_n$ is a regular cardinal, $1\leq n<\omega$ and
$F\subset [\omega_n]^{\omega}$ has cardinality $\kappa$, then
there exists C countable such that  $[C]^{\omega}\intersect F$ has
cardinality $\kappa$.
\label{cover}
\end{lemma}
proof: The proof is by induction on n.  Since $\omega_n$ is regular and
uncountable there is some $\alpha < \omega_n$ which contains $\kappa$ many
elements of F.  Now just regard $\alpha$ as $\omega_{n-1}$ and proceed.
\qed

\noindent proof of Theorem {\ref{weakdelta}}:
The proof of the first part of Theorem {\ref{weakdelta}}
 is by induction on $\kappa$.
For $\kappa=\omega_n$ first apply Lemma \ref{halfdelta} to get G
and R with R of cardinality $\omega_{n-1}$.  Then
apply Lemma \ref{cover} to the family $\{X\intersect R \setof X\in G\}$.

To do the case $\kappa=\omega_{\omega}$ let $F=\union_{n\in\omega}  F_n$
where $|F_n|=\omega_n$. Apply Lemma \ref{cover} to find
$H_n\in [F_n]^{\omega_n}$ and $C_n\in [\union F_{n-1}]^{\omega}$ such
that for every $A\in H_n$ $$ A\intersect(\union F_{n-1})\subset C_n$$
Next apply the induction case to the $H_n$ to obtain
$G_n\in [H_n]^{\omega_n}$ and weak roots $R_n$ and let
 $$G=\union_{n\in\omega} G_n$$ and
$$ R=\union\{ R_n \union C_n \setof {n\in\omega}\} $$

To prove the second part of Theorem {\ref{weakdelta}} let F be a family
of $\omega_{\omega+1}$ countable subsets of $\omega_{\omega}$,
which exists by K\"{o}nig's Theorem.
This family cannot contain a large weak delta system
if the continuum is small.  For suppose $G\subset F$ is a weak delta system of
size $\kappa$ with a countable weak root R.  Since
$$\{A\setminus R \setof A\in G\}$$
are disjoint all but at most $\omega_{\omega}$ must be empty and
hence $2^{\omega}=2^{|R|}\geq\omega_{\omega+1}$
\qed

The referee remarks that the second part of Theorem {\ref{weakdelta}}
holds also under the  assumption that $2^\omega=\omega_{\omega+1}$.  Just
construct the family F inductively avoiding every potential weak root.
I don't know what happens when the continuum is larger.



\section{Strongly Almost Disjoint Families}
\label{stro}
 A family of sets F is strongly almost disjoint if there is an $n\in\omega$
such that any two distinct elements of F meet in a set of cardinality at most
n. Now we show that there is no Borel version of E. Miller's Theorem.
  This Theorem says
that for every strongly almost disjoint family F of infinite countable
sets there exists a set X such that for every $A\in F$ both
$X\intersect A$ and $A\setminus X$ are infinite.  The family F is
said to have property B if such an X exists. This is in honor
 of Bernstein 1908 \cite{bernstein}
  who showed that countable families of infinite sets
 have property B.

\begin{theorem} \label{bkomjath}
There is a Borel set $A\subset R\cross R$ such that
$\{A_x\setof x\in R\}$ is strongly almost disjoint family of
countable infinite sets,
but there does not exist a Borel set $X\subset R$ such that
for every $x\in R$ both
 $X\intersect A_x$ and $A_x\setminus X$ are infinite.
\end{theorem}
proof:  Define $A_x=\{x+a_n\setof n=1,2,\ldots\}$.
where $<a_n : n\in\omega>$ is a sequence converging to zero
with the property that
$a_n-a_m=a_k-a_l$ iff $<n,m>=<k,l>$.  For example
$a_n={1/{2^n}}$. Then if $x\not=y$
$A_x\intersect A_y$ has size at most one. For suppose
there were n, m, l, and k such that
$$ x+a_n = y +a_m$$
$$ x+a_k = y +a_l$$
Then
$$a_n-a_m= y-x=a_k-a_l$$
Suppose X is Borel.  Let $x\in R$ be a Cohen real. Then for some
rational interval p=(r,s) with $r<x<s$ we have either
$$p\forces x\in X$$ or $$p\forces x\notin X$$
Suppose the first happens. Then for all but finitely many n
$r<x+a_n<s$ and for every n, $x+a_n$ is Cohen real and so
$A_x\subset^* X$.  If the second happens, then
$A_x\intersect X=^* \emptyset$. \qed

Komj\'{a}th 1984  \cite{komjath} showed that if
 $F=\{A_{\alpha} \setof \alpha<\kappa\}$ is any
strongly almost disjoint family of countable sets then there exists a
family of finite sets $\{B_{\alpha} \setof \alpha<\kappa\}$ such that
$$\{A_{\alpha}\setminus B_{\alpha} \setof \alpha<\kappa\}$$
is a disjoint family.  This result generalizes
E.Miller 1937 \cite{emiller}.
 It is easy to see using standard selection theorems
that Theorem \ref{bkomjath} gives a counterexample to a Borel version
of Komj\'{a}th's theorem.  Below we will give an alternative proof of this
fact.

\begin{theorem}
There is a Borel set $A\subset\cantorspace\cross\cantorspace$ such that
$\{A_x\setof x\in\cantorspace\}$ is strongly almost disjoint family
of countable sets such that there is a Borel set X such that for every
$x\in\cantorspace$,  $X\intersect A_x$ and $A_x\setminus X$ are infinite,
but there is no
Borel set $B\subset\cantorspace\cross\cantorspace$ such that for every
 $x\in\cantorspace, B_x$ is finite and
$$\{A_x\setminus B_x \setof x\in\cantorspace\}$$
is a disjoint family.
\end{theorem}
proof:  We can regard $[\cantorspace]^2$ as being a Borel subset of
$\cantorspace$, since $\cantorspace\cross\cantorspace$ is homeomorphic
to $\cantorspace$ and we can regard
$[\cantorspace]^2 \subset\cantorspace\cross\cantorspace$ by looking
only at ordered pairs where the the first coordinate is lexicographically
less than the second coordinate.
The example is defined by
$$ A_x =\{\{x,y\}\setof x\turingequiv y, x\not=y\}$$
where $\turingequiv$ stands for Turing equivalent, i.\ e.\  x and y are
each recursive in the other. It is easy to see that A is Borel and
each $A_x$ is countable.  Also $X=\{\{x,y\}\setof x(0)=y(0)\}$ splits
every element of the family.
Note that for distinct x and y, $ A_x\intersect A_y $ is empty unless
x and y are Turing equivalent and then it contains exactly
the pair $\{x,y\}$. So we have a strongly almost disjoint family.
Now suppose B were a counterexample to the Theorem
and let P be Cohen real forcing and x the name of the Cohen real.
There exists $p\in P$ and $k\in\omega$ such that
$$ p\forces |B_x|=k$$
For any recursive automorphisms $\pi$ of P we have
$$ \pi(p)\forces |B_{\pi(x)}|=k$$
It is easy to find infinitely many recursive automorphisms of P which
fix p but give different $\pi(x)$ with boolean value one.  Hence by
using a countable standard model of $ZFC^*$ and
absoluteness, there must be a Turing degree X such that for infinitely
many $x\in X, |B_x|=k $. Let $Y\subset X$ be these x and for each
$y\in Y$ let $$C_y=\{z \setof \{y,z\}\in B_y\}$$
Since each of the $C_y$ has cardinality k we can apply the delta system
lemma to find distinct u and v in Y such that $u\notin  C_v$ and
$v\notin C_u$. It follows then that
$$ \{u,v\} \in (A_u\setminus B_u)\intersect (A_v\setminus B_v)$$
contradicting their disjointedness.\qed


\section{Similar Sequences}
\label{simi}

Two sequences of real numbers $<a_n : n\in\omega>$ and $<b_n : n\in\omega>$
are similar iff there are real numbers $q\not= 0$ and r such that for all
$n\in\omega$, $b_n=qa_n+r$.
It is shown in H.Miller-P.Xenikakis 1980 \cite{hmiller}
 that given any convergent
sequence $<c_n : n\in\omega>$
and set A which has the property of Baire and is not meager, there
exists a similar sequence entirely contained in A.  The forcing proof of
this fact would be as follows.  Suppose A is comeager in the interval
(a,b).  Choose a rational number r so that for some $\epsilon >0$ and
for every $n\in\omega$, $a+\epsilon< rc_n < b -\epsilon $.
Let $x\in (-\epsilon,\epsilon)$ be a Cohen real.  Then for every $n\in\omega$,
$rc_n+x$ is a Cohen real and since each $rc_n+x\in (a,b)$ we have that
for every $n\in\omega$, $ rc_n+x\in A$.

\begin{theorem}\label{simpart}
For every sequence of distinct reals $<c_n : n\in\omega>$ there exists
a set $X\subset R$ such that neither $X$ nor $R\setminus X$ contain a
sequence similar to $<c_n : n\in\omega>$.
\end{theorem}
This will be proved using Lowenheim-Skolem arguments.
Both  Komj\'{a}th 1984 \cite{komjath}
 and E.Miller 1937 \cite{emiller} could be proved this way also.
In fact for most sequences the result would follow from E.Miller's
Theorem.

First note the following lemma.
\begin{lemma}
Suppose M is a standard model of $ZFC^*$,
 $<c_n : n\in\omega>\in M$, and $<b_n : n\in\omega>$ is similar
  to $<c_n : n\in\omega>$.  Then if M contains at least two points of
$<b_n : n\in\omega>$, then it contains all of them.
\end{lemma}
proof: Suppose for every $n\in\omega$, $b_n=qc_n+r$.  Then if two
of the $b_n$'s are in M we can solve for q and r, so they are in M
and so all the $b_n$'s are in M. \qed

\noindent proof of the Theorem \ref{simpart}:
We show by induction on the cardinality of
$Y\subset R$ that there exists $X\subset Y$ such that every
sequence $<b_n : n\in\omega>$ similar to $<c_n : n\in\omega>$ which meets Y
in an infinite set meets both  $X$ and $Y\setminus X$ in an infinite set
( in this case we say X splits Y ).
If Y is countable, then let M be a countable standard model of a large
enough finite fragment of ZFC which contains Y and the sequence
$<c_n : n\in\omega>$.  Then by the lemma we need only to split countably
many infinite sets.  But this is easy to do, in fact, it is the classical
result of Bernstein 1908 \cite{bernstein} for which property B is named.
If Y has cardinality $\kappa$ then find a  chain $M_{\alpha}$
of standard models of $ZFC^*$ such that
\begin{enumerate}
\item  Y,$<c_n : n\in\omega>\in M_0$
\item  cardinality of each $M_{\alpha}$ is less than $\kappa$
\item  the $M_{\alpha}$'s form a continuous chain, i.\ e.\ for
 $\alpha<\beta$ we have $M_{\alpha}\subset M_{\beta}$ and for limit
 ordinals $\lambda<\kappa$, $M_{\lambda}=\union_{\alpha<\lambda} M_{\alpha}$
\item  $Y\subset\union_{\alpha<\kappa} M_{\alpha}$
\end{enumerate}
Now let
$$Y_{\alpha}= Y \intersect ( M_{\alpha + 1}\setminus   M_{\alpha})$$
By induction we can find $X\subset Y$ which splits each $Y_{\alpha}$.
But such an X must split Y. If $<b_n : n\in\omega>$ is
similar to $<c_n : n\in\omega>$ and meets Y in an infinite set, then
it meets some $Y_{\alpha}$ in an infinite set.  This follows from the
lemma and the continuity of the $M_{\alpha}$'s since no new sequence can
appear at limit stages. \qed
Next we improve on a theorem of H.Miller 1979 \cite{hmiller2}.
\begin{theorem}
Suppose the E is a three element set of reals.  Then there exists
a set of reals X which has full outer measure and is
of the second category everywhere but  contains no three element subset
similar to E.
\end{theorem}
proof:  Let $\{G_{\alpha}\setof \alpha<c\}$ be the set of all uncountable
Borel sets.  Note that each $G_{\alpha}$ has cardinality c.  It is
enough to find X which intersects
each $G_{\alpha}$ and contains no three element 
subset
similar to E. Inductively choose $y_{\alpha}$ for $\alpha<c$ as
follows.  At stage $\alpha$ suppose we have
 $\{y_{\beta}\setof \beta<\alpha\}$.  Let $F_{\alpha}$ be the smallest
 subfield of R such  that
$$\{y_{\beta}\setof \beta<\alpha\}\union E\subset F_{\alpha}$$
Let $y_{\alpha}$ be any point in $G_{\alpha}\setminus F_{\alpha}$.  Note
that this is possible since $|F_{\alpha}|=\alpha+\omega<c$.
We claim that $X=\{y_{\beta}\setof \beta<c\}$ contains no three
element subset similar to E.  For suppose
 $\{y_{\alpha},y_{\beta},y_{\gamma}\}$ was similar to E where
 $\alpha<\beta<\gamma$.  Then for some reals $a\not= 0$ and $b$ we would have
 $$y_{\alpha}=ax_1+b$$
 $$y_{\beta}=ax_2+b$$
 $$y_{\gamma}=ax_3+b$$
where $E=\{x_1,x_2,x_3\}$.
Then
$$ \frac{y_{\gamma}-y_{\beta}}{y_{\beta}-y_{\alpha}}
=  \frac{x_3-x_2}{x_2-x_1} $$
and hence
$$y_{\gamma}=y_{\beta} + (y_{\beta}-y_{\alpha})(\frac{x_3-x_2}{x_2-x_1})
\in F_{\gamma}$$
contradicting $y_{\gamma}
\notin F_{\gamma}$.\qed
Erd\"{o}s conjectured that for every
convergent sequence there is a  set of reals of positive measure
which contains no subset similar to the
sequence.  This still seems to be open. Falconer 1984 \cite{falconer}
has proved this if the sequence does not converge too rapidly.
Komj\'{a}th 1983 \cite{komjath3} has proved this if we consider only
translates of the sequence. H.Miller and P.Xenikakis 1980 \cite{hmiller}
have proved that the set of reals cannot have full measure in any interval.
It is also easy to see that for every finite set of reals E and positive
measure set X, X contains a set similar to E. ( see \cite{hmiller2}).
It is impossible to partition the reals into two ( or even finitely many )
sets neither of which contains a set similar to a given finite set E.
This is the one dimensional case of Gallai's Theorem \cite{ramsey}
p.38.







\section{Hitting every line twice}
\label{twopt}
It is a well-known result of Mazurkiewicz 1914 \cite{mazurkiewicz}
 that there exists a subset of the plane which hits every
line in exactly two points.  It is not known whether a Borel set can have
this property.  D.G. Larman 1968 \cite{larman} has shown that an
$F_{\sigma}$ set cannot have this property.

 Mauldin remarks that if
a $\Sigma^1_1$ set S has this property, then it is a Borel set.
To see this just note that
$$(x,y)\notin S \Longleftrightarrow
 \exists u,v \;u\not=v,v\not=y,u\not=v,(x,u)\in S,
(x,v)\in S$$
and so the complement of S is $\Sigma^1_1$ and so S is Borel.

\begin{theorem}\label{twoptplane}
If V=L then there is a $\Pi^1_1$ subset of the plane that meets every
line in exactly two points.
\end{theorem}
The result will follow easily from
the following lemma.
\begin{lemma}\label{encode}
Suppose $z\in\cantorspace$ is arbitrary, l is a line in the plane, and
X is a countable subset of the plane which does not contain three collinear
points and contains at most one point of l.
  Then there exists a point P on l
such that $z\turingred P$ and $X\union \{P\}$ does not contain three collinear
points. Furthermore the point P can be found recursively in the given data.
\end{lemma}
proof: Note that the noncollinearity condition only rules out countable
many points on l.  It is easy to have either the x-coordinate encode z
and then choose the y-coordinate to put P on l or vice-versa if l is a
vertical line.\qed
Since V=L implies there is a $\Delta_2^1$ well ordering of the reals,
many transfinite constructions of a subset of the reals ( which are
sufficiently effective ) will in the context of V=L produce a
$\Delta_2^1$ set.  When can such a construction be done to get
a $\Pi^1_1$ set?

For example, it is easy to show that if V=L, then
there exists a $\Delta_2^1$ Luzin set X contained in the reals ( i.e.
X is uncountable and for every meager Borel set B, $X\intersect B$ is
countable ).  The usual construction is to just choose the $\alpha^{th}$
element of X so as to avoid the first $\alpha$ many meager Borel sets.
However a Luzin set cannot have the property of Baire and so cannot be
$\Sigma^1_1$ or $\Pi^1_1$.  The reason is that Cohen reals cannot encode
information.  For example, it is not hard to show that if x is a Cohen real
and y is a ground model real recursive in x, then y is recursive.

The general principle is that if a transfinite construction can be done
so that at each  stage an arbitrary real can be encoded into the
real constructed at that stage then the set being constructed will be
$\Pi^1_1$.  The reason is basically
that then each element of the set can encode
the entire construction up to that point at which
it itself is constructed.  This encoding argument will be used in all
the $\Pi^1_1$ constructions in this paper.
 See also Erd\"{o}s-Mauldin-Kunen 1981 \cite{erdos-mauldin-kunen}
  and van Engelen-Miller-Steel 1987 \cite{von-miller-steel}.

\noindent proof of Theorem \ref{twoptplane}:
\par The usual transfinite induction would be to list all lines
$\{l_{\alpha}\setof \alpha<c\}$ and inductively pick points in the
plane so that at each stage $\alpha$ we would have picked at most
$|\alpha|$ points, no three of which are collinear, but
$l_{\alpha}$ containing two of the points.
The construction of a $\Delta_2^1$ set in L which meets every line
in exactly two places is the same except the ordering on lines is the
constructible ordering and at each stage we choose the first constructed
points that will do.  To see that the set $X\subset R^2$ is $\Delta_2^1$
note that
$$\begin{array}{lll}
x\in X & \mbox{iff} & \exists L_{\alpha} \;\models x\in X\\
       & \mbox{iff} & \forall L_{\alpha} \; x\in L_{\alpha}\implies
        L_{\alpha}\models x\in X
\end{array}$$
The statement $L_{\alpha}\models x\in X$ refers to the definition
of X relativized to $L_{\alpha}$. The statement ``$\exists L_{\alpha}$''
can be replaced by ``$\exists$ a well founded relation on $\omega$
which models V=L''.  Since well-foundedness is a $\Pi^1_1$ relation
and $\models$ is a $\Delta_1^1$ relation we see that X is $\Delta_2^1$.

  Define $L_{\alpha}$ to
be point definable iff the Skolem-hull of $(L_{\alpha},\in)$ under the
usual definable Skolem functions of V=L is isomorphic to $(L_{\alpha},\in)$.
Note that the Skolem-hull is the same as  the set of definable elements.
It is well known that there are unboundedly many $\alpha<\omega_1^L$ such
that $L_{\alpha}$ is point definable (see for example
\cite{von-miller-steel}).  Also since L has built in Skolem functions if
$L_{\alpha}$ is point definable then there exists
 $E\subset\omega\cross\omega$ recursive in $Th(L_{\alpha},\in)$
(the first-order theory of $(L_{\alpha},\in)$)
such
 that $(L_{\alpha},\in)$ is isomorphic to $(\omega,E)$.
 Since the first-order of $(L_{\alpha},\in)$ appears in say $L_{\alpha+2}$
 we have that the E above appears in $L_{\alpha+3}$


Let $$\{L_{\beta_{\alpha}}\setof \alpha<\omega_1\}$$ be the set of all
point definable $L_{\alpha}$'s listed in order.  Inductively construct
points in the plane $x_{\beta_{\alpha}},y_{\beta_{\alpha}}$ for
$\alpha<\omega_1$ as follows.  At stage $\alpha$ choose
$x_{\beta_{\alpha}},y_{\beta_{\alpha}}$ so that
$<x_{\beta_{\alpha}},y_{\beta_{\alpha}}>$ is the least constructed
pair of points in the plane such that:
\begin{enumerate}
\item $<x_{\beta_{\alpha}},y_{\beta_{\alpha}}>\in L_{\beta_{\alpha}+\omega}$.
\item No three points of $\{x_{\beta_{\gamma}},y_{\beta_{\gamma}}\setof
\gamma\leq\alpha\}$ are collinear.
\item If l is the first constructed line which fails to contain two points
from $\{x_{\beta_{\gamma}},y_{\beta_{\gamma}}\setof
\gamma<\alpha\}$ then $\{x_{\beta_{\gamma}},y_{\beta_{\gamma}}\setof
\gamma\leq\alpha\}$ does contain two points of l.
\item There is a relation $E\subset\omega^2$ such that
$E\turingred x_{\beta_{\gamma}}$ and $E\turingred y_{\beta_{\gamma}}$
and $(\omega,E)$ is isomorphic to $L_{\beta_{\alpha}}$.
\end{enumerate}
Such a pair exists by Lemma \ref{encode} and note that there exists
$E\subset\omega\cross\omega$ which is $\Delta_1^1$ in $x_{\beta_{\alpha}}$
such that $(L_{\beta_{\alpha}+\omega},\in)$ is isomorphic to
$(\omega,E)$ (similarly for $y_{\beta_{\alpha}}$).

 Now let
$X=\{x_{\beta_{\gamma}},y_{\beta_{\gamma}}\setof
\gamma<\omega_1\}$. To see that X is $\Pi^1_1$ note that
$$z\in X \;\mbox{iff}\;\exists L_{\alpha}\;\mbox{$\Delta_1^1$ in z}
 \; L_{\alpha}\models z\in X$$
\qed

Is there a Borel subset of the plane which meets every circle in
exactly three points?  The same proof as above shows that if V=L,
then there is such a $\Pi^1_1$ set.

Call a set in the plane a two point set iff every line meets it in
exactly two points.
Mauldin (unpublished) has shown that any two point set in the plane
must be totally disconnected.  He asks whether every two point
set must be zero-dimensional.

Kunen and I have shown that any $\Sigma^1_1$ subset of the plane which
cannot be covered by countably many lines must contain a perfect set P
with the property that that no three points of P are collinear.
Dougherty, Kechris, and Jackson have shown that the axiom of determinacy
and V=L[R] implies that every subset of the plane which
cannot be covered by countably many lines must contain a perfect set P
with the property that that no three points of P are collinear.







\section{Maximal Almost Disjoint Families}
\label{maxi}

A maximal almost disjoint (mad) family  is a set $F\subset\infsets$
such that for every two distinct $A,B\in F$, $A\intersect B$ is finite
and for every $X\in\infsets$ there is an $A\in F$ such that
$A\intersect X$ is infinite.  In Mathias 1977 \cite{mathias}
 it is shown that
no mad family
can be $\Sigma^1_1$.  The following theorem was proved jointly
with K.\ Kunen.

\begin{theorem}\label{madfam}
If V=L then there is a mad family which is $\Pi^1_1$.
\end{theorem}
We will need the following lemma.
\begin{lemma}
Suppose $P\subset\infsets$ is a countable family of almost disjoint
sets which include an infinite recursive partition of $\omega$, and
let $z\in\cantorspace$ be arbitrary and let u be any element of
$\infsets$ which is almost disjoint from every element of P.
Then there exists $x\in\infsets$ such that $z\turingred x$,
x is almost disjoint from every element of P, and $u\subset x$.
Furthermore x can be found recursively in the given data.
\end{lemma}
proof:  Let $\{A_n \setof n\in\omega\}$ be the infinite recursive
partition of $\omega$ which is contained in P and let
$$
\{B_n \setof n\in\omega\}=P\setminus\{A_n \setof n\in\omega\}
$$
In order to make $z\turingred x$ we will choose x so that for every
$n\in\omega$,$z(n)=0$ iff $x\intersect A_n$ has even cardinality.
The set  x will be  $u\union\;\bigcup\{F_n\setof n\in\omega\}$
where each $F_n$ is a finite subset of $A_n$, where $F_n$ is
disjoint from $B_m$ for each $m\leq n$ and the appropriate cardinal
so as to encode z(n). \qed

Now this encoding lemma allows us to prove the theorem just as in
section \ref{twopt}.

R. Pol has pointed out some connections between mad families and compact
sets in the spaces $B_1(E)$ of the first Baire class functions on E, endowed
with the pointwise topology.  What follows are some excerpts from a letter
he wrote to me.

Given an almost disjoint family $F\subset\infsets$, let $E=F\union\finsets$,
let $f_A:E\mapsto\{0,1\}$ be the characteristic function of the singleton
$A\in F$, let $p_n:E\mapsto\{0,1\}$ for $n\in\omega$ be defined by
$p_n(S)=1$ iff $n\in S$,
and let $f_{\infty}\equiv 0$ on E.
The space
$$\Phi=\{p_n\setof n\in\omega\}\union\{f_A\setof A\in F\}
\union\{f_{\infty}\}$$
considered  as a subspace of $B_1(E)$ is compact; in fact $\Phi$
is homeomorphic to the compact space associated in a
standard way with the almost-disjoint family F, see Gillman-Jerrison,
(1960) \cite{gillman} , 5I ($f_{\infty}$ is the point at infinity).
The space $\Phi$ is not Fr\'{e}chet iff F is mad.  Now, if F is analytic,
so is E, and $\Phi$, being a compact subspace of $B_1(E)$, is Fr\'{e}chet,
by Rosenthal's theorem (see S. Negrepontis (1984) \cite{negre} section 1),
therefore F is not mad.

Theorem \ref{madfam} provides (under V=L) a compact subspace $\Phi$
of $B_1(E)$ with E being a $\Pi_1^1$ set, which is not Fr\'{e}chet.



\section{Hamel Basis}\label{hame}
Sierpi\'{n}ski 1920 \cite{sierpinski1} and
F. Burton Jones 1942 (\cite{jones}) showed that it is impossible to have
a Hamel basis for the real line R considered as a vector space over
the rationals Q which is Borel, or even in fact $\Sigma_1^1$.
This result is also proved in
Erd\"{o}s 1950 \cite{erdos}.
These proofs use the measurability of $\Sigma^1_1$ sets and Steinhaus's
Theorem that the difference set of a set of positive measure contains
an interval.  Here we give a proof using the property of Baire instead of
measure.
\begin{theorem}\label{hamelbase}
There does not exist a $\Sigma^1_1$ Hamel basis for R over Q.
\end{theorem}
proof:  Suppose H was such a Hamel basis.
We can assume without loss of generality that $1\in H$, since there must
be for some n,
$$\mbox{nonzero $r_1,r_2,\ldots,r_n \in Q$ and $x_1,x_2,\ldots,x_n\in H$} $$
such that $$1= r_1x_1+r_2x_2+\cdots+r_nx_n $$
so then
$(H\setminus\{x_1\})\union\{1\}$ is a $\Sigma^1_1$ Hamel basis.
 Let P be the partial order
for forcing a Cohen real in R (i.e. P is the set of open intervals
with rational end points ordered by inclusion).
Since the statement ``H is a Hamel basis'' is $\Pi^1_2$, it is absolute.
Hence for any $x\in R$ P-generic over V there exist $n\in\omega$ and
$r_0,r_1,r_2,\ldots,r_n \in Q$ such that
$$ p\forces \exists x_1,x_2,\ldots,x_n\in H\;
 x=r_0+r_1x_1+r_2x_2+\cdots+r_nx_n$$
where $r_0$ the coefficient of 1 may be zero.
Let $\epsilon$ be  a small positive rational number such that
$r<x+\epsilon<s$ where $p=(r,s)$. Then since $x+\epsilon$ is a
Cohen real too
$$  \exists y_1,y_2,\ldots,y_n\in H\;
 x+\epsilon =r_0+r_1y_1+r_2y_2+\cdots+r_ny_n$$
But then
$$ \epsilon =(r_1y_1+r_2y_2+\cdots+r_ny_n)-  ( r_1x_1+r_2x_2+\cdots+r_nx_n)$$
which is a contradiction since none of the $y_i$'s or $x_i$'s are
rational but all are from H.\qed


This proof gives a little bit more than the measure theory proof since
Shelah 1984 \cite{shelah} has shown that Con(ZF) implies Con(ZF+DC+BP), where
BP is the statement that every set has the property of Baire.
Hence BP implies there is no Hamel basis.
Shelah's result also shows that it is relatively consistent with
ZFC that no Hamel basis is definable.
The analogous statement for  Lebesgue measure requires the existence of an
inaccessible cardinal.

Sierpi\'{n}ski 1935 \cite{sierpinski3} gives a proof that a Hamel basis
with the property of Baire must be meager. But this does not give the
above result.

\begin{theorem}
If V=L then there is a $\Pi_1^1$ Hamel basis for R over Q.
\end{theorem}
Let Q[X] for $X\subset R$ be the smallest vector space over Q containing
X.
\begin{lemma}
Suppose $X\subset R$ is countable, $z\in R\setminus Q[X]$, and
$w \in\cantorspace$.  Then there exists $y_1,y_2\in R$ such that
$w\turingred y_1,$  $w\turingred y_2$, $y_1\notin Q[X],$
$y_2 \notin Q[X\union\{y_1\}]$, and $z\in Q[X\union\{y_1,y_2\}]$.
Furthermore $y_1,y_2$ can be found recursively in the given data.
\end{lemma}
proof:  First without loss of generality we may assume that w is not
recursive in any finite join of elements from $X\union\{z\}$, since
it can always be replaced by something more complicated.
Let
$$ v=.w(0)w(0)w(1)w(1)w(2)w(2)\cdots \in R$$
and note that $0<v<\frac{1}{9}$.
Find $r\in Q$ such that $\frac{1}{9}< rz< 1$ and let $u=rz-v$, so
$0<u<1$, and write $$ u=.u(0)u(1)u(2)\cdots $$
Define
$$ y_1= . w(0)u(1)w(1)u(3)w(2)u(5)\cdots$$
$$ y_2= . u(0)w(0)u(2)w(1)u(4)w(2)\cdots$$
and note that $y_1+y_2=rz$, so $z\in Q[X\union\{y_1,y_2\}]$.  It is
clear that $w\turingred y_1$ and  $w\turingred y_2$. We also have that
$y_1\notin Q[X]$  since otherwise w is recursive in some finite join
of elements of X. The last thing to check is that
$y_2 \notin Q[X\union\{y_1\}]$.  This is true since otherwise
$z\in Q[X\union\{y_1\}]$ but since $z\notin Q[X]$ then
$y_1 \in Q[X\union\{z\}]$ but this would imply that w is recursive in
a finite join from $X\union\{z\}$. \qed
The lemma allows us to choose inductively  a Hamel basis so that at
each stage the reals we choose recursively code up the whole construction,
and hence we get a $\Pi_1^1$ set just as in section \ref{twopt}.

R. Pol has proven the following generalization of Theorem \ref{hamelbase}.
\begin{quote}
Let X be a complete separable linear metric space over a field
K which is an analytic set and let E be an analytic linear subspace of
X.  If the codimension of E in X is infinite, then it is $2^{\aleph_0}$
(in fact, there is a Cantor set $C\subset X$ linearly independent
over E).
\end{quote}
This gives Theorem \ref{hamelbase} for $X=R$ and $K=Q$.
Pol asks if V=L then does there always exist a linear $\Pi^1_1$ subspace
E of a Banach separable space X with codimension $\aleph_0$?

\section{Maximal Independent Families}\label{mixa}

A set $I\subset\infsets$ is called an independent family iff for
every $F\in\finsubsets{I}$ and disjoint $G\in\finsubsets{I}$ the set
$$\left( \underset {\intersect}{A\in F}  A\right) \intersect
\left(\underset {\intersect}{B\in G}{\omega\setminus B}\right)  $$
 is infinite.
\begin{theorem}\label{notmif}
There does not exist a $\Sigma^1_1$ maximal independent family.
\end{theorem}
We will use the following lemma in the proof.
\begin{lemma} \label{perf}
Suppose that M is a countable standard model, then
there exists a perfect set P of Cohen reals over M such
that every pair from P is almost disjoint.
\end{lemma}
proof: Inductively construct an increasing sequence
 $$<n_k\setof k\in\omega>\in\bairespace$$
and a nested sequence of trees
$$<T_k\subset 2^{\leq n_k}\setof k\in\omega>$$
with the following properties:
\begin{enumerate}
 \item Every branch of $T_k$ has length $n_k$.
 \item All but at most one $s\in T_{k+1}\intersect 2^{n_{k+1}}$
       is identically zero on $[n_k,n_{k+1})$.
 \item For every $k\in\omega$ and $s\in T_k$ there exists $l>k$ such
       that $T_l$ contains two incomparable extensions of s.
 \item For every the dense open subset $D\subset 2^{<\omega}$
       in M there exists $k\in\omega$  such that
       $T_k\intersect 2^{n_k} \subset D$.
\end{enumerate}
The details of this construction will be left to the reader.
The perfect set P is just the set of infinite branches through the tree
$\union\{T_k\setof k\in\omega\}$.\qed

\noindent proof of Theorem \ref{notmif}:
Define
$$ \sigma(F,G)= \left(\underset{\intersect}{A\in F} A \right)\intersect
\left(\underset {\intersect}{B\in G}{\omega\setminus B}\right)$$

\begin{eqnarray*}
 H & = & \{X\in\infsets\setof \exists F\in\finsubsets{I}\;\;
 \exists G\in\finsubsets{I\setminus F}\;\;
\sigma(F,G) \subset^* X\} \\
 K & = & \{X\in\infsets\setof \exists F\in\finsubsets{I}\;\;
 \exists G\in\finsubsets{I\setminus F}\;\;
\sigma(F,G)\intersect X
 =^* \emptyset\}
\end{eqnarray*}

By the maximality of I, $\infsets = H\union K$ and since I is
$\Sigma^1_1$ so are both H and K.  Hence they have the property
of Baire and so one must be nonmeager, say H.
It follows easily from the lemma that there exists a perfect set
$P\subset H$ of almost disjoint sets.
For each $x\in P$ let $F_x$ and $G_x$ witness that x is in H.
By applying the delta systems lemma we can find distinct x and
y in P such that
$$ (F_x\union F_y)\intersect (G_x\union G_y)=\emptyset$$
But then
$$ \left(\underset{\intersect} {A\in F_x\union F_y} A\right) \intersect
\left( \underset{\intersect} {B\in G_x\union G_y}{\omega\setminus B}
\right)\subset^*
X\intersect Y =^* \emptyset $$
which contradicts the independence of I.  A similar proof can be given
if K is nonmeager.
\qed
A family of functions $F\in\bairespace$ is independent iff for every
$n\in\omega$, distinct $f_0,f_1,\ldots,f_{n-1}\subset F$,
 and $s\in {\omega}^n$ the set
$$\{m\in\omega\setof \forall i<n\; f_i(m)=s(i)\}$$
is infinite.
\begin{theorem}
There does not exist a maximal independent family F of functions in
$\bairespace$ which is $\Sigma^1_1$.
\end{theorem}
proof:  The proof is similar to the last one so we only sketch it.
For some $n\in\omega$, $s\in\omega^n$, and $k\in\omega$ the set  H
of all $g\in\bairespace$ such that
$$\exists f_0,f_1,\ldots,f_{n-1}\subset F\;\;
 |\{m\in\omega\setof g(m)=k,\forall i<n\; f_i(m)=s(i)\}|<\omega$$
is a nonmeager $\Sigma^1_1$ set.
By an argument similar to Lemma {\ref{perf}}, we can find a perfect set
$P\subset H$ with the property that for every two distinct
g and h in P for all but finitely many $m\in\omega\;\;g(m)=k$ or
$h(m)=k$.  Letting $<f^g_0,f^g_1,\ldots,f^g_{n-1}>$ witness that
$g\in H$, apply the delta systems lemma to get $g,h\in H$ such
that for all $i\in\omega$ either $f^g_i=f^h_i$ or else both
$f^g_i$ is distinct from all $f^h_j$'s and also
$f^h_i$ is distinct from all $f^g_j$'s.
But then the set
$$\{m\in\omega\setof\forall i<n\; f^g_i(m)=s(i)\}
\intersect \{m\in\omega\setof\forall i<n\; f^h_i(m)=s(i)\}
$$
is finite, contradicting the independence of F.\qed


\begin{theorem}
 If V=L then there exists a $\Pi^1_1$ maximal independent family
 of functions $F\subset\bairespace$.
\end{theorem}
We need the following coding lemma.
\begin{lemma}
 Suppose $F\union\{g\}\subset\bairespace$ is a countable independent
 family and $z\in\cantorspace$ is arbitrary.  Then there
 exists $f\in\bairespace$ such that $z\turingred f$,
 $F\union\{f\}$ is independent, but  $F\union\{f,g\}$ is not.
\end{lemma}
proof:  We will construct an increasing
 sequence $<n_k\setof k\in\omega>\in\bairespace$ and then define
 $f\in\bairespace$ by
 $$ f(m)=\left\{
         \begin{array}{cl}
             g(m)                & \mbox{if $m\not=n_k$ all k} \\
             p(z(k),n_{k+1})    & \mbox{if $m=n_k$}
         \end{array}
         \right.  $$
where $p(\;,\;)$ is a  recursive pairing function.
Note that this makes $z\turingred f$.  We will also pick the
$n_k$'s so that for all k , $g(n_k)\not= 0$ and this guarantees
that f and g cannot belong to the same independent family.
The only thing left is to pick the $n_k$'s thin enough so as to
ensure that $F\union\{f\}$ is an independent family.
But since F is countable and $F\union\{g\}$ is independent,
there is a countable family $C\subset\infsets$ such that it is
enough to make sure that for all $X\in C$ we have
$X\setminus\{n_k\setof n\in\omega\}$ is infinite.\qed

This coding lemma allows us to get a $\Pi^1_1$ maximal independent
family from V=L the same as in section \ref{twopt}.
\begin{theorem}
If V=L, then there exists a $\Pi^1_1$ maximal independent family in
$\infsets$.
\end{theorem}
The proof will follow from the following encoding lemma.
\begin{lemma}
Suppose $I\subset\infsets$ is countable containing an infinite recursive
subset,
 $z\in\infsets$ is such that
$I\union\{z\}$ is an independent family, and $w\in\cantorspace$ is
arbitrary.  Then there exists $u\in\infsets$ such that $w\turingred u$
and $I\union\{u\}$ is independent but $I\union\{u,z\}$ is not.
Furthermore u can be found recursively in the given data.
\end{lemma}
proof: Suppose $<X_n\setof n\in\omega>$ is the infinite recursive subset
of I.  Define $$P_n=X_0\intersect X_1\intersect\cdots\intersect X_{n-1}
\intersect (\omega\setminus X_n)$$
$$ H=\{\left( \underset {\intersect}{A\in F}  A\right) \intersect
\left(\underset {\intersect}{B\in G}{\omega\setminus B}\right)
\setof  F\in\finsubsets{I}\;\;
 G\in\finsubsets{I\setminus F}\}$$
Note that for every $X\in H$ there exist $n\in\omega$ such that
$X\intersect Z\intersect P_n$ is infinite.
Construct  $u\subset\omega$ such that
\begin{enumerate}
\item $u\in\infsubsets{z}$ , so for every
 $x\in H$, $x\intersect (\omega\setminus u)$ is infinite.
\item for every $x\in H$, $x\intersect u$ is infinite.
\item for every $n\in\omega$ ( $w(n)=0$ iff
$\min (P_{2n}\intersect u) < \min (P_{2n+1}\intersect u))$.
\end{enumerate}
The last condition ensures $w\turingred u$ and the first two ensure
that $I\union\{u\}$ is an independent family while $I\union\{u,z\}$
is not.\qed

It is consistent with ZFC that the continuum is arbitrarily large but
there is a maximal independent family of size $\omega_1$
( see Kunen \cite{kunen} chapter 8 ex. A13 p.289 ).
Note that if every $\Sigma^1_2$ set of reals has the property of
Baire, then the arguments above shows that there is no $\Pi^1_1$ maximal
independent family of either type. Similarly, if every set of reals
has the Baire property, then there are no maximal independent families.

In ZF (no choice) does the existence of a maximal independent family in
$\infsets$ imply the existence of a maximal independent
family in $\bairespace$?    What about the converse?

\section{Notation}\label{nota}
For general background see
Kunen \cite{kunen}, Jech \cite{jech}, and Moschovakis
\cite{moschovakis}.
\begin{enumerate}
\item R denotes the real line.
\item $\finsubsets{X}$ is the set of all finite subsets of X.
\item $\infsubsets{X}$ is the set of countably infinite subsets of X.
\item $f\res A$ is the restriction of the function f to the domain A.
\item $X \turingred Y$ means that X is Turing reducible to
Y.
\item $\cantorspace$, the Cantor space
 is the set of functions from $\omega$ into
$2=\{0,1\}$. This is given the product topology where 2 is given the
discrete topology.
\item $2^{<\omega}$ is the partial order of functions whose
domain is some $n\in\omega$ and range is 2.  The order is just inclusion.
\item FIN(X) is the partial order of functions whose domain is some
finite subset of X and whose range is 2.
\item $ZFC^*$ stands for a sufficiently large finite fragment of
ZFC Zermelo-Fraenkel set including the axiom of choice.  By sufficiently
large we mean whatever it takes to get the argument to work.
\item Standard models of $ZFC^*$ are transitive sets which
model $ZFC^*$ when $\in$ interprets itself.
For any $ZFC^*$ there exist a countable transitive model of it.  This follows
from the reflection theorem and the Mostowski collapse
 ( see Kunen \cite{kunen} ). Also generic extensions of countable standard
 model of $ZFC^*$ are also models of $ZFC^*$ , although of a smaller
 fragment.
\item $\Sigma^1_1$ sets are the projection of Borel sets
, i.e. analytic sets . $\Pi^1_1$ sets
are the complements of $\Sigma^1_1$ sets, i.e. coanalytic sets.
  For more on descriptive set
theory see Moschovakis \cite{moschovakis}.  We use here the absoluteness
of $\Sigma^1_1$ predicates in models of $ZFC^*$.  All of the positive
results, e.g. if V=L then there exists a $\Pi^1_1$ maximal independent
 family,  actually give a light-face $\Pi^1_1$ set.
  Similarly all of the negative
 results, e.g. there is no $\Sigma^1_1$ maximal independent family,
 actually show there is no bold-face $\Sigma^1_1$ set.
\item An ultrafilter U on $\omega$ is Ramsey iff for every
partition $f:[\omega]^2\mapsto 2$ there exists $X\in U$ such that
$f\res[X]^2$ is constant.
\end{enumerate}\begin{thebibliography}{99}

\bibitem{baumgartner-laver}
 J.Baumgartner and R.Laver,
 Iterated perfect set forcing, Annals Math. Logic, 17(1979), 271-288.

\bibitem{bernstein}
F.Bernstein, Zur Theorie der trigonometrischen Reihen, Berichte
\"{u}ber die Verhandlungen der K\"{o}nigl. S\"{a}chsischen Gesellschaft der
Wiss\-en\-schaft\-en zu Leipzig. Math.-phs. Klasse, 60(1908),325-338.

\bibitem{blass}
A.Blass, A partition theorem for perfect sets, Proceedings American
Mathematical Society, 82(1981), 271-277.

\bibitem{ellentuck}
 E.Ellentuck,
A new proof that analytic sets are Ramsey, J. Symbolic
Logic, 39(1974),163-165.

\bibitem{von-miller-steel}
F.van Engelen, A.Miller, and J.Steel,
Rigid Borel sets and better
quasiorder theory, in {\bf Logic and Combinatorics,
Proceedings of a Summer Reasearch Conference held August 4-10, 1985,}
 edited by S. Simpson,
Contemporary Math Series AMS, 65(1987),199-222.

\bibitem{erdos}
E.Erd\"{o}s,
Some remarks on set theory, Proceedings American Mathematical
Society, 1(1950), 127-141.

\bibitem{erdos-mauldin-kunen}
E.Erd\"{o}s, D.Mauldin, and K.Kunen,
Some additive properties of sets of real numbers, Fundamenta
 Mathematicae, 93(1981), 187-199.

\bibitem{falconer}
K.Falconer, On a problem of Erd\"{o}s on sequences and measurable
sets, Proceedings American Mathematical
Society, 90(1984), 77-78.

\bibitem{fremlin-jasinski}
D.H.Fremlin and Jasi\'{n}ski,
$G_{\delta}$-covers and large thin sets of reals, to appear.

\bibitem{galvin2}
F.Galvin, Partition theorem for the real line, Notices AMS, 15(1968), 666;
erratum Notices AMS, 16(1969), 1095.

\bibitem{galvin-prikry}
F.Galvin and K.Prikry,
Borel sets and Ramsey's theorem, J. Symbolic Logic, (1973)38, 193-198.

\bibitem{gillman}
L.Gillman and M.Jerison, {\bf Rings of Continuous Functions},
Van Nostrand, (1960).

\bibitem{ramsey}
R.Graham, B.Rothschild, and J.Spencer,
{\bf Ramsey Theory }, John Wiley and Sons, (1980).

\bibitem{hausdorff}
F.Hausdorff,
Summen von $\aleph_1$ Mengen, Fundamenta Mathematicae, 26(1934), 241-255.

\bibitem{harrington}
L.Harrington and S.Shelah, Counting equivalence classes for
co-$\kappa$-Sous\-lin equivalence relations, in {\bf Logic Colloquim 80},
North-Holland, 1982.

\bibitem{harr}
L.Harrington, D.Marker, and S.Shelah, Borel Orderings, to appear in
Transactions of American Mathematical Society (1988).


\bibitem{jech}
T.Jech, {\bf Set Theory }, Academic Press, 1978.

\bibitem{jones}
F.B.Jones,
Measure and other properties of a Hamel basis, Bulletin American
Mathematical Society, 48(1942), 472-481.

\bibitem{komjath3}
P.Komj\'{a}th, Large sets not containing images of a given sequence,
Canadian Mathematical Bulletin, 26(1983), 41-43.

\bibitem{komjath}
P.Komj\'{a}th,
Families close to disjoint ones, Acta. Math. Hungary, 43(1984), 199-207.

\bibitem{komjath2}
P.Komj\'{a}th, On the limit superior of analytic sets, Analysis Mathematica,
 10(1984), 283-293.

\bibitem{kunen}
K.Kunen, {\bf Set Theory },
North-Holland, 1980.

\bibitem{larman}
D.G.Larman, A problem of incidence, J. London
Mathematical Society, 43(1968), 407-409.


\bibitem{laver}
R.Laver, Products of infinitely many perfect trees, to appear.

\bibitem{marczewski}
E.Marczewski,
Sur une classe de fonctions de M. Sierpi\'{n}ski et la classe
 correspondant d'ensembles,
 Fundamenta Mathematicae, 24(1935), 17-34.

\bibitem{martin}
D.Martin, The use of set-theoretic hypotheses in the study of measure
and topology, in {\bf General Topology and Modern Analysis },
 Academic Press, 1981, 417-429.

\bibitem{mathias}
A.R.D.Mathias,
Happy families, Annals of Math Logic, 12(1977), 59-111.


\bibitem{mazurkiewicz}
S.Mazurkiewicz,
 C. R. Sc. et Letres de Varsovie, 7(1914), 322-383.

\bibitem{mazurkiewicz2}
S.Mazurkiewicz, Sur les suites de fonctions continues, Fundamenta
Mathematicae, 18(1932), 114-117.

\bibitem{survey}
A.Miller,
Special subsets of the real line, in {\bf Handbook of Set Theoretic
Topology}, ed. by K.Kunen and J.Vaughan, North-Holland, 1984, 201-234.

\bibitem{emiller}
E.Miller,
On a property of families of sets, Comptes rendus Varsovie, 30(1937), 31-38.

\bibitem{hmiller}
H.Miller and P.Xenikakis
Some results connected with a problem of Erd\"{o}s,
Akademija Nauka i Umjetnosti Bosne i Hercegovine
Radovi Odjeljenje Prirodnih i Matemati\v{c}kih Nauka, 19(1980), 71-75.

\bibitem{hmiller2}
H.Miller, Some results connected with a problem of Erd\"{o}s. II,
Proceedings American Mathematical Society, 75(1979), 265-268.

\bibitem{moschovakis}
Y.Moschovakis, {\bf Descriptive Set Theory },
North-Holland, 1980.

\bibitem{mycielski1}
J.Mycielski, Independent sets in topological algebras, Fundamenta
Mathematicae, 55(1964), 139-147.

\bibitem{mycielski2}
J.Mycielski, Algebraic independence and measure, Fundamenta
Mathematicae, 61(1967), 165-169.

\bibitem{negre}
S.Negrepontis, Banach spaces and topology, in {\bf Handbook of
Set-Theoretic Topology}, North-Holland (1984), 1045-1142.


\bibitem{shelahsouslin}
S.Shelah,
On co-$\kappa$ Souslin relations, Israel J. Math, 47(1984), 139-153.

\bibitem{shelah}
S.Shelah,
Can you take Solovay's inaccessible away?, Israel J. Math, 48(1984), 1-47.

\bibitem{sierpinski1}
W.Sierpi\'{n}ski, Sur la question de la mesurabilit/'e de la base de M.
Hamel, Fundamenta Mathematicae, 1(1920), 105-111.

\bibitem{sierpinski3}
W.Sierpi\'{n}ski, La Base de M. Hamel et al propri\'et\'e de Baire,
Publ. Math. Univ. Belgrade, (1935), 220-224.

\bibitem{sierpinski2}
W.Sierpi\'{n}ski, Fonctions additives non-compl\`etement additives
et fonctions nonmeasurables, Fundamenta Mathematicae,
30(1938), 96-99.


\bibitem{silver}
J.Silver,
Every analytic set is Ramsey, J. Symbolic Logic, 35(1970), 60-64.

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

\bibitem{talagrand}
M.Talagrand, Compacts de fonctions me\-sur\-a\-bles et filtres non
me\-sur\-a\-bles, Studia Mathematica, 67(1980), 13-43.

\end{thebibliography}
\end{document}