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

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

\newcommand{\qed}{\nopagebreak\par\noindent\nopagebreak$\Box$\par}
\newcommand{\rel}[1]{{\Sigma^1_1(#1)}}
\newcommand{\proj}[1]{\Sigma_1^{#1}}
\newcommand{\bor}[1]{\mbox{Borel}(#1)}
\newcommand{\bref}[1]{(\ref{#1})}
\newcommand{\cantorspace}{2^{\omega}}
\newcommand{\claim}{\par\bigskip\noindent {\bf Claim: }}
\newcommand{\elemsub}{\preceq}
\newcommand{\eq}{\approx}
\newcommand{\example}{\par\bigskip\noindent {\bf Example: }}
\newcommand{\forces}{\mid\vdash}
\newcommand{\problem}{\par\bigskip\noindent {\bf Problem: }}
\newcommand{\proof}{\par\noindent proof:\par}
\newcommand{\propsub}{\subsetneqq}
\def\cross{\times}
\def\bairespace{\omega^\omega}
\def\res{\upharpoonright}
\def\Union{\bigcup}
\def\union{\cup}
\def\Intersect{\bigcap}
\def\intersect{\cap}
\def\implies{\rightarrow}
\def\seq{\omega^{<\omega}}

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


\begin{document}

\begin{center}
  {\bf \Huge Projective subsets of \\ separable metric spaces}
  \footnote{in Annals of Pure and Applied Logic, 50(1990), 53-69.}
\end{center}

\begin{center}
  Arnold W. Miller\footnote{Partially supported by
  NSF grant 8801139}\\
\end{center}

\bigskip

\begin{center}
  Abstract
\end{center}

\begin{quote}
In this paper we will consider two possible definitions of
projective subsets of a separable metric space $X$.
A set $A\subseteq X$ is $\rel{X}$
iff there exists a complete separable metric space $Y$ and Borel set
$B\subseteq X\cross Y$ such that
 $A=\{x\in X:\exists y\in Y\;(x,y)\in B\}$.
Except for the fact that $X$ may not be completely metrizable,
this is the classical
definition of analytic set and hence has many equivalent definitions,
for example, $A$ is $\rel{X}$ iff $A$ is relatively analytic in $X$, i.e.
$A$ is the restriction to $X$ of an analytic set
in the completion of $X$.
Another definition of projective we denote by $\proj{X}$ or abstract
projective subset of $X$.
A set $A\subseteq X$ is $\proj{X}$
iff there exists an $n\in\omega$ and a Borel set
$B\subseteq X\cross X^n$ such that
 $A=\{x\in X:\exists y\in X^n\;(x,y)\in B\}$.
These sets can be far more pathological.
While the family of sets $\rel{X}$ is closed under countable intersections
and countable unions,
there is a consistent example of a separable metric space
 $X$ where $\proj{X}$ is not closed
under countable intersections or countable unions.  This takes place
in the Cohen real model.
Assuming CH there exists a separable
metric space $X$ such that every $\rel{X}$ set is Borel in X but there
exists a $\rel{X^2}$ set which is not Borel in $X^2$. The space $X^2$
has Borel subsets of arbitrarily large rank while $X$ has bounded Borel
rank.  This space is a Luzin set and the technique used here is Steel
forcing with tagged trees.  We give examples of spaces $X$ illustrating
the relationship between $\rel{X}$ and $\proj{X}$ and give some
consistent examples partially answering an abstract projective hierarchy
problem of Ulam.

\end{quote}

\newpage

\section{Equivalent definitions}

For general background about analytic sets the reader should consult
Kuratowski \cite{kur}, Rogers \cite{ro}, or Moschovakis \cite{mo}.
One notation we will
use thruout is
$$proj_X(B)=\{x\in X :\exists y\in Y\;(x,y)\in B\}$$
i.e. the projection of $B\subseteq X\cross Y$ onto $X$.
We begin by considering the notion of $\rel{X}$. This notion
corresponds to any of the following equivalent definitions.

\begin{theorem} \label{eq1}
   For $X$ a separable metric space and $A\subseteq X$ the following
   are all equivalent and denoted $\rel{X}$:
  \begin{enumerate}
    \item \label{4}
      there exists a complete separable metric space $Y$ and a Borel
      $B\subseteq X\cross Y$ such that
      $A=proj_X(B)=\{x\in X:\exists y\in Y\;(x,y)\in B\}$
    \item  \label{5} (relatively analytic)
      if $\hat{X}$ is the completion of $X$, then there exists
      $\hat{A} \subseteq \hat{X}$ a $\rel{\hat{X}}$ set such that
      $A=\hat{A} \intersect X$
    \item \label{1} (Souslin in $X$)
      there exists $\langle A_s:s\in \seq\rangle$ where each
      $A_s\subseteq X$ is closed in $X$ and
      $A=\Union_{f\in\bairespace}\intersect_{n\in\omega}A_{f\res n}$
    \item \label{2}
      there exists $\langle A_s:s\in \seq\rangle$ where each
      $A_s\subseteq X$ is Borel in $X$ and
      $A=\Union_{f\in\bairespace}\intersect_{n\in\omega}A_{f\res n}$
    \item \label{0}
      there exists a closed set
      $C\subseteq X\cross \bairespace$ such that
      $A=proj_X(C)$
    \item \label{3}
      there exists a complete separable metric space $Y$ and a closed set
      $C\subseteq X\cross Y$ such that
      $A=proj_X(C)$
    \item \label{6} (truth tables)
      there exists $T\subseteq P(\omega)$ which is $\Sigma_1^1$ and
      $\langle U_n:n\in\omega\rangle$ each $U_n\subseteq X$ Borel
      in $X$ and
      $A=\left\{x\in X:\{n\in\omega:x\in U_n\}\in T\right\}$
  \end{enumerate}
\end{theorem}
\proof
$\bref{1}\implies\bref{2}$, $\bref{0}\implies\bref{3}$, $\bref{3}\implies
\bref{4}$
 trivial.

$\bref{5}\implies\bref{1}$ Note that
by the classical theory of analytic sets in complete metric spaces
$$\hat{A} =\Union_{f\in\bairespace}\intersect_{n\in\omega}A_{f\res n}$$
where each $A_{f\res n}\subseteq Y$ is closed in $Y$.  Hence
$$A=\Union_{f\in\bairespace}\intersect_{n\in\omega}(A_{f\res n}\intersect X)$$

$\bref{1}\implies\bref{0}$
 Let
$$A=\Union_{f\in\bairespace}\intersect_{n\in\omega}A_{f\res n}$$
where each $A_{f\res n}$ is closed in $X$.
Define $C\subseteq X\cross\bairespace$ by
$$C=\Intersect_{n\in\omega}(\union_{s\in\omega^n} [s]\cross A_s)$$
Then $C$ is closed in $X\cross\bairespace$ and $A$ is the projection
onto $X$ of $C$.

$\bref{2}\implies\bref{4}$ same proof as $\bref{1}\implies\bref{0}$.

$\bref{4}\implies\bref{5}$ Let $B\subseteq X\cross Y$ be Borel.
and let
$\hat{B}\subseteq \hat{X}\cross Y$ be Borel such that
$\hat{B}\intersect(X\cross Y)=B$. Now if $\hat{A} =proj_{\hat{X}}(\hat{B})$
then $\hat{A} $ is $\rel{\hat{X}}$, and
$A=\hat{A} \intersect X$.

$\bref{2}\implies\bref{6}$ Let
$$T=\{Q\subseteq \seq:\exists f\in\bairespace\forall n\in\omega\;
f\res n\in Q\}$$
so $T\subseteq P(\seq)$, then
$$x\in\Union_{f\in\bairespace}\intersect_{n\in\omega}A_{f\res n}\mbox{ iff }
\{s\in\seq :x\in A_s\}\in T$$

$\bref{6}\implies\bref{4}$ Let $D\subseteq P(\omega)\cross \bairespace$
be Borel such that
$$T=\{y\in P(\omega):\exists z\in \bairespace\;(y,z)\in D\}$$
Then
$$Q=\{(x,y,z): (y,z)\in D\mbox{ and }\forall n(n\in y\mbox{ iff }
x\in U_n)\}$$
is Borel in $X\cross \bairespace\cross P(\omega)$ and
$$x\in A\mbox{ iff } \{n\in\omega:x\in U_n\}\in T\mbox { iff }
\exists y \exists z \; (x,y,z)\in Q$$

This completes the proof.\qed


From a more abstract point of view, for example see Ulam \cite{u},
suppose we started with arbitrary countable field of subsets of a set
$X$.  We could then form the $\sigma-$algebra of subsets of $X$ that
they generated and similarly the $\sigma-$algebra of subsets of $X\cross X$
generated by products of our original family and so on for all finite
products $X^{n}$.  Then closing under projection would give the abstract
projective sets.  Using the idea of Szpilrajn's characteristic function
of a sequence of sets (\cite{sz}) this is basically equivalent
to the following notion of $\proj{X}$ subset of $X$.
\begin{theorem}
      For $X$ a separable metric space and $A\subseteq X$ the following
      are all equivalent and denoted $\proj{X}$:
  \begin{enumerate}
    \item \label{11}
       there exists $n\in\omega$ and a Borel set $B\subseteq X\cross X^n$
       such that $A=\{x\in X:\exists y\in X^n\; (x,y)\in B\}$
    \item \label{12}
       there exists $n\in\omega$ and a Borel set $B\subseteq X\cross X^n$
       and a continuous function $f:B\mapsto X$ such that
       $f^{\prime\prime}B=A$.
    \item \label{13}
       there exists $n\in\omega$ and a Borel set $B\subseteq X\cross X^n$
       and a Borel function $f:B\mapsto X$ such that
       $f^{\prime\prime}B=A$.
  \end{enumerate}
\end{theorem}
\proof
$\bref{11}\implies\bref{12}$ since projection is continuous,
$\bref{12}\implies\bref{13}$
is trivial, and $\bref{13}\implies\bref{11}$ because the graph of $f$
is a Borel subset of $X^n\cross X$ and $f^{\prime\prime}B$ is the
projection onto $X$ of the graph of $f$.  \qed

Unlike $\rel{X}$, any of which can
be obtained by projecting a closed subset of $X\cross\bairespace$,
$\proj{X}$ may require projecting arbitrarily
high ranking Borel subsets of $X\cross X^n$.
The example of Miller~\cite{m1} (Theorem 43 p.259)
shows this.
This $X$  has the property that
there exists a $\Pi^0_{\alpha+1}$ Borel subset of $X$ which is
not the projection of any $\Sigma^0_{\alpha+1}$ set.
The argument is similar to that of the last example of Section \ref{examp}.


Note that it would be a mistake to consider a notion of projective
which would allow  arbitrary separable metric spaces
$Y$ in Theorem~\ref{eq1}$\bref{3}$,
because then every subset of $X$ would
be projective.  To see this note that if $A\subseteq X$ is arbitrary,
then $D=\{(x,y)\in X\cross A: x=y\}$ is closed in $X\cross A$ and
$A$ is the projection of $D$ onto $X$.




\section{Relationship between $\rel{X}$ and $\proj{X}$}\label{examp}


Let $\bor{X}$ be the family of Borel subsets of $X$.
Clearly, we always have $\bor{X}\subseteq\rel{X}\intersect\proj{X}$.
In this section we give some (consistent) examples
of separable metric spaces illustrating some of the possible relationships
between these three families.


\example $\bor{X}\propsub\rel{X}=\proj{X}$.

If $X$ is an uncountable
complete separable metric space, such as $\bairespace$,
then $\rel{X}=\proj{X}$ and $\bor{X}$ is a proper subset of
$\rel{X}$, i.e. $\bor{X}\propsub\rel{X}$.

\example $\bor{X}\propsub\rel{X}\propsub\proj{X}$.

For $A\subseteq\bairespace$ and $n\in\omega$ let
$$(n)A=\{y\in\bairespace:y(0)=n\mbox{ and }\exists x\in A
\forall m\;x(m)=y(m+1)\}$$
Let $A\subset\bairespace$ be a set
which is not $\rel{\bairespace}$.  Then $X=(0)A\union(1)\bairespace$.
To see that this works note that $\bor{X}\propsub\rel{X}$ because
$\bairespace$ is a clopen subspace of $X$. Also because $X$ includes
 $\bairespace$ we have $\rel{X}\subseteq\proj{X}$ (see Theorem~\ref{eq1}).
Also by Theorem~\ref{eq1} for every set of the form
$(0)B\union (1)C$ which is
$\rel{X}$ we have that $C$ is $\rel{\bairespace}$. However
$(1)A$ is $\proj{X}$, since it's the projection of
$$D=\{(x,y)\in X^2: x(0)=0,y(0)=1,\mbox{ and } \forall n>0 \; x(n)=y(n)\}$$
Consequently $\rel{X}\propsub\proj{X}$.

\bigskip

The remaining examples are all consistent examples.  The first two
use Luzin sets (see Section~\ref{prod}).

\example (CH) $\bor{X}=\rel{X}\propsub\proj{X}$

Let $Y\subset\bairespace$ be a Luzin set, so by Theorem~\ref{l1}
section~\ref{prod}
$\bor{Y}=\rel{Y}$. Let $A\subset Y$ be a set which is not $\rel{Y}$,
and let $X=(0)Y\union(1)A$. Since $X$ is a Luzin set
$\bor{X}=\rel{X}$. On the other hand $(0)A$ is $\proj{X}$, so
$\rel{X}\propsub\proj{X}$.


\example If $X$ is a generic Luzin set, then
$\bor{X}=\rel{X}=\proj{X}$.

If $X$ is countable or every subset of $X$ is Borel in $X$
(for example a Q-set), then
we have $\bor{X}=\rel{X}=\proj{X}$.  To get an $X$ of cardinality
the continuum we can use a generic Luzin set.
By a generic Luzin set we mean that $X\subset\bairespace$ is produced
by forcing with the partial order $\Bbb P$ of finite partial
functions from $\omega_1\cross\omega$ into $\omega$
over some model of ZFC $M$. Then the $\Bbb P$-generic object
is essentially a function $G:\omega_1\cross\omega\mapsto\omega$ and we let
$X=\{x_\alpha:\alpha<\omega_1\}$ where $x_{\alpha}(n)=G(\alpha,n)$.

We need only show
$\bor{X}=\proj{X}$, since by Theorem~\ref{l1}
section~\ref{prod}, we already have that $\rel{X}=\bor{X}$.
We do the argument just for the projection
of Borel subsets of $X\cross X$, since the argument for
$X\cross X^n$ is similar.
Let $B\subseteq \bairespace\cross \bairespace$
be a Borel set.  By the countable chain condition there exists
a countable set $Q\in M$ such that $B$ has a Borel code in
$M[G\res (Q\cross\omega)]$. Let $D=\{(x,x):x\in\bairespace\}$
and let $Y=\{x_\alpha:\alpha\in Q\}$ then
\begin{eqnarray*}
proj(B\intersect (X\cross X)) & = & proj(B\intersect (Y\cross X)) \\
         & &  \union \; proj(B\intersect (X\cross Y))\\
         & &  \union \; proj(B\intersect D \intersect X   ) \\
         & &  \union \; proj(  B\intersect (X-Y)^2-D   )
\end{eqnarray*}
where projection is taken onto the first coordinate.
Since $Y$ is countable and $proj(B\intersect (Y\cross X))\subseteq Y$
it is Borel. Since cross sections of Borel sets are Borel and
$proj(B\intersect (X\cross Y))$ is a countable union of cross sections,
it is Borel.  If we let $C=\{x:(x,x)\in B\}$, then $C$ is Borel and
$C\intersect X=proj(B\intersect D \intersect X )$.

So it suffices
to see that $proj(  B\intersect (X-Y)^2-D   )$ is in $\bor{X}$.
Without loss of generality we may assume that $Y=\emptyset$ and that
$B\subseteq (\bairespace\cross\bairespace)-D$ is coded in the
ground model $M$ (otherwise we could work over a new ground model $M[Y]$).

Let $\Bbb Q=\seq$ the partial order for forcing a single Cohen real
and let $[p]=\{x\in\bairespace : p\subseteq x\}$ for $p\in\Bbb Q$.
For any two distinct $x,y\in X$ we have
$x\in proj(B\intersect X)$ iff there exists $y\in X$ distinct from
$x$ such that $(x,y)\in B$. But since $(x,y)$ is $\Bbb Q\cross \Bbb Q$
generic over the ground model, we have that $(x,y)\in B$ iff
there exists $p,q\in \Bbb Q$ with $p\subset x$ and $q\subset y$ such
that $(p,q)\forces (x,y)\in B$.  But since $B$ is a Borel set coded
in the ground model  $(p,q)\forces (x,y)\in B$ iff
$([p]\cross [q])\intersect B$ is comeager in $[p]\cross [q]$,
(see  Solovay~\cite{sol}).  Note that $X$ is dense, so that
it is easy to check now that
$x\in proj(B\intersect X)$ iff  $x\in X$  and
$\exists p,q\in\Bbb Q\; x\in [p]$ and
$([p]\cross [q])\intersect B$ is comeager in $[p]\cross [q]$.
Hence the projection of $B\intersect X$ is in $\bor{X}$.

This example can also be obtained under CH using a proof
similar to that of Theorem~\ref{proda}.

\example (the set from Miller \cite{m3})
$\proj{X}\propsub\rel{X}$.

In Miller~\cite{m3} (Theorem 4 p. 177) a forcing construction is given for a
set $X^*\subset\bairespace$ with the property that every
subset of $X^*$ is $\rel{X^*}$, but not every subset of $X^*$ is in
$\bor{X^*}$. From here on we will refer to $X$ for the $X^*$ of \cite{m3}.
The argument given in \cite{m3} that not every subset of  $X$ is $\bor{X}$
generalizes
to show that the first generic Souslin set (i.e. $A\in\rel{X}$) is not
the projection of a Borel subset of $X\cross X^n$ for any $n\in\omega$.
See the last paragraph of section 3 \cite{m3}.  Suppose there exists
$p\in\Bbb Q_{\omega_2}$ and $\tau\in\cantorspace$ such that
%
\begin{equation}
p\forces ``\forall x \in X(x\in A\mbox{ iff }\exists \vec{y}\in X^n
            \;(x,\vec{y})\in B_{\tau})\mbox{''}\label{(*)}
\end{equation}
%
where $B_{\tau}\subseteq X\cross X^n$ is $\Sigma^0_\beta$ set with
code $\tau$.  Using the countable chain condition of $p\in\Bbb Q_{\omega_2}$
it is easy to obtain a countable $K\subset \omega_2$ with
$0\in K$, and an $\alpha$ with $0<\beta<\alpha<\omega_1$,
such that  $K$ and $\alpha$  also satisfies
$|p|(K,\alpha)=0$,  $|\tau|(K,\alpha)=0$, and
$$\forall \delta\in K\;\forall \gamma<\alpha \;\;
\{q\in \Bbb Q_\delta:|q|(K,\alpha)=0\}\mbox{ decides }``\gamma\in
Z_\delta\mbox{''}$$
Hence by Lemma~5 \cite{m3} $|\;|(K,\alpha)$ is a rank function with $p$ in
its domain (see \cite {m3} definition (11) p.172).  Now we use the argument
of the last paragraph on p.174 \cite{m3}. Let $\gamma>\alpha+\omega$ be
arbitrary and extend $p$ to $p_1$ by adding to $p(0)$,
$p_{\gamma}(\emptyset)=1$,
which means that
$$p_1\forces ``x_\gamma\in A\mbox{''}$$
Since $p_1$ extends $p$ by line~\bref{(*)}
$$p_1\forces ``\exists \vec{y}\in X^n
\;(x_\gamma,\vec{y})\in B_{\tau}\mbox{''}$$
 So find $\vec{y}\in X^n$
and $p_2$ extending $p_1$ so that
$$p_2\forces ``(x_\gamma,\vec{y})\in B_{\tau}\mbox{''}$$
Now since $(x_\gamma,\vec{y})$ is in the ground model we can think
of this as a $\Sigma^0_\beta$ statement about $\tau$, consequently by
Lemma 2 \cite{m3} p.173, there exists a $q\in\Bbb Q_{\omega_2}$ with
$|q|(K,\alpha)<\beta$ which is compatible with $p_2$ such that
$$q\forces ``(x_\gamma,\vec{y})\in B_{\tau}\mbox{''}$$
But now extend $q$ to $q_1$ by adding to $q(0)$ that
$q_{\gamma}(\emptyset)=0$ (this is possible because $|q|(K,\alpha)<\beta$)
but then
$$q_1\forces ``x_\gamma\notin A\mbox{ and }\exists \vec{y}\in X^n
\;(x_\gamma,\vec{y})\in B_{\tau}\mbox{''}$$
contradicting line~\bref{(*)} and the fact that $q_1$ extends $p$.




\problem  Give examples of $X$ such that
$\bor{X}=\proj{X}\propsub\rel{X}$ and
$\bor{X}\propsub\proj{X}\propsub\rel{X}$.




\section{Closure under unions and intersections}

Our first two results are simple observations.


\begin{theorem}
   For any separable metric space $X$ the family of sets
   $\rel{X}$ is closed under countable unions and intersections.
\end{theorem}
\proof
This is immediate from Theorem \ref{eq1}\bref{5} since in complete
metric spaces $\Sigma_1^1$ sets are closed under countable intersection
and union.
\qed

\begin{theorem} \label{int}
   For any separable metric space $X$ the family of subsets of
   $X$, $\proj{X}$, is closed under finite unions and intersections.
\end{theorem}
\proof
Let $A_i=proj_{X}(B_i)$ where $B_i\subseteq X\cross X^{n_i}$ is Borel
for $i=0$ or $1$.  By replacing $B_i$ with $B_i\cross X^{k_i}$
for a suitable $k_i$ we may
assume without loss of generality that $n_0=n_1$.
Then $$A_0\union A_1=proj(B_0\union B_1)$$
For intersection let $\hat{B_0}=B_0\cross X^{n_1}$ and
$$\hat{B_1}=\{(x,y,z)\in X\cross X^{n_0}\cross X^{n_1}:(x,z)\in B_0\}$$
Then
$$A_0\intersect A_1=proj_X(\hat{B_0}\intersect\hat{B_1})$$
\qed

The remainder of this section is devoted to proving the following
theorem.

\begin{theorem} \label{thm5}
   It is relatively consistent with ZFC that there exists a separable
   metric space $X$ such that $\proj{X}$ is closed under neither
   countable unions nor countable intersections.
\end{theorem}
\proof
Fix $Y\subseteq \bairespace$  a set in the ground model of cardinality
$\omega_1$
and consider the following forcing notions:
${\Bbb Q}$ is the partial order of finite
partial functions from $Y$ to $2$ and $\Bbb P$ is the
direct sum of countably many copies of $\Bbb Q$, $\Sigma_{n\in\omega}\Bbb Q$.
Of course both  $\Bbb P$ and $\Bbb Q$ are isomorphic to the usual
way of adding $\omega_1$ Cohen reals.
We view forcing with $\Bbb P$ as equivalent to adding a sequence
$\langle A_n:n\in\omega\rangle$ of generic subsets of $Y$,
i.e. if $G$ is a $\Bbb P$-generic filter, then for each $n\in\omega$
let $A_n=\{x\in Y: \exists p\in G\;\; p_n(x)=1 \}$.
For $n\in\omega$ and $A\subseteq\bairespace$ recall that
$$(n)A=\{x\in\bairespace:x(0)=n\mbox{ and }\exists y\in A\;\forall m\in\omega
\;\;x(m+1)=y(m)\}$$
The space $X$ is defined by
$$X=\Union_{n\in\omega}(2n)Y\union \Union_{n\in\omega}(2n+1)A_n$$
i.e. countably many copies of $Y$ and one of each $A_n$.

\begin{lemma}
   For each $n,m\in\omega$ the set $(2m)A_n$ is $\proj{X}$.
\end{lemma}
\proof
Let $D_{nm}\subset X\cross X$ be the appropriate diagonal, namely,
$$D_{nm}=\{(x,y)\in X\cross X: x(0)=2m,y(0)=2n+1,\forall k>0\; x(k)=y(k)\}$$
Then $D_{nm}$ is closed and $proj(D_{nm})=(2m)A_n$.
\qed
For $k<\omega$ let $B_k=(2k)(\Intersect_{n<k}A_n)$. So $B_k$ is
$\proj{X}$ by Theorem~\ref{int}. Also let
$B_k^*=B_k\union \Union\{(2n)Y:n<\omega,n\not=k\}$, then
$B_k^*$ is $\proj{X}$, since $\Union\{(2n)Y:n<\omega,n\not=k\}$ is  clopen
in $X$ and hence $\proj{X}$.  So to prove the theorem it suffices to
show $R$ is not $\proj{X}$ where $R$ is defined by:
$$R=\Union_{k\in\omega}B_k=\Intersect_{k\in\omega}B_k^*$$
Now since each $B_k$ is a clopen subset of $R$
it suffices to prove:
\begin{lemma}
   $B_{k+1}$ is not the projection of a Borel subset of $X\cross X^k$.
\end{lemma}
\proof
Suppose for contradiction that
$$B_{k+1}=(2k)(A_0\intersect\ldots\intersect A_k)=proj(B)$$
where $B\subseteq X\cross X^k$ is Borel.
Decompose $B$ as the countable union of Borel sets:
$$B=\Union_{n_1,\ldots,n_k\in\omega}C_{n_1,\ldots,n_k}$$
where each
$C_{n_1,\ldots,n_k}\subseteq (2k)Y\cross (n_1)Z_1\cross\cdots\cross (n_k)Z_k$
is Borel and each $Z_i$ is either $Y$ or some $A_j$ depending whether
$n_i$ is even or odd.   By an easy density argument we can see that
$B_{k+1}$ must be uncountable.  Hence to prove the lemma it suffices to see:

\par\noindent{\bf Claim: } Each $proj(C_{n_1,\ldots,n_k})$ is countable.

To see this note that since there are only $k$ $Z$'s but $k+1$ many
$A_j$'s in the definition of $B_{k+1}$ there must be some $j\leq k$ which
does not appear as a $Z_i$, however
$proj(C_{n_1,\ldots,n_k})\subseteq(2k)A_j$.  By the countable chain condition
there exists a countable $K\subset X$ such that the Borel code for
$C_{n_1,\ldots,n_k}$ and hence $C_{n_1,\ldots,n_k}$ itself is an
element of
$N=M[\langle A_j\res K\rangle\langle A_i:i<\omega,i\not= j\rangle]$
where $M$ is the ground model.
It follows that $proj(C_{n_1,\ldots,n_k})$ is also in $N$.
However $A_j\res(Y-K)$ is generic over $N$, so if
$proj(C_{n_1,\ldots,n_k})\intersect(2k)(Y-K)$ is infinite then
$proj(C_{n_1,\ldots,n_k})-(2k)A_j\not=\emptyset$, which would contradict
the fact that $proj(C_{n_1,\ldots,n_k})\subseteq(2k)A_j$.
This proves the Claim, Lemma, and Theorem \ref{thm5}.
\qed

This proof also shows that it is possible that
$n-\proj{X}\not=(n+1)-\proj{X}$ for all $n\in\omega$ where
$n-\proj{X}$ is the family of projections of Borel subsets of
$X\cross X^n$. Note also that for fixed $n$ the family
of $n-\proj{X}$ sets is closed under countable union but not
finite intersection.
It is also true in this example that there
exists a countable intersection of $1-\proj{X}$ sets which is not
$\proj{X}$, namely if $E_{kn}=(2n)A_k\union\Union\{(2m)Y:m<\omega, m\not=n\}$
(each of which is $1-\proj{X}$), then
$R=\intersect_{n\in\omega}\intersect_{k<n}E_{kn}$.

\problem
Can we have an example where $\proj{X}$ is closed under countable union
but not countable intersection?
Can we have an example where $\proj{X}$ is closed under countable intersection
but not countable union?
\section{Properties of Products}\label{prod}

A separable metric space $X$ is Luzin iff it is uncountable and
every meager subset of $X$ is countable.  A set is nowhere
dense iff its closure has empty interior and meager iff it is
the countable union of nowhere dense sets.  The following theorem
is well known.

\begin{theorem}\label{l1}
   If $X$ is Luzin, then every $\rel{X}$ set is Borel in $X$.
\end{theorem}
\proof
In an arbitrary topological space the Souslin operation preserves
the property of Baire (see Kuratowski~\cite{kur}).  Hence for
any $A\in\rel{X}$ (by Theorem~\ref{eq1}\bref{1}) there exists
open $U$ and meager $M$ such that $A=(U-M)\union (M-U)$.  But
since meager sets are countable, clearly $A$ is Borel.
\qed

\begin{theorem}\label{proda}
   Assume the continuum hypothesis. Then there exists a Luzin space
   $X$ such that every $\rel{X^2}$ is Borel in $X^2$.
\end{theorem}
\proof
This is true of any sufficiently generic Luzin set.  Suppose that
$M_{\alpha}\elemsub (HC,\in)$ for $\alpha<\omega_1$ is an
increasing
sequence of countable elementary substructures whose union is all
of $HC$, the hereditarily countable sets,
and $M_{\alpha}\in M_{\alpha+1}$ for each
$\alpha$.  For each $\alpha<\omega_1$
let $x_{\alpha}\in (\cantorspace\intersect M_{\alpha+1})$
be a Cohen generic real over
$M_{\alpha}$.  Then $X=\{x_\alpha:\alpha<\omega_1\}$ has the
required property.
Suppose $A\subseteq\cantorspace\cross\cantorspace$ is
$\rel{\cantorspace\cross\cantorspace}$, then since it has the property
of Baire, there exists a open $U$ and meager $M$ such that
$A=(U-M)\union(M-U)$.  Let $F$ be a meager Borel set with
$M\subseteq F$.
Suppose that $F$ is coded in $M_\alpha$, then for every
$\beta\not=\gamma>\alpha$ we have that $(x_\beta,x_\gamma)\notin F$.
To see this suppose that $\alpha<\beta<\gamma$ and note that
since $F$ is meager, for comeagerly many $x$, $F_x=\{y:(x,y)\in F\}$
is meager (by the Kuratowski-Ulam Theorem see Oxtoby \cite{o}).
Consequently $F_{x_\beta}$ which is coded in $M_\gamma$ is meager
and therefore
$x_\gamma\notin F_{x_\beta}$.
Hence
$$A\intersect\{(x_\beta,x_\gamma):\beta\not=\gamma>\alpha\}=
  U\intersect\{(x_\beta,x_\gamma):\beta\not=\gamma>\alpha\}$$
Also letting $D=\{(x,x):x\in X\}$, then since $D$ is homeomorphic
to $X$ we have that $A\intersect D$ is Borel in $X$.
Finally for all $\beta\leq\alpha$ let
$A_\beta=\{(x_\beta,x_\gamma):\gamma<\omega_1\}\intersect A$ and
$A^\beta=\{(x_\gamma,x_\beta):\gamma<\omega_1\}\intersect A$.
Each of these is Borel in $X^2$, and so $A$ is Borel in $X^2$.
\qed

This result also holds for generic Luzin sets.

\begin{theorem} \label{mainprod}
   Assume the continuum hypothesis. Then there exists a Luzin space
   $X$ such that not every $\rel{X^2}$ is Borel in $X^2$.
\end{theorem}
\proof
It suffices to construct $X,Y\subseteq \cantorspace$ Luzin sets
such that there exists $A\subseteq X\cross Y$ which is $\rel{X\cross Y}$ but
not (relatively) Borel in $X\cross Y$.  For $x,y\in\cantorspace$
let $x+y$ be pointwise addition modulo 2,
i.e. $(x+y)(n)=x(n)+y(n)\mbox{ mod }2$.
Let
$$A=\{(x,y): x+y \mbox{ is the characteristic function of a
nonwellfounded set }\}$$
More precisely let $\#:\seq\mapsto\omega$ be a fixed bijection, then
$$(x,y)\in A \mbox{ iff }
\exists f\in\bairespace\;\forall n\in\omega\;\;(x+y)(\# f\res n)=1$$
Clearly $A$ is $\rel{\cantorspace\cross\cantorspace}$.
Lemma~\ref{L1} will finish the proof of the theorem.  Let $M_{\alpha}$ be as
in the proof of Theorem~\ref{proda} and let
$\langle B_{\alpha}:\alpha<\omega_1\rangle$ list all Borel subsets
of $\cantorspace\cross\cantorspace$ with $B_\alpha$ coded in
$M_\alpha$.  Using Lemma~\ref{L1} construct $X=\{x_\alpha:\alpha<\omega_1\}$
and $Y=\{y_\alpha:\alpha<\omega_1\}$ such that
$x_\alpha$ and $y_\alpha$ are Cohen generic over $M_\alpha$ and
$(x_\alpha,y_\alpha)\in (A-B_\alpha)\union (B_\alpha-A)$.
Then $X$ and $Y$ are Luzin sets, but $A\intersect (X\cross Y)$ is not
Borel in $X\cross Y$.

\begin{lemma} \label{L1}
   Suppose that $M$ is a countable transitive model of ZFC-Power Set and
   $B\subseteq\cantorspace\cross\cantorspace$ is a Borel set coded
   in $M$, then there exists $x,y\in\cantorspace$ Cohen generic
   over $M$ such that $(x,y)\in (A-B)\union (B-A)$.
\end{lemma}
\proof
To prove this we use Steel forcing \cite{st} as explained in
Harrington \cite{h}.  Let $\Bbb Q$ be Steel forcing with tagged trees,
hence
$${\Bbb Q}=\{\langle t,h\rangle: t\subseteq\seq \mbox{ finite
subtree, } h:t\mapsto\omega_1\union\{\infty\}\mbox{ a rank function}\}$$
where rank function means that $h(\emptyset)=\infty$ and
$s\propsub r\in t\implies h(s)<h(r)$ ($\alpha<\infty<\infty$ for
$\alpha<\omega_1$).  If $G$ is $\Bbb Q$-generic over a model $M$,
then $G$ is essentially equal to $(T,H)$ where $T\subseteq\seq$
is a tree and $H:T\mapsto\omega_1\union\{\infty\}$ is a rank function.
It has the property that if $H(s)=\infty$, then $T_s$ is nonwellfounded
($T_s=\{t\in\seq: s\;\hat{ }\;t\in T\}$); and otherwise if
$H(s)\in\omega_1$, then $T_s$ is wellfounded.  Let $x\in\cantorspace$
 be Cohen generic real
over $M$ and let $G=(T,H)$ be $\Bbb Q$-generic over $M[x]$.
Let $z\in\cantorspace$ be the characteristic function of some
$T_{\langle n\rangle}\subseteq\seq$ and let $y=x+z$.

\claim $y$ is a Cohen real over $M$.

\proof
Let $\Bbb P=2^{<\omega}$ be Cohen real forcing, then iterated forcing
is the same as product forcing: ${\Bbb P}\cross {\Bbb Q}$ since
conditions are finite.  So $x$ is $\Bbb P$-generic over $M[G]$
and since $z\in M[G]$ and $y=x+z$ we have that $y$ is
$\Bbb P$-generic over $M[G]$ and hence over $M$.
\qed

Let $\langle n\rangle$ be such that $H(\langle n\rangle)=\infty$ so that
$T_{\langle n\rangle}$ is not wellfounded.

\noindent{\bf Case 1. } $\langle x,y \rangle \notin B$

Since $x+y=z$ codes a nonwellfounded tree we're done, since
$\langle x,y \rangle\in A-B$.

\noindent{\bf Case 2. } $\langle x,y \rangle \in B$

In this case we use the main property of Steel forcing.
Let $p\in G$ be a condition such that
$p\forces \langle x,y \rangle \in B$.  The
statement ``$\langle x,y \rangle \in B$'' is a Borel proposition
with code in $M[x]$ about the real $z$ since $y=x+z$. Therefore
``$\langle x,y \rangle \in B$''is equivalent
to a propositional sentence in $L_{\omega_1\omega}$ built up
from the atomic propositions ``$s\in \hat{T}$'' where
$s\in\seq$ and $\hat{T}$ is a name in the ground model for
the generic object $T$.  This propositional sentence is in $M[x]$ and has
rank less than $\omega_1^{M[x]}$.  Say it has rank $\gamma$.
Then working in $M[x]$ we can find a condition
$\overline{p}\in{\Bbb Q}$ such that
$p(\gamma)=\overline{p}(\gamma)$ (see Harrington \cite{h})
with the property $\overline{h}(\langle n\rangle)\in\omega_1$.
By the retagging lemma
$\overline{p}\forces \langle x,y \rangle \in B$.
Hence if we take $\overline{G}$ to be $\Bbb Q$-generic over $M[x]$
with $\overline{p}\in \overline{G}$, then
$\langle x,y \rangle\in B-A$.
This proves the lemma and hence the theorem. \qed

This result can also be proved for Sierpi\'{n}ski sets.   Steel forcing
has also been used effectively in Stern \cite{ster1} \cite{ster2}
\cite{ster3} \cite{ster4} and Friedman~\cite{fr}.
This proof is a slight generalization of a classical construction due
to Sierpi\'{n}ski~\cite{sier} of a Luzin set $X$ such that $X^2$ can
be mapped continuously onto $2^\omega$.  In fact we show that
this set could have been used to prove Theorem~\ref{mainprod}.

I. Rec{\l}aw has pointed out the following result.

\begin{theorem}
(Rec{\l}aw) For any separable metric space $X$ if
$X$ has bounded Borel order, then $X$ cannot be mapped continuously
onto the real line.
\end{theorem}
\proof
Theorem 12 of Bing, Bledsoe, and Mauldin \cite{bbm} says that
if $G$ is a countable family of subsets of the real line closed under
complementation and
whose $\sigma-$algebra contains all Borel subsets of the real line,
then the $\sigma-$algebra generated by $G$ contains $\omega_1$ distinct
levels.  Now suppose $f:X\mapsto\Bbb R$ is continuous, onto, and one-to-one.
Let $G$ smallest family of sets closed under complements and containing
a basis for $\Bbb R$ and the image under
$f$ of a basis for $X$.  The hierarchy generated by $G$ must
have $\omega_1$ levels and therefore the same is true for the
Borel hierarchy of $X$.
\qed

Thus Rec{\l}aw answers a question of Miller \cite{m5} negatively, since
it is impossible to map a $\sigma-$ set continuously onto the reals.
The following is proved similarly to Theorem 12 of Bing et al \cite{bbm}.

\begin{theorem}
   Suppose $G$ is a countable family of subsets of $\bairespace$
   closed under complementation and
   such that the $\sigma-$algebra generated by $G$, which we denote
   $B(G)$, contains all Borel subsets
   of $\bairespace$. Then there exists a set $X\subset\bairespace$ which is
   not in $B(G)$ but is obtained by applying the Souslin
   operation to sets in $B(G)$, i.e. there exists
   $B_s\in B(G)$ for $s\in\seq$ such that
   $X=\Union_{f\in\bairespace}\intersect_{n\in\omega} B_{f\res n}$
\end{theorem}
\proof
Denote by $S(G)$ the family of sets obtained by applying the Souslin
operation to sets in $G$.  The idea of the proof is to obtain
a universal set for $S(G)$.  Namely there exists a map
$U:\bairespace\mapsto S(G)$ which is onto and has the property that
the diagonal
$D=\{x:x\in U(x)\}$ is in $S(G)$. This will conclude the proof
since $D$ cannot be in $B(G)$, else
for some $x\in \bairespace$ we would have $U(x)=\bairespace-D$ and
hence for this $x$ we would have $x\in U(x)$ iff $x\notin U(x)$.

Let $G=\{G_n:n\in\omega\}$ and
let $\#:\seq\mapsto \omega$ be our fixed bijection.
For any $x\in\bairespace$ let $A_s^x=G_{x(\# s )}$ and let
$U(x)=\Union_{f\in\bairespace}\intersect_{n<\omega}A_{f\res n}^x$
We need to see that the diagonal $D$ is in $S(G)$.
For fixed $s\in\seq$ let $B_s=\{x:x\in G_{x(\# s )}\}$.  It is easy
to see that
$$D=\{x:x\in U(x)\}=\Union_{f\in\bairespace}
\intersect_{n\in\omega} B_{f\res n}$$
Now $B_s=\Union_{n<\omega}\{x\in\bairespace:x(\# s )=n\mbox{ and } x\in G_n\}$
since we are assuming every clopen subset of $\bairespace$ is in
$B(G)$ we have that each $B_s$ is in $B(G)$.  Since $G$ is closed under
complementation we know that $B(G)$ is the smallest family of sets containing
$G$ and closed under countable unions and countable intersections.
Two classical results of Sierpi\'{n}ski
 are that $S(S(G))=S(G)$ and
$S(G)$ is closed under countable union and countable intersection
(for a proof see Rogers and Jayne \cite{rj}). So $B(G)\subseteq S(G)$ and
$D\in S(G)$.
\qed

Note that since every uncountable complete separable metric space contains
a homeomorphic Borel copy of $\bairespace$ this result also holds
for every uncountable complete separable metric space. Just as in
Rec{\l}aw's result we have the following corollary.

\begin{corollary}
 For any separable metric space $X$ if
$X$ can be mapped continuously
onto $\bairespace$, then $\rel{X}-\bor{X}$ is nonempty.
\end{corollary}

\problem (Mauldin) Is it consistent to have a separable metric
space $X$ with bounded Borel order but not every $\rel{X}$ subset
is Borel in $X$?

\bigskip

In Theorem \ref{mainprod} the Borel order of $X^2$ is
$\omega_1$.


\section{The hierarchy of projective sets}

For $X$ a separable metric space we make the following definitions.
\begin{itemize}

\item Define $\Sigma^X_0=\Pi^X_0=\Union_{n\in\omega}\bor{X^n}$
(the set of all Borel subsets of finite products of $X$).

\item Define $A\subseteq X^m$ to be $\Pi^X_{n+1}$ iff
$X^m-A$ is $\Sigma^X_{n+1}$.

\item Define $A\subseteq X^m$ to be $\Sigma^X_{n+1}$
iff there exists a $k\in\omega$ and $B\subseteq X^m\cross X^k$ in
$\Pi^X_n$ such that
$A=proj_{X^m}(B)=\{x\in X^m:\exists y\in X^k\;(x,y)\in B\}$.

\item Define $\Delta_n^X=\Sigma^X_n\intersect\Pi^X_n$.

\end{itemize}

\begin{theorem}
   $\Delta_n^X\subseteq \Sigma^X_n\subseteq\Delta_{n+1}^X$ and
   $\Delta_n^X\subseteq \Pi^X_n\subseteq\Delta_{n+1}^X$.
\end{theorem}
\proof
Left to the reader.
\qed

\begin{theorem} \label{ord2}
   $\Delta_n^X$, $\Sigma^X_n$, and $\Pi^X_n$ are closed under
   finite unions and intersections.
\end{theorem}
\proof
Similar to the proof of Theorem~\ref{int}.
\qed

Define the projective subsets of $X$ to be the
$\Union_{n\in\omega} \Sigma^X_n$ and
define the projective order of $X$ to be the least $n<\omega$ such
that every  projective subset of $X$ is $\Sigma^X_n$.

\problem (Ulam~\cite{u}) For what $n$ does there exist a space of
projective order $n$.

\bigskip

Obviously a countable space has projective
order 0 and a complete uncountable
space has infinite projective order.

\problem Is it
consistent with ZFC that every  uncountable space has infinite projective
order?  In fact,
I do not know if it is
consistent with ZFC that every  uncountable space has projective
order greater than 0.

\begin{theorem} \label{mainthm}
   In the Cohen real model there exist subsets of $\bairespace$
   which have projective order 1 and 2.
\end{theorem}

\proof
Let $X\subset\bairespace$ be a batch of $\omega_1$ Cohen reals
and let $A\subset X$ be a Cohen generic subset with finite conditions.
Let $Y=(0)X\union (1)A$ and let $Z=(0)X\union (1)A\union (2)(X-A)$.
We will show that the projective order of $Y$ is 2 and the projective
order of $Z$ is 1.  We begin with the proof for $Y$.


An $A$-cylinder is one of the sets
$A_{in}$ where $1\leq i\leq n<\omega$ and
$A_{in}=Y^{i-1}\cross (0)A\cross Y^{n-i}$.   Let $\Sigma$
be the smallest family of sets containing
$\bor{Y^n}$ for all $n$ and all $A$-cylinders and closed
under finite union and finite intersection.  Our main lemma
is that $\Sigma=\proj{Y}$ (Lemma~\ref{mainlem}).
The next three lemmas will be used to prove the main lemma.

\begin{lemma} \label{ordlem1}
   Suppose $C\in\Sigma$ where $C\subseteq Y^n\cross Y$ and there exists
   $i$, $1\leq i\leq n$, such that for all
   $(\langle y_1,\ldots,y_n\rangle,y)\in C$ we have $y_i=y$, then
   $proj_{Y^n}(C)\in\Sigma$.
\end{lemma}
\proof
Define $p:Y^n\mapsto Y^n\cross Y$ by $p(\vec{y})=(\vec{y},y)$ where
$y=y_i$. Then $p$ is continuous, hence for any $B$ Borel we have
$p^{-1}(B)$ is Borel.  Also for $A$-cylinders:
$$p^{-1}(Y^n\cross (0)A)=Y^{i-1}\cross (0)A\cross Y^{n-i}$$
and for $j<n$:
$$p^{-1}(Y^j\cross (0)A\cross Y^{n-j})=Y^{j}\cross (0)A\cross Y^{n-j-1}$$
Hence $p^{-1}$ of elements of $\Sigma$ are elements of $\Sigma$.
But note that $proj_{Y^n}(C)=p^{-1}(C)$.
\qed

For $y\in\bairespace$ with $y(0)=0$ or $1$ define $\tilde{y}\in\bairespace$
by $\tilde{y}(0)=1-y(0)$ and for all $m>0$, $\tilde{y}(m)=y(m)$.

\begin{lemma}\label{ordlem2}
   Suppose $C\in\Sigma$ where $C\subseteq Y^n\cross Y$ and there exists
   $i$, $1\leq i\leq n$, such that for all
   $(\langle y_1,\ldots,y_n\rangle,y)\in C$ we have $y=\tilde{y_i}$,
   then    $proj_{Y^n}(C)\in\Sigma$.
\end{lemma}
\proof
Define $q:Y^n\mapsto Y^n\cross \bairespace$ by
$q(\vec{y})=(\vec{y},y)$ where $y=\tilde{y_i}$.
Note that $proj_{Y^n}(C)=q^{-1}(C)$, so it is enough to check that
preimages of Borel sets and $A$-cylinders are elements of $\Sigma$.
Let $B\subseteq Y^n\cross Y$ be Borel and let
$\hat{B}\subseteq Y^n\cross\bairespace$ be Borel such that
$B=\hat{B}\intersect ( Y^n\cross Y)$, then
%
$$q^{-1}(B)=q^{-1}(\hat{B})\intersect
         (Y^{i-1}\cross [(0)A\union (1)A] \cross Y^{n-i})$$
%
This set is the intersection of a Borel set with the union of
an $A-$cylindar and a clopen set, hence it is in $\Sigma$.
Now we consider the preimages of $A-$cylindars, $q^{-1}(A_{jn+1})$.
Suppose $1\leq j<n+1$, then
%
$$q^{-1}(Y^{j-1}\cross (0)A\cross Y^{n+1-j})=
  \{\langle y_1,\ldots,y_n\rangle :
         y_j\in (0)A \mbox { and } y_i\in (0)A\union (1)A\}$$
%
which is the union of a clopen set and an $A-$cylindar.
In case $j=n+1$:
%
$$q^{-1}(Y^{n}\cross (0)A)=Y^{i-1}\cross (1)A\cross Y^{n-i}$$
%
which is a clopen set.
So in each case the preimage is in $\Sigma$ and the lemma is proved.
\qed

\begin{lemma} \label{ordlem3}
   Suppose $1\leq j_1< j_2<\cdots <j_k\leq n+1$ ($k$ may be zero) and
   $C\subseteq Y^{n+1}$ is given by
   $$C=A_{j_1n+1}\intersect A_{j_2n+1}\intersect \cdots\intersect
    A_{j_kn+1}\intersect B$$
   \begin{itemize}
     \item $B\subseteq Y^{n+1}$ is the intersection with $Y^{n+1}$
           of a  Borel subset of $(\bairespace)^{n+1}$ coded in
           $V[X\res\Gamma, A\res \Gamma]$
           where $\Gamma$ is a countable set indexed in the ground model $V$,
     \item there exists $s\in 2^{n+1}$ such that
           $C\subset s(0)\bairespace\union\ldots\union s(n)\bairespace$,
     \item  there exists an equivalence relation $\eq$ on
            $\{0,1,\ldots,n\}$ with the property that
             for all
            $\langle y_0,\ldots,y_{n} \rangle \in C$ and
            $i,j < n+1$
            $$i\eq j\mbox{ iff } \forall m>0\; y_i(m)= y_j(m)$$
            and for all $i\not= n$, $i\not\eq n$,
      \item there exists $t\in (\Gamma\union\{*\})^{n+1}$ such that
            $t(n)=*$ and for all $i<n+1$
            $t(i)\in \Gamma$ implies $y_i=s(i)\;\hat{ }\;t(i) $ and
            $ t(i)=*$ implies $y_i\notin (s(i))\Gamma$.
   \end{itemize}
   Then $proj_{Y^n}(C)\in\Sigma$.
\end{lemma}
\proof
Define $Q\subseteq (\bairespace)^{n+1}$ to be the $G_\delta$ set
determined by the above conditions, namely $\vec{y}\in Q$ iff
for all $i,j<n+1$
$y_i(0)=s(i)$,
$i\eq j$ iff $\forall m>0\; y_i(m)= y_j(m))$,
$t(i)\in\Gamma$ implies $y_i=s(i)\;\hat{ }\;t(i)$, and
$t(i)=*$ implies $y_i\notin (s(i))\Gamma$.

Let $\Bbb P\subseteq (\seq)^{n+1}$ be the subpartial order defined by
%
$$\vec{p}\in\Bbb P\mbox{ iff }
\exists\vec{y}\in Q\;\forall i<n+1\;\;p_i\subseteq y_i$$
%
And for $\vec{p}\in\Bbb P$ define
%
$$[\vec{p}]=\{\vec{y}\in Q: \forall i<n+1\;\;p_i\subseteq y_i\}$$
%
The set of $[\vec{p}]$ form a
basis for $Q$.

Consider $V[X\res\Gamma, A\res \Gamma]$ to be the ground model.
Any $\vec{y}\in Q$ determines the filter
$\{\vec{p}:\forall i<n+1\;p_i\subseteq y_i\}$ on $\Bbb P$.
We claim that
every $\vec{y}\in Y^{n+1}\intersect Q$ is $\Bbb P$-generic over
$V[X\res\Gamma, A\res \Gamma]$.
To see this note that $\Bbb P$ is defined in $V[X\res\Gamma, A\res \Gamma]$
and the rest of $X$ and $A$ are generic over $V[X\res\Gamma, A\res \Gamma]$.

Since
%
   $$C=A_{j_1n+1}\intersect \cdots\intersect
    A_{j_kn+1}\intersect B\subseteq Y^{n+1}\intersect Q$$
%
where $B\subseteq Y^{n+1}$ is Borel and coded in the ground model
$V[X\res\Gamma, A\res \Gamma]$, by genericity we have:
%
$$\forall\vec{y}\in C \exists \vec{p}\in\Bbb P\;\;
\vec{y}\in[\vec{p}]\mbox{ and } [\vec{p}]\intersect Y^{n+1}\intersect Q
\subseteq B$$
%
Let $B=Y^{n+1}\intersect \hat{B}$ where $\hat{B}\subseteq Q$ is
an (absolute) Borel subset of the complete metric space $Q$.
Since Borel sets have the property of Baire, there
exists an open set $U\subseteq Q$ and a meager (in $Q$) Borel
set $F\subset Q$ such that $U$ and $F$ are coded in the
ground model $V[X\res\Gamma, A\res \Gamma]$ and
$(\hat{B}-U)\union (U-\hat{B})\subseteq F$.  Consequently we have
that $B=Y^{n+1}\intersect U$.  For $\vec{p}\in\Bbb P$ define
$[\vec{p}\res n]\subseteq Y^n$ by $\vec{y}\in [\vec{p}\res n]$ iff
$\forall i,j <n$,
  $p_i\subseteq y_i$,
  $y_i(0)=s(i)$,
  $(i\eq j$ iff $\forall m>0\; y_i(m)= y_j(m))$,
  $ t(i)\in\Gamma\implies y_i=s(i)\;\hat{ }\;t(i)$, and
  $ t(i)=*\implies y_i\notin (s(i))\Gamma)$.

\claim  If $j_k<n$, then
$$proj_{Y^n}(C)=A_{j_1n}\intersect\ldots\intersect A_{j_kn}\intersect
 (\Union_{[\vec{p}]\subseteq U}[\vec{p}\res n]\intersect Y^n)$$
else if $j_k=n$, then
$$proj_{Y^n}(C)=A_{j_1n}\intersect\ldots\intersect A_{j_{k-1}n}\intersect
 (\Union_{[\vec{p}]\subseteq U}[\vec{p}\res n]\intersect Y^n)$$

\proof
$\subseteq\;\;$ This is clear since $B=Y^{n+1}\intersect U$.

 $\supseteq\;\;$ Suppose $\vec{y}=\langle y_0,\ldots,y_{n-1}\rangle
\in [\vec{p}\res n]$ where $[\vec{p}]\subseteq U$. We need to show
that $\exists y_n\in Y$ such that $(\vec{y},y_n)\in C$.
Now $A_{j_kn+1}$ may or may not be $A_{nn+1}$ which would require
$y_n\in (0)A$.   But note that $t(n)=*$ so $y_n\notin (s(n))\Gamma$
and $\forall i<n$ we have $i\not\eq n$ so for all $m>0$ $y_i(m)\not=y_n(m)$.
Since $A$ is generically chosen we can always find such a $y_n$.

This concludes the proof of the Claim and
since the right hand sides are clearly in $\Sigma$ the Lemma
is proved.
\qed


Finally, we are ready to prove the main lemma:

\begin{lemma} \label{mainlem}
   $\proj{Y}=\Sigma$, i.e. the smallest family of sets containing
   $\bor{Y^n}$ for all $n$ and all $A$-cylinders and closed
   under finite union and intersection.
\end{lemma}
\proof

Recall that
 $A$-cylinders are
sets of form $A_{in}=Y^{i-1}\cross (0)A\cross Y^{n-i}$
Each  $A$-cylinder is in $\proj{Y}$ since $A_{in}=proj_{Y^n}(D_{in+1})$
where
%
$$D_{in+1}=\{(\vec{y},y)\in Y^{n+1}:y_i(0)=0,y(0)=1, \mbox{ and }\forall
m>0 \;y(m)=y_i(m)\}$$
%
Hence $\Sigma\subseteq\proj{Y}$ since each Borel set in $Y$
 and each $A$-cylinder  is in $\proj{Y}$ and $\proj{Y}$ is closed
 under finite unions and intersections (Theorem~\ref{ord2}).

To show that $\proj{Y}\subseteq\Sigma$ it is enough to show that
$\Sigma$ is closed under projection, i.e. if $C\in\Sigma$ and
$C\subseteq Y^n\cross Y$, then $proj_{Y^n}(C)\subseteq Y^n$ is in
$\Sigma$.   To this end for
$i<n$ let $C_i=\{\vec{y}\in C:\forall m>0\; y_i(m)=y_n(m)\}$ and
define $C_n=C-\Union_{i<n}C_i$.  Note that each $C_i$ for $i\leq n$
is a Borel set intersected with $C$.  Since
$proj_{Y^n}(C)=\Union_{i\leq n}proj_{Y^n}(C_i)$ it is enough to see each
$proj_{Y^n}(C_i)$ is in $\Sigma$.  The case $C_i$ for $i<n$ is handled
by Lemma~\ref{ordlem1} and \ref{ordlem2}.

So without loss of generality assume $C=C_n$, i.e.
%
\begin{equation}
\forall \vec{y}\in C\;\forall i<n\;\exists m>0\;
                          y_i(m)\not=y_n(m) \label{a}
\end{equation}
%
By normal form every set in $\Sigma$ which is contained in $Y^{n+1}$
is a finite union of sets of the form:
$A_{j_1n+1}\intersect \cdots\intersect
    A_{j_kn+1}\intersect B$ where $B$ is Borel. So we can assume
%
\begin{equation}
C=A_{j_1n+1}\intersect \cdots\intersect
                    A_{j_kn+1}\intersect B \label{b}
\end{equation}
%
where  $B\subseteq Y^{n+1}$ is the intersection with $Y^{n+1}$
of a  Borel subset of $(\bairespace)^{n+1}$ coded in
$V[X\res\Gamma, A\res \Gamma]$
where $\Gamma$ is a countable set indexed in the  model $V$.
Although we will cut $B$ down some more it will only be by
intersecting it with Borel sets
coded in the ground model  $V[X\res\Gamma, A\res \Gamma]$.
Working in this model we can write $B$ as a union
of Borel sets $B_k$ for $k<\omega$ such that for each
$B_k$:
%
\begin{equation}
\exists s\in 2^{n+1}\;\;\;
           B_k\subset s(0)\bairespace\union\ldots\union s(n)\bairespace
           \label{c}
\end{equation}
%
and there exists $t\in (\Gamma\union\{*\})^{n+1}$ such that
    $\forall\vec{y}\in B_k \;\forall i<n+1$
%
\begin{eqnarray}
     t(i)\in \Gamma &\implies& y_i=s(i)\;\hat{ }\;t(i) \label{d}\\
                    &\mbox{ and }&\nonumber \\
     t(i)=*    &\implies& y_i\notin (s(i))\Gamma  \label{e}
\end{eqnarray}
%
 and an equivalence relation $\eq$ on $\{0,1,\ldots,n\}$
 such that     $\forall\vec{y}\in B_k \forall j,i<n+1$
%
\begin{equation}\label{f}
 j\eq i\mbox{ iff }\forall m>0\;y_i(m)=y_j(m)
\end{equation}
%
Fix $B_k$ and the $t$ and $\eq$ given by lines \bref{e} and \bref{f}.
And let $C_k=C\intersect B_k$.
We claim
there exists a Borel set $H_k$ such that
$$proj_{Y^n}(C_k)=A_{j_1n}\intersect \cdots\intersect A_{j_{k^*n}}
\intersect H_k$$
where $k^*=n-1$ if $k=n$ and otherwise $k^*=k$.
The reason is that
if $t(n)\in\Gamma$, then $proj_{Y^n}(C_k)$ is the
$t(n)$ cross section of $C_k$.  Otherwise use lines \bref{a} thru
\bref{f}
to apply Lemma~\ref{ordlem3}.
Hence
\begin{eqnarray*}
proj_{Y^n}(C)&=& proj_{Y^n}\left( \Union_{k<\omega} C_k \right)=
                \Union_{k<\omega} proj_{Y^n}(C_k)\\
&=&\Union_{k<\omega}
(A_{j_1n}\intersect \cdots\intersect A_{j_{k^*n}}\intersect H_k)=
A_{j_1n}\intersect \cdots\intersect A_{j_{k^*n}}\intersect
 \Union_{k<\omega}H_k\\
\end{eqnarray*}
Since this set is in $\Sigma$ we are done.
\qed

Now we prove the Theorem.

We claim the
the projective order of $Y$ is $2$ where
$Y=(0)X\union(1)A$.  By the Lemma~\ref{mainlem}
we see that $(0)A$ is not $\Pi^{Y}_1$, hence the projective order
of $Y$ is at least $2$.  Let $\Delta$ be the smallest family containing
all Borel subsets of $Y^n$ for all $n$ and all
$A$ cylinders ($Y^i\cross (0)A\cross Y^j$), and
$(X-A)$ cylinders ($Y^i\cross (0)(X-A)\cross Y^j$), and
closed under finite union and intersection.
Note that $\Delta$ is closed under complementation and
$\Delta\subseteq \Delta^{Y}_2$.

\begin{lemma}
   $\Delta$ is closed under projection.
\end{lemma}
\proof
Similar to Lemma~\ref{mainlem}.
\qed
Hence $\Delta$ is the set of all projective subsets of $Y$ and the projective
order of $Y$ is 2.

Next we see that
$Z=(0)X\union(1)A\union (2)(X-A)$ has projective order 1. Let $\Delta_0$
be defined similarly to $\Delta$ but for $Z$, i.e.
let $\Delta_0$ be the smallest family containing
all Borel subsets of $Z^n$ for all $n$ and all
$A$-cylinders ($Z^i\cross (0)A\cross Z^j$), and
$(X-A)$-cylinders ($Z^i\cross (0)(X-A)\cross Z^j$), and
closed under finite union and intersection.
Note that $\Delta_0$ is closed under complementation and
$\Delta_0\subseteq \Delta^{Z}_1$.
\begin{lemma}
   $\Delta_0$ is closed under projection.
\end{lemma}
\proof
Similar to Lemma~\ref{mainlem}.
\qed
An easy density argument shows that
$(0)A$ is not Borel in $Z$ hence the projective order of $Z$ is exactly 1.
This ends the proof of Theorem~\ref{mainthm}.
\qed



\begin{thebibliography}{99}

\bibitem{bbm}
R.H.Bing, W.W.Bledsoe, and R.D.Mauldin,
Sets generated by rectangles, Pacific Journal of Mathematics, 51(1974),
27-36.


\bibitem{fr}
Sy Friedman, Steel Forcing and Barwise compactness,
Annals of Mathematical Logic, 22(1982), 31-46.

\bibitem{h}
Leo Harrington, Analytic determinacy and $0^{\#}$,
Journal of Symbolic Logic, 43(1978), 685-693.


\bibitem{kur}
K. Kuratowski, {\bf Topology }, vol 1, Academic Press, 1966.

\bibitem{m1}
Arnold W. Miller, On the length of Borel hierarchies,
Annals of Mathematical Logic, 16(1979), 233-267.

\bibitem{m3}
Arnold W. Miller, Generic Souslin sets,
Pacific Journal of Mathematics, 97(1981), 171-181.

\bibitem{m5}
Arnold W. 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{mo}
Yiannis Moschovakis, {\bf Descriptive Set Theory },
North-Holland, 1980.

\bibitem{o}
J.C.Oxtoby, {\bf Measure and category}, Springer-Verlag, 1971.

\bibitem{ro}
C.A.Rogers
et al, editors, {\bf Analytic Sets}, Academic Press, 1980.

\bibitem{rj}
C.A.Rogers and J.E.Jayne,
K-analytic sets, in {\bf Analytic Sets}, ed. by C. A. Rogers
et al, Academic Press, (1980), 2-175.

\bibitem{sier}
W.Sierpi\'{n}ski, Sur les produit combinatoire de deux ensembles
jouissant de la propri\'{e}t\'{e} C, Fundamenta Mathematicae,
24(1935), 48-50.

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

\bibitem{st}
John R. Steel, Forcing with tagged trees,
Annals of Mathematical Logic, 15(1978), 55-74.

\bibitem{ster1}
Jacques Stern, \'{E}valuation du rang de Borel de certains ensembles,
C.R. Acad. Sc. Paris, 286(1978), 855-857.

\bibitem{ster4}
Jacques Stern, Effective partitions of the real line into Borel
sets of bounded rank, Annals of Mathematical Logic, 18(1980), 29-60.

\bibitem{ster3}
Jacques Stern, Analytic equivalence relations and coanalytic games,
Patras Logic Symposium, North-Holland (1982), Amsterdam, 239-259.


\bibitem{ster2}
Jacques Stern, On the notion of rank in the theory of Borel sets,
unpublished.


\bibitem{sz}
E. Szpilrajn, The characteristic function of a sequence of sets and
some of its applications,
Fundamenta Mathematicae, 31(1938), 207-223.

\bibitem{u}
S. M. Ulam, {\bf Problems in Modern Mathematics},
Wiley, New York, 1964.

\end{thebibliography}

\begin{flushright}
  University of Wisconsin\\
  Department of Mathematics\\
  480 Lincoln Drive\\
  Madison, WI  53706\\
  miller@.math.wisc.edu
\end{flushright}\end{document}