% 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\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)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 j0\; 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 $i0\; 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 i0\; 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_k0$ $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
$i0\; y_i(m)=y_n(m)\}$ and
define $C_n=C-\Union_{i0\;
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 i0\;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}