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