
\documentclass[12pt]{article}

\def\lastrevised{June 11, 2012.}

\title{Universal sets for pointsets properly on the $n^{th}$ level of
the projective hierarchy}

\author{ Greg Hjorth\thanks{\blurb},  $\;$ Leigh Humphries, $\;$
and Arnold W. Miller }

\date{}

\def\blurb{The first author gratefully acknowledges support
  from the Australian Research Council in the form of an Australian
  Professorial Fellowship.}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{undertilde}
\usepackage{palatino}
\usepackage{mathrsfs}

\newcommand{\C}{2^\omega}
\newcommand{\D}{\mathcal{D}}
\newcommand{\G}{\mathcal{G}}
\newcommand{\LO}{\textrm{LO}}
\newcommand{\MA}{\textrm{MA}(\aleph_{1})}
\newcommand{\PNB}{\utilde{\Pi}^{1}_{1}\setminus\utilde{\Delta}^{1}_{1}}
\newcommand{\Po}{\mathbb{P}}
\newcommand{\R}{2^{\omega}}
\newcommand{\U}{\mathcal{U}}
\newcommand{\V}{\mathbb{V}}
\newcommand{\WO}{\textrm{WO}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\card}{\textrm{ card}}
\newcommand{\claimend}{\hfill \mbox{($\square$ Claim)}}
\newcommand{\conc}{^{\frown}}
\newcommand{\cu}{\mathbb{L}}
\newcommand{\dom}{\textrm{dom}}
\newcommand{\lh}{\ell h}
\newcommand{\rank}{\textrm{ rank}}
\newcommand{\res}{\!\! \upharpoonright \!}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{define}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{prop}[theorem]{Proposition}

\def\ZFC{\textrm{ZFC}}
\def\al{\alpha}
\def\bfpi{{\utilde{\Pi}^1_1}}
\def\bfsig{{\utilde{\Sigma}_1^1}}
\def\implies{\to}
\def\om{\omega}
\def\pow{{({\mathcal P}(\om)})^\om}
\def\proof{\par\noindent proof \par}
\def\qed{\par\hfill $\square$}
\def\rmand{\mbox{ and }}
\def\rmiff{\mbox{ iff }}
\def\selfconst{{\mathcal C}}
\def\sm{\setminus}
\def\stleq{\preceq^*}
\def\su{\subseteq}
\def\tleq{\preceq}
\def\zz{\mathbb Z}

\begin{document}

\maketitle

\begin{abstract}
The Axiom of Projective
Determinacy implies the existence of a universal
$\utilde{\Pi}^{1}_{n}\setminus\utilde{\Delta}^{1}_{n}$
set for every $n \geq 1$.
Assuming $\MA+\aleph_{1}=\aleph_{1}^{\cu}$ there
exists a  universal $\PNB$ set.
In ZFC  there is a universal
$\utilde{\Pi}^{0}_{\al}\setminus\utilde{\Delta}^{0}_{\al}$ set
for every $\al$.
\end{abstract}

