% LaTeX2e
% A hodgepodge of sets of reals
% A. Miller   Feb 2006 last revised 8-1-06

\documentclass[12pt]{article}
\usepackage{amssymb}

\def\al{\alpha}
\def\anal{{\bf \Sigma}^1_1}
\def\base{{\mathcal B}}
\def\bb{{\mathfrak b}}
\def\be{\beta}
\def\bool{{\mathbb B}}
\def\borel{{\rm Borel}}
\def\bsn{{\mathfrak s \mathfrak n}^*}
\def\coanal{{\bf \Pi}^1_1}
\def\de{\delta}
\def\diff{{\Delta}}
\def\ff{{\mathcal F}}
\def\forces{{\;\Vdash}}
\def\force{\forces}
\def\gak{{\gamma_k}}
\def\ga{\gamma}
\def\gg{{\mathcal G}}
\def\ka{\kappa}
\def\nonmeag{{\rm non}({\mathcal M})}
\def\om{\omega}
\def\ord{{\rm ord}}
\def\proof{\par\noindent Proof\par\noindent}
\def\pr{\prime}
\def\qed{\par\noindent QED\par}
\def\rationals{{\mathbb Q}}
\def\reals{{\mathbb R}}
\def\res{\upharpoonright}
\def\si{\sigma}
\def\sm{{\setminus}}
\def\sn{{\mathfrak s \mathfrak n}}
\def\sq{\subseteq}
\def\st{\;:\;} % such that
\def\uu{{\mathcal U}}
\def\vv{{\mathcal V}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{sublemma}[theorem]{subLemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{question}[theorem]{Question}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{example}[theorem]{Example}

\begin{document}

\begin{center}
{\large A hodgepodge of sets of reals }
\end{center}

\begin{flushright}
Arnold W. Miller\footnote{
Thanks to the conference organizers: Cosimo Guido, Ljubisa Ko\v{c}inac, Boaz
Tsaban, Liljana Babinkostova, and Marion Scheepers for their generosity in
inviting me to speak at the Second Workshop on Coverings, 
Selections and Games in
Topology, December 2005, University of Lecce, Italy. 
\par Mathematics Subject Classification 2000: 03E17; 54D20; 03E50 
\par Keywords: $\ga$-set,
$\sigma$-sets, Laver forcing, $Q$-sets, universal $G_\de$-sets,
retractive boolean algebras, Souslin numbers, Borel hierarchies,
meager ideal. }
\end{flushright}

\begin{center}
Abstract
\end{center}

\begin{quote}
We open up a grab bag of miscellaneous results and remarks about sets
of reals.  Results concern: Kysiak and Laver-null sets,
Ko\v{c}inac
and $\gak$-sets, Fleissner and square $Q$-sets,  Alikhani-Koopaei and
minimal $Q$-like-sets, Rubin and $\sigma$-sets, and
Zapletal and the Souslin number.
See the survey papers Brown, Cox \cite{browncox},
and Miller \cite{survey1,survey2}.
\end{quote}

\section{$\si$-sets are Laver null}

A subtree $T\sq\om^{<\om}$ of the finite sequences
of elements of $\om=\{0,1,2,\ldots\}$ is called a Laver tree
\cite{laver} iff there exists $s\in T$ (called the root node of
$T$) with the property that for every $t\in T$ with $s\sq t$ there
are infinitely many $n\in\om$ with $t n$ in $T$.  Here $tn$ is
the sequence of length exactly one more than $t$ and ending in
$n$.  We use $[T]$ to denote the infinite branches of $T$, i.e.,
$$[T]=\{x\in\om^\om\st \forall n\in\om\;\; x\res n\in T\}$$

A set $X\sq \om^\om$ is Laver-null iff for every Laver tree
$T$ there exists a Laver subtree $T^\pr\sq T$ such that
$$[T^\pr]\cap X=\emptyset$$
This is analogous to the ideal of Marczewski null sets, $(s)_0$.
For some background on this topic,
see Kysiak and Weiss \cite{kysiak} and Brown \cite{brown}.

A separable metric space $X$ is a $\si$-set iff every
$G_\de$ in $X$ is also $F_\si$.  It is known to be
relatively consistent
(Miller \cite{borhier})
with the usual axioms of set theory that every $\si$-set
is countable.

At the Second Lecce conference, Kysiak asked if it is consistent to have a
$\si$-set which is not Laver-null. The answer is no.\footnote{ As I was writing
this I learned from Jack Brown that M.\ Kysiak, A.\ Nowik, and T.\ Weiss 
\cite{KNW},
also solved this problem at about the same time.  In fact, their solution is a
little better as it also solves the analogous problem for Ramsey null sets.}

\begin{theorem}
Every $\si$-set is Laver-null.  In fact, the
Borel hierarchy of a non-Laver-null set must have $\om_1$ levels.
\end{theorem}

\proof
Here we use a result of Rec\l aw that appears in Miller \cite{survey2}.
Rec\l aw proved that if $X$ is a set of reals and there exists
a continuous onto map
$f:X\to 2^\om$, then the Borel hierarchy on $X$
has $\om_1$ levels, in particular, $X$ is not a $\si$-set.

\begin{lemma}\label{laver-null}
Every set  not Laver-null can be continuously mapped
onto $2^\om$.
\end{lemma}
\proof
Let $X\sq\om^\om$ be a set which is not Laver-null.  Hence
there exists a Laver tree $T$ such that for every Laver subtree
$T^\pr\sq T$ we have that $[T^\pr]$ meets $X$.

To simplify our
notation assume that $T=\om^{<\om}$.  Define the following continuous
function $f:\om^\om\to 2^\om$:
$$f(x)(n)=\left\{
\begin{array}{ll}
0 & \mbox{ if $x(n)$ is even} \\
1 & \mbox{ if $x(n)$ is odd}
\end{array}
\right.
$$
The function  $f$ is the parity function.
Note that $f$ maps $X$ continuously onto $2^\om$.  This is because for
any $y\in 2^\om$ there is a Laver-tree $T$ such that
$f([T])=\{y\}$.  But since $[T]$ meets $X$ there is some $x\in X$
with $f(x)=y$.

In the more general case $T$ is an arbitrary Laver-tree. In
this case note that there is a natural 
bijection from the splitting nodes of $T$ to $\om^{<\om}$.
If $g:[T]\to\om^\om$ is the continuous function corresponding
to this natural map, then $f\circ g$
will map $X\cap [T]$ continuously onto $2^\om$.
This proves the Lemma and hence the Theorem.
\qed

It follows from Lemma \ref{laver-null} that all $S_1$-type properties
in the Scheepers diagram imply being Laver-null.


\section{$\gak$-sets}

In  Ko\v{c}inac \cite{koc} the notion of a $\gak$-set is defined.
See also
Caserta, Di Maio, Ko\v{c}inac, and Meccariello \cite{cmkm}.
A $k$-cover of topological space $X$ is a family of
open subsets with the property that every compact subset of
$X$ is subset of an element of the family.  $X$ is called
$\gak$-set iff for every $k$-cover $\uu$ of
$X$ there exists a sequence $(U_n\in\uu : n\in\om)$ such that
for every compact $C\sq X$ we have that $C\sq U_n$ for all but finitely
many $n$.

This is a generalization of $\ga$-sets which were first considered by
Gerlits-Nagy \cite{gn} and studied in many papers.

A theorem of Galvin and Todor\v cevi\'c 
(see Galvin and Miller \cite{gm}) shows that
it is consistent that the union of two $\ga$-sets need not be a $\ga$-set.
Ko\v{c}inac asked at the Lecce conference if such a counterexample exists for
$\gak$-sets.  We show that it does.

\begin{example}\label{exampkoc}
There exist disjoint subsets of the plane $X$ and $Y$ such
that both $X$ and $Y$ are $\gak$-sets but
$X\cup Y$ is not.
\end{example}

Let $X$ be the open disk of radius one, i.e.,
$X=\{(x,y)\st x^2+y^2<1\}$,
and $Y$ be any singleton on the boundary of $X$, e.g.,
$Y=\{(1,0)\}$.
The result follows easily from the following:

\begin{lemma}
Suppose that $Z$ is a metric space.  Then $Z$ is
a $\gak$-set iff $Z$ is locally compact and separable.
\end{lemma}
\proof
First suppose that $Z$ is locally compact and separable.  Then
we can write $Z$ as an increasing union of compact subsets
$C_n$ whose interiors cover $Z$.  
Given a $k$-cover $\uu$ we simply choose $U_n\in\uu$
so that $C_n\sq U_n$.  This works because for every compact set $C$
there exists $n$ with $C\sq C_n$.

Conversely, suppose that $Z$ is not locally compact. This
means that for some $x\in Z$ we have that $x$ is not in the
interior of any compact set.  Define a sequence
$(\uu_n : n<\om)$ as follows:
For each $n$, let $\uu_n$ be the set of all open subsets of $Z$ such
that $U$ does not contain the open ball of radius $1/2^n$ around
$x$, i.e. there exists $y\notin U$ such that $d(x,y)<1/2^n$.

Note that each $\uu_n$ is a $k$-cover of $Z$.  To see this, suppose $C$
is a compact subset of $Z$.  Since $x$ is not in the interior of
$C$, the set $C$ cannot contain an open ball centered at $x$.
Choose $y\notin C$ with $d(x,y)<1/2^n$.  Now cover $C$ with
(finitely) many open balls not containing $y$. The union of this
cover is in $\uu_n$.

We can use the trick of Gerlits and Nagy to get a single $k$-cover
from the
sequence  of
$k$-covers, $(\uu_n\st n\in\om)$.
Since $Z$ cannot be compact there
must exist a sequence $(x_n:n\in\om)$ with no limit point.  Define
$$\uu=\{U\sm\{x_n\} \st n<\om,\;\; U\in \uu_n\}.$$
Since any compact set can contain at most finitely many of
the $x_n$, we see that $\uu$ is a $k$-cover of $Z$.

For contradiction, suppose $Z$ is $\gak$-set and
$(U_n\in\uu:n\in\om)$ eventually contains each compact set.
Without loss, we may assume that $U_n\in \uu_{l_n}$ with
$l_n$ distinct. This is because at most finitely many $U_n$ can
be ``from'' any $\uu_l$ since they eventually must include $x_l$.
Choose $y_n\notin U_n$ with $d(x,y_n)<1/{2^{l_n}}$.  Then
$$\{y_n\st n\in\om\}\cup \{x\}$$
is a convergent sequence, hence compact. But it is not a
subset of any $U_n$.

It is easy to see that $Z$ must be separable as we can take
$\uu_n$ to be the family of finite unions of open balls of
radius less than $1/2^n$, then apply the Gerlits Nagy trick
as above to obtain a countable basis for $Z$.

\qed

In Example \ref{exampkoc}
each of $X$ and $Y$ are locally compact metric spaces but
$X\cup Y$ is not locally compact at the point $(0,1)$, so the
result follows.

Ko\v{c}niac also asked if $X\times Y$ is $\gak$-set if both
$X$ and $Y$ are.  For metric spaces, this must be true by the Lemma,
since the product of locally compact separable metric spaces is a locally
compact separable metric space.

This is very different from the situation for usual $\gamma$-sets.

\begin{prop}(Tsaban). If $X\times Y$ is a $\ga$-set, then $X \cup Y$ is a
$\gamma$-set.
\end{prop}
\proof
If $\uu$ is an open $\om$-cover of $X\cup Y$, then 
$\uu^2=\{U^2 \st U\in \uu\}$
 is an open
$\om$-cover of $X\times Y$, 
so there is 
$\vv\sq\uu$ such that 
$\vv^2=\{V^2 \st V \in \vv\}$ is a $\ga$-cover
of $X\times Y$, but then $\vv$ is a $\ga$-cover of $X\cup Y$.
\qed
This was not noticed in Galvin-Miller \cite{gm}, where a direct argument for
$X\times Y$ not being
a $\ga$-set is provided after it is shown that $X\cup Y$ is not a
$\ga$-set.


\section{Q-sets}

A Q-set is a separable metric space $X$ such that every subset
of $X$ is a (relative) $G_\de$-set.  It is easy to
see that $2^{|X|}=2^\om$, hence, if there is an uncountable
Q-set, then $2^{\aleph_1}=2^{\aleph_0}$.  So uncountable Q-sets
might not exist.  Martin's axiom (MA) implies that every separable
metric space of size less than the continuum is a Q-set
(see Martin and Solovay \cite{internal}).

The Rothberger cardinal, $\bb$, is defined to be the cardinality
of the smallest family $\ff\sq\om^\om$ such that for every $g\in\om^\om$
there is some $f\in \ff$ with $f(n)\geq g(n)$ for infinitely many $n$.
That is to say, $\bb$ is the size of the smallest unbounded family
in the quasi-ordering $(\om^\om,\leq^*)$.
Martin's Axiom implies that $\bb$ is the continuum.

A set $U$ is a universal $G_\de$-set, if it is $G_\de$ and for every
$G_\de$-set $V\sq 2^\om$ there exists $x\in 2^\om$ such that
$$U(x)=^{def}\{y\in 2^\om\st (x,y)\in U\}=V.$$

\begin{theorem} \label{qsets}
Suppose $\ka<\bb$.  Then the following are equivalent:
\begin{enumerate}
\item \label{existq} There exists a Q-set $X\sq 2^\om$ with $|X|=\ka$.
\item \label{functionq}
There exists $(f_\al:\om^\om\to 2^\om\st \al<\ka)$ continuous
functions such that given any $(y_\al\in 2^\om\st \al<\ka)$ there exists
$x\in \om^\om$ with the property that
$f_\al(x)=^*y_\al$ for every $\al<\ka$.
\item \label{univq}
There exists a sequence $(U_\al\sq 2^\om\times 2^\om\st\al<\ka)$
of $G_\de$-sets which is universal for $\ka$ sequences
of $G_\de$-sets, i.e., for every sequence
$$(V_\al\sq 2^\om\st\al<\ka)$$
of $G_\de$-sets there exists $x\in 2^\om$ such that for every $\al<\ka$
$$V_\al=U_\al(x)=^{def}\{y\st (x,y)\in U_\al\}.$$
\end{enumerate}
\end{theorem}
\proof

We will need the following lemma and the details of its proof.

\begin{lemma} \label{lemq}
There exists $U\sq 2^\om\times 2^\om$ which is a universal $G_\de$-set
such that for every $x_1,x_2\in 2^\om$ if
$x_1=^*x_2$, then $U(x_1)=U(x_2)$.
\end{lemma}
\proof
Define
$$U=\{(A,y)\in P(2^{<\om})\times 2^\om\st\exists^\infty n\;\; y\res n\in A\}$$
where $\exists^\infty$ stands for ``there exists infinitely many''.
It is easy to see that $U$ is $G_\de$.   To see that it is universal, suppose
that $V=\bigcap_{n<\om} V_n$ where the $V_n\sq 2^\om$ are open and
descending, i.e.,  $V_{n+1}\sq V_n$ for each $n$.
For $\si\in 2^{<\om}$ nontrivial
let $\si^*\sq\si$ be the initial
segment of $\si$ of length exactly one less than $\si$,
i.e., $|\si^*|=|\si|-1$.   Define
$$A=\{\si\st [\si]\sq V \mbox{ or }\exists n\;\; [\si]\sq V_n
\mbox{ and } [\si^*]\not\sq V_n\}$$
Then $U(A)=V$.  To see this,  suppose $x\in U(A)$.
If for some $n$ we have that $x\res n\in A$ because $[x\res n]\sq V$
then clearly $x\in V$.  On the other hand, if there are infinitely
many $k$ such that for some $n$, $[x\res k]\sq V_n$ but
$[x\res (k-1)]\not\sq V_n$, then these $n$'s must all be distinct
and since the $V_n$ were descending $x\in V$.

Conversely, if $x\in V$
then either $x$ is in the interior of $V$ and so
$x\res k\in A$ for all but finitely many $k$ or it isn't in the
interior of $V$ and there are thus infinitely many $n$ with
$x\res n\in A$.  Hence $x\in U(A)$.

From the definition of $U$ it is easy to check that if
$A=^*A^\prime$, then $U(A)=U(A^\prime)$.

\qed

\bigskip
\ref{functionq}$\to$\ref{univq}:

\noindent This follows immediately from the Lemma.  Just define
$$(x,y)\in U_\al\mbox{ iff } (f_\al(x),y)\in U$$
identify $\om^\om$ with a $G_\de$ subset of $2^\om$.

\bigskip
\ref{univq}$\to$\ref{existq}:

\noindent By the proof of Lemma \ref{lemq} there exists
$A_\al\sq 2^{<\om}\times 2^{<\om}$ such that
for any $(x,y)$ we have that
$(x,y)\in U_\al$ iff $\exists^\infty n\;\; (x\res n,y\res n)\in A_\al$.
We claim that
$$\{A_\al\st \al<\ka\}$$
is a $Q$-set.  Fix $y\in 2^\om$ arbitrary.  Consider any
$\Gamma\sq \ka$ and define the sequence of $G_\de$ sets
$(V_\al:\al<\ka)$ by 
$$V_\al=\left\{
\begin{array}{ll}
\{y\} & \mbox{ if } \al\in\Gamma\\
\emptyset & \mbox{ if } \al\notin\Gamma\\
\end{array}\right.
$$ 
\def\miff{\;\;\mbox{ iff } \;\;}
By assumption there exists $x\in 2^\om$ such that
$U_\al(x)=V_\al$ for every $\al<\ka$.  But then
$$\al\in\Gamma \miff
y\in U_\al(x) \miff
\exists^\infty n\;\; (x\res n,y\res n)\in A_\al \miff $$
$$A_\al\in \{A\st \exists^\infty n\;\;(x\res n,y\res n)\in A\}$$
But this last set is $G_\de$.  It follows
that $\{A_\al\st\al\in\Gamma\}$ is relatively $G_\de$
in the set $\{A_\al\st\al\in\ka\}$.


\bigskip
\ref{existq} $\to$ \ref{functionq}:

\noindent Let $\{v_\al^n\in 2^\om \st n<\om,\;\;\al<\ka\}$
be a $Q$-set.  Now for each $\al<\ka$ define a continuous map
$f_\al:\om^\om \to 2^\om$ as follows. 
Suppose $x=(A,(I_n:n<\om))$ where $A\sq 2^{<\om}$ and
each $I_n\sq 2^{<\om}$ is finite.  (We can easily identify the set
of such $x$ with
$\om^\om$.)     Define
$$f_\al((A,(I_n:n<\om)))(n)=
\left\{
\begin{array}{ll}
1 & \mbox{ if } \exists k\;\; v_\al^n\res k\in I_n\cap A\\
0 & \mbox{ otherwise }\\
\end{array}\right.
$$ 
Since the $I_n$ are finite, the function
$f_\al$ is continuous.  We verify that it has the property required.
Let $x_\al\in 2^\om$ for $\al<\ka$ be arbitrary.  Since
$\{v_\al^n\in 2^\om \st n<\om,\;\;\al<\ka\}$ is a $Q$-set,
there is a $G_\de$-set $U\sq 2^\om$ with
the property that for every $\al<\ka$ and $n<\om$ we
have that $v_\al^n\in U$ iff $x_\al(n)=1$.
By the proof of Lemma \ref{lemq} there exists $A\sq 2^{<\om}$ such
that for all $\al,n$

$v_\al^n\in U$ iff $A\cap\{v_\al^n\res k\st k<\om\}$ is
infinite.

\noindent Since $\bb>\ka$ there exists a partition
$(I_l : l<\om)$ of $2^{<\om}$ into finite sets such that
for every $\al<\ka$ and $n<\om$
the set $A\cap\{v_\al^n\res k\st k<\om\}$ is
infinite iff $I_l\cap A\cap\{v_\al^n\res k\st k<\om\}\neq \emptyset$
for all but finitely many $l<\om$.  But this implies that
for $f_\al((A,(I_l : l<\om))=^*x_\al$ for each $\al$.

\qed

\bigskip
Condition \ref{univq} is a kind of uncountable version of Luzin's doubly
universal sets, see Kechris \cite{kec} page 171 22.15 iv.  Luzin used
a doubly universal set to prove that the classical properties
of separation and reduction cannot hold on the same side of a
reasonable point-class.

In condition \ref{functionq},  $u=^*v$
means that $u(n)=v(n)$ except for finitely many $n$.  It is impossible
to have the stronger condition with ``$=$'' in place of ``$=^*$'' at least
when $\ka$ is uncountable.  To see this, fix $y_0\in 2^\om$ and
define $E_\al=f_\al^{-1}(y_0)$ for $\al<\om_1$.  It is not
hard to see that the $F_\al=\bigcap_{\be<\al}E_\be$ would have
to be a strictly decreasing sequence of closed sets, which is impossible
in a separable metric space.

We do not know if the condition $\ka<\bb$ is needed for this result.
There are several models of set theory where there is a $Q$-set
and $\bb=\om_1$,  Fleissner and Miller \cite{FM},
Judah and Shelah \cite{JS}, and Miller \cite{madq}.

We obtained this result while working on the square Q-set problem,
see Fleissner \cite{squareQ}.  Unfortunately, Fleissner's proof that
it is consistent there is a $Q$-set whose square is not a $Q$-set contains
a gap. In his paper,
he claims to show that in his model of set theory:
\begin{enumerate}
\item there is a $Q$-set $Y\sq 2^\om$ of size $\om_2$, and
\item for any set of $Z=\{z_\al \st \al< \om_2\}\sq  2^\om$ the set
$$\{(z_\al,z_\be) \st \al<\be<\om_2\}$$
 is not $G_\de$ in $Z \times Z$.
\end{enumerate}
But we have a fairly easy proof that (1) implies the negation of (2).

\begin{theorem}
If there exists a Q-set $Y\sq 2^\om$
with $|Y|=\om_2$, then there exists
$Z=\{z_\al:\al<\om_2\}\sq 2^\om$ such that
$$\{(z_\al,z_\be):\al<\be<\om_2\}$$
is (relatively) $G_\delta$ in $Z^2$.
\end{theorem}

\proof Let $Y=\{y_\al:\al<\om_2\}$ and let
$U\sq 2^\om\times 2^\om$ be a universal $G_\de$-set.
Choose for each $\be<\om_2$ a $u_\be\in 2^\om$ such that
for every $\alpha<\om_2$
$$y_\alpha \in U(u_\be)\mbox{ iff } \alpha<\be .$$
Since $U$ is $G_\delta$ there are clopen $C_{n,m},D_{n,m}\sq 2^\om$
with
$$U=\bigcap_{n<\om}\bigcup_{m<\om} (C_{n,m}\times D_{n,m})$$

Now let $z_\alpha=(y_\alpha,u_\alpha)$ and identify $2^\om\times 2^\om$
with $2^\om$.


Then for any $\alpha,\be<\om_2$ we have that

$\alpha<\be$

iff  $(y_\alpha,u_\be)\in U$


iff $(y_\alpha,u_\be)
\in \bigcap_{n<\om}\bigcup_{m<\om} (C_{n,m}\times D_{n,m})$

iff $(z_\alpha,z_\be)=((y_\alpha,u_\alpha),(y_\be,u_\be))
\in
\bigcap_{n<\om}\bigcup_{m<\om} ((C_{n,m}\times 2^\om)\times
(2^\om\times D_{n,m}))$

\qed

As far as we know, the problem of the consistency
of a $Q$-set whose square is not a $Q$-set, is open. 
We do not know where the mistake in Fleissner's proof occurs.
One way to connect this problem with Theorem \ref{qsets} is the
following:

\begin{cor}
Suppose there is a $Q$-set of size $\om_2$ and
$\bb>\om_2$.  Then given any family $\Gamma\sq P(\om_2\times\om_2)$
with $|\Gamma|=\om_2$
there is a $Q$-set $$Z=\{z_\al\in 2^\om\st\al<\om_2\}$$
such that for every $A\in\Gamma$ the
set $\{(z_\al,z_\be)\st (\al,\be)\in A\}$ is
$G_\de$ in $Z$.
\end{cor}

The corollary is also valid for any $\ka$ in place of $\om_2$.

\section{Minimal $Q$-like-sets}

At the Slippery-Rock conference in June 2004, Ali A. Alikhani-Koopaei
asked me if the following $Q$-like example was possible.  We show that
it is.

\begin{example}
There exist a $T_0$ space $Y$ such that $Y$ is not a $Q$-set
but for every
$A\sq Y$ there is a minimal $G_\de$ set $Q$ with
$A\sq Q$.
By minimal we mean that for any $G_\de$ set $Q^\pr$ if
$A\sq Q^\pr$, then $Q\sq Q^\pr$.
\end{example}

\proof
Let $X$ be any Q-set, i.e., every subset of $X$ is $G_\de$ and
$X$ at least $T_0$.  For example, a
discrete space.  Now let $X^\pr$ be a disjoint copy of $X$ and
let $p\mapsto p^\pr$ a bijection from $X$ to $X^\pr$.  For each $A\sq X$
let $A^\pr=\{p^\pr:p\in A\}$.  Define the topology on $Y=X\cup X^\pr$
by letting the open sets of $Y$ be exactly those of the form $U\cup V^\pr$
where $U,V\sq X$ are open in $X$ and $U\sq V$.  Then $Y$ is $T_0$, e.g.
$X^\pr$ is open in $Y$ and separates any $p$ and $p^\pr$.

\bigskip

Claim: For $A,B\sq X$ the set $A\cup B^\pr$ is $G_\de$ in $Y$ iff
$A\sq B$. Furthermore, given any $A,B\sq X$ the set
$A\cup (A\cup B)^\pr$ is the minimal $G_\de$ in $Y$ containing
$A\cup B^\pr$.
\proof

Suppose that $A$ is not a subset of $B$ and let $p\in A\sm B$.  Then any
open set in $Y$ which contains $A$ must also contain $p^\pr$.  The same is
true for any $G_\de$ and hence $A\cup B^\pr$ is not $G_\de$.

On the other hand, suppose $A\sq B$.  Let $A=\bigcap_{n<\om}U_n$ and
$B=\bigcap_{n<\om}V_n$ where the $U_n$ and $V_n$ are open in $X$. Now since
$A\sq B$ we may assume that $U_n\sq V_n$ (if not just replace $U_n$ by
$U_n\cap V_n$).  But then
$$A\cup B^\pr=\bigcap_{n<\om} (U_n\cup V_n^\pr).$$
Furthermore, note that if $C\cup D^\pr$ is $G_\de$ and
contains $A\cup B^\pr$, then $A\sq C$ and $C\cup B\sq D$ and so
$A\cup (A\cup B)^\pr\sq C\cup D^\pr$

\qed

\bigskip

Question. Can we get an example which is uncountable but contains no
uncountable Q-set?

\bigskip
Yes.  Let $X=\om_1$ have the topology
with $U\sq X$ is open iff $U=\emptyset$ or
there exists $\al$ with
$$U=[\al,\om_1)=^{def}\{\be:\al\leq\be<\om_1\}$$
Given any $A\sq X$ the smallest $G_\de$ containing $A$
is $[\min(A),\om_1)$.


\section{$\si$-sets and retractive boolean algebras}


The definition of thin set of reals is due to Rubin \cite{rubin} who showed it
equivalent to a certain construction yielding a retractive boolean algebra
which is not the subalgebra of any interval algebra.  Rubin asked whether or
not there is always an uncountable thin set of reals.  We show
that every thin set is a $\si$-set and so by the results of
Miller \cite{borhier} that it is consistent there are no
uncountable $\si$-sets, it is also consistent there are no uncountable
thin sets.

A thin set of reals is defined as follows.  An OIT (ordered interval
tree) is a family of $(G_n:n\in \om)$ such that
each $G_n$ is a family of pairwise disjoint open intervals
such that for $n$ and $I\in G_{n+1}$ there
exists $J\in G_n$ with $I\sq J$.
A set of reals $Y$ is
$(G_n:n\in \om)$-small iff there exists $(F_n\in [G_n]^{<\om}:n\in \om)$
such that for every $x\in Y$ and $n\in\om$ if
$x\in \cup G_n$, then $x\in\cup F_n$.
A set of reals $X$ is thin iff for every OIT, $(G_n:n\in \om)$,
the set $X$ is a countable union of $(G_n:n\in \om)$-small sets.

\begin{prop}
 If $X\sq\reals$ is thin, then $X$ is a $\si$-set.
\end{prop}
\proof

A thin set cannot contain an interval (see Rubin \cite{rubin})
so we may suppose that $X$ is disjoint from a countable dense
set $D\sq\reals$.  Let $\base$ be the family of nonempty open intervals with
end points from $D$.
The following claim is easy to prove and left to the reader.

\bigskip

{\bf Claim}. Given any open set $U\sq I$ where $I\in\base$
we can construct a family of
pairwise disjoint intervals $G\sq \base$ so that
\begin{enumerate}
\item $cl(J)\sq I$ for each
$J\in G$ and
\item $\bigcup G \sq U \sq \bigcup G \cup D$.
\end{enumerate}

\bigskip
Now suppose that $\bigcap_{n<\om} U_n$ is an arbitrary
$G_\de$ set of reals where
the $U_n$ are open sets. Using the claim it is easy to construct a sequence
$G_n\sq \base$ of pairwise disjoint intervals such that:
\begin{enumerate}
\item if $I\in G_{n+1}$, then for some $J\in G_n$ we have $cl(I)\sq J$ and
\item $\bigcup G_n \sq U_n \sq \bigcup G_n \cup D$.
\end{enumerate}
Since $X$ is thin, we have
that $X=\cup_{m<\om}X_m$ where each
$X_m$ is $\{G_n:n<\om\}$-small.
Fix $m$.
There exists $F_{n,m}\in [G_n]^{<\om}$ for $n<\om$ which
witness the smallness of $X_m$.
Let
$$C_m=\bigcap_{n<\om}(\cup F_{n,m})$$
Note that we may assume that for each $n$ and $I\in F_{n+1,m}$ there
is a $J\in F_{n,m}$ with $cl(I)\sq J$.  Hence
$$\bigcap_{n<\om}(\cup F_{n,m})=\bigcap_{n<\om}(\cup_{I\in F_{n,m}}cl(I))$$
and since each
$F_{n,m}$ is finite, $C_m$ is closed.
Since $X$ is disjoint from $D$  we have that
$$X\cap (\bigcap_{n<\om} U_n) = X\cap (\cup_{m<\om} C_m).$$
Since we started with an arbitrary $G_\de$ set we have that
$X$ is a $\si$-set.
\qed

Next we see that a set of reals is thin iff it is hereditarily
Hurewicz.  See Miller and Fremlin \cite{fremlin} for the definition of
the Hurewicz property.

\begin{prop}
A set of reals $X$ is thin iff it is hereditarily
Hurewicz.
\end{prop}
\proof
Suppose $X$ is hereditarily Hurewicz and let $(G_n:n\in \om)$
be an OIT.  Let 
$$Y=\{x\in X\st \forall n\;\; x\in \cup G_n\}.$$
Since $Y$ has the Hurewicz property, there exists
$(F_n\in [G_n]^{<\om}:n<\om)$ such that 
$\forall^\infty n \;\;x\in \cup F_n$
for each $x\in Y$.  Let $(F_n^m\in [G_n]^{<\om} : n<\om)$ 
for $m<\om$ list all sequences
such that $F_n^m=F_n$ for all but finitely many $n$. 
Define 
$$X_m=X\cap (\bigcap_n \cup F_n^m).$$
Note that each $X_m$ is $(G_n:n\in \om)$-small and
$$X=\cup_m X_m\cup (X\sm \cup G_0)$$
because the $G_n$ are refining.

Conversely, suppose $X$ is thin, $Y\sq X$, and $(\uu_n:n\in \om)$
a sequence of open covers of $Y$.  As in the above proof
we can find an OIT, $(G_n:n\in \om)$, such that each
$G_n$ refines $\uu_n$ and covers $Y$.  Since $X$ is thin, we
have that is the countable union of $(G_n:n\in \om)$-small
sets.  Let $(F_n^m\in [G_n]^{<\om} : n<\om)$ 
for $m<\om$ list the finite sets given by the notion of smallness.
Define 
$$F_n=F_n^0\cup F_n^1\cup\cdots\cup F_n^n$$
Choose $\vv_n\in [\uu_n]^{<\om}$ so that for each $n$ and
$I\in F_n$ there exists $V\in\vv_n$ with $I\sq V$.  For each
$x\in Y$ we have that $x\in\cup F_n$ for all but finitely many $n$.
\qed




\section{Souslin number and nonmeager sets}

We obtained these results in March 2004.
First we define the following small cardinal number:

$$\nonmeag=\min\{|X|\;:\; X\sq 2^\om\mbox{ nonmeager }\}$$

For $X\sq 2^\om$ we define $\ord(X)$  (the Borel order of $X$) to be the
smallest $\al<\om_1$ such that every Borel subset $A$ of $2^\om$ there
exist a ${\bf \Sigma}^0_\al$ subset $B$ of $2^\om$ such that
$A\cap X=B\cap X$, if there is no such $\al<\om_1$, we define
$\ord(X)=\om_1$.

To prove our main result (Theorem \ref{two})
we will use the following theorem:

\begin{theorem}\label{one}
There exists $X\sq 2^\om$ with $|X|\leq\nonmeag$ and $\ord(X)=\om_1$.
\end{theorem}
\proof
This is similar to the proof of Miller \cite{borhier} Theorem 18.  Notice
that it is enough to show that for each $\al<\om_1$ there
exists an $X_\al\sq 2^\om$ with
$$|X_\al|\leq \nonmeag$$
 and
$\ord(X_\al)\geq\al$, since the $\om_1$ union of these sets would be
the $X$ we need.

So fix $\al_0<\om_1$ with $\al_0>1$.
According to Miller \cite{borhier} Theorem 13, there exists
a countable subalgebra $\gg\sq \bool$ where $\bool$ is the complete boolean
algebra:
 $$\bool={{\mbox{Borel}(2^\om)}\over {\mbox{meager}(2^\om)}}$$
such that $\gg$ countably generates  $\bool$ in exactly $\al_0$
steps. This last statement means the following:

Define $\gg_0=\gg$. For $\al>0$ an even ordinal define $\gg_\al$ to be the
family of countable disjuncts of elements from $\bigcup_{\be<\al}\gg_\be$ and
for $\al$ an odd ordinal define $\gg_\al$ to be the family of countable
conjuncts of elements from  $\bigcup_{\be<\al}\gg_\be$.   These classes are
analogous to the ${\bf\Sigma}^0_\al$ and ${\bf\Pi}^0_\al$ families of Borel
sets.  Then $\gg$ has the property that $\gg_{\al_0}=\bool$ but for each
$\be<\al_0$, $\gg_\be\not=\bool$.


Now let $Y\sq 2^\om$ be such that $|Y|=\nonmeag$ and  $Y\cap U$ is
nonmeager for every nonempty open subset $U$ of $2^\om$.  Note that
$Y$ has the property that for any Borel subsets $A$ and $B$ of
$2^\om$, if $A\cap Y=B\cap Y$, then the symmetric difference, 
$A\diff B$ is meager.

Let $\ff\sq \borel(2^\om)$
be a family of representatives for $\gg$, i.e.,
 $$\gg=\{[A]:A\in \ff\}$$
where $[A]\in\bool$ is the equivalence class of $A$ modulo the meager 
ideal
in $2^\om$.  Assume $\ff$ is chosen so that the map $A\mapsto [A]$ is
one-to-one and $2^\om$ and $\emptyset$ are the representatives of
$1$ and $0$.
By throwing out a meager subset
of $Y$ we may assume that for any $A,B,C\in \ff$
\begin{enumerate}
\item $[A]\vee [B]=[C]$ iff $(A\cup B)\cap Y=C\cap Y$
\item $[A] \wedge [B]=[C]$ iff $(A\cap B)\cap Y=C\cap Y$
\end{enumerate}
Define $\ff^Y=\{Y\cap A: A\in\ff\}$.
Then we have that $\gg$ and $\ff^Y$ are isomorphic as boolean algebras:
$$(\gg,\vee,\wedge, 0,1)\simeq (\ff^Y,\cup,\cap,\emptyset,Y)$$

Define
$\ff_\be$ and $\ff_\be^Y$ exactly as we did $\gg_\be$ but using countable
unions and intersections instead of disjuncts and conjuncts as we do in a
boolean algebra.

\bigskip
\noindent {\bf Claim}.
\par
\begin{enumerate}
\item By induction on $\be$
\begin{enumerate}
\item $\gg_\be=\{[B]:B\in \ff_\be\}$ and
\item $\ff^Y_\be=\{B\cap Y:B\in \ff_\be\}$.
\end{enumerate}
\item If $\be<\al_0$, then $\ff^Y_\be\not=\ff^Y_{\al_0}$.
\end{enumerate}
\proof
Item (1) is an easy induction.  To see (2)
suppose that $[B]\in\gg_{\al_0}\sm \cup_{\be<\al_0}\gg_{\be}$. 
Without loss $B\in\ff_{\al_0}$ and we claim that
$B\cap Y\in \ff_{\al_0}^Y\sm \cup_{\be<\al_0}\ff_{\be}^Y$. 
Suppose for contradiction that
$B\cap Y\in \ff^Y_\be$ for some $\be<\al_0$.  Then there would exist
$C\in\ff_\be$ with $B\cap Y=C\cap Y$.  But this would imply that
$[B]=[C]\in \gg_\be$ which is a contradiction.
This proves the claim.

\bigskip Now let $\ff^Y=\{C_n:n<\om\}$ and let $i:Y\to 2^\om$ be the
Marczewski characteristic function of the sequence, which is defined
by
 $$i(a)(n)=\left\{
\begin{array}{ll}
1 & \mbox{ if } a\in C_n \\
0 & \mbox{ if } a\notin C_n\\
\end{array}\right.
$$ 
Let $X=i(Y)$.  $i$ need not be one-to-one but by definition, it is onto
$X$, 
so $|X|\leq |Y|=\nonmeag$.  Note that
 $$\{C\cap X\;:\; C \mbox{ is clopen in } 2^\om\}=\{i(C):C\in\ff^Y\}$$
Hence, since the Borel order of $\ff^Y$ is at least $\al_0$ we have that
$\ord(X)\geq\al_0$. This proves Theorem \ref{one}.

\qed

We define the Souslin number $\sn$:
$$\sn=\min\{|X|\;:\; X\sq 2^\om,\;\; 
\exists A\in\anal\;\forall B\in\coanal
\; A\cap X\not= B\cap X\}$$

In Zapletal \cite{zap2} Appendix C, it is shown that
$\sn\geq \bb$, where $\bb$ is the smallest cardinality of
an unbounded family in $\om^\om$.
In Miller \cite{relanal} it is
shown to be consistent to have $\sn > \bb$.

Define the following variant of the Souslin number $\bsn$:
$$\bsn=\min\{|X|\;:\; X\sq 2^\om,\;\; 
\exists A\in\anal\;\forall B\in\borel
\; A\cap X\not= B\cap X\}$$

The following theorem partially confirms a conjecture of Zapletal
that $\sn\leq\nonmeag$, since $\bsn\leq\sn$.   Zapletal was motivated by
results in \cite{zap2} Appendix C and \cite{zap},
which roughly speaking show that it is
impossible to force  $\sn>\nonmeag$ using a 
countable support iteration of
definable real forcing in the presence of suitable large cardinal axioms.
Zapletal's conjecture remains open.

\begin{theorem}\label{two}
$\bsn\leq\nonmeag$
\end{theorem}
\proof

Let $U\sq 2^\om\times 2^\om$ be a universal ${\bf \Sigma}^1_1$ set and 
consider the set of reals $X$
from Theorem \ref{one}.  For each $\al<\om_1$ let $B_\al\sq 2^\om$ be a
${\bf\Sigma}^0_\al$ such that for every $C$ which is ${\bf \Pi}^0_\al$
we have that
 $$B_\al\cap X\not=C\cap X$$
Since $U$ is universal there exists $a_\al\in 2^\om$ such that the cross
section $U_{a_\al}=B_\al$.  Let $Z$ be defined by
 $$Z=\{a_\al:\al<\om_1\}\times X\sq 2^\om\times 2^\om$$
Then $|Z|\leq\nonmeag$ and there is no Borel set $B\sq 2^\om\times 2^\om$ such
that $Z\cap U=Z\cap B$.  This is because if $B$ is say ${\bf \Pi}^0_\al$, then
every cross section of $B$ is ${\bf \Pi}^0_\al$, but then
  $$B_\al\cap X = U_{a_\al}\cap X=B_{a_\al}\cap X$$
which contradicts our choice of $B_\al$.
\qed


\begin{thebibliography}{99}

\bibitem{browncox}  Brown, J. B.; Cox, G. V.; Classical theory of totally
imperfect spaces.  Real Anal. Exchange  7  (1981/82), no. 2, 185--232.

\bibitem{brown} Brown, Jack B.; The Ramsey sets and related sigma algebras and
ideals.  Fund. Math.  136  (1990),  no. 3, 179--185.

\bibitem{cmkm} Caserta, A.; Di Maio, G.; Ko\v cinac, Lj. D. R.;
Meccariello, E.; Applications of $k$-covers II, to appear
Topology and its applications (2006).

\bibitem{FM} Fleissner, William G.; Miller, Arnold W.; On $Q$ sets.  Proc.
Amer. Math. Soc.  78  (1980), no. 2, 280--284.

\bibitem{squareQ} Fleissner, William G.; Squares of $Q$ sets. Fund. Math. 118
(1983), no. 3, 223--231.



\bibitem{JS} Judah, Haim; Shelah, Saharon; $Q$-sets, Sierpi\'nski sets, and
rapid filters.  Proc. Amer. Math. Soc.  111  (1991),  no. 3, 821--832.

\bibitem{gm}
Galvin, Fred; Miller, Arnold W.; $\ga$-sets and other singular sets of real
numbers.  Topology Appl. 17 (1984), no. 2, 145--155.

\bibitem{gn}
Gerlits, J.; Nagy, Zs.; Some properties of $C(X)$. I. Topology
Appl. 14 (1982), no. 2, 151--161.

\bibitem{jmss}
Just, Winfried; Miller, Arnold W.; Scheepers, Marion; Szeptycki, Paul J.; The
combinatorics of open covers. II. Topology Appl. 73 (1996), no. 3, 241--266.

\bibitem{kec} Kechris, Alexander S.; {\bf Classical descriptive set theory.}
Graduate Texts in Mathematics, 156. Springer-Verlag, New York,
1995.

\bibitem{koc} Ko\v cinac, Ljubi\v sa D. R.; $\gamma$-sets, $\gamma\sb k$-sets
and hyperspaces.  Math. Balkanica (N.S.)  19  (2005),  no. 1-2, 109--118.

\bibitem{kysiak}
Kysiak, Marcin; Weiss, Tomasz; Small subsets of the reals and tree forcing
notions.  Proc. Amer. Math. Soc.  132  (2004),  no. 1, 251--259.

\bibitem{KNW} Kysiak, Marcin; Nowik, Andrzej; Weiss, Tomasz;
Special subsets of the reals and tree forcing notions, eprint 3-06.

\bibitem{laver}
Laver, Richard;
On the consistency of Borel's conjecture.
Acta Math. 137 (1976), no. 3-4, 151--169.

\bibitem{internal} Martin, D. A.; Solovay, R. M.; Internal Cohen extensions.
Ann. Math. Logic  2  1970 no. 2, 143--178.

\bibitem{borhier} Miller, Arnold W.; On the length of Borel hierarchies. Ann.
Math. Logic 16 (1979), no. 3, 233--267.

\bibitem{survey1} Miller, Arnold W.; Special subsets of the real line.
Handbook of set-theoretic topology,  201--233, North-Holland, Amsterdam, 1984.

\bibitem{fremlin}
Miller, Arnold W.; Fremlin, David H.;
On some properties of Hurewicz, Menger, and Rothberger.
Fund. Math. 129 (1988), no. 1, 17--33.

\bibitem{survey2} Miller, Arnold W.; Special sets of reals.  Set theory of the
reals (Ramat Gan, 1991),  415--431, Israel Math. Conf. Proc., 6, Bar-Ilan
Univ., Ramat Gan, 1993.

\bibitem{madq} Miller, Arnold W.; A MAD Q-set.  Fund. Math.  178  (2003),  no.
3, 271--281.

\bibitem{relanal} Miller, Arnold W.; On relatively analytic and Borel subsets.
J. Symbolic Logic 70 (2005), no. 1, 346--352.

\bibitem{rubin}
Rubin, Matatyahu;
A Boolean algebra with few subalgebras, interval Boolean algebras and retractiveness.
Trans. Amer. Math. Soc. 278 (1983), no. 1, 65--89.

\bibitem{zap2}
Zapletal, Jind\v rich; {\bf Descriptive set theory and definable
forcing},  Mem. Amer. Math. Soc.  167  (2004),  no. 793, viii+141 pp.

\bibitem{zap}
Zapletal, Jind\v rich; Proper forcing and rectangular Ramsey theorems,
eprint 11-2003. www.arxiv.org/abs/math.LO/0311135


\end{thebibliography}

\begin{flushleft}
Arnold W. Miller \\
miller@math.wisc.edu \\
http://www.math.wisc.edu/$\sim$miller\\
University of Wisconsin-Madison \\
Department of Mathematics, Van Vleck Hall \\
480 Lincoln Drive \\
Madison, Wisconsin 53706-1388 \\
\end{flushleft}

\appendix


\end{document}

