\documentclass{report}






\usepackage{oldlfont}
 
 
 
 
 
\usepackage{amsmath, amssymb}
 
 
\input{amssymb.def}
\input{amssymb.tex}
 
 

 


% Set left margin - The default is 1 inch, so the following 
% command sets a 1.25-inch left margin.
%\setlength{\oddsidemargin}{0.25in} 

\setlength{\oddsidemargin}{0in}

% Set width of the text - What is left will be the right margin.
% In this case, right margin is 8.5in - 1.25in - 6in = 1.25in.
%\setlength{\textwidth}{6in} 

\setlength{\textwidth}{6.5in}

% Set top margin - The default is 1 inch, so the following 
% command sets a 0.75-inch top margin.
\setlength{\topmargin}{-0.25in}

% Set height of the header
\setlength{\headheight}{0.3in}

% Set vertical distance between the header and the text
\setlength{\headsep}{0.2in}

% Set height of the text
\setlength{\textheight}{9in}

% Set vertical distance between the text and the
% bottom of footer
\setlength{\footskip}{0.1in} 

%\markboth{TFA groups}{TFA groups} 

% Set the beginning of a LaTeX document
\begin{document} 



\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}
\def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}
\def\R{{\mathbb R}}
\def\V{{\mathbb V}}
\def\N{{\mathbb N}}
\def\n{{\cal N}}
\def\Q{{\mathbb Q}}
\def\Z{{\mathbb Z}} 
\def\C{{\mathbb C}} 
\def\m{{\cal M}}
\def\O{{\cal O}}
\def\e{\epsilon}
\def\h{{\hat{X}}}
\def\B{{\cal B}}
\def\n{\noindent} 
%\def\Box{\square} 
%\def\box{\square} 



% Redefine "plain" pagestyle

\makeatletter	   % `@' is now a normal "letter' for LaTeX
\renewcommand{\ps@plain}{%
     \renewcommand{\@oddhead}{\textrm{\large Coanalytic sets}\hfil\textrm{\thepage}}% 
     \renewcommand{\@evenhead}{\@oddhead}%
     \renewcommand{\@oddfoot}{}% empty footer
     \renewcommand{\@evenfoot}{\@oddfoot}}
\makeatother     % `@' is restored as a "non-letter" character


\Huge 

\bigskip 

\bigskip 

\bigskip 


\title{\Huge { INJECTIVE IMAGES OF COANALYTIC SETS 
\bigskip 
\bigskip 
\bigskip 
\bigskip 
\bigskip 
\bigskip 
}}         % Enter your title between curly braces


\bigskip 

\bigskip 

\bigskip 


\author{{\Huge Greg Hjorth}\\ \\
{\LARGE greg@math.ucla.edu}\\
\bigskip 
\bigskip 
\bigskip 
\bigskip }        % Enter your name between curly braces

\bigskip 

\bigskip 

\bigskip 






\date{
\Huge March 5, 1999\\ Berkeley}          % Enter your date or \today between curly braces

\maketitle


\vfill

\newpage 

\pagestyle{myheadings} 
\markright{\large Coanalytic sets} 

% Set to use the "plain" pagestyle
%\pagestyle{plain}

\null 

\bigskip 



\n{\Huge {\bf $\S$1. DEFINITIONS}} 

\bigskip 




\bigskip 




\bigskip

\bigskip
\bigskip

\bigskip

\bigskip

\bigskip
\bigskip

\bigskip

\n{\bf 1.1 Definition} A separable space $X$ is said to be {\it Polish} if it allows a 
complete metric.  A subset $B$ of a Polish space is {\it Borel} if it appears in 
the $\sigma$-algebra generated by the open sets. 

\newpage 

\n {\bf 1.2 Examples} 

\bigskip

(i) $\R$ in the usual topology is Polish. 

\bigskip 

\bigskip

\bigskip 

\bigskip


(ii) $\N^\N$, the space of functions with the topology of pointwise 
convergence, is Polish. 
\bigskip 

