\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_{}=\U_x$ and $\U_x$ is properly $\bfpi$. \end{claim} \proof No $z$ can enter $\W_{}$ 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_{}=\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}