{
\let\thefootnote\relax\footnote{
Mathematics Subject Classification 2000: 03E15 03E60.
\par $\;\;$ Keywords: Universal sets,
Projective Determancy, Wadge reducibility, Constructible
Universe, Martin's Axiom.
\par $\;\;$ Last revised \lastrevised
\par $\;\;$ Latest
version at http://www.math.wisc.edu/$\sim$miller/}
}

\section{Introduction}


It is a classical result of descriptive set theory that universal
sets exist for various natural
pointclasses\footnote{A pointclass is a collection of
pointsets and a pointset is a subset of a Polish space.}
such as
$\utilde{\Pi}^0_\al$, $\utilde{\Sigma}^0_\al$,
$\utilde{\Pi}^{1}_{n}$, and
$\utilde{\Sigma}^{1}_{n}$.


\begin{define} \label{universalset}
For $\Gamma$ a pointclass and $X$ a Polish space,
a subset $\U\su \C\times X$ is a universal set  %\emph{universal set}
for $\Gamma$ iff

(i) $\U \in \Gamma$ and

(ii) for all  $B \subseteq X\;\;\;\;$

$B\in\Gamma$ iff
there exists $x \in \C$ such that
$B = \U_{x} =_\textrm{df} \{y \;:\;  (x,y)\in \U\}.$
\end{define}


The existence of universal sets for pointclasses of
the form $\utilde{\Pi}^{1}_{n}\setminus\utilde{\Delta}^{1}_{n}$
has not been extensively investigated.
Hjorth \cite{Hjorth 96} shows that the existence of a set
universal for $\utilde{\Pi}^{1}_{1} \setminus \utilde{\Delta}^{1}_{1}$ is
independent of ZFC, answering a question of Mauldin (recalled in Miller
\cite{Miller}). In particular, Hjorth \cite{Hjorth 96} shows that the existence
of such a set follows from $\bfpi$-Determinacy, but is
inconsistent with $\V=\cu$.  See \S 33 of
Jech \cite{Jech} for an elementary discussion of games and
descriptive set theory.

In Section \ref{det} we extend this result
by showing that the Axiom of Projective Determinacy implies
that for each $n$ there is a universal
$\utilde{\Pi}^{1}_{n} \setminus \utilde{\Delta}^{1}_{n}$ set. The proof we use is quite unlike that of the original result, in that it requires only the closure properties of the $\utilde{\Pi}^{1}_{n}$ pointclasses and the determinacy hypothesis is only utilized via Wadge's Lemma. Using the same argument we
show that there are universal $\utilde{\Pi}^{0}_{\alpha} \setminus
\utilde{\Delta}^{0}_{\alpha}$ for each countable ordinal $\alpha \geq 3$.
For the Borel classes we need Borel Determinacy but that is a
Theorem of ZFC
(Martin \cite{boreldet}).


In Section \ref{MA} we show that the
existence of a Universal $\PNB$ set follows from
$\ZFC + \MA + \aleph_1=\aleph_1^L$.  This theory is equiconsistent
with $\ZFC$.  For contrast
$\bfpi$-Determinacy is a large cardinal axiom and
Projective Determinacy is a much stronger large cardinal axiom.
See Kanamori \cite{kanamori} Chapter 6 for a discussion of
determinacy and large cardinals.

For simplicity's sake, we state these results for the space
$\R$ but analogous results can be proven for any
other uncountable Polish space.

We will follow the notation that
lowercase Greek letters denote ordinals, lowercase Roman letters denote
reals, uppercase Roman letters stand for sets of reals, and
capital Greek letters stand for pointclasses (sets of sets of reals).

General background on descriptive set theory
can be found in
Kechris \cite{Kechris}, Moschovakis \cite{Moschovakis}, and Sacks \cite{Sacks}.

\section{Determinacy \label{det}}

Recall that the Axiom of Projective Determinacy (PD) states that for every
Gale-Stewart game with payoff set in the projective hierarchy, one
of players has a winning strategy.  We will use only the consequence
of this axiom that appears in Lemma \ref{harrlem}.

\begin{theorem}\label{1nTheorem}
(a) For every
$\alpha \geq 3$ there is a universal
$\utilde{\Pi}^{0}_{\alpha} \setminus \utilde{\Delta}^{0}_{\alpha}$ set.
\par\medskip (b) Assuming PD, for every $n \geq 1$ there is a universal
$\utilde{\Pi}^{1}_{n} \setminus
\utilde{\Delta}^{1}_{n}$ set.
\end{theorem}

\begin{proof}
Let $\Gamma$ be one of the classes $\utilde{\Pi}^{1}_{n}$ for
$n\geq 1$ or $\utilde{\Pi}^{0}_{\alpha}$ for $\alpha \geq 3$. Assuming
Projective Determinacy in the former case, or using Borel Determinacy in the
later, we employ the following lemma due to Harrington
(see Steel \cite{Steel}).

\begin{lemma}[Harrington]\label{harrlem}
Suppose $A,B \subseteq \R$. If $A \in \Gamma$ and
$B \in \Gamma \setminus\Delta$, then $A \leq_{1} B$. i.e.
$A$ is one-to-one Wadge reducible to
$B$. This means that there exists a one-to-one continuous map
$f: \R\rightarrow \R$ such that $f^{-1}(B)=A$.
\end{lemma}

Let $T_{0} \subseteq 2^{< \omega}$ be a perfect subtree such that the
corresponding closed set $[T_{0}]$ is nowhere dense. Define
\[T^{\ast}_{0}= \{s \in 2^{< \omega}\setminus T_{0} \;:\;  s\res n \in T_0
 \mbox{ where } \lh(s)=n+1\}.\]
These are the nodes which are just outside of $T_0$.

Take $C_{0},C_{1} \in \Gamma\setminus\Delta$ such that
$C_{0} \subseteq [T_{0}]$
and note that the following set $C$ is in $\Gamma$.
\[C = C_{0} \cup \bigcup_{s\in T^{\ast}_{0}}\{s \conc x : x \in C_{1}\}.\]

\begin{claim}
Let $P_{0}=[T_{0}]$. For every $A \in \Gamma\setminus\Delta$ there exists
continuous maps $f : P_{0} \rightarrow \R$ and $g : \R \rightarrow \R$ and a
closed set $P_{1} \subseteq \R$ such that the following five conditions are
satisfied.
\begin{enumerate}
\item $g^{-1}(C)=A$
\item $g(P_{1}) \subseteq P_{0}$
\item $f(P_{0}) \subseteq P_{1}$
\item $f(g(y))=y$ for all $y \in P_{1}$, and
\item$g(f(x))=x$ for all $x \in P_{0}$.
\end{enumerate}
\end{claim}


Before proving the claim, note that the existence of such an $f$, $g$, and
$P_{1}$ implies that $A \in \Gamma\setminus \Delta$. The set $A$ is in
$\Gamma$ since $g$ witnesses that $A \leq_{W} C$. Conditions (2)-(5)
guarantee that $f: P_{0}\rightarrow P_{1}$ is a homeomorphism with $f^{-1}
= g\upharpoonright P_{1}$. Condition (1) is equivalent to:
\[ \forall x \in \R (x \in A \iff g(x) \in C)\]
which implies
\[ \forall x \in P_{1}(x \in A \iff g(x) \in C_{0}).\]

But, since $f$ is the inverse of $g \upharpoonright P_{1}$, this implies
\[\forall y \in P_{0}(y\in C_{0} \iff f(y) \in P_{1} \cap A).\]
Since $C_{0} \not\in \Delta$ it follows that $A \not\in \Delta$.

\emph{Proof of Claim:}\\
We will define our continuous functions by means of Wadge strategies.
A Wadge strategy is a function $\sigma:2^{<\omega}\to 2^{<\omega}$ which
satisfies:
\begin{enumerate}
\item for all $s,t\in 2^{<\omega}$ if $s\subseteq t$ then
$\sigma(s)\subseteq \sigma(t)$ and
\item for all $n\in\omega$ there exists $m\in\omega$ such
that $\lh(\sigma(s))\geq n$ whenever $\lh(s)\geq m$.
\end{enumerate}

Let $f_{\sigma}:\R \rightarrow \R$ denote the continuous function
corresponding to the strategy $\sigma$, i.e.,
$f(x)=\bigcup_{n\in\omega}\sigma(x\res n)$.

Define the set $D$ to consist of the triples $(\sigma, \tau, T_{1})$ satisfying
the following conditions:
\begin{enumerate}
\item $\sigma : T_{0}\rightarrow 2^{<\omega}$ is a Wadge strategy,
\item $\tau : 2^{<\omega} \rightarrow 2^{< \omega}$ is a Wadge strategy,
\item $T_{1} \subseteq 2^{< \omega}$ is a nonempty subtree without terminal
      nodes,
\item $\sigma(T_{0})\subseteq T_{1}$,
\item $\tau(T_{1}) \subseteq T_{0}$,
\item $t\subseteq \sigma(\tau(t))$ or $\sigma(\tau(t))\subseteq t$ for all
      $t \in T_{1}$, and
\item $s \subseteq \tau(\sigma(s))$ or $\tau(\sigma(s)) \subseteq s$ for
      all $s \in T_{0}$.
\end{enumerate}
Note that $D$ is $\utilde{\Pi}^{0}_{2}$. We show that if
$A \in \Gamma \setminus \Delta$, then there exists
$(\sigma, \tau, T_{1}) \in D$ such that $f^{-1}_{\tau}(C)=A$.

By Lemma \ref{harrlem} there exists a one to one continuous map
$f: P_{0} \rightarrow \R$ such that $C_{0} = f^{-1}(A)$.
Let $P_{1} = [T_{1}]$ be the range of $f$ and let
$\sigma$ be such that $f_{\sigma}= f$. By compactness,
$f: P_{0} \rightarrow P_{1}$ is a homeomorphism. Let
$\tau : T_{1} \rightarrow T_{0}$ be a Wadge strategy
corresponding to $f^{-1}$. We extend $\tau$ to $2^{<\omega}$ as follows:
Suppose $t \in T^{\ast}_{1}$, where
$\lh(t)=n+1$. If $\tau(t\upharpoonright n) = s$, then
take any $s^{\ast}\in T_{0}^{\ast}$ extending $s$. This
is possible since $[T_{0}]$ is nowhere dense. But we
know from Wadge's Lemma that $A^{t} \leq_{W} C_{1}$ where
\[A^{t} = \{x \in \R : t\conc x \in A \}\]
Hence we can find a Wadge strategy $\tau_{t,s^{\ast}}$ which  takes $t$ to
$s^{\ast}$ and reduces $A\cap[t]$ to $C \cap [s^{\ast}]$. We use
$\tau_{t,s^{\ast}}$ to define $\tau$ for all extensions of $t$.
This proves the Claim.
\qed

We now define the universal $\Gamma \setminus \Delta$ set $W$ by sections:
\[W_{(\sigma, \tau, T_{1})} = \left\{
\begin{array}{ll}
\{x : f_{\tau}(x) \in C\} & \textrm{if } (\sigma, \tau, T_{1}) \in D \\
C & \textrm{otherwise.}
\end{array} \right.
\]

This proves the Theorem.
\qed

\end{proof}

This leaves the case $\utilde{\Pi}^{0}_{\alpha}$ for $\alpha = 1,2$.
\begin{prop}
There does not exist a closed $U \subseteq \R \times \R$
universal for non-clopen closed sets but there does exist a
${\Pi}^{0}_{1}$ set
$V \subseteq \omega^{\omega} \times \R$ universal for
non-clopen closed subsets of $\R$. There exists a
${\Pi}^{0}_{2}$ set $W \subseteq \omega^{\omega} \times\R$
universal for $\utilde{\Pi}^{0}_{2} \setminus\utilde{\Delta}^{0}_{2}$
subsets  of $\R$.
\end{prop}
\begin{proof}
$U$ cannot exist because for each $n$ there would be an $x_{n}$ with
\[U_{x_{n}} = \{y \in \R : \forall m > n \;\; y(m) = 0 \}.\]
But some subsequence of the $x_{n}$ must converge to (say) $x \in \R$, but
then $U_{x} = \R$.

$V$ can be defined as follows: Put $(T,f) \in Q$ if and only if
$T \subseteq 2^{<\omega}$ is a nonempty subtree without terminal nodes
and $f:\omega
\rightarrow 2^{<\omega}$ has the property that for every $n$ if $f(n)=s$ then
$|s|>n$, $s\res n \in T$, but $s\not\in T$. 
Note that 
$Q$ is homeomorphic to
$\omega^{\omega}$.  To see this
note that 
$$P(2^{<\om})\times (2^{<\om})^\om\approx 2^\om\times \om^\om\approx \om^\om$$
and that $Q$ is a $\Pi^0_2$ subspace of the first space
and therefor a zero dimensional Polish
space.  
Note that given any $(T,f)\in Q$ and $m$ it is easy to construct
a sequence $(T_n,f_n)\in Q$ with $T\cap 2^m=T_n\cap 2^m$,
$f_n\res m=f\res m$, and $|f_n(m)|>n$ for every $n$.  But this
sequence has no convergent subsequence.  It follows that
compact sets have empty interior.
Hence by the Alexandrov-Urysohn Theorem, $Q$ is
homeomorphic to $\om^\om$
(see Kechris \cite{Kechris} 7.7 p.37.)
Put $V_{(T,f)}=[T]$.

Define $W$ analogously to the proof of Theorem \ref{1nTheorem}. The set $D$
above is homeomorphic to $\omega^{\omega}$ by a similar argument to the
one for $Q$. (Construct a sequence of Wadge strategies to witness 
non-compactness.)
Take $P_{0}$ a perfect closed
nowhere dense set and let $C_{0} \subseteq P_{0}$ be such that
$P_{0} \setminus C_{0}$ is countable and dense in $P_{0}$.
By Hurewicz's Theorem (See
\cite{Kechris}) for any analytic $A \subseteq \R$ which is not $F_{\sigma}$
there is a perfect $P_{1}$ and a homeomorphism $f: P_{0} \rightarrow P_{1}$
which takes $C_{0}$ to $A \cap P_{1}$. For $C_{1}$ take any universal
$G_{\delta}$ set.
\end{proof}
\qed

The existence of a universal $\utilde{\Pi}^{0}_{2}\setminus
\utilde{\Delta}^{0}_{2}$ set for the case of $\R \times \R$ is unknown
to us.

\section{Martin's Axiom \label{MA}}

\begin{theorem}\label{Theorem 1}
Assume $\MA$ and $\aleph_{1}^{\cu} =\aleph_{1}$.
 Then there exists $\W \su \om^\om \times \C$
 with the properties:
\begin{enumerate}
 \item $\W \in {\Pi}^{1}_{1}$,
 \item $\forall x \in \om^\om \;\;\W_{x} \in \PNB$, and
 \item $\forall A \in \PNB \;\exists x \in \om^\om \;\;A = \W_{x}$.
\end{enumerate}
Hence $\W$ is
a universal set for $\PNB$.
\end{theorem}

We use the following standard results, details of which can be found 
in chapter 4 of
Moschovakis \cite{Moschovakis}.
Recall that $\LO$ is the set of binary predicates on $\om$ which
are linear orderings and $\WO\su\LO$ are the well-orderings.
For each countable ordinal
$\al$ the set $\WO_{<\al}$ are the elements of $\WO$
of order type less than
$\al$.
Then $\WO$ is a $\Pi^1_1$ set and the sets $\WO_{<\al}$ are Borel.


\begin{theorem}[The Boundedness Lemma]
\label{boundedness} Let $A \subseteq \WO$ be
$\utilde{\Sigma}^{1}_{1}$. Then there exists $\alpha < \aleph_{1}$
such that $A\su WO_{<\al}$.
\end{theorem}

\begin{theorem} For any $\Pi^1_1$ set $A\su\om^\om$ there is a continuous function
$f: \om^\om \rightarrow LO$ such that $f^{-1}(\WO) = A$.
\end{theorem}
We identify each such $f$ with the norm on $A$ defined by  $\phi(x)=$ order type of $f(x)$.

We also need the following Theorem.

\begin{theorem}[Kleene, Kripke-Platek] \label{kleene}
(a) The $\Pi_1^1$ predicates are closed under the quantifier
$\exists x\in \Delta^1_1(y)$, e.g.,
$\;\;\; Q(y,z)\equiv \exists x\in \Delta^1_1(y)\;P(x,y,z)$.
\par(b) The $\Delta^1_1(z)$ sets
(or hyperarithmetic in $z$ sets) can be
described from the constructible hierarchy as follows:
$$\Delta^1_1(z)=\cu_{\om_1^z}[z]\cap\C$$
where $\om_1^z$ is the first ordinal which is not the order type
of a well-ordered relation recursive in $z$.  The
countable ordinal $\om_1^z$ is also known
as Church-Kleene $\om_1$ of $z$ and the first admissible in
$z$.
\end{theorem}

Part (a) can be found in Mos\-cho\-vak\-is \cite{Moschovakis} 4D.3 p.220.
For part (b) Sacks \cite{Sacks} exercise 9.12
gives the unrelativized version as
an exercise and Barwise, Gandy, Moschovakis \cite{barwise}
3.1(b) prove it using admissible sets language.
For nonrelativized versions of (a) and (b) see Mansfield and Weit\-kamp
\cite{MW} 4.19 and 5.19.

Intuitively, the proof of Theorem \ref{Theorem 1} proceeds by  taking a
special universal ${\Pi}^{1}_{1}$ set $\U$ and identifying each
non-$\utilde{\Delta}^{1}_{1}$ section $\U_{z}$ by means of a function $f$
designed to witness the unboundedness of the norm on $\U_{z}$.
The function $f$ will be coded
by a real $a$ which we create using almost disjoint forcing
and $\MA$.
If the function $f_a$ fails to perform as
required, we fall back to a
default position, and code into the cross section
some canonical $\PNB$ set.

Next we discuss almost disjoint sets forcing.

\begin{define} Fix a recursive enumeration $(s_{n})_{n\in \omega}$
of $2^{<\omega}$.
For $b \in \C$ let $b^{\star} = \{n : s_{n} \subset b\}$.
\end{define}

\begin{lemma} Assume $\MA$. Suppose $X\su\C$ for
has size $\aleph_1$ and $B\su X$ is arbitrary.  Then
there exists $a\su\om$ such that for every $b\in X$
$$b^*\cap a \mbox{ is infinite iff } b\in B.$$
\end{lemma}

This lemma is standard and can be found in the textbooks
Kunen \cite{kunen} p.57,
Jech \cite{Jech} p.276, Fremlin \cite{fremlin} 21C,
or the handbook article Rudin \cite{rudin}.  Almost
disjoint sets forcing was originally invented for
its use in definability by Jensen and Solovay around 1968.

We use it in a way similar to
Martin-Solovay \cite{MS} who showed that assuming
$\MA+ \aleph_1=\aleph_1^\cu$ every set of
reals of cardinality $\aleph_1$ is $\bfpi$.

Given $a=(a_n\su\om:n<\om)$ define the function
$f_a:\C\to\C$ as follows:
$$f_a(b)=c \rmiff \forall n \; (c(n)=1
\Leftrightarrow b\cap a_n \mbox{ is infinite} ).$$

Note that $f_a$ is a Borel function, in fact ${\Delta}^{0}_{3}(a)$
uniformly in $a$.
Consider a set $X\su\C$ of size $\aleph_1$ and an arbitrary function
$f:X\to \C$. For each $n<\om$ let
$$B_n=\{b\in X\;:\: f(b)(n)=1\}.$$
By the Lemma there exists $a_n$
such that:
$$\forall b\in X \;(b^*\cap a_n \mbox{ is infinite iff } b\in B_n).$$
It follows that if we set $a=(a_n\su\om:n<\om)$ that
$f\res X= f_a\res X$.


To summarize:

\begin{lemma}\label{fa-lemma}
Assume $\MA$. There exists a $\Delta_3^0$ function
$$f:\pow\times \C\to \C$$ such that
for any $g:X\to\C$ an arbitrary function
with domain $X\su\C$ of size $\aleph_1$, there
exist $a\in \pow$ with $f=f_a\res X$.
\end{lemma}



\begin{lemma}\label{perfect}
There exists a $\Pi_1^1$ set $\U\su \om^\om\times 2^\om$
and a $\Pi_1^0$ set $P\su\om^\om\times 2^\om$ such that

(1) for all $x\in\om^\om$ $\;\;P_x\su 2^\om$ is a nonempty perfect
set disjoint from $\U_x$ and

(2) for any $\bfpi$ set $A\su 2^\om$ with uncountable complement
there exists $x$ with $\U_x=A$.
\end{lemma}

\proof
Let $Q\su \om^\om\times 2^\om$ be a $\Pi_1^0$ set universal
for perfect subsets of $2^\om$, i.e., every cross section is
perfect and every perfect set occurs as a cross
section.

Let $V\su \om^\om\times 2^\om$ be a $\Pi_1^1$ set universal
for $\bfpi$ sets.

Let $\U_{\langle u,v\rangle}= V_u\sm Q_v$ and
let $P_{\langle u,v\rangle}=Q_v.$

Since every uncountable $\bfsig$ set contains a perfect
set we are done.
\qed

Note that the results established until this point do not use the  hypothesis
$\aleph_{1} = \aleph_{1}^\cu$. From this point on, however, we will be assuming
both the hypotheses of Theorem \ref{Theorem 1}.

The self-constructible reals are defined by
$$\selfconst=\{x\in \C\;:\; x\in L_{\om_1^{x}}\}$$
where $\om_1^x$ is the Church-Kleene $\om_1$ of $x$.
The set $\selfconst$ is
$\Pi^1_1$ and has cardinality
$\aleph_1$ but does not contain a perfect set.
Since uncountable Borel sets contain
perfect sets, for any norm $g$ for $\selfconst$ and countable
ordinal $\al$ it must be that $g^{-1}(\WO_{<\al})$ is countable.

The self-constructible reals were studied by Guaspari, Kechris,
and Sacks, see Kechris \cite{kechris2}
\S 2.  See also Mansfield and Weitkamp \cite{MW} 6.20.

Define the (relativized) self-constructible reals:
$$C_x=\{z\in P_x\;:\; z\in L_{\om_1^{x,z}} [x]\}.$$
The set $C=\{(x,z)\;:\;z \in C_x\}$ is $\Pi^1_1$.
Each $C_x\su L[x]$
has cardinality $\aleph_1$ but contains no perfect set.
Note that the perfect set $P_x$ from Lemma \ref{perfect}
is the set of branches of tree
recursive in $x$, so the restriction $C_x\su P_x$
is harmless.

Let $\U$ be from Lemma \ref{perfect}.
Take $h,g:\om^\om\times 2^\om \to \LO$ to be recursive
continuous maps such that $h^{-1}(\WO)=\U$ and $g^{-1}(\WO)=C$.
(i.e., norms for the two sets).
As usual we use  $g_x(\cdot)=g(x,\cdot)$ and $h_x(\cdot)=g(x,\cdot)$
to denote the cross sectional functions.
Take $f_a$ from Lemma \ref{fa-lemma}.

Recall the standard prewell-ordering predicate for $\Pi^1_1$.
For $L_1$ and $L_2$ linear orders define
$L_1\tleq L_2$ iff $L_1$ can be order embedded into $L_2$, i.e.,
there exists $f:\om\to \om$ such that for all $a,b\in \om$
if $a<_{L_1} b$ then $f(a)<_{L_2} f(b)$.
The predicate $\tleq$ is $\Sigma_1^1$ as a subset of
$LO\times LO$.

\begin{center}
Definition of $\W$
\end{center}

\noindent Define $\W\su (\pow\times\om^\om)\times\C$
as follows:

\bigskip

\noindent $z\in \W_{\langle a,x\rangle}$ iff either

(a) $z\in \U_x$

or

(b) $z\in C_x$ and  $\exists w,b\in \Delta^1_1(x,z,a)$ with $w\in C_x$
and either

$\;\;\;\;\;$ (1) $g_x(w)\not\tleq h_x(f_a(w))$ or

$\;\;\;\;\;$ (2) $b\su\om$ is nonempty with no $h_x(f_a(w))$ least element.


\bigskip\noindent
We show that  $\W$ is universal for $\PNB$ via three Claims.


\begin{claim}\label{Claim 1}
$\W \in {\Pi}^{1}_{1}$.
\end{claim}
\proof
Clause (a) is $\Pi_1^1$ and
omitting all super-sub-scripts-1,  the logical form of
(b) is
$$
\Pi \wedge \exists w,b \in\Delta(x,z,a) \;
(\Pi\wedge (\neg\Sigma\vee \Delta))$$

Since the quantifier $\exists u\in \Delta^1_1(v)$ preserves
the class of $\Pi_1^1$ predicates (\ref{kleene}) we have
that $\W$ is $\Pi^1_1$.
\qed

\bigskip
Suppose that $\U_x$ is properly
$\bfpi$.  Choose $a$ so that $f_a:C_x\to \U_x$ and
$g_x(z)\tleq h_x(f_a(z))$
for every $z\in C_x$.  This is possible because
the set $C_x$ has cardinality $\aleph_1$ and because
the order types of $h_x(u)$ for $u\in \U_x$ are
unbounded.  So we may find $a$ using Lemma \ref{fa-lemma}.

We say that $a$ is good for $x$ iff

\centerline{
for all $z\in C_x\;\;$  $f_a(z)\in \U_x$ and $g_x(z)\tleq h_x(f_a(z))$.}

\begin{claim}
If $a$ is good for $x$, then $\W_{<a,x>}=\U_x$
and $\U_x$ is properly $\bfpi$.
\end{claim}
\proof
No $z$ can enter  $\W_{<a,x>}$ because of clause (b)(2) because
$w\in C_x$ implies $f_a(w)\in \U_x$ and so $h_x(f_a(w))$
is a well-ordering.  No $z$ can enter by clause (b)(1)
since it would directly contradict our choice of $f_a$.
So $\W_{<a,x>}=\U_x$.

Since $a$ is good for $x$
the norm $h_x$ is unbounded on $\U_x$
and so by the Boundedness Theorem \ref{boundedness},
$\;\;\U_x$ cannot be $\bfsig$.

\qed

\bigskip

\begin{claim}
If  $a$ is bad for $x$, then there is a countable
set $Z$ such that
$$\W_{\langle a,x\rangle}\cap P_x=C_x\sm Z.$$
\end{claim}

\proof
Since $P_x$ is disjoint from $\U_x$ and $C_x\su P_x$ no $z\in P_x$
enters $\W_{\langle a,x\rangle}$ because
of clause (a), so $\W_{\langle a,x\rangle}\cap P_x\su C_x$.
For the reverse inclusion, note that since $C_x\su P_x$, it suffices
to show that for all but countably many $z\in C_x$ that
$z\in \W_{\langle a,x\rangle}$.  The point is that for any
countable $\al$ for all but countably many $z\in C_x$
will have $\om_1^{x,z}>\al$.

\bigskip\noindent
Case 1. $f_a(w)\notin \U_x$ for some $w\in C_x$.

Since $h_x(f_a(w))$ is not a well-ordering there is a
set $b$ with no $h_x(f_a(w))$ least element.
By absoluteness such a set $b$ exists in $L[x,a,w]$.
Choose a countable ordinal $\al$ with $w\in L_\al[x]$
and $b\in L_\al[x,a]$.
Since $L_\al[x]$ is countable
for all but countably many $z\in C_x$ we have that
$\om_1^{x,z}>\al$, hence
$w,b\in\Delta^1_1(x,z,a)$ by Theorem \ref{kleene},
so $z$ is put into $\W_{\langle a,x\rangle}$ by (b)(2).

\bigskip\noindent
Case 2.  $g_x(w)\not\tleq h_x(f_a(w)$ for some $w\in C_x$.

Choose a countable ordinal $\al$ with $w\in L_\al[x]$.
Then for all but countably many $z\in C_x$ we have that $\om_1^{x,z}>\al$
and hence $w\in \Delta_1^1(x,z)$.  It follows from clause
(b)(1) that $z\in \W_{\langle a,x\rangle}$.

\bigskip
This proves the Claim.
\qed

Since $C_x$ cannot be Borel even if a countable set is
extracted, $\W_{\langle a,x\rangle}$
is properly $\bfpi$ for every $a$.  This concludes the
proof of Theorem \ref{Theorem 1}.
\qed

We do not know what the consistency strength of the
existence of a universal
$\utilde{\Pi}^{1}_{2}\sm\utilde{\Delta}^{1}_{2}$ set
is.  Perhaps a variant of the model of
Harrington \cite{harrington} could be made to work.


\begin{thebibliography}{99}

\bibitem{barwise} Barwise, K. J.; Gandy, R. O.; Moschovakis, Y. N.;
\emph{The next admissible set}.
J. Symbolic Logic 36 (1971), 108-120.

\bibitem{fremlin} Fremlin, D. H.; \emph{Consequences of Martin's
axiom.} Cambridge Tracts in Mathematics, 84. Cambridge University Press,
Cambridge, 1984.   ISBN: 0-521-25091-9.

\bibitem{harrington}
Harrington, Leo;
\emph{Long projective wellorderings.}
Ann. Math. Logic \textbf{12} (1977), no. 1, 1-24.

\bibitem{Hjorth 96} Hjorth; Greg; \emph{Universal Co-Analytic Sets}, Proceedings
of the American Mathematical Society \textbf{124} (1996), no. 12, 3867-3873.

\bibitem{Jech} Jech, T.; \emph{Set Theory}, Springer 2003.

\bibitem{kanamori} Kanamori, Akihiro; \emph{The higher
infinite. Large cardinals in set theory from their beginnings.} Perspectives in
Mathematical Logic. Springer-Verlag, Berlin, 1994. ISBN:
3-540-57071-3

\bibitem{kechris2} Kechris, Alexander S.;
\emph{The theory of countable analytical sets.}
Trans. Amer. Math. Soc. \textbf{202} (1975),  259-297.

\bibitem{Kechris} Kechris, Alexander S.; \emph{Classical Descriptive Set Theory},
Graduate Texts in Mathematics, 156. Spring-Verlag, New York, 1995.

\bibitem{kunen} Kunen, Kenneth; \emph{Set theory. An introduction to
independence proofs.} Reprint of the 1980 original. Studies in Logic and the
Foundations of Mathematics, 102. North-Holland Publishing Co., Amsterdam, 1983. 
ISBN: 0-444-86839-9

\bibitem{MW} Mansfield, R., Weitkamp, G.; \emph{Recursive Aspects of Descriptive
Set Theory}, Oxford University Press, 1985

\bibitem{MS} Martin, Donald A., Solovay, R. M., \emph{Internal Cohen Extensions},
Annals of Mathematical Logic \textbf{2} (1970), no.2 143-178

\bibitem{boreldet} Martin, Donald A.; \emph{Borel determinacy}. Ann. of Math.
(2) \textbf{102} (1975) no.2, 363-371.

\bibitem{Miller} Miller, Arnold W.; \emph{Some Interesting Problems},
\par\noindent  http://www.math.wisc.edu/~miller/res/problem.pdf.

\bibitem{Moschovakis} Moschovakis, Y.N.; \emph{Descriptive Set Theory},
North-Holland Publishing Company, Amsterdam, New York, Oxford, 1980.

\bibitem{rudin} Rudin; M.E.; \emph{Martin's Axiom}, in Handbook of mathematical
logic. Edited by Jon Barwise. With the cooperation of H. J. Keisler, K. Kunen,
Y. N. Moschovakis and A. S. Troelstra. Studies in Logic and the Foundations of
Mathematics, Vol. 90. North-Holland Publishing Co., Amsterdam-New York-Oxford,
1977. ISBN: 0-7204-2285-X

\bibitem{Sacks} Sacks, G.; \emph{Higher Recursion Theory}, Springer 1990.

\bibitem{Steel} Steel, J. R.; \emph{Analytic Sets and Borel Isomorphisms.}
Fund. Math. \textbf{108}(1980), no.2, 83-88.


\end{thebibliography}

\newpage

\begin{center}
Addresses
\end{center}

\begin{flushleft}
Greg Hjorth\footnote{Greg Hjorth died on January 13, 2011} \\
www.math.ucla.edu/$\sim$greg/ \\
Department of Mathematics \& Statistics \\
The University of Melbourne \\
Parkville, Victoria 3010 \\
Australia
\end{flushleft}

\begin{flushleft}
Leigh Humphries \\
leighh@unimelb.edu.au \\
Department of Mathematics \& Statistics \\
The University of Melbourne \\
Parkville, Victoria 3010 \\
Australia
\end{flushleft}

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

\end{document}
