
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym,hyperref}

\newtheorem{theorem}{Theorem}  
\newtheorem{corollary}[theorem]{Corollary}

\def\sectiontitle#1{\begin{center} #1 \end{center}}

\newcount\probno
\probno=1
\def\qq{\par\noindent {\bf Q \the\probno.  } \advance\probno by 1}

\def\mm{\mathcal M}
\def\graph{\mbox{graph}}
\def\bool{{\mathbb B}}
 \mathchardef\wtilde="0365
\def\al{\alpha}
\def\be{\beta}
\def\bde#1#2{\vtop{\hbox{${\bf\Delta}^{#1}_{#2}$} \kern-4pt  \hbox{\kern1pt$\wtilde$}\kern-6pt}}
\def\bpi#1#2{\vtop{\hbox{${\bf\Pi}^{#1}_{#2}$} \kern-4pt  \hbox{\kern1pt$\wtilde$}\kern-6pt}}
\def\bsi#1#2{\vtop{\hbox{${\bf\Sigma}^{#1}_{#2}$} \kern-4pt \hbox{\kern1pt$\wtilde$}\kern-6pt}}
\def\cc{{\mathfrak c}}
\def\dd{\mathfrak{d}}
\def\dense{{\cal D}}
\def\de{\delta}
\def\ff{\mathcal{F}}
\def\ga{\gamma}
\def\ka{\kappa}
\def\om{\omega}
\def\ord{{\rm ord}}
\def\pow{\mathcal{P}}
\def\reals{{\mathbb R}}
\def\res{\upharpoonright}
\def\rmand{\mbox{ and }}
\def\rmiff{\mbox{ iff }}
\def\rmor{\mbox{ or }}
\def\si{\sigma}
\def\sm{{\setminus}}
\def\starpi(#1){{\bf \Pi}^*_{#1}}
\def\starsi(#1){{\bf \Sigma}^*_{#1}}
\def\st{\;:\;} % such that
\def\su{\subseteq}


\begin{document}

\begin{center}{On the Length of Borel Hierarchies}\end{center}

\begin{flushright}
Arnold W. Miller \\
November 7, 2016
\end{flushright}

This is a survey paper on the lengths of Borel hierarchies and related hierarchies.
It consists of lecture notes of a lecture given in July 2016
at the Kurt Godel Research Center, Vienna, Austria and at the 
TOPOSYM, Prague, Czech Republic. 

Notation for the Borel hierarchy is as follows:

\medskip
$\mbox{ open }= \bsi01 = G$

\medskip$\mbox{ closed }= \bpi01 = F$

\medskip$\bsi02 = F_\si =$ countable unions of closed sets

\medskip$\bpi02 = G_\de =$ countable intersections of open sets = 
complements of $\bsi02$-sets

\medskip$\bsi0\al=\{\;\bigcup_{n<\om} A_n \;:\; A_n\in \bpi0{<\al}=\bigcup_{\be<\al}\bpi0\be\;\}$

\medskip$\bpi0\al=$ complements of $\bsi0\al$ sets 

\medskip Borel $=\bpi0{\om_1}=\bsi0{\om_1}$


\medskip In a metric space closed sets are $G_\de$, i.e.,
$\bpi01\su\bpi02$.  Similarly for $1\leq \al<\be$
 $$\bsi0\al\cup \bpi0\al\;\su\; \bsi0\be\cap \bpi0\be=^{def}\bde0\be$$

 

 
\begin{theorem}
[Lebesgue 1905] For every countable $\alpha>0$ 
  $$\bsi0\alpha( 2^\om )\not=\bpi0\alpha( 2^\om ).$$
\end{theorem}

Define $\ord(X)$ to be the least $\al$ such
that $\bsi0\al(X)=\bpi0\al(X).$  

\bigskip
Hence $\ord(2^\om)=\om_1$.
If $X$ is any topological space which contains a homeomorphic
copy of $2^\om$, then $\ord(X)=\om_1$.  More generally, if
$Y\su X$, then $\ord(Y)\leq \ord(X)$.   This is because 
$$\bsi0\al(Y)=\{A\cap Y\;:\; A\in \bsi0\al(X)\}\rmand
\bpi0\al(Y)=\{A\cap Y\;:\; A\in \bpi0\al(X)\}.$$

\medskip
If $X$ countable, then $\ord(X)\leq 2$.

\begin{theorem}
[Bing, Bledsoe, Mauldin 1974]  Suppose $(2^\om,\tau)$ 
refines the usual topology and is second countable.
 Then $\ord(2^\om,\tau)=\om_1$.
\end{theorem}

\begin{theorem}
[Rec{\l}aw 1993]
If $X$ is a second countable space
and $X$ can be mapped continuously onto any
space containing $2^\om$,
then $\ord(X)=\omega_1$.
\end{theorem}

\qq It is  consistent that for any $2\leq\be\leq\om_1$
there are $X,Y\su 2^\om$ and $f:X\to Y$ continuous,
one-to-one, and onto such that $\ord(X)=2$ and $\ord(Y)=\be$,
see Theorem \ref{shelah}.
What other pairs of orders $(\al,\be)$ are possible?

\begin{corollary}
If $X$ is separable metric space which is not zero-dimensional,
then $\ord(X)=\om_1$.
\end{corollary}

To see why, let $x_0\in X$ be any point and consider the
map $x\mapsto d(x_0,x)$.   If the image of this map contains
an interval then $\ord(X)=\om_1$.   Otherwise there are
arbitrarily small clopen balls centered at $x_0$.

If $X$ is separable, metric, and zero-dimensional, then
it is homeomorphic to a subspace of $2^\om$.   So from
now on we consider only $X$ which are subsets of $2^\om$.

Define $X\su 2^\om$ is a Luzin set iff it is uncountable and 
$X\cap M$ is countable for every
meager set $M\su 2^\om$.
\begin{theorem} [Poprougenko and Sierpi\'nski 1930]
If $X\su 2^\om$ is a Luzin set, then $\ord(X)=3$.
\end{theorem}

If $X\su 2^\om$ is a Luzin set, then for every Borel set $B$ there are
 $\bpi02$ $C$ and $\bsi02$ $D$ such that $B\cap X= (C\cup D)\cap X$.
This is because every Borel sets is open mod meager and hence relative to
$X$ open mod countable.    It cannot have order 2 because a dense $G_\de$ would
meet it in an uncountable set.    We might think of the order of $X$ as being
$2+\epsilon$, since these sets are at level one of the Hausdorff difference hierarchy.

\medskip
\qq Can we have $X\su 2^\om$ with $\ord(X)=4$ and  for every Borel set $B$ there are
 $\bpi03$  $C$ and $\bsi03$ $D$ such that $B\cap X= (C\cup D)\cap X$?   
 
 \medskip
 \qq  Same question for the $\be^{th}$ level of the Hausdorff difference hierarchy inside
 the $\bde0{\al+1}$ sets?
 
\begin{theorem} [Szpilrajn 1930]
If $X\su 2^\om$ is a Sierpi\'nski set, then the order of $X$ is $2$.
\end{theorem}
This is because every Borel set contains an $F_\si$ of the same measure.

\begin{theorem}
[Miller 1979]  The following are each consistent with ZFC:
\begin{itemize}
\item for all $\al<\om_1$ there is $X\su 2^\om$ with $\ord(X)=\al$.
\item $ord(X)=\om_1$ for all uncountable $X\su 2^\om$.
\item  $\{\al: \al_0<\al\leq\om_1\}=\{\ord(X): \mbox{ unctbl }X\su 2^\om\}$.
\end{itemize}
\end{theorem}

\qq What other sets can $\{\ord(X): \mbox{ unctbl }X\su 2^\om\}$ be?
\par $\{\al : \om\leq\al\leq\om_1\}$?  $   \;\;\;\;   $  Even ordinals?

  
\begin{theorem} [Miller 1979] For any $\al\leq\om_1$ there is
a complete ccc Boolean algebra $\bool$ which can be countably
generated in exactly $\al$ steps.
\end{theorem}
\begin{theorem} [Kunen 1979] (CH) For any $\al<\om_1$ there is
an $X\su 2^\om$ with $\ord(X)=\al$.
\end{theorem}
\begin{theorem} [Fremlin 1982] 
(MA)  For any $\al<\om_1$ there is
an $X\su 2^\om$ with $\ord(X)=\al$.
\end{theorem}

\begin{theorem} [Miller 1979a] 
For any $\al$ with $1\leq \al<\om_1$ there is a countable set 
$G_\al$ of generators of the category algebra, Borel$(2^\om)$ mod meager,
which take
exactly $\al$ steps.
\end{theorem}

Suppose  Borel$(2^\om)/I_\al$ has order $\al$.  If
$\al<\be$ and there is an $I_\al$-Luzin set, then does there exists a $I_\be$-Luzin set?
If $X$ is $I_\om$-Luzin is it the clopen sum of sets of order $<\om$?

 
 

\sectiontitle{Cohen real model and Random real model}

\begin{theorem}[Miller 1995]  \label{luzin} If there is a Luzin set of size $\ka$, then
for any $\al$ with $3\leq \al<\om_1$ there is an $X\su2^\om$
of size $\ka$ and hereditarily of order $\al$.
\end{theorem}
In the Cohen real model there is $X,Y\in [2^\om]^{\om_1}$ with hereditary order 2 and $\om_1$
respectively.  Also, every $X\in[2^\om]^{\om_2}$ has $\ord(X)\geq 3$ and contains
$Y\in [X]^{\om_2}$ with $\ord(Y)<\om_1$.
 

\begin{theorem}[Miller 1995]
In the random real model, 
for any $\al$ with $2\leq \al\leq\om_1$ there is
an $X_\al\su 2^\om$ of size $\om_1$ with $\al\leq \ord(X_\al)\leq \al+1$.
\end{theorem}

\qq Presumably, $\ord(X_\al)=\al$ but I haven't been able to prove this.
  
\newpage
\sectiontitle{Sacks real model}
\begin{theorem}[Miller 1995]
In the iterated Sacks real model 
for any $\al$ with $2\leq \al\leq\om_1$ there is
an $X\su 2^\om$ of size $\om_1$ with $ \ord(X)= \al$.
Every $X\su 2^\om$ of size $\om_2$ has order $\om_1$.
\end{theorem}
In this model there is a Luzin set of size $\om_1$. 
Also  for every $X\su 2^\om$ of size $\om_2$ there is a continuous
onto map $f:X\to 2^\om$ (Miller 1983) and hence by
(Rec{\l}aw 1993) $\ord(X)=\om_1$.  

  

\sectiontitle{What if the Axiom of Choice fails?}

\begin{theorem}[Miller 2008]
It is consistent with ZF that $\ord(2^\om)=\om_2$.
\end{theorem}
This implies that $\om_1$ has countable cofinality, so
the axiom of choice fails very badly in our model.
We also show that using Gitik's model (1980) where every
cardinal has countable cofinality,
there are models of ZF in which the Borel
hierarchy is arbitrarily long.   It cannot be ``class''  long
since then there would be a map
from the family of Borel sets onto the ordinals.

\bigskip
\qq If we change the definition of $\bsi0\al$ so that it is closed under 
countable unions, then I don't know  if the Borel hierarchy can
have length greater than $\om_1$.

\medskip
\qq Over a model of ZF can forcing with $Fin(\ka,2)$ collapse cardinals?

\bigskip
 No, see Klausner and Goldstern 2016 \cite{klausner}.

\bigskip\noindent

\sectiontitle{The 
$\om_1$-Borel hierarchy of subsets of $2^\om$}

\begin{itemize}
\item $\starsi(0)=\starpi(0)=$ clopen subsets of $2^\om$
\item $\starsi(\al)=\{\cup_{\be<\om_1}A_\be\st (A_\be:\be<\om_1)\in
(\cup_{\be<\al}\starpi(\be))^{\om_1}\}$
\item $\starpi(\al)=\{2^\om\sm A \st A\in \starsi(\al)\}$
\end{itemize}

CH $\to$ $\starpi(2)=\starsi(2)=\pow(2^\om)$

\begin{theorem} [Miller 2011] 
(MA+notCH)  $\;\;\;\;\starpi(\al)\neq\starsi(\al)$ for every positive $\al<\om_2$.
\end{theorem}

\qq  This result generalizes: (MA) if $\ka<\cc$ then
the $\ka$-Borel hierarchy has length $\ka^+$.   
What about the $<\cc$-Borel hierarchy for $\cc$ weakly inaccessible?

\begin{theorem} [Miller 2011] 
In the Cohen real model 
$\starsi(\om_1+1)=\starpi(\om_1+1)$ and 
$\starsi(\al)\neq\starpi(\al)$
for every $\al<\om_1$.
\end{theorem}

\qq I don't know if $\starsi(\om_1)=\starpi(\om_1)$ holds in the Cohen real model.
  
\medskip
\qq (Brendle, Larson, Todorcevic 2008) Is it consistent with
notCH to have $\starpi(2)=\starsi(2)$?

\medskip
If notCH, then $\pow(2^\om)\neq \starsi(2)$;
consider a Bernstein set.

\begin{theorem}[Steprans 1982]  It is
consistent that
$\starpi(3)=\starsi(3)=\pow(2^\om)$ and $\starpi(2)\neq\starsi(2)$.
\end{theorem}
\begin{theorem} [Carlson 1982]
If every subset of $2^\om$ is $\om_1$-Borel, then the cofinality
of the continuum must be $\om_1$.
\end{theorem}

\begin{theorem} [Miller 2012]
(1) If $\pow(2^\om)=\om_1$-Borel, then $\pow(2^\om)=\starsi(\al)$
for some $\al<\om_2$.  

(2) For each $\al\leq\om_1$ it is consistent
that $\starsi(\al+1)=\pow(2^\om)$ and 
$\starsi(<\al)\neq \pow(2^\om)$, i.e. length $\al$ or $\al+1$.
\end{theorem}

\qq  Can the $\om_1$- Borel hierarchy have length $\al$ for some $\al$ with $\om_1<\al<\om_2$?

  \bigskip
Define
$X\su 2^\om$ is a $Q_\al$-set iff $\ord(X)=\al$ and ${\rm Borel}(X)=\pow(X)$.
$Q$-set is the same as $Q_2$-set.

\begin{theorem}[Fleissner, Miller 1980]  \label{fm}
It is consistent to have  $X\su 2^\om$, an uncountable $Q$-set,
which is concentrated on $E=\{x\in 2^\om \;:\;\forall^{\infty} n \;\;x(n)=0\}$.
\par\noindent Hence $X\cup E$ is a $Q_3$-set.
\end{theorem}

Concentrated means that $X\sm U$ is countable for any open $U\supseteq E$.  
Hence the order of $X\cup E$ is $2+\epsilon$.  
It is also consistent to have a concentrated set with $\ord(X)=\om_1$.

\begin{theorem}
[Miller 2014] (CH) For any $\al$ with 
$3\leq \al<\om_1$ there are $X_0,X_1\su 2^\om$ with
$\ord(X_0)=\al=\ord(X_1)$ and $\ord(X_0\cup X_1)=\al+1$.
\end{theorem}

\qq Is it consistent that the $X_i$ be  $Q_\al$-sets?

\qq What about getting $\ord(X_0\cup X_1)\geq\al+2$?  


   
\begin{theorem}[Judah and Shelah 1991]  \label{shelah} It is consistent to have a  $Q$-set 
and ${\dd}=\om_1$ using an iteration of proper forcings with the Sacks property.
\end{theorem}
\qq What about a $Q_\al$-set for $\al>2$?

\bigskip
In this model for any $\al$ with $2<\al\leq\om_1$ there are $X,Z\su 2^\om$ with
$\ord(X)=\al$ , $\ord(Z)=2$, and a continuous one-to-one map $f:Z\to X$. 
The Sacks property implies that the cofinality of the meager ideal is $\om_1$,
i.e., there is a family of  meager sets $\mm$ with  $|\mm|=\om_1$ such that
for every meager set $X$ there is $Y\in\mm$ with $X\su Y$.   It follows that
there is a Luzin set $X$ of size $\om_1$.  Hence by Theorem \ref{luzin} 
for any $\al$ with $2<\al<\om_1$ there
is a set $X_\al$ of size $\om_1$ with $\ord(X_\al)=\om_1$.   If we put $X_{\om_1}=\bigcup_{\al<\om_1}X_\al$,  
then $\ord(X_{\om_1})=\om_1$.

Now let $Y=\{y_\be:\be<\om_1\}$
be the $Q$-set and let $X_\al=\{x_\be:\be<\om_1\}$.    Put $Z=\{(x_\be,y_\be):\be<\om_1\}$.
Then $\ord(Z)=2$ and the projection map from $Z$ to $X_\al$ is one-to-one and continuous.



 
\begin{theorem}[Miller 2003] It is consistent to have a  $Q$-set $X\su [\om]^\om$
which is a maximal almost disjoint family.
\end{theorem}

\qq
It is consistent to have Q-set  $\{x_\al:\al<\om_1\}$ 
and 
 a non Q-set $\{y_\al:\al<\om_1\}$
such that $x_\al=^*y_\al$ all $\al$.   
Can  such an $\{x_\al:\al<\om_1\}$ be MAD?


\sectiontitle{Products of $Q$-sets}

\begin{theorem}[Brendle 2016] \label{brend}
It is consistent to have a  $Q$-set $X$
such that $X^2$ is not a $Q$-set.
\end{theorem}
In this theorem $\ord(X^2)=3$, in fact,  there is a subset $\Delta\su X^2$ such
that $\Delta\neq A\cap X^2$  for any $\bde03$ set $A\su (2^\om)^2$, i.e., the
order of $X^2$ is not $2+\epsilon$.
To see this let $\Delta=\{(x_\al,x_\be)\;:\;\al<\be<\om_1\}$.

Define $\Delta\su^*A$ iff $\exists \ga_0<\om_1\;\forall \al,\be\; (\ga_0<\al<\be<\om_1) \to (\al,\be)\in A$
and  similarly define $\overline{\Delta}\su^*A$ iff $\exists \ga_0<\om_1\;\forall \al,\be\;(\ga_0<\be<\al<\om_1)
 \to (\al,\be)\in A$.
 
 Brendle shows that for his $Q$-set that for any $G_\de$ set $A\su (2^\om)^2$
 that $\Delta\su^*A$ iff $\overline{\Delta}\su^*A$.   Now consider any $A\su (2^\om)^2$ which is
 $\bde03$.    The Hausdorff difference hierarchy Theorem implies that there are
 $G_\de$ sets $(G_\al:\al<\lambda)$ for some limit $\lambda<\om_1$ such that
 \begin{enumerate}
\item $\al<\be<\lambda$ implies $G_\be\su G_\al$,
\item $G_\gamma=\bigcap_{\al<\gamma}$ for limit $\gamma<\lambda$, and
\item $A=\bigcup \{G_\al\sm G_{\al+1}\;:\; \al$ even $<\lambda\}$.
 \end{enumerate}
 Suppose $\Delta=A\cap X^2$.  
 Let $\Sigma=\{\al<\lambda\;:\;\Delta\su^*G_\al$ and $\al$ even$\}$. 
 Since $A\su G_0$ it follows that $0\in \Sigma$.
 Let $\be=\sup(\Sigma)$.  Then $\be\in\Sigma$ or $\be=\lambda$ by condition (2).
We claim that $\be=\lambda$.    Assume not.
 Since $\Delta\su^*G_\be$ we have that $\overline{\Delta}\su^*G_\be$.
 But since $\be$ is even, $\overline{\Delta}$ is disjoint from $G_\be\sm G_{\be+1}$ which
 is a subset of $A$.  It follows that $\overline{\Delta}\su^* G_{\be+1}$ and so
 $\Delta\su^* G_{\be+1}$.   But $G_{\be+1}\sm G_{\be+2}$ is disjoint
 from $\Delta$, hence $\be+2\in\Sigma$ which contradicts $\be=\sup(\Sigma)$.
 
 So $\be=\lambda$.    But this implies $\Delta\su^*\bigcap_{\al<\lambda} G_\al$ and
 hence is disjoint from $A$, contradiction.
 

\begin{theorem}[Miller] 
 (1) If $X^2$  $Q_\al$-set and $|X|=\om_1$, then $X^n$ is a $Q_\al$-set
for all $n$.
\par (2)  If $X^3$  $Q_\al$-set and $|X|=\om_2$, then $X^n$ is a $Q_\al$-set
for all $n$.
\par (3) If $|X_i|< \om_n$, $\prod_{i\in K}X_i$ a $Q_\al$-set for every
$K\in [N]^{n}$, then $\prod_{i\in N}X_i$ is a $Q_\al$-set.
\end{theorem}

(1) Suppose $X=\{x_\al\in 2^\om\;:\; \al<\om_1 \}$.
Let $$\Delta_3=\{(x_\al,x_\be,x_\ga)\;:\; \al,\be\leq\ga\}.$$
Choose $F_n:\om_1\to\om_1^2$ so that for each $\ga<\om_1$
$\;\;\;(\ga+1)^2=\{F_n(\ga)\;:\;n<\om\}$.  Define $F_n^i$ by
$F_n(\ga)=(F_n^0(\ga),F_n^1(\ga))$.   Then since $\ord(X^2)=\al$
the set $H_n^i=\{(x_\de,x_\ga)\;:\; F_n^i(\ga)=\de\}$ is a  relative $\bsi0\al$ in $X^2$. 
And so 
$$G_n=^{def}\{(x,y,z)\;:\; (x,z)\in H_n^0\} \cap\{(x,y,z)\;:\; (y,z)\in H_n^1\} .$$
is $\bsi0\al$ in $X^3$.
Consider any $A\su \Delta_3$.   Define 
$$D_n=\{x_\ga\;:\; F_n(\ga)=(\al,\be)\rmand (x_\al,x_\be,x_\ga)\in A\}.$$
Since $\ord(X)\leq\al$ the set $D_n$ is a relative $\bsi0\al$ in $X$ and
$$A= \bigcup_{n<\om} (X^2\times D_n) \cap G_n$$
is $\bsi0\al$ in $X^3$.    The same argument works for the
sets $$\Delta_1=\{(x_\al,x_\be,x_\ga)\;:\; \ga,\be\leq\al\}\rmand
\Delta_2=\{(x_\al,x_\be,x_\ga)\;:\; \ga,\al\leq\be\}.$$   For any $A\su X^3$ there
are $A_i\su \Delta_i$ so that $A=A_1\cup A_2\cup A_3$, therefor
$\ord(X^3)=\al$.

(2) Suppose $X=\{x_\al\;:\; \al<\om_2\}$.  For each $\al<\om_2$ let
$g_\al:\om_1\to \al+\om_1$ be a bijection.
Choose $F_n:\om_2^2\to \om_2^2$ for
$n<\om$ so that for every $\al_3\leq\al_4<\om_2$
$$(\ga+1)^2=\{F_n(\al_3,\al_4)\;:\;n<\om\} \mbox{ where  } g_{\al_4}(\ga)=\al_3.$$
Define $F_n^i$ by $F_n(\al_3,\al_4)=(F_n^0(\al_3,\al_4),F_n^1(\al_3,\al_4))$.
Since $\ord(X^3)=\al$ we have that  the graphs of the $F_n^i$ are $\bsi0\al$ in
$X^3$ and since the graph $F_n$ is essentially the intersection of these it is $\bsi0\al$ in $X^4$.
It follows as above that if 
$$A\su\{(x_{\al_1},x_{\al_2},x_{\al_3},x_{\al_4})\;:\; \al_1,\al_2\leq\al_3\leq\al_4<\om_2\}$$
then $A$ is $\bsi0\al$ in $X^4$.   Similarly for any permutation $i,j,k,l$ of $1,2,3,4$ if
$$A\su\{(x_{\al_1},x_{\al_2},x_{\al_3},x_{\al_4})\;:\; \al_i,\al_j\leq\al_k\leq\al_l<\om_2\}$$
then $A$ is $\bsi0\al$ in $X^4$.    Hence any $A\su X^4$ is a finite union of $\bsi0\al$ sets and 
so $\ord(X^4)=\al$.

(3) is left to the reader.


\bigskip
\qq Can we have an $X\su 2^\om$ such that $X^2$ a $Q$-set but $X^3$ is not  $Q$-set?

\medskip
In Theorem \ref{brend} Brendle could have used a generic relation $R\su \om_1\times\om_1$ instead
of a well-ordering to witness that $X^2$ is not a $Q$-set.  Perhaps here a generic relation
$R\su \om_2\times\om_2\times\om_2$ would work.

\medskip
\qq For $\al>2$ can we have $X$ a $Q_\al$-set but $X^2$ not a $Q_\al$-set?



\begin{theorem}
[Miller 1995] (CH) For any $\al$ with 
$3\leq \al<\om_1$ there is a $Y\su 2^\om$ such that $\ord(Y)=\al$ and $\ord(Y^2)=\om_1$.
\end{theorem}
\qq Can we have $\;\;\al<\ord(Y^2)<\om_1$ in this Theorem?

  

\begin{theorem}[Miller 1979]
 If ${\rm Borel}(X)=\pow(X)$, then $\ord(X)<\om_1$. In other words, there can be  no
 $Q_{\om_1}$-set.
\end{theorem}

\begin{theorem}[Miller 1979]
It is consistent to have: for every $\al<\om_1$ there
is a $Q_\al$-set.
\end{theorem}
In this model the continuum is $\aleph_{\om_1+1}$.

\bigskip
\qq For $\al\geq 3$ can we have a $Q_\al$ of cardinality greater than or equal to
some $Q_{\al+1}$-set? 

\medskip
\qq If we have a $Q_\om$-set must there be $Q_n$-sets for infinitely many $n<\om$?

\medskip
\qq Can there be a $Q_\om$-set of cardinality $\om_1$?

  

\begin{theorem}[Miller 1979, 2014]
For any successor $\al$ with $3\leq \al<\om_1$ it is consistent to have
a $Q_\al$-set but no $Q_\be$-set for $\be<\al$.
\end{theorem}

In this model the continuum has cardinality $\om_2$.  The 
$Q_\al$-set $X$ has size $\om_1$ and has ``strong order'' $\al$.
Namely, even if you add countably many more sets to the topology of
$X$ its order is still $\al$.   Another way to say this is that
in this model $\pow(\om_1)$ is a countably generated $\si$-algebra
in $\al$-steps but it cannot be countably
generated in fewer steps.  
(In fact, not even with $\om_1$-generators.)  I don't know
about $Q_\be$ sets for $\be>\al$ in this model.  However, if Brendle's argument 
can be generalized it would show that $X^2$ is a $Q_{\al+1}$-set.

  

\sectiontitle{Abstract Rectangles}

\begin{theorem}
[Rao 1969, Kunen 1968]  Assume the continuum hypothesis,
then every subset of the plane  is in the $\si$-algebra generated by
the abstract rectangles  at level 2:
$\;\;\;\;\;\pow(2^\om\times 2^\om)=\si_2(\{A\times B\;:\;A,B\su 2^\om\}).$
\end{theorem}

\begin{theorem}
[Kunen 1968] Assume Martin's axiom, then
\par $\;\;\;\;\;\pow(2^\om\times 2^\om)=\si_2(\{A\times B\;:\;A,B\su 2^\om\}).$

\noindent In the Cohen real model
or the random real model any  well-ordering of $2^\om$ is not 
in the $\si$-algebra generated by
the abstract rectangles.
\end{theorem}

\begin{theorem} 
[Rothberger 1952 and Bing, Bledsoe, Mauldin  1974]  
Suppose that $2^{\om}=\om_2$ and
$2^{\om_1}=\aleph_{\om_2}$ then the $\si$-algebra generated by the abstract
rectangles in the plane is not the power set of the plane. 
\end{theorem}

  

\begin{theorem}
[Bing, Bledsoe, Mauldin 1974] 
Suppose every subset of the plane
is in the $\si$-algebra generated by the abstract rectangles.  Then
for some countable $\al$ every subset of the plane
is in the $\si$-algebra generated by the abstract rectangles by level
$\al$.  $\pow(2^\om\times 2^\om)=\si_\al(\{A\times B: A,B\su 2^\om\})$
\end{theorem}

\begin{theorem}
[Miller 1979 ] For any countable $\al\geq 2$ it is consistent
that every subset of the plane
is in the $\si$-algebra generated by the abstract rectangles
at level $\al$ but for every $\be<\al$ not every subset is at level $\be$.
$\ord(\si(\{A\times B: A,B\su 2^\om\}))=\al$
\end{theorem}
  
\begin{theorem}
[Miller 1979 ] Suppose $2^{<\cc}=\cc$ and $\al<\om_1$. 
Then the following are equivalent:
\par (1) Every subset of $2^\om\times 2^\om$
is in the $\si$-algebra generated by the abstract rectangles
at level $\al$.
\par  (2) There exists $X\su 2^\om$ with $|X|=\cc$ and
every subset of $X$ of cardinality less than $\cc$ is $\Sigma^0_\al$ in $X$.
\end{theorem}

\qq Can we have $2^{<\cc}\neq\cc$ and  
$\pow(2^\om\times 2^\om)=\si(\{A\times B: A,B\su 2^\om\})$?

\medskip \qq Can we have $\ord(\si(\{A\times B: A,B\su 2^\om\}))<\om_1$
and $\pow(2^\om\times 2^\om)\neq\si(\{A\times B: A,B\su 2^\om\})$?

\medskip\qq Can we have  $\ord(\si(\{A\times B: A,B\su 2^\om\}))$ be strictly smaller than
 $\ord(\si(\{A\times B\times C: A,B,C\su 2^\om\}))$?



  

\sectiontitle{Borel Universal Functions}

\begin{theorem}
[Larson, Miller, Steprans, Weiss 2014]  Suppose
$2^{<\cc}=\cc$ then the following are equivalent:
\par (1) There is a Borel universal function, i.e, 
a Borel function $F:2^\om\times 2^\om\to 2^\om$ such that
for every abstract $G:2^\om\times 2^\om\to 2^\om$ there are
$h:2^\om\to 2^\om$ and $k:2^\om\to 2^\om$ such that for
every $x,y\in 2^\om\;\;$
$G(x,y)=F(h(x),k(y))$.
\par (2) Every subset of the plane
is in the $\si$-algebra generated by the abstract rectangles.
\par\medskip Furthermore the universal function has level $\al$ iff every
subset of the plane
is in the $\si$-algebra generated by the abstract rectangles at level $\al$.
\end{theorem}

  

\sectiontitle{Abstract Universal Functions}

\begin{theorem}[Larson, Miller, Steprans, Weiss 2014]  
If $2^{<\ka}=\ka$, then there is an abstract universal function
$F:\ka\times\ka\to\ka$, i.e., 

$\forall G\exists h,k\forall \al,\be \;\; G(\al,\be)=F(h(\al),k(\be))$.
\end{theorem}


\begin{theorem}[Larson, Miller, Steprans, Weiss 2014]  
It is relatively consistent that there is no abstract
universal function $F:\cc\times\cc\to\cc$.
\end{theorem}

\qq Is it consistent with $2^{<\cc}\neq \cc$ to have a universal $F:\cc\times\cc\to\cc$?

  

\sectiontitle{Higher Dimensional Abstract Universal Functions}

\begin{theorem}[Larson, Miller, Steprans, Weiss 2014]  
Abstract universal functions $F:\ka^n\to\ka$ of higher dimensions reduce
to countably many cases where the only thing that matters is
the arity of the parameter functions, e.g. 
\par (1) $\exists F\forall G\exists  h,k \forall x,y\;\;\; G(x,y)=F(h(x),k(y))$
\par (2) ...$G(x,y,z)=F(h(x,y),k(y,z),l(x,z))$
\par (n) ...$G(x_0,\ldots, x_n)=F(h_S(x_S):S\in [n+1]^n)$
\end{theorem}


\begin{theorem}[Larson, Miller, Steprans, Weiss 2014]  
In the Cohen real model for every $n\geq 1$ 
there is a universal function on $\om_n$ where the parameter 
functions have arity
$n+1$ but no universal function where the parameters functions have arity $n$.
\end{theorem}


  

A set is Souslin in $X$ iff it has the form 
$\bigcup_{f\in\om^\om}\bigcap_{n<\om} A_{f\res n}$
where each $A_s$ for $s\in\om^{<\om}$ is Borel in X.  


\begin{theorem}
[Miller 1981] It is consistent to have $X\su 2^\om$ such
that every subset of $X$ is Souslin in $X$ and $\ord(X)=\om_1$. 
A $Q_{\mathcal S}$-set.
\end{theorem}

\begin{theorem}[Miller 1995]
(CH) For any $\al$ with $2\leq \al \leq \om_1$ there is exists
an uncountable $X\su 2^\om$ such that $\ord(X)=\al$ and
every Souslin set in $X$ is Borel in $X$.
\end{theorem}

\begin{theorem}[Miller 2005]
It is consistent that there exists
$X\su 2^\om$ such  $\ord(X)\leq 3$ and there is a Souslin set in $X$ which is not
Borel in $X$.
\end{theorem}

\qq Can we have $\ord(X)=2$ here?

  

\begin{theorem}[Miller 1981]  It is  consistent that for every subset 
$A\su 2^\om\times 2^\om$
there are abstract rectangles $B_s\times C_s$ with
$A=\bigcup_{f\in\om^\om}\;\bigcap_{n<\om} \;(B_{f\res n}\times C_{f\res n})$
but $\pow(2^\om\times 2^\om)\neq \si(\{A\times B: A,B\su 2^\om\})$. 
\end{theorem}

\begin{theorem}[Miller 1979]  It is  consistent that the
universal $\Sigma^1_1$ set $U\su 2^\om\times 2^\om$
is not in the $\si$-algebra generated by the abstract rectangles.
\end{theorem}

\begin{theorem}[Miller 1981]  It is  consistent that there is no
countably generated $\si$-algebra which contains all $\Sigma_1^1$
subsets of $2^\om$.
\end{theorem}

\qq Thm 3 is stronger than Thm 2.  Is the converse true?

  

For $X$ a separable metric space define:
\begin{itemize}
\item $\Sigma^X_0=\Pi^X_0=$
Borel subsets of $X^m$ some $m$.
\item $\Sigma^X_{n+1}$ the projections of $\Pi^X_n$ sets.
\item $\Pi^X_{n+1}$ the complements of $ \Sigma^X_{n+1} $ sets.
\item Proj$(X)=\bigcup_{n<\om}\Sigma^X_n$.
\end{itemize}

\begin{theorem}[Miller 1990]
It is consistent there are $X,Y,Z\su 2^\om$ of projective orders 0, 1, 2:
\begin{itemize}
\item $\ord(X)=\om_1$ and $\Sigma^X_0=$ Proj$(X)$
\item $\Sigma^Y_0\neq \Sigma^Y_1=$ Proj$(Y)$
\item $\Sigma^Z_0\neq \Sigma^Z_1\neq \Sigma^Z_2=$ Proj$(Z)$
\end{itemize}
\end{theorem}

\qq (Ulam) What about projective order 3 or higher?

  \begin{thebibliography}{99}


\bibitem{BBM} Bing, R. H.; Bledsoe, W. W.; Mauldin, R. D.;
Sets generated by rectangles.
Pacific J. Math. 51 (1974), 27-36. 

\bibitem{blt}
Brendle, Joerg; Larson, Paul; and
Todorcevic, Stevo; Rectangular axioms, perfect set properties and
decompositions, Bulletin de l'Academie Serbe des Sciences et
des Arts, Classe des Sciences Mathematiques et Naturelles,
Sciences mathematiques, vol. 33, (2008), 91--130.

\bibitem{carlson}
Tim Carlson, On $\om_1$-Borel sets, unpublished 1982.
(see Miller 2014)

\bibitem{qsets} Fleissner, William G.; Miller, Arnold W.;
On Q Sets,
Proceedings of the American Mathematical Society, 78(1980), 280-284.
\par\url{http://www.math.wisc.edu/~miller/res/qsets.pdf}

\bibitem{gitik}  
Gitik, M.; All uncountable cardinals can be singular. Israel J. Math. 35 (1980), no. 1-2, 61–88. 

\bibitem{klausner} Klausner, Lukas Daniel; Goldstern, Martin;
Fin(X,2) without AC, eprint Sept 12, 2016.

\bibitem{kunen} Kunen, Kenneth;  INACCESSIBILITY PROPERTIES OF CARDINALS.
 Thesis
(Ph.D.) Stanford University. 1968.

\bibitem{kunen2} Kunen 1979 see Miller 1979

\bibitem{fremlin} Fremlin  1982 see Miller 1982

\bibitem{judah} 
Judah, Haim; Shelah, Saharon Q-sets, Sierpiński sets, and rapid filters. Proc. Amer. Math. Soc. 111 (1991), no. 3, 821–832. 

\bibitem{univ} Larson, Paul B.; Miller, Arnold W.;
Steprans, Juris; Weiss, William A.R.; Universal Functions,
Fund. Math. 227 (2014), no. 3, 197--246. 
\par\url{http://www.math.wisc.edu/~miller/res/univ.pdf}

\bibitem{hier} Miller, Arnold W.; On the length of Borel hierarchies,
Annals of Math Logic, 16(1979), 233-267.
\par\url{http://www.math.wisc.edu/~miller/res/gen.pdf}

\bibitem{gencat}  Miller, Arnold W.; 
On generating the category algebra and the Baire order problem
Bulletin de L'Academie Polonaise des Science, 27(1979a), 751-755.
\par\url{http://www.math.wisc.edu/~miller/res/hier.pdf}

\bibitem{gensous} Miller, Arnold W.; Generic Souslin sets,
Pacific Journal of Mathematics, 97(1981), 171-181.
\par\url{http://www.math.wisc.edu/~miller/res/gensous.pdf}

\bibitem{map} Miller, Arnold W.;
Mapping a Set of Reals Onto the Reals,
Journal of Symbolic Logic, 48(1983), 575-584.
\par\url{http://www.math.wisc.edu/~miller/res/map.pdf}

\bibitem{special} Miller, Arnold W.; Special subsets of the real line,
in {\bf Handbook of Set Theoretic Topology}, North Holland, (1984), 201-233.
\par\url{http://www.math.wisc.edu/~miller/res/special.pdf}

\bibitem{proj}
Miller, Arnold W.; Projective subsets of separable metric spaces
Annals of Pure and Applied Logic, 50(1990), 53-69. 
\par\url{http://www.math.wisc.edu/~miller/res/proj.pdf}

% \bibitem{survey}  Miller, Arnold W.; Special sets of reals,
% in {\bf Set Theory of the Reals}, ed Haim Judah, Israel Mathematical
% Conference Proceedings, 6(1993), 415-432, American Math Society.
% \par\url{http://www.math.wisc.edu/~miller/res/survey.pdf}

\bibitem{dstfor}  Miller, Arnold W.; Descriptive Set Theory and Forcing:
how to prove theorems about Borel sets the hard way, 
Lecture Notes in Logic 4(1995), Springer-Verlag.
New edition 4-2001 now published by Association for Symbolic Logic.
\par\url{http://www.math.wisc.edu/~miller/res/dstfor.pdf}

\bibitem{rel-anal} Miller, Arnold W.;  On relatively analytic and Borel subsets
Journal of Symbolic Logic 70(2005), 346-352.
\par\url{http://www.math.wisc.edu/~miller/res/rel-anal.pdf}

\bibitem{longbor} Miller, Arnold W.;  Long Borel hierarchies
Math Logic Quarterly, 54(2008), 301-316.
\par\url{http://www.math.wisc.edu/~miller/res/longbor.pdf}

\bibitem{omega1} Miller, Arnold W.;
The hierarchy of $\omega_1$-Borel sets,
eprint July 2011 
\par\url{http://www.math.wisc.edu/~miller/res/omega1.pdf}

\bibitem{bor} Miller, Arnold W.; Borel hierarchies, 
Lecture notes 2014-2016.  Under construction.
\par\url{ http://www.math.wisc.edu/~miller/old/m873-14/bor.pdf}


\bibitem{rao} Rao, B.V.; On discrete Borel spaces and projective
sets. Bull. Amer. Math. Soc. 75 1969 614-617.

\bibitem{reclaw} Rec{\l}aw 1993 see Miller 1995

\bibitem{roth}  Rothberger, Fritz; A remark on the existence of a denumerable
base for a family of functions. Canadian J. Math. 4, (1952). 117-119. 

\bibitem{steprans}
Steprans, Juris; Cardinal arithmetic and $\aleph_1$-Borel sets.
Proc. Amer. Math. Soc. 84 (1982), no. 1, 121--126.



\end{thebibliography}
 
\end{document}