Let $B=\{f: \exists N\forall n>N(f(n+1)\geq f(n))\}$ be the set of 
all eventually increasing functions. $B$ is Borel (in fact, $F_{\sigma}=\Ubf{\Sigma}^0_2$) 
since it is a countable union of closed sets. 

\bigskip 

%(iii) Let $A$ be a countable set and 
%let Mod$(R, A)$ be the space of all countable models for a single binary relation $R$ whose 
%underlying set is $A$. We take the topology generated by subbasic open sets of the form: 
%\[\{\m:\m\models R(a_1, a_2)\},\] 
%\[\{\m:\m\models \neg R(a_1, a_2)\},\] 
%where $a_1, a_2\in A$. 

\bigskip 

%(iii) Let ${\cal L}$ be a countable language and $A$ a countable set. Let Mod$({\cal L}, A)$ be 
%the set of all models whose underlying set is $A$ equipped with the topology generated 
%by basic open sets of the form 
%\[\{\m\in {\rm Mod}({\cal L}, A):\m\models \psi(a_1, ...a_n)\}\] 
%for $\psi$ a quantifier free and $a_1, ..., a_n\in A$. 

%Then for any first order (or even ${\cal L}_{\omega_1, \omega}$) $\phi$ 
%and $\vec a\in A$ 
%\[\{\m\in {\rm Mod}({\cal L}, A):\m\models \phi(\vec a)\] 
%is Borel. 
\bigskip
\bigskip


\bigskip
\bigskip



(iii) $\Q$ in the usual topology is not Polish, since any countable Polish space 
contains an isolated point. 



\newpage 

\null 

\bigskip 
\bigskip 

\bigskip 
\bigskip 

\n{\bf 1.3 Definition} A subset of $A$ of a Polish space $X$ is {\it analytic}, or 
$\Ubf{\Sigma}^1_1$, if there is a Polish $Y$, Borel $B\subset Y$, continuous 
\[f:B\rightarrow X\] 
with $A=f[B]$ the image of $B$ under $f$. 

A subset $C\subset X$ is {\it coanalytic}, or $\Ubf{\Pi}^1_1$, if its complement 
$X\setminus C$ is analytic. 


\bigskip
\bigskip
\bigskip 

Obviously the Borel sets are included in the analytic and the coanalytic. 

 

\newpage 

\n{\bf 1.4 Examples} 

\bigskip 

(i) Let LO be the collection of all linear orderings on $\N$ with 
subbasic open sets of the 
form 
\[\{\prec\in {\rm LO}: k\prec l\}.\] 
This is Polish, and the set of linear orderings with an infinite descending chain 
is analytic but not Borel. 

\bigskip
\bigskip
\bigskip  

(ii) Let $C([0,1])$ be the continuous functions from the unit interval. 
This is a Polish space (under the topology generated by the sup norm) and the set 
of functions differentiable in the interior $(0, 1)$ is coanalytic and not Borel. 


\newpage 

\null 

\bigskip 



\n{\Huge {\bf $\S$2. CLASSICAL RESULTS}} 

\bigskip 

\bigskip 

\bigskip 

\bigskip 

\n{\bf 2.1 Definition} {\it Baire space} is the space $\N^\N$ of all functions from 
the natural numbers to the natural numbers with the topology of point wise  convergence. 
That is to say, the basic open sets have the form 
\[\{f\in\N^\N: \forall n<K (f(n) =g(n) )\}\] 
where $K\in\N$ and $g:\N\rightarrow \N$. 




\bigskip 

\bigskip 

\bigskip 

\bigskip 



\n{\bf 2.2 Theorem} (Luzin; 
Lusin-Souslin\footnote{\large Texts differ in their choice of 
attribution:  
see for instance Kechris' {\bf Classical Descriptive Set Theory}, 
Springer-Verlag Graduate Texts in Mathematics 156, New-York, 1995.}) 
A subset of a Polish space is Borel if and only if it 
is the continuous {\it injective} image of a closed subset of Baire space. 




\newpage 


\n {\bf Some remarks about the ``only if"} 

\bigskip 

\bigskip 

The proof can be thought of as a variation of the fact that any first order 
theory $T$ admits a ``Skolemization" by a universally axiomatizable theory -- 
that is to say there is a theory $T'\supset T$ all of whose axioms contain a 
single universal quantifier, and such that the reducts of $T'$ models to 
${\cal L}(T)$ are exactly the models of $T$. 

\bigskip 

\bigskip 

\bigskip 

In general there will be many models of $T'$ which expand a given model of 
$T$, and so the map is not one to one. 


\bigskip
 
\bigskip
 
\bigskip
 
But in the present situation there is a canonical well order of 
$\N$, which can be thought of as the domain of our ``models" 
in the Borel set. If we only look at models of $T'$ where the Skolem 
functions always choose the least natural number possible as a witness, 
we can reassert injectivity. 

\newpage 

 
 
\null
 
\bigskip
 
\bigskip
 


For concreteness suppose our Borel set is 
\[B=\bigcup_{n\in\N^+} C_n,\] 
where each $C_n$ is closed. Assume for notational 
convenience\footnote{\large In the 
general case we need to consider each $U_s$ being an the 
intersection of an open set and a closed set.} that the space 
is zero-dimensional and that we can find basic clopen sets 
$(U_s)_{s\in \N^{<\N}}$, where 
\[U_{\emptyset}={\rm \: whole\:\: space},\] 
\[d(U_s)\leq (lh(s))^{-1},\] 
\[U_s=\bigcup_{i\in\N}U_{s\frown i},\] 
\[i\neq j\Rightarrow U_{s\frown i}\cap U_{s\frown j}=\emptyset.\] 




\newpage  

 

 


\n Then we can let $C_B$ be the space of all triples 
\[(f, k, g)\in \N^\N\times \N\times \N^\N\] 
where 

\leftskip 1in 

\n (i) $U_{f|n}\cap C_k \neq \emptyset$ all $n$; 

\n (ii) $g(i)=0$ all $i\geq k$; 

\n (iii) at each $j<k$ we have that $g(j)$ is the least $m$ such that 
\[C_j\cap U_{f|m}=\emptyset.\] 

\leftskip 0in 

\bigskip 
\bigskip 





Since 
$\N^\N\times \N\times \N^\N$ is homeomorphic to $\N^\N$, 
we can  think of $C_B$ as a closed subset of Baire space. 
The structure of the definition implies that for each $x\in B$ there will 
be a unique $(f_x, k_x, g_x)\in C_B$ with 
\[x=\bigcap_{n\in \N} U_{f_x|n}.\] 

\newpage 

\null 

\bigskip 

\bigskip 

\bigskip 

\bigskip 



\n{\bf 2.3 Theorem} (Lusin-Souslin) Every analytic set is the continuous image of a 
closed subset of Baire space. 


\bigskip 

\bigskip 

\bigskip 
\bigskip 

\bigskip 

\bigskip 

\bigskip 

\bigskip 
\bigskip 

\bigskip 

\bigskip 

\bigskip 



\n{\bf 2.4 Theorem} (Classical) Let $D$ be a countable discrete space. 

\bigskip 

Every uncountable Borel set is the continuous injective image of the 
disjoint union of $\N^\N$ and $D$. 


\newpage 

\n{\bf Idea of the proof for $\N^\N\dot{\bigcup} D$} 

\bigskip 

\bigskip 

In light of Luzin's theorem, 
wish to show that every uncountable closed subset of $\N^\N$ is the  continuous one to one 
image of $\N^\N\dot{\bigcup} D$. 

\bigskip 

\bigskip 



Let $C\subset \N^\N$ be closed and uncountable. We can let ${\cal O}_1\subset \N^\N$ 
be a maximal open set such that $C\cap {\cal O}_1$ is countable. (Uses $\N^\N$ separable.) 

\bigskip 
\bigskip 

$C\setminus {\cal O}_1$ is without isolated 
points and it suffices to show that modulo some countable 
set it is the continuous injective image of Baire space. 

\bigskip 

{\bf FACT:} If $Y$ is Polish and $Y_0\subset Y$ is countable, then 
$Y\setminus Y_0$ is again Polish. For instance, Baire space is homeomorphic 
to $\{f\in 2^\N:\exists^\infty n(f(n)\neq 0)\}$. 

\bigskip 

Thus after subtracting off a further countable set $C_0$ we may 
assume that $C\setminus({\cal O}_1\cup C_0)$ is nowhere compact. 
Hence we have that $C\setminus({\cal O}_1\cup C_0)$ is Polish, 
zero-dimensional, no where compact, and hence homeomorphic to 
Baire space. 



\newpage 


\null 

\bigskip 



\n{\Huge {\bf $\S$3. SIERPINSKI'S QUESTION}} 

\bigskip 

\bigskip 


\bigskip 

\bigskip 



\bigskip 
\bigskip 


\bigskip 
\bigskip 



\n{\bf 3.1 Question} (Sierpinski; 1936) Is there a subset of Baire space having 
every uncountable analytic set as its continuous injective image? 

\newpage 

\null 

\bigskip 

\bigskip 


\bigskip 

\bigskip 



\bigskip 
\bigskip 


\bigskip 
\bigskip 


\bigskip 
\bigskip 


\n {\bf 3.2 Theorem} (Slaman; 1997) Yes. 




\bigskip 
\bigskip 




\newpage 

\null 

\bigskip 

\bigskip 


\bigskip 

\bigskip 



\bigskip 
\bigskip 


\bigskip 
\bigskip 


\bigskip 
\bigskip 


\bigskip 
\bigskip 


\n {\bf 3.3 Theorem} (Slaman) BUT there is no analytic set having every uncountable 
analytic set as its continuous injective image. 





\bigskip 
\bigskip 


\bigskip 
\bigskip 


Ted Slaman's proof made serious use of the axiom of choice in 
constructing the ``injectively universal set". 

This prompted the further question of whether one could obtain a 
{\it definable} example. 

\newpage 


\null 

\bigskip 



\n{\Huge {\bf $\S$4. A NEW QUESTION}} 

\bigskip 

\bigskip 


\bigskip 

\n{\bf 4.1 Definition} We inductively define the projective hierarchy, 
commencing with the $\Ubf{\Sigma}^1_1$ sets defined above. 

We say that a set is $\Ubf{\Pi}^1_n$ if it is the complement of a 
$\Ubf{\Sigma}^1_1$ set and that a set is $\Ubf{\Sigma}^1_{n+1}$ if it 
is the continuous image of a $\Ubf{\Pi}^1_n$ set. 


\bigskip 

\bigskip 

Note that \[\Ubf{\Pi}^1_n, \Ubf{\Sigma}^1_n\subset \Ubf{\Sigma}^1_{n+1}
\cap \Ubf{\Pi}^1_{n+1}.\] 

\bigskip 
\bigskip 


We let $\Ubf{\Delta}^1_n= \Ubf{\Pi}^1_n\cap\Ubf{\Sigma}^1_n$. 



\bigskip 

\bigskip 


\bigskip 

\bigskip 

\bigskip 


\bigskip 

Thus one can reasonably ask whether Slaman's theorem can be proved using say a 
projective set. 

\newpage 

\null 

\bigskip 

\n {\bf 4.2 Theorem} There is $\Ubf{\Pi}^1_1$ (that is to say coanalytic) set having 
every uncountable $\Ubf{\Sigma}^1_1$ set as its continuous injective image. 


\bigskip 

\bigskip 

\bigskip 

\bigskip 


\bigskip 


\bigskip 


\bigskip 
\bigskip 


\bigskip 

\n {\bf Idea} Let $U\subset \N\times \N^\N$ be universal (light faced) $\Sigma^1_1$, 
so that the $\Sigma^1_1$ subsets of $\N^\N$ are exactly those of the form 
\[\{x\in \N^\N: (n, x)\in U\}.\] 
For $x\in \N^\N$ let ${\cal O}^x=\{n:(n, x)\in U\}$. 
Finally let ${\cal H}=\{{\cal O}^x: x\in \N^\N\}$. 

\bigskip 

\bigskip 


Then for $D$ a countably infinite 
discrete set, ${\cal H}\dot{\bigcup} D$ succeeds.\footnote{\large In fact we 
do not need the countable set $D$, since the set of hyperjumps of 
recursive reals is an infinite, discrete, clopen subset of ${\cal H}$.}  

\newpage 


\n One uses about ${\cal H}$ that: 

\leftskip 0.4in 
\bigskip 

\n (i) it is zero dimensional; 




\bigskip 


\bigskip 

\n (ii) ${\cal H}$ is homeomorphic to $\N\times {\cal H}$;  
\bigskip 
\bigskip 


\n (iii) $\N^\N$ is the continuous injective image of ${\cal H}$ (via 
${\cal O}^x\mapsto x$); 
\bigskip 
\bigskip 


\n (iv) for any 
$A\subset \N^\N$ analytic there is relatively closed $C_A\subset {\cal H}$ having 
$A$ as its one to one continuous image. 

Namely: If \[A=\{x: (n, \langle x, z_0\rangle) \in U\},\] then we can 
take \[C_A=\{{\cal O}^{\langle x, z_0\rangle}: x\in \N^\N, n\in 
{\cal O}^{\langle x, z_0\rangle}\}.\] 

\leftskip 0in 


\newpage 


\null 

\bigskip 



\n{\Huge {\bf $\S$5. GENERALIZATIONS}} 

\bigskip 
\bigskip 

Under appropriate large cardinal or determinacy assumptions we can hope to extend 
these results to higher levels in the projective hierarchy. 


\bigskip 
\bigskip 
\bigskip 
\bigskip 
\bigskip 
\bigskip 

\n {\bf 5.1 Theorem} Assume every uncountable $\Ubf{\Pi}^1_1$ set contains a 
perfect subset.\footnote{\large A {\it 
perfect} set is an closed, non-empty set with no isolated points. 
Every perfect set contains a homeomorphic copy of Cantor space.} 
 (Equivalently: $\aleph_1$ is   inaccessible in $L[z]$ for every 
$z\subset \N$.) 

Then every uncountable $\Ubf{\Sigma}^1_2$ set is the continuous injective image of 
${\cal H}\dot{\bigcup} D$. 

\newpage 

\null   
\bigskip
\bigskip
\bigskip
\bigskip


Plainly this is not provable in ZFC alone -- 
since ${\cal H}$ contains a perfect 
set, the conclusion would imply that every 
coanalytic set contains a perfect set. 


 
 
 
\bigskip
\bigskip
\bigskip


Even in the more modest sense that there just be {\it some} 
``injectively universal $\Ubf{\Pi}^1_1$ set", no 
proof exists in ZFC, as there are generic extensions of 
$L$ where there are $\Ubf{\Pi}^1_1$ sets having cardinalities $\aleph_1$ and 
$\aleph_2$. 








 
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip


In fact the assumptions of the theorem fit the conclusion. One can show that 
if there is a $\Ubf{\Pi}^1_1$ set having every uncountable $\Ubf{\Pi}^1_1$ set as its 
continuous injective image, then 

\[\forall z\subset \N((\aleph_1)^{L[z]}<\aleph_1).\] 


\newpage 

\null 
\bigskip 
\bigskip 
\bigskip 
\bigskip 

\n {\bf 5.2 Theorem} Assume $\Ubf{\Sigma}^1_1$-determinacy. (Equivalently: 
Every subset of $\N$ has a sharp.) 

Then whenever $B$ is an uncountable $\Ubf{\Sigma}^1_2$ set and $C$ is a zero-dimensional 
$\Ubf{\Pi}^1_1$ non-Borel set, $B$ is the continuous image of $C\dot{\bigcup} D$. 


\bigskip 
\bigskip 
\bigskip 
\bigskip 
\bigskip 
\bigskip 

The main point is to play a Wadge type game to show that $C$ has a relatively 
closed subset homeomorphic to ${\cal H}$. 

\newpage 

Putting together these results with the classical theorems (Luzin etc) and the not 
so classical theorems  (Moschovakis etc) one can give a complete picture under 
projective determinacy. 

\bigskip 
\bigskip 
\bigskip\bigskip 
\bigskip 
\bigskip\bigskip 
\bigskip 
\bigskip

Class of uncountable \hfill Least projective 


set $B$       \hfill class $\Gamma$ where 

\hfill every such 

\hfill $B$ is the continuous 

\hfill injective image of some 

\hfill fixed $C\subset \N^\N$  in $\Gamma$ 



\bigskip\bigskip 
\bigskip 

\centerline{--------------------------------------------------------}


Borel (=$\Ubf{\Delta}^1_1$) \hfill closed (=$\Ubf{\Pi}^0_1$) 

\bigskip 
\bigskip 

$\Ubf{\Sigma}^1_1$, $\Ubf{\Pi}^1_1$, 
$\Ubf{\Sigma}^1_2$ \hfill $\Ubf{\Pi}^1_1$ 

\bigskip 
\bigskip 

$\Ubf{\Pi}^1_{2n}$, 
$\Ubf{\Delta}^1_{2n+1}$ ($n>0$) \hfill $\Ubf{\Pi}^1_{2n}$ 


\bigskip 
\bigskip 



$\Ubf{\Sigma}^1_{2n+1}$, $\Ubf{\Pi}^1_{2n+1}$, 
$\Ubf{\Sigma}^1_{2n+2}$ \hfill $\Ubf{\Pi}^1_{2n+1}$ 





\newpage 


\null 

\bigskip 



\n{\Huge {\bf $\S$6. SOME ``REVERSE DESCRIPTIVE SET THEORY" TYPE QUESTIONS}} 




\bigskip 
\bigskip 


\bigskip 
\bigskip 


\bigskip 
\bigskip 

\n {\bf 6.1 Question} 
Suppose that  for any uncountable 
$\Ubf{\Sigma}^1_2$ set $B$ and zero-dimensional 
$\Ubf{\Pi}^1_1$ non-Borel set $C$ we have that 
$B$ is the continuous image of $C\dot{\bigcup} D$. 

Must $\Ubf{\Sigma}^1_1$ determinacy hold? 


\bigskip 


\bigskip 
\bigskip 

This might be compared with the following theorem and question due to Leo Harrington: 








\newpage 


\null 

\bigskip 


\n {\bf 6.2 Theorem} (Harrington\footnote{\large {\it Analytic determinacy and $0^{\sharp}$,} 
{\bf Journal of  Symbolic
Logic,}  vol. 43(1978), pp. 685-693} ) 
Suppose that every $\Ubf{\Sigma}^1_1$ set $A\subset \N^\N$ is 
either Borel or complete in the sense of Wadge degrees -- that is to say, 
for any other analytic $B\subset \N^\N$ we have 
some continuous $f:\N^\N\rightarrow \N^\N$ with 
\[f^{-1}[A]=B.\] 

Then $\Ubf{\Sigma}^1_1$ determinacy. 

\bigskip 


\bigskip 
\bigskip 
\bigskip 


\bigskip 
\bigskip 

 
\bigskip
\bigskip
 
 
\bigskip
\bigskip
 

\n {\bf 6.3 Question} (Harrington) Suppose any two $\Ubf{\Sigma}^1_1$ non-Borel sets 
are Wadge comparable. Must we have 
$\Ubf{\Sigma}^1_1$ determinacy? 

\newpage 

\null 

\bigskip
\bigskip
 
 
\bigskip
\bigskip
 


\n{\bf 6.4 ``Question"} For $A, B$ countable metric spaces, set $A\prec B$ if there 
is a continuous bijection 
\[\pi: B\rightarrow A.\] 

What does $\prec$ look like? (Is anything known?) 


\bigskip
\bigskip
 
 
\bigskip
\bigskip
 
\bigskip
\bigskip
 
 
\bigskip
\bigskip
 

Remark: $\omega+1$ and $\omega+\omega+1$ (in the order topology) are 
$\prec$ incomparable. 









% Set the ending of a LaTeX document
\end{document}