% todo: could publish omega1-borel here % list of open problems at the end \documentclass[12pt]{article} \usepackage{amssymb,latexsym,hyperref} \def\pair(#1,#2){\la #1, #2 \ra} \def\comb(#1,#2){ \left( \begin{array}{c} #1 \\ #2 \end{array} \right) } \def\rmif{\mbox{ if }} \def\supp{\mbox{supp}} \def\concat{\hat{\phantom{aa}}} \def\cn{\mbox{CN}} \def\rank{\mbox{rank}} \def\nn{\mathcal{N}} \def\rr{\mathcal{R}} \def\bool{\mbox{bool}} \def\graph{\mbox{graph}} \def\cof{\mbox{cof}} \def\calc{\mathcal{C}} \def\lam{\lambda} \def\elemsub{\preceq} \def\rank{\mbox{rank}} \def\concat(#1){\hat{\phantom{a}}#1} \def\continuum{{\mathfrak c}} \def\Sig#1{\Sigma_#1} \def\cantorspace{2^\omega} \def\Intersect{\bigcap} \def\Union{\bigcup} \def\intersect{\cap} \def\cross{\times} \def\ep{\epsilon} \def\aa{\mathcal{A}} \def\al{\alpha} \def\bb{\mathcal{B}} \def\be{\beta} \def\borel{{\rm Borel}} \mathchardef\wtilde="0365 \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\ccal{\mathcal{C}} \def\conj{\mathop{\bigwedge}} \def\cc{{\mathfrak c}} \def\dd{\mathfrak{d}} \def\dense{{\cal D}} \def\de{\delta} \def\diffeven{\mbox{Diffeven}} \def\diffodd{\mbox{Diffodd}} \def\disj{\mathop{\bigvee}} \def\ff{\mathcal{F}} \def\forces{{\;\Vdash}} \def\ga{\gamma} \def\gg{{\mathcal{G}}} \def\hh{\mathcal{H}} \def\ka{\kappa} \def\la{\langle} \def\name#1{\stackrel{\circ}{#1}} \def\nam{{\mathcal N}} \def\om{\omega} \def\ord{{\rm ord}} \def\poset{{\mathbb P}} \def\pow{\mathcal{P}} \def\proof{\par\noindent proof:\par} \def\proves{\vdash} \def\qed{\nopagebreak\par\noindent\nopagebreak$\Box$\par} \def\rationals{{\mathbb Q}} \def\ra{\rangle} \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\ss{\mathfrak{s}_{mm}} \def\starpi(#1){{\bf \Pi}^*_{#1}} \def\starsi(#1){{\bf \Sigma}^*_{#1}} \def\st{\;:\;} % such that \def\su{\subseteq} \newtheorem{theorem}{Theorem}[section] \newtheorem{thm}[theorem]{Theorem} \newtheorem{cor}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{question}[theorem]{Question} \newtheorem{remark}[theorem]{Remark} \newtheorem{prop}[theorem]{Proposition} \newtheorem{example}[theorem]{Example} \newtheorem{define}[theorem]{Definition} \begin{document} \begin{flushright} A.Miller\\ Spring 2014\\ last revised August 10, 2017\\ (still working on it) \end{flushright} \begin{center} {\large Borel hierarchies} \end{center} These are lecture notes from a course I gave in the spring semester of 2014\footnote{\url{http://www.math.wisc.edu/~miller/old/m873-14/}}. The following results are new: \begin{itemize} \item \ref{remark4.6} $\;$ It is consistent that the Borel subsets of the plane are not contained in any bounded level of the $\si$-algebra generated by the abstract rectangles. \item \ref{bbmanswer} $\;$ It is consistent that for some $\ka$ every family of size $\ka$ of sets of reals is included in a countably generated $\si$-algebra but not necessarily at a bounded level. \item \ref{answer7.13} If $2^{<\cc}=\cc$ and there is a Borel universal map, then there is a map $H:2^\om\times 2^\om\to 2^\om$ such that for every $\ka<\cc$ and $G:\ka\times\ka\to\ka$ there are $x_\al\in 2^\om$ for $\al<\ka$ such that for all $\al,\be,\ga<\ka$ $\;\;G(\al,\be)=\ga$ iff $H(x_\al,x_\be)=x_\ga$. \item \ref{newunion} $\;$ CH implies that for any $\al_0$ with $3\leq \al_0<\om_1$ there are $X_0,X_1\su 2^\om$ with $\ord(X_0)=\al_0=\ord(X_1)$ and $\ord(X_0\cup X_1)=\al_0+1$. \end{itemize} Also the proof of Theorem \ref{newproof} is new. I have omitted some of the results proved in lecture but only when the proof I gave is identical to that found in the literature. % The last section will??? contain a summary of many other results that % I did not lecture on, as well as, some open ??? questions. \tableofcontents \section{Classical Results} This section contains the Theorem of Lebesgue which uses universal sets and a diagonal argument to show that the length of the Borel hierarchy is as long as possible, $\om_1$. We also give some results of Bing, Beldsoe, and Mauldin and of Rec{\l}aw which I think of as generalizations of Lebesgue's Theorem. First we review some standard terminology and results. The Baire space is $\om^\om=\{x \;|\; x:\om\to\om\}$ where $\om=\{0,1,2,\ldots\}$. For $s\in \om^{<\om}=\bigcup_{n<\om} \om^n$ a finite sequence define a basic clopen set: $$[s]=\{x\in\om^\om\;:\; s\su x\}$$ The Baire space is homeomorphic to the irrationals and is a zero dimensional Polish space, i.e., completely metrizable separable with a clopen basis. One complete metric is $d(x,y)=\frac{1}{n}$ where $n$ is the least with $x\res n \neq y\res n$. The Cantor space $2^\om\su \om^\om$ is homeomorphic to the middle thirds set $$\{\sum_{n=0}^\infty \frac{2x(n)}3 \;:\; x\in 2^\om\}$$ \noindent The Borel hierarchy is described as follows: \medskip $\mbox{ open }= \bsi01 = G$ \medskip$\mbox{ closed }= \bpi01 = F$ \medskip$\bpi02 = G_\de =$ countable intersections of open sets \medskip$\bsi02 = F_\si =$ countable unions of closed sets \medskip$\bsi03 = G_{\de\si} =$ countable unions of $G_\de$ sets \medskip$\bsi0\al=\{\;\bigcup_{n<\om} A_n \;:\; A_n\in \bpi0{<\al}\;\}$ \medskip$\bpi0\al=\{\;\bigcap_{n<\om} A_n \;:\; A_n\in \bsi0{<\al}\;\}$ \medskip $G_{\de\si}$, $G_{\de\si\de}$, \ldots, $\;\;\;\;F_{\si\de}$, $F_{\si\de\si}$ \ldots \bigskip\noindent The Borel sets are the smallest $\si$-algebra containing the open sets. In a metric space $F\su G_\de$ ($\bpi01\su\bpi02$), i.e., every closed set is the countable intersection of open sets.\footnote{If $C$ is closed, then $C=\bigcap_n U_n$ where $U_n=\{x\;:\; \exists y\in C\; d(x,y)<\frac1n\}$.} It follows that in a metric space for $1\leq \al<\be$ that $$\bsi0\al\cup \bpi0\al\;\su\; \bsi0\be\cap \bpi0\be\;=\;^{def}\bde0\be$$ \begin{example}(Willard 1971 \cite{willard}) There are nice spaces in which closed sets are $G_{\de\si}$ but not $G_\de$. \end{example} \proof Suppose $(X,\tau)$ is a space for which closed sets are $G_\de$ and $G_{\de\si}\neq G_\de$. Fix $A\in G_{\de\si}\sm G_\de$. Let $\tau_A$ be the smallest topology containing $\tau$ and the complement of $A$, $\sim A=^{def}X\sm A$. Then the closed sets of $\tau_A$ are a subset of $G_{\de\si}(\tau_A)$ but not of $G_{\de}(\tau_A)$. $U\in \tau_A$ iff there are $V,W\in\tau$ with $U=(V\cap \sim A)\cup W$. $A$ is closed in $\tau_A$ but is not the countable intersection of $\tau_A$ open sets, else $$A=\bigcap_{n<\om} (V_n\cap\sim A)\cup W_n$$ But then $A=\bigcap_{n<\om} W_n$, but $A$ is not $G_\de$. \qed The equation $$\bigcup_n P_n \;\cap\; \bigcup_m Q_m\;=\; \bigcup_{n,m}\;P_n\cap Q_m$$ shows by induction that \begin{itemize} \item $\bsi0\al$ is closed under finite intersections and \item $\bpi0\al$ is closed under finite unions. \end{itemize} Another easy proposition is that for $f:X\to Y$ a continuous map: \begin{itemize} \item If $A\in\bsi0\al(Y)$, then $f^{-1}(A)\in\bsi0\al(X)$. \item If $A\in\bpi0\al(Y)$, then $f^{-1}(A)\in\bpi0\al(X)$. \end{itemize} Note that $2^\om$ is naturally homeomorphic to $2^\om\times 2^\om$ via the map $x\mapsto ( y,z )$ where $y(n)=x(2n)$ and $z(n)=x(2n+1)$. We use $x=\la y,z\ra$ to denote the pairing map. Similarly $(2^\om)^\om$ is homeomorphic to $2^\om$ via $x=\la x_n : n<\om\ra$ where $x_n(m)=x(\la n,m\ra)$ and $\la n,m\ra = 2^n(2m+1)-1$ is a bijection between $\om\times\om$ and $\om$. \begin{theorem}\label{leb} (Lebesgue 1905 see \cite{dstfor} Thm 2.5) For every countable $\alpha>0$ $$\bsi0\alpha( 2^\om )\not=\bpi0\alpha( 2^\om ).$$ \end{theorem} This follows from the existence of universal sets and a diagonal argument. \bigskip\noindent {\bf Universal Sets Lemma.} {\it For every countable $\al>0$ there exists $U\su 2^\om\times 2^\om$ which is $\bsi0\al$ and universal for $\bsi0\al$-sets, i.e., for every $V\su 2^\om $ which is $\bsi0\al$ there exists $x\in 2^\om$ such that $V=U_x=^{def}\{y\;:\; (x,y)\in U\}$.} \proof Note that $U\in \bsi0\al$ implies $U_x\in \bsi0\al$ for all $x\in 2^\om$. To see this let $f:2^\om \to 2^\om\times 2^\om$ be defined by $f(y)=(x,y)$, then $U_x=f^{-1}(U)$. \bigskip\noindent Case $\al=1$. Let $\{C_n:n<\om\}$ list all clopen subsets of $2^\om$. Define $$(x,y)\in U\rmiff \exists n\; (x(n)=1\rmand y\in C_n).$$ Note that $U=\bigcup_{n<\om}(\{x:x(n)=1\}\times C_n)$. \bigskip\noindent Case $\al>1$. Let $\{\al_n:n<\om\}$ list with infinitely many repetitions the nonzero elements of $\al$. Let $U^{\al_n}$ be a universal $\bsi0\al_n$ set. Define $U$ by $$(x,y)\in U \rmiff \exists n \; (x_n,y)\notin U^{\al_n}$$ Note that $\sim U^{\al_n}$ is a universal $\bpi0\al_n$ set. For each fixed $n$ the set $$\{(x,y)\;:\; (x_n,y)\in U^{\al_n}\}$$ is $\bsi0\al_n$ because it is the preimage of $U^{\al_n}$ under a continuous map, namely $(x,y)\mapsto (x_n,y)$. Hence it is easy to verify that $U$ is a universal $\bsi0\al$ set. \qed \bigskip\noindent {\bf The Diagonal Argument}. Suppose $U\su 2^\om \times 2^\om$ is a universal $\bsi0\al$ set. Let $$D=\{x\in 2^\om\;:\; (x,x)\notin U\}.$$ Then $D$ is $\bpi0\al$ because it is the continuous preimage of $\sim U$ under the map $x\mapsto (x,x)$. However $D\neq U_x$ for any $x\in 2^\om$ so $D$ is not $\bsi0\al$. This proves Theorem \ref{leb}. \qed Define $\ord(X)$ to the least ordinal such that $\bsi0\al(X)=\borel(X)$. Hence $\ord(2^\om)=\om_1$. \begin{cor} 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$ is subspace, then $\ord(Y)\leq \ord(X)$. \end{cor} \proof If $Y\su X$, then $$\bsi0\al(Y)=\{B\cap Y\;:\;B\in \bsi0\al(X)\}$$ and $$ \borel(Y)=\{B\cap Y\;:\; B\in\borel(X)\}.$$ \qed Suppose $\hh\su\pow(Y)$ define $\Sig\al(\hh)$ as follows: \noindent $\Sig0(\hh)=\{\sim A\;:\; A\in\hh\}$ and for $\al>0$ $$\Sig\al(\hh)=\{\bigcup_{n<\om}\sim A \;:\; A_n\in \bigcup_{\be<\al} \Sig\be(\hh)\}$$ We let $\borel(\hh)$ be the $\si$-algebra generated by $\hh$ and let $\ord(\hh)$ be the least $\al$ with $\Sig\al(\hh)=\borel(\hh)$. \begin{theorem} \label{bbm} (Bing, Bledsoe, Mauldin \cite{BBM} also \cite{dstfor} Thm 3.2 \cite{survey} Thm 18) Suppose $\hh\subseteq \pow( 2^\om )$ is a countable family such that $\borel( 2^\om )\subseteq \borel(\hh)$. Then $\ord(\hh)=\om_1$, i.e., the $\si$-algebra generated by $\hh$ has $\om_1$ many levels. \end{theorem} To prove this theorem we will need the following two lemmas. Given a countable $\hh\subseteq P(\cantorspace)$ let $$\ff=\{C\cross A \;:\; C\subseteq \cantorspace\;\mbox{ is clopen} \rmand A\in \hh \} \;\;\su\;\;\pow(2^\om\times 2^\om).$$ \begin{lemma} (Universal sets) \label{univ} For each $\alpha$ with $1\leq\alpha<\omega_1$ there exists a set $U\in\Sigma_\alpha(\ff)$ which is universal for $\Sigma_\alpha(\hh)$ sets, i.e., for every $A\in\Sigma_\alpha(\hh)$, there exists $x\in\cantorspace$ such that $A=\{y: (x,y)\in U\}$. \end{lemma} \proof For $\alpha=1$: Let $\hh=\{A_n:n\in\omega\}$ let $$U=\Union_{n\in\omega}\{x: x(n)=1\}\cross (\cantorspace\setminus A_n).$$ For $\alpha>1$: Let $x\mapsto \langle x_n:n\in\omega\rangle$ be a nice recursive coding taking $\cantorspace\rightarrow(\cantorspace)^\omega$. Let $\beta_n$ for $n\in\omega$ be cofinal in $\alpha$, and $U_n\in\Sigma_{\beta_n}(\ff)$ be universal for $\Sigma_{\beta_n}(\hh)$ sets. Define $U_n^{\prime}$ by $(x,y)\in U_n^{\prime}$ iff $(x_n,y)\in U_n$. It is easy to check that $U_n^\prime$ is also $\Sigma_{\beta_n}(\ff)$ and universal for $\Sigma_{\beta_n}(\hh)$. But now taking $$U=\Union_{n\in\omega}(\cantorspace\setminus U_n^\prime)$$ gives us a set in $\Sigma_\alpha(\ff)$ which is universal for $\Sigma_\alpha(\hh)$ sets. \qed \begin{lemma} (Diagonalization) \label{diag} Suppose that every clopen set is in Borel($\hh$). Then for every $B\in$Borel($\ff$) the set $\{x:(x,x)\in B\}$ is in Borel($\hh$). \end{lemma} \proof For $B=C\cross A$ where $A\in \hh$ and $C\subseteq \cantorspace$ is clopen, note that $$\{x:(x,x)\in B\}=C\intersect A.$$ Since by assumption $C\in$Borel($\hh$), we have the lemma for elements of $\ff$. To do Borel($\ff$) is an easy induction. \qed Now we give a proof of Theorem \ref{bbm}. Suppose Borel($\hh)=\Sigma_\alpha(\hh)$. By Lemma \ref{univ} there exist $U$ in Borel($\ff$) which is universal for $\Sigma_\alpha(\hh)$ and hence Borel($\hh$). By Lemma \ref{diag} the set $$D=\{x:(x,x)\notin U\}$$ is in Borel($\hh$). But this means that for some $x$ that $D=\{y:(x,y)\in U\}$. But then $x\in D$ iff $x\notin D$. \qed \begin{theorem}\label{rec} (Rec{\l}aw 1993 see \cite{dstfor} Thm 3.5 \cite{survey} Thm 17) 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} \proof By going to a subspace of $X$ we may that there is an $f:X\rightarrow \cantorspace$ which is one-to-one, onto, and continuous. Let $\calc$ be a countable open basis for $X$ containing the pre-images under $f$ of the clopen subsets of $2^\om$. Let $$\hh=\{f(C)\;:\; C\in\cal C\}.$$ Since it is clear that $\hh$ contains all clopen sets, by Theorem \ref{bbm}, the $\ord(\hh)=\omega_1$. But the map $f$ takes the Borel hierarchy of $X$ directly over to the hierarchy on Borel($\hh$), so $\ord(X)=\omega_1$. \qed \begin{remark} Rec{\l}aw's result is also true, $\ord(X)=\om_1$, if we only assume that there is a Borel map onto map $f:X\to 2^\om$. \end{remark} To see this let $\cal C$ be a countable open basis for $X$ and let $\cal B$ be the pre-images under $f$ of the clopen subsets of $2^\om$. Let ${\cal G} ={\cal C}\cup {\cal B}$ and $\hh=\{f(C)\;:\; C\in{\cal G}\}$. Then $\ord(\hh)=\om_1$ by Theorem \ref{bbm}. And so $\ord({\cal G})=\om_1$. This means that $\ord(X)=\om_1$, since $\borel({\cal G})=\borel(X)$ and $\bsi01(X)\su \Sig1({\cal G})$ implies $\ord({\cal G})\leq\ord(X)$. To see this note that if $\al=\ord(X)$, then $$\borel({\cal G})=\borel(X)=\bsi0\al(X)\su\Sig\al({\cal G})\su \borel({\cal G}).$$ An extension of Rec{\l}aw's result to Souslin (operation A) sets appears in Miller \cite{proj}. \begin{remark} It is relatively consistent to have $X,Y\su 2^\om$ and $f:X\to Y$ continuous, one-to-one, and onto such that $\ord(X)=2$ and $\ord(Y)=3$. \end{remark} \proof To see this note that it is relatively consistent to have a $Q$-set $H$ of size $\om_1$ which is concentrated on a countable set $E$ (Fleissner and Miller \cite{qsets}). Let $Y=H\cup E=\{y_\al:\al<\om_1\}$ and $H=\{x_\al:\al<\om_1\}$ be one-to-one enumerations. Put $X=\{\la x_\al,y_\al\ra:\al<\om_1\}$ and let $f$ be projection onto the second coordinate, i.e., $f(\la x,y\ra)=y$. $X$ is a $Q$-set so has order 2 and it easy to check that $Y$ has order 3. \qed %??? maybe put in some more remarks open questions. Maybe should %check if Luzin set of size omega1 is there and hence Y's of %all borel orders.??? In the iterated Sack real model the continuum is $\om_2$ and for every $X\su 2^\om$ of size $\om_2$ there is a continuous onto map $f:X\to 2^\om$ (see Miller \cite{map}) and hence $\ord(X)=\om_1$. So in the Sacks real model every set of reals of size continuum has order $\om_1$. \begin{cor} If $X$ is separable, metric, but not zero-dimensional, then $\ord(X)=\om_1$. \end{cor} \proof Suppose $\ord(X)<\om_1$. Let $d$ be any metric on $X$ and $x\in X$ arbitrary. There must be arbitrarily small $\ep>0$ such that there is no $y\in X$ with $d(x,y)=\ep$. Otherwise the map $y\mapsto d(x,y)$ has a nontrivial interval in its image. \qed Any zero-dimensional separable metric space is homeomorphic to a subspace of $2^\om$. See Kechris \cite{kechris} page 38. \section{The \texorpdfstring{$\om_1$}{omega-1}-Borel hierarchy} \bigskip\noindent Define the levels of the $\om_1$-Borel hierarchy of subsets of $2^\om$ as follows: \begin{enumerate} \item $\starsi(0)=\starpi(0)=$ clopen subsets of $2^\om$ \item $\starsi(\al)=\{\bigcup_{\be<\om_1}A_\be\st (A_\be:\be<\om_1)\in (\starpi(<\al))^{\om_1}\}$ \item $\starpi(\al)=\{2^\om\sm A \st A\in \starsi(\al)\}$ \item $\starpi(<\al)=\bigcup_{\be<\al}\starpi(\be)$ $\;\;\;\;\starsi(<\al)=\bigcup_{\be<\al}\starsi(\be)$ \end{enumerate} \noindent The length of this hierarchy is the smallest $\al\geq 1$ such that $$\starpi(\al)=\starsi(\al).$$ \begin{theorem} (Miller \cite{omega1}) \label{ma-hier} (MA$_{\om_1}$) $\starpi(\al)\neq\starsi(\al)$ for every $\al<\om_2$. \end{theorem} We prove this using the following two lemmas. A well-known consequence of MA$_{\om_1}$ is that every subset $Q\su 2^\om$ of size $\om_1$ is a Q-set, i.e., for every subset $X\su Q$ there is a $G_\de$ set $G\su 2^\om$ with $G\cap Q=X$ (see Fleissner and Miller \cite{qsets}). \begin{lemma}\label{qset} Suppose there exists a Q-set of size $\om_1$. Then there exists an onto map $F:2^\om\to 2^{\om_1}$ such for every subbasic clopen set $C\su 2^{\om_1}$ the set $F^{-1}(C)$ is either $G_\de$ or $F_\si$. \end{lemma} \proof Fix $Q=\{u_\al\in 2^\om\st\al<\om_1\}$ a Q-set. Let $G\su 2^\om\times 2^\om$ be a universal $G_\de$ set, i.e., $G$ is $G_\de$ and for every $G_\de$ set $H\su 2^\om$ there exists $x\in 2^\om$ with $G_x=H$. Define $F$ as follows, given $x\in 2^\om$ let $$F(x)(\alpha)=1 \rmiff u_\al\in G_x $$ If $C$ is a subbasic clopen set, then for some $\al$ and $i=0$ or $i=1$ $$C_{\al,i}=\{p\in 2^{\om_1}\st p(\al)=i\}.$$ Then for $i=1$ $$F^{-1}(C_{\al,1})=\{x\st u_\al\in G_x \}$$ which is a $G_\de$ set. Since $C_{\al,0}$ is the complement of $C_{\al,1}$ we have that $F^{-1}(C_{\al,0})$ is an $F_{\si}$-set Finally, we note that since $Q$ is a Q-set, i.e., every subset is a relative $G_\de$, it follows that $F$ is onto. \qed The next Lemma is true without any additional assumptions beyond ZFC. Its proof is a generalization of Lebesgue's 1905 proof (see Kechris \cite{kechris} p.168) for the standard Borel hierarchy. \begin{lemma}\label{univstar} For any $\al$ with $0<\al<\om_2$ there exists a $\starsi(\al)$ set $U\su 2^{\om_1}\times 2^\om$ which is universal for $\starsi(\al)$ subsets of $2^\om$, i.e., for any $Q\su 2^\om$ which is $\starsi(\al)$ there exists $p\in 2^{\om_1}$ with $U_p=Q$. Similarly, there is a universal $\starpi(\al)$ set. \end{lemma} \proof The proof is by induction on $\al$. Note that the complement of a universal $\starsi(\al)$ set is a universal $\starpi(\al)$-set. For $\al=1$, $\starsi(\al)$ is just the open sets. There is a universal open set $V\su 2^\om\times 2^\om$. Put $$U=\{(p,x)\in 2^{\om_1}\times 2^\om\st (p\res \om,x)\in V\}$$ For $\al$ such that $2\leq \al<\om_2$ proceed as follows. Let $(\de_\be<\al:\be<\om_1)$ have the property that for every $\ga<\al$ there are $\om_1$ many $\de_\be \geq \ga$. It follows that for every $\starsi(\al)$ set $Q\su 2^\om$ there is $(Q_\be\in \starpi(\de_\be)\st \be<\om_1)$ with $$Q=\bigcup_{\be<\om_1}Q_\be.$$ By induction, there are $U_\be\su 2^{\om_1}\times 2^\om$ universal $\starpi(\de_\be)$ sets. Let $a:\om_1\times\om_1\to\om_1$ be a bijection. For each $\be$ define $$\pi_\be: 2^{\om_1}\times 2^\om\to 2^{\om_1}\times 2^\om,\;\; (p,x)\mapsto (q,x)$$ where $q(\al)=p(a(\be,\al))$. Put $$U=\bigcup_{\be<\om_1}\pi_\be^{-1}(U_\be)$$ then $U$ will be a universal $\starsi(\al)$ set. \qed Now we prove Theorem \ref{ma-hier}. Suppose for contradiction, that every $\om_1$-Borel set is $\starsi(\al)$ for some fixed $\al<\om_2$. Let $U\su 2^{\om_1}\times 2^\om$ be a universal $\starsi(\al)$ and define $$V=\{(x,y)\in 2^\om\times 2^\om\st (F(x),y)\in U\}.$$ Then $V$ is an $\om_1$-Borel set (although not necessarily at the $\starsi(\al)$) because the preimage of any clopen box $C\times D$ is $\om_1$-Borel by Lemma \ref{qset}. Define $$D=\{x:(x,x)\notin V\}.$$ But then $D$ is $\om_1$-Borel but not $\starsi(\al)$. We see this by the usual diagonal argument that if $D=U_p$, then since $F$ is onto there would be $x\in 2^\om$ such that $F(x)=p$ but then $$x\in D \rmiff (F(x),x)\notin U \rmiff x\notin U_p \rmiff x\notin D.$$ \qed \begin{remark} In the Cohen real model this hierarchy has order either $\om_1+1$ or $\om_1+2$, I am not sure which. \end{remark} \begin{remark} Note that in the proof $V\su 2^\om\times 2^\om$ is a $\starsi(2+\al)$-set, since the preimage of a clopen set under $F$ is ${\bf\Delta}_3^0$. Hence for levels $\al\geq\om$ the set $V$ is a $\starsi(\al)$ set which is universal for $\starsi(\al)$ sets. \end{remark} \begin{remark} Our result easily generalizes to show that MA implies that for any $\ka$ a cardinal with $\om\leq \ka <|2^\om|$ the $\ka$-Borel hierarchy has length $\ka^+$. This implies that assuming MA for any $\ka_1<\ka_2$ there are $\ka_2$-Borel sets which are not $\ka_1$-Borel.\footnote{Since $\ka_2$-Borel sets at level $\ka_1^+$ or higher cannot be $\ka_1$-Borel.} It is also true for the Cohen real model that for $\om\leq \ka_1<\ka_2<|2^\om|$ that there are $\ka_2$-Borel sets which are not $\ka_1$-Borel. \end{remark} \begin{prop} (\cite{omega1}) If $\pow(2^\om)=\om_1$-Borel, then $\pow(2^\om)=\starsi(\al)$ for some $\al<\om_2$. \end{prop} \proof Suppose not and let $P_\al$ for $\al<\om_2$ be pairwise disjoint homeomorphic copies of $2^\om$. For each $\al$ let $A_\al\su P_\al$ be such that $A_\al\notin\starsi(\al)$. Then $$A=^{def}\bigcup_{\al<\om_2}A_\al$$ is not $\om_1$-Borel. \qed Steprans \cite{steprans} showed that it is relatively consistent with ZFC that $$\starpi(3)=\starsi(3)=\pow(2^\om)\rmand \starpi(2)\neq\starsi(2)$$ and the continuum is $\aleph_{\om_1}$. Carlson \cite{carlson} showed: \begin{theorem} (Carlson) If every subset of $2^\om$ is $\om_1$-Borel, then the cofinality of the continuum must be $\om_1$. \end{theorem} \proof Let $B_\al\su 2^\om$ for $\al<\cc$ list all (ordinary) Borel sets. Let $X_\al\in[2^\om]^\om$ for $\al<\cc$ be a family of pairwise disjoint infinite countable sets. For each $\al$ choose $Z_\al\su X_\al$ such that $B_\be\cap X_\al\neq Z_\al$ for every $\be<\al<\cc$. Put $Z=\bigcup_{\al<\cc}Z_\al$. We claim that if $\cof(\cc)>\om_1$ then $Z$ is not $\om_1$-Borel. This will follow easily from the following \par\bigskip\noindent {\bf Claim}. For any $C\su 2^\om$ an $\om_1$-Borel set, there are (ordinary) Borel sets $C_\al$ for $\al<\om_1$ such that for any $x\in 2^\om$ there is a closed unbounded $Q\su\om_1$ such that for every $\al\in Q$ ($x\in C$ iff $x\in C_\al$). \proof We code $\om_1$-Borel sets with well-founded trees. For $T\su \om_1^{<\om}$ a well-founded tree let $T^*$ be the rank zero or terminal nodes of $T$. To simplify matters assume that for every $s\in T\sm T^*$ all immediate extensions of $s$, i.e., $s\concat(\al)$, are in $T$. Let $\calc$ be the clopen subsets of $2^\om$. Given $c:T^*\to \calc$ define $H(s,(T,c))\su 2^\om$ for $s\in T$ by the rank of $s$. \begin{itemize} \item $H(s,(T,c))=c(s)$ for $s\in T^*$ and otherwise \item $H(s,(T,c))=\bigcap_{\al<\om_1}\sim H(s\concat(\al),(T,c))$ \end{itemize} Now let $C=H(\la\ra,(T,c))$. For any $\al<\om_1$ let $T_\al=\al^{<\om}\cap T$, $c_\al=c\res T_\al^*$, and $C_\al=H(\la\ra,(T_\al,c_\al))$. Since $\al$ is countable $C_\al$ is an ordinary Borel set. Consider any $x\in 2^\om$. Let $\ka$ be a large enough regular cardinal. Construct a continuous $\om_1$ chain $M_\al\elemsub H_\ka$ of countable elementary substructures satisfying: \begin{enumerate} \item $(T,c)\in M_0$ and $x\in M_0$, \item $M_\al\in M_{\al+1}$ \item $M_\lam=\bigcup_{\al<\lam} M_\al$ for $\lam<\om_1$ limit. \end{enumerate} Then automatically $Q=\{M_\be\cap\om_1:\be<\om_1\}$ will be a closed unbounded set. Now if $\al=M_\be\cap\om_1$. Since $(T,c)$ and $x$ are both in $M_\be$ it is easy to see by induction on rank that for any $s\in T_\al$ that $$x\in H(s,(T_\al,c_\al)) \rmiff x\in H(s,(T,c)).$$ This proves the Claim. To prove the Theorem suppose for contradiction that $Z=C$ where $C$ is $\om_1$-Borel and let $(C_\al:\al<\om_1)$ be given by the Claim. If the cofinality of $\cc$ is greater $\om_1$ then for some $\be<\cc$ we have that $\{C_\al:\al<\om_1\}\su \{B_\al:\al<\be\}$. But $Z_\be\neq X_\be \cap C_\al$ for every $\al<\om_1$ which is a contradiction. \qed \section{The order of a separable metric space} \begin{theorem} \label{mainthm} (Miller \cite{hier} Thm 22) It is relatively consistent with ZFC that $ord(X)=\om_1$ for all uncountable $X\su 2^\om$. \end{theorem} It also consistent with any cardinal arithmetic that for every $\al$ with $2\leq\al\leq\om_1$ there is an uncountable $X\su 2^\om$ with $\ord(X)=\al$. One can also have model where these orders are precisely the interval $[\al_0+1,\om_1]$. The model for this theorem is the $\om_2$ finite support iteration of the direct sum $\poset$ of $\Pi_\al$-forcings for $\al<\om_1$. \begin{define} Nice $\al$ tree. \label{nicetree} For $2\leq\al<\om_1$ we define $T\su\om^{<\om}$ to be a nice $\al$-tree iff \begin{enumerate} \item it is well-founded tree of rank $\al$, i.e., $\rank_T(\la\ra)=\al$ \item for any $s\in T$ with $\rank_T(s)>0$ we have that $s\concat(n)\in T$ for all $n<\om$ \item if $\rank_T(s)=\be+1$, then $\rank_T(s\concat(n))=\be$ for all $n$ \item if $\rank_T(s)=\lambda$ a limit ordinal, then for any $\be<\lambda$ there are at most finitely many $n$ with $\rank_T(s\concat(n))\leq \be$. \end{enumerate} \end{define} \begin{define}\label{defpialpha} Fix a nice $\al$-tree $T$, let $T^*$ be the terminal nodes of $T$, i.e., those of rank zero, and let $T^+=T\sm T^*$. $\Pi_\al$-forcing is the poset $\poset_\al$ defined as follows: $p\in\poset_\al$ iff there are finite $p_0\su T^*\cross 2^{<\om}$ and $p_1\su T^+\cross 2^{\om}$ such that $p=p_0\cup p_1$ and $p_0$ is the graph of a partial function and they are consistent. Consistency means that \begin{itemize} \item if $(s,x),(s\concat(n),y)\in p_1$ then $x\neq y$ and \item if $(s,x)\in p_1$ and $(s\concat(n),t)\in p_0$, then $x\notin [t]$. \end{itemize} \end{define} We think of our conditions as attaching elements of $2^\om$ to nodes of the tree $T$ subject to the condition that no $x$ is attached to immediately adjacent nodes, i.e., $s$ and $s\concat(n)$ are immediately adjacent. We think of $(s\concat(n),t)\in p_0$ (or equivalently $p_0(s\concat(n))=t$ since it is a partial function) as attaching all elements of the clopen set $[t]=\{x\in 2^\om\;:\; t\su x\}$ to the terminal node $s\concat(n)\in T^*$. \begin{lemma} For any countable ordinal $\al_0$, $\;\Pi_{\al_0}$-forcing $\poset_{\al_0}$ has the countable chain condition. \end{lemma} \proof Suppose $A$ is uncountable antichain. Since there are only countably many different $p_0$ without loss we may assume that there exists $r$ such that $p_0=r$ for all $p\in A$. Consequently for $p,q\in A$ the only thing that can keep $p\cup q$ from being a condition is that there must be an $x\in 2^\om$ and an $s,s\concat(n)\in T^+$ such that $$(s,x),(s\concat(n),x)\in p\cup q.$$ But now for each $p\in A$ let $H_p:X\to [T^+]^{<\omega}$ be the finite partial function defined by $$H_p(x)=\{s\in T^+: (s,x)\in p_1\}$$ where $X=\{x:\exists s\in T^+ \; (s,x)\in p_1\}$. Then $\{H_p:p\in A\}$ is an uncountable antichain in the order of finite partial functions from $2^\om$ to $[T^+]^{<\omega}$. But this is impossible. \qed It is easy to see that it has property K, in fact, it is $\si$-centered, so ccc productive. It follows that the direct sum $$\poset=^{def}\sum\{\poset_{\al+1}\;\;:\;\;2\leq \al<\om_1\}$$ also has the countable chain condition. To obtain our model for Theorem \ref{mainthm} start with a countable transitive model of ZFC, $M$, and do a finite support iteration of $\poset$ of length $\om_2$, denoted $\poset^{\om_2}$. We let $\poset^\al$ be the iteration of $\poset$ up to length $\al$. Fix $T$ a nice $\al$-tree for some $\al$. Given $G$ $\poset_\al$-generic over $M$, for each $s\in T$ define $U_s^G\su 2^\om$. For $s\in T^*$ define $U_s^G=[t]$ if there exists $p\in G$ such that $p_0(s)=t$. Note that by genericity such a $t$ will always exist, i.e., for any $q$ there exists $p\leq q$ such that $s$ is in the domain of $p$. For $s\in T^+$ define $$U_s^G=\bigcap_{n<\om}\sim U_{s\concat(n)}^G.$$ Note that $U_s^G$ is a $\bpi0\al$-set where $\al=\rank_T(s)$. \begin{lemma} For any $x\in 2^\om\cap M$ and $s\in T^+$ and $G$ $\poset_\al$-generic over $M$ $$x\in U_s^G \rmiff\exists p\in G\;\; (s,x)\in p$$ \end{lemma} \proof To simplify notation write $(s,x)\in G$ instead of $\{(s,x)\}\in G$ or there exists $p\in G$ with $(s,x)\in p$. Fix $x$ and $s$. It is easy to see that the following sets are dense: \par\noindent (if $\rank_T(s)=1$) $D=\{p\in\poset_\al\;:\; (s,x)\in p \rmor \exists n,t \;\; p_0(s\concat(n))=t \rmand x\in [t]\}$ \par\noindent (if $\rank_T(s)>1$) $E=\{p\in\poset_\al\;:\; (s,x)\in p \rmor \exists n \; (s\concat(n),x)\in p\}$ \noindent By definition $x\in U_s^G$ iff $x\notin U_{s\concat(n)}^G$ for all $n$. \noindent If $\rank_T(s)>1$, then by induction: $x\notin U_{s\concat(n)}^G$ for all $n$ iff $(s\concat(n),x)\notin G$ for all $n$ \noindent Since $E$ is dense: $(s\concat(n),x)\notin G$ for all $n$ iff $(s,x)\in G$. \noindent If $\rank_T(s)=1$, then $x\notin U_{s\concat(n)}^G$ for all $n$ iff for all $p\in G$ if $p_0(s\concat(n))=t$ then $x\notin [t]$. \noindent Since $D$ is dense: for all $p\in G$ if $p_0(s\concat(n))=t$ then $x\notin [t]$ iff $(s,x)\in G$. \qed \begin{define} Canonical names. For any poset $\poset$ the canonical names $\cn(\poset)$ for an element of $2^\om$ are defined as follows. $\tau\in\cn(\poset)$ iff there exists $(A_n^0,A_n^1\;:\;n<\om)$ such that $A_n^0\cup A_n^1\su\poset$ is a maximal antichain and $$\tau=\{(p,\check{(n,i)})\;:\; n<\om, i<2, \rmand p\in A^i_n\}.$$ \end{define} \begin{define} Nice conditions. Let $T_\al$ for $2\leq \al<\om_1$ be the nice $\al$-trees used to define $\Pi_{\al}$-forcing $\poset_\al$. $\poset$ For $p\in\poset^\al$ we say the $p$ is nice iff $p(0)\in\poset$ and for all $\ga$ with $0<\ga<\al$ $p(\ga)$ is a name for a finite set $p_0\cup p_1$ where $$p_0:\bigcup_{2\leq\al<\om_1}(\{\al+1\}\times T^\star_{\al+1})\to 2^{<\om}$$ is a finite partial map and $$p_1\su \bigcup_{2\leq\al<\om_1}\{\al+1\}\times (T^+_{\al+1}\times \cn(\poset_\ga))$$ is finite. For every $\tau$ in the range of $p_1$ there is a $t_\tau\in 2^{<\om}$ such that $p\res\ga\forces t_\tau\su\tau$ and for all $\al,s,n,\tau,\si,r$ \begin{enumerate} \item if $(\al,(s,\tau)),(\al,(sn,\si))\in p_1$ then $t_\tau\perp t_\si$ \item if $(\al,(s,\tau))\in p_1$ and $p_0(\al,sn)=r\in 2^{<\om}$, then $t_\tau\perp r$. \end{enumerate} \end{define} The nice conditions are dense so from now on we will assume all conditions are nice. \begin{define} Rank. Given $H\su 2^\om$, nice $p\in\poset^\al$, and $\tau\in\cn(\poset^\al)$ define $\rank(p,H)$ and $\rank(\tau,H,p)$ by induction on $\al$. \begin{enumerate} \item For $\poset_\al$ ($\Pi_\al$-forcing), if $p=p_0\cup p_1\in\poset_\al$ then $$\rank(p,H)=\max\{\rank_{T_\al}(s)\;:\; \exists x\in 2^\om\sm H\;\; (s,x)\in p_1\}$$ \item For $p\in\poset=\sum\{\poset_{\al+1}\;\;:\;\;2\leq \al<\om_1\}$ $$\rank(p,H)=\max\{\rank(p_\al,H)\;:\;\al<\om_1\}$$ \item For $\ga$ a limit ordinal and $p\in\poset^\ga$ $$\rank(p,H)=\max\{\rank(p\res\be, H)\;:\; \be<\ga\}.$$ \item For $\tau\in\cn(\poset^\ga)$ and $p\in\poset^\ga$, $\rank(\tau,H,p)$ is the least $\be$ such that for every $n<\om$ $$Q=^{def}\{q\in\poset^\ga\;:\; q\perp p \rmor\rank(q,H)\leq\be\} \mbox{ decides ``}\tau(n)=0\mbox{''}.$$ By which we mean $$\{r\in\poset^\ga\;:\; \exists q\in Q\;\;\; r\leq q\rmand (q\forces\tau(n)=0 \rmor q\forces\tau(n)=1)\}$$ is dense in $\poset^\ga$. \item For $p\in\poset^\ga\star\name\poset$ $\;\;\;\;\; N_p(\ga)=\{\tau\;:\; \exists \al<\om_1\;\exists s\in 2^{<\om} \;(\al,(s,\tau)\in p(\ga)\}$ $$\rank(p,H)=\max\{\rank(p\res\ga,H),\rank(\tau,H,p\res\ga)\::\;\tau\in N_p(\ga)\}.$$ \end{enumerate} \end{define} A set of conditions $Q$ decides $\theta$ iff for every generic $G$ there is a $q\in Q\cap G$ which forces $\theta$ or forces $\neg\theta$. \begin{lemma} (ccc) \label{ccc} For any countable $P\su\poset^\ga$ and countable $N\su\cn(\poset^\ga)$ there is a countable $H\su 2^\om$ such that $\rank(p,H)=0$ for every $p\in P$ and $\rank(\tau,H,1)=0$ for every $\tau\in Q$. \end{lemma} \proof Let $\poset^\ga,P,Q\in\nn \elemsub H_\ka$ where $\nn$ is a countable elementary substructure of the hereditarily of cardinality less than $\ka$ sets for some sufficiently large regular $\ka$. Take $H=\nn\cap 2^\om$. Then for any $p\in \nn\cap \poset^\ga$ and $\tau\in\nn\cap\cn(\poset^\ga)$ we have that $\rank(p,H)=0$ and $\rank(\tau,H,1)=0$. % ??? fill in more proof \qed \begin{define} $|\cdot|$ abbreviations for $\rank$. For the next two lemmas (meet \ref{meet} and rank \ref{rank}) we will fix a countable $H\su 2^\om$ and use the abbreviations: $$|p|=\rank(p,H) \;\;\; \rmand \;\;\;|\tau|(p)=\rank(\tau,H,p).$$ \end{define} \begin{lemma}\label{meet} (Meet lemma) If $G$ is $\poset^\al$-generic over $M$ and $(q_i\in G:i0$. Let $B(v)=\conj_{n<\om} B_n(v)$ where $B_n(v)$ $\bsi0{\beta_n}$ for some $\be_n<\be$. If for contradiction $\hat{p}$ does not force $B(\tau)$, then there exists $q\leq\hat{p}$ and $n<\om$ such that $q\forces \neg B_n$. By induction there exists $\hat{q}$ compatible with $q$, $|\hat{q}|\leq\be_n$ and $\hat{q}\forces \neg B_n$. Since $q$ extends $\hat{p}$ it follows that $\hat{q},\hat{p}$ are compatible. Since $|\hat{q}|\leq\be_n<\be$ we have that $\hat{q}$ is compatible with $p$. This is a contradiction since $p\forces B_n(\tau)$. \qed \begin{prop} Suppose $G$ $\poset^{\om_1}$-generic over $M$. Then for any $Y\in M$ and $\al<\om_1^M$ if $M\models Y\su 2^\om \rmand |Y|=\om_1$, then $$M[G]\models \forall \al<\om\; \forall V\in\bsi0\al \;\;\;V\cap Y \neq U^{G_0}_{\al,\langle\rangle}\cap Y.$$ Here $U^{G_0}_{\al,\langle\rangle}$ is the generic $\bpi0\al$ set added by the first coordinate's $\Pi_\al$-forcing, namely $$U^{G_0}_{\al,\langle\rangle}=\{x\in 2^\om\cap M\;:\; \exists p\in G \; (\al,(\langle\rangle,x))\in p(0)\}.$$ \end{prop} \proof Let $V$ be a universal $\bsi0\al$-set coded in $M$. Suppose $$p_0\forces\forall y\in Y\;\; (y\in V_\tau \rmiff y\in U^{G_0}_{\al,\langle\rangle})$$ Using ccc Lemma \ref{ccc} choose $H\su 2^\om$ countable so that $|p|=\rank(p_,H)=0$ and $|\tau|=\rank(\tau,H,1)=0$. Take any $y\in Y\sm H$. Let $p_1(0)=p(0)\cup (\al,(\langle\rangle,y))$ and $p_1\res[1,\om_2)=p_0\res[1,\om_2)$, Note that $p_1\forces y\in U^{G_0}_{\al,\langle\rangle}$ and hence $p_1\forces y\in V_\tau$. Now $B(v)=^{def} y\in V_v$ is a $\bsi0\al$ predicate coded in $M$. Let $B(v)=\disj_{n<\om}B_n(v)$ where $B_n(v)$ is a $\bpi0{\be_n}$ predicate with $\be_n<\be$. Find $p\leq p_1$ and $n<\om$ such that $p\forces B_n(\tau)$. By Proposition \ref{mainpoint} there is a condition $\hat{p}$ compatible with $p$ such that $\hat{p}\forces B_n(\tau)$ and $\rank(\hat{p},H)\leq\be_n<\be$. By using the meet Lemma \ref{meet} we may assume $\hat{p}\leq p_0$. Hence it follows $\hat{p}\forces y y\in U^{G_0}_{\al,\langle\rangle}$. But by the definition of rank since $y\notin H$, there is some sufficiently large $m<\om$ such that $r(0)=\hat{p}(0)\cup (\al,(\langle m \rangle,y))$ is consistent. Letting $r\res[1,\om_2)=\hat{p}\res[1,\om_2)$ leads to a contradiction: $$r\forces B_n(\tau)$$ $$r\forces (\disj_{n<\om} B_n(\tau))\rmiff y\in U^{G_0}_{\al,\langle\rangle}$$ $$r\forces y\notin U^{G_0}_{\al,\langle\rangle}$$ \qed \bigskip\noindent {\bf Claim}. $M[G]\models\forall Y\in [2^\om]^{\om_1}\;\;\ord(Y)=\om_1$. \bigskip This follows from two standard facts: \begin{enumerate} \item $\forall Z\in \pow(\om_1)^{M[G]}\;\;\exists \al_0<\om_2^M\;\; Z\in M[G_{\al_0}]$ \item $\forall G \;\;(\poset^{\om_2})^M$ generic over $M$ $\;\;\forall \al_0<\om_2^M$ $\exists H \;\;(\poset^{\om_2})^{M[G_{\al_0}]}$ generic over $M[G_{\al_0}]$ such that $M[G]=M[G_{\al_0}][H]$. \end{enumerate} This concludes the proof of Theorem \ref{mainthm}. \section{The sigma-algebra of abstract rectangles} \begin{thm}\label{chrectangle} (Rao 1968 \cite{rao}, Kunen \cite{kunen}) Assume the continuum hypothesis then every subset of the plane is in the $\si$-algebra generated by the abstract rectangles. In fact, at level two. \end{thm} \proof It is enough to see that $\pow(\om_1\times\om_1)=\si\{A\times B\;:\;A,B\su\om_1\}$, i.e. every subset of $\om_1\times\om_1$ is in the $\si$-algebra generated by the abstract rectangles. \begin{define} \begin{itemize} \item $\rr=\{A\times B\;:\;A,B\su\om_1\}$ \item $\Sigma_0(\rr)=\Pi_0(\rr)=\rr$ \item $\Pi_\al(\rr)=\{\om_1\times\om_1\sm P\;:\; P\in\Sigma_\al(\rr)\}$ \item $\Sigma_\al(\rr)=\{\bigcup_{n<\om}P_n\;:\; P_n\in\bigcup_{\be<\al}\Pi_\be(\rr)\}$ \item $\si\{A\times B\;:\;A,B\su\om_1\}=\si\rr= \bigcup_{\al<\om_1}\Sigma_\al(\rr)=\bigcup_{\al<\om_1}\Pi_\al(\rr)$ \item $\bool(\rr)=$ smallest family containing $\rr$ and closed under finite union and complementation \end{itemize} \end{define} Note that $\bool(\rr)\su \Sigma_1(\rr)\cap \Pi_1(\rr)$. Also $\Sigma_\al(\rr)$ for $\al>0$ is closed under countable union and finite intersection. \begin{lemma} For $f:2^\om\to 2^\om$, the $\graph(f)\in\Pi_1(\{A\times B\;:\; A,B\su 2^\om\})$. \end{lemma} \proof For any $s\in 2^{<\om}$ let $D_s=f^{-1}([s])$. Then the following are equivalent for any $x,y\in 2^\om$: \begin{itemize} \item $f(x)=y$ \item $\forall s(s\su f(x) \rmiff s\su y)$ \item $\forall s(x\in A_s \rmiff y\in [s]$ \item $(x,y)\in\bigcap_{s\in 2^{<\om}}(D_s\times [s])\cup (\sim D_s\times \sim [s])$ \end{itemize} \qed Note that the Lemma is also true for any partial function $f:D\to 2^\om$ for some $D\su 2^\om$. Since if $\hat{f}\supseteq f$ is total, then $$\graph(f)=\graph(\hat{f})\cap (D\times 2^\om) \in \Pi_1(\rr).$$ Now we prove Theorem \ref{chrectangle} that $\pow(\om_1\times\om_1)=\Sigma_2(\rr)$. Suppose $A$ is a subset of $\om_1\times\om_1$ with the property that $\be\leq\al$ for every $(\al,\be)\in A$. Let $f_n:\om_1\to\om_1$ be partial functions for $n<\om$ so that for any $\al<\om_1$ $$\{\be\;:\; (\al,\be)\in A\}=\{f_n(\al)\;:\; n<\om\}.$$ It follows that $A=\bigcup_{n<\om}\graph(f_n)$ is $\Sigma_2(\rr)$. Now any subset of $\om_1\times\om_1$ can be written as a union $A\cup B$ where $B$ has the property that $\al\leq\be$ for any $(\al,\be)\in B$. By symmetry $B\in\Sigma_2(\rr)$ and so $(A\cup B)\in\Sigma_2(\rr)$. \qed \begin{thm} (Kunen \cite{kunen} 1968) Assume Martin's axiom, then every subset of the plane is in the $\si$-algebra generated by the abstract rectangles at level two. In the Cohen real model or the random real model the well-ordering on the continuum is not in the $\si$-algebra generated by the abstract rectangles. \end{thm} \begin{thm} (Rothberger \cite{roth} 1952) Suppose that $2^{\om}=\om_2$ and $2^{\om_1}=\om_{\om_2}$ then the $\si$-algebra generated by the abstract rectangles in the plane is not the power set of the plane. \end{thm} \proof Let $H_\al$ for $\al<\aleph_{\om_2}$ list all countable subsets of $\pow(\om_1)$. Let $\si H_\al$ be the $\si$-algebra generated by $H_\al$. Note that $|\si H_\al|\leq |2^\om|=\om_2$ since $H_\al$ is countable. For each $\be<\om_2$ choose $X_\al\su \om_1$ with $X_\al\notin \bigcup_{\al<\aleph_\be}\si H_\al$. Let $X=\bigcup_{\be<\om_2}\{\be\}\times X_\be$. \bigskip {\bf Claim}. $X\notin \si\{A\times B\;:\; A\su\om_2 \rmand B\su\om_1\}$. \bigskip Suppose for contradiction that $$X\in \Sigma_\ga(\{A_n\times B_n\su \om_2\times\om_1\;:\; n<\om \}).$$ It is easy to see that the cross sections satisfy: $$\forall \be<\om_2 \;\; X_\be\in \Sigma_\ga(\{B_n \;:\;n<\om\}).$$ But if $H_{\al_0}=\{B_n \;:\;n<\om\}$ where $\al_0<\om_{\be_0}$, then $X_{\be_0}\notin \si H_{\al_0}$, which is a contradiction. \qed Note Rothberger states this result in more generality, this is the simplest case. \begin{thm}\label{bbmbdd} (Bing, Bledsoe, Mauldin \cite{BBM} 1974) If 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$. \end{thm} \proof This is more general: \bigskip\noindent {\bf Claim}. For any cardinal $\ka$ if $\si\{A\times B\;:\; A,B\su\ka\}=\pow(\ka\times\ka)$, then there exists $\al<\om_1$ such that $\Pi_\al(\{A\times B\;:\; A,B\su\ka\})=\pow(\ka\times\ka)$. \bigskip Suppose not. Take $P_\al\su\ka$ for $\al<\om_1$ pairwise disjoint and cardinality $\ka$. For each $\al<\om_1$ take $A_\al\su P_\al \times P_\al$ such that $$A_\al\notin \Pi_\al(\{A\times B\;:\; A,B\su \ka\}).$$ Let $A=\bigcup_{\al<\om_1}A_\al$. Note that for any $\al<\om_1$ $(P_\al\times P_\al)\in \Pi_1$. It follows that if $A\in\Pi_{\al_0}$, then for any $\al<\om_1$ $A_\al=A\cap (P_\al\times P_\al)\in \Pi_{\al_0}$, which is a contradiction. \qed \begin{thm}\label{qomega1} (Miller \cite{hier} \footnote{I proved this on the plane trip back to Berkeley from the January 1977 AMS-ASL meeting in St. Louis. It was so cold that year the AMS vowed never to have their January meetings anywhere but warm places. It was late at night; the plane was pretty much empty and was delayed due to excessive ice on the wings, so they opened up the bar cart as we sat on the tarmac.}) If every subset of a separable metric space $X$ is Borel in $X$, then for some countable $\al$ every subset of $X$ is $\Sigma_\al^0$ in $X$. \end{thm} For the proof, we will need the following two Lemmas. \begin{lemma}\label{rectangle} Suppose there exists $X\su 2^\om$, $X=\{x_\al:\al<\ka\}$, and there exists $\al<\om_1$ such that for every $\ga<\ka$ every $Y\su \{x_\be:\be<\ga\}$ is $\bsi0\al$ in $X$. Then $$\Sigma_\al\{A\times B\;:\;A,B\su\ka\}=\pow(\ka\times\ka).$$ \end{lemma} \proof Consider any $A\su\ka\times\ka$ such that $\be\leq\al$ for any $(\al,\be)\in A$. Let $X=\{x_\al\;:\;\al<\ka\}$ and let $V\su 2^\om\times 2^\om$ be a universal $\bsi0\al$-set. For each $\al<\ka$ choose $y_\al\in 2^\om$ distinct such that $$\forall \be<\ka \;\;\;(\al,\be)\in A \rmiff (y_\al,x_\be)\in V \rmiff x_\be\in V_{y_\al}.$$ Define $F:\ka\times\ka\to X\times Y$ by $F(\al,\be)=(x_\al,y_\be)$. Note that $F$ is a rectangle preserving bijection such that $F(A)=V\cap (X\times Y)$. Note that $$V\in \bsi0\al\{C_n\times D_n\;:\;n<\om\}$$ where $C_n,D_n$ are clopen subsets of $2^\om$. It follows that $$A\in\bsi0\al(\{\al:y_\al\in C_n\}\times \{\be:x_\be\in D_n\}).$$ By a symmetrical argument we can handle any $B\su\ka\times\ka$ where $\be\geq\al$ for any $(\al,\be)\in B$, and hence any set of the form $A\cup B$. \qed \begin{lemma} \label{diagonal} If $X\su 2^\om$, every subset of $X$ is Borel in $X$, $\om<\ka=|X|$, and $\si\{A\times B\;:\; A\times B\su \om_1\times\ka\}=\pow(\om_1\times\ka)$, then $\ord(X)<\om_1$. \end{lemma} \proof Every rectangle $A\times B\su X\times X$ is Borel in $X\times X$, so every subset of $X\times X$ is Borel in $X$. If $\ord(X)=\om_1$, then for every $\al<\om_1$ choose $H_\al\su X$ such that $H_\al\notin \bsi0\al(X)$. Choose $x_\al\in X$ for $\al<\om_1$ distinct. Let $H=\bigcup_{\al<\om_1}\{x_\al\}\times H_\al$. If $H$ is $\bsi0{\al_0}$ in $X\times X$, then $H_\al$ is $\bsi0{\al_0}$ in $X$ for all $\al<\om_1$. This is a contradiction. \qed \noindent Proof of Theorem \ref{qomega1}: Let $X=\{x_\al\;:\;\al<\ka\}$ and prove the Theorem by induction on $\ka$. \bigskip\noindent {\bf Case}. $\ka=\om_1$. We are done by Lemma \ref{diagonal} and Theorem \ref{chrectangle} since $$\Sigma_2\{A\times B\;:\; A,B\su \om_1\times\om_1\}=\pow(\om_1\times\om_1).$$ \bigskip\noindent {\bf Case}. $\cof(\ka)=\om$. Let $X=\bigcup_{n<\om}X_n$ pairwise disjoint and each $|X_n|<\ka$. By induction $\ord(X_n)<\om_1$ for each $n<\om$. Choose countable $\al$ so that $\ord(X_n)\leq\al$ and each $X_n$ is $\bsi0\al$ in $X$. For any $A\su X$ we have that $A\cap X_n$ is $\bsi0\al$ in $X$ and so $X\cap A=\bigcup_{n<\om}A\cap X_n$ is $\bsi0\al$ in $X$. \bigskip\noindent {\bf Case}. $\cof(\ka)>\om_1$. Define $X_\al=\{x_\be:\be<\al\}$. Note that $\ord(X_\al)$ for $\al<\ka$ is a nondecreasing function and so there is a $\be<\om_1$ such that $\ord(X_\al)\leq\be$ all $\al<\ka$. Similarly there is a countable $\ga\geq\be$ such that every $X_\al$ is $\bsi0\ga$ in $X$. To see this note that for $\al<\be$, if $X_\al$ is $\bsi0\ga$ in $X_\be$ and $X_\be$ is $\bsi0\ga$ in $X$, then $X_\al$ is $\bsi0\ga$ in $X$. It follows that every $Y\su X$ with $Y\su X_\al$ for some $\al<\ka$ is $\bsi0\ga$ and so by Lemma \ref{rectangle} we have that $\Sigma_\al\{A\times B\;:\;A,B\su\ka\}=\pow(\ka\times\ka).$ Hence we are done by Lemma \ref{diagonal}. \bigskip\noindent {\bf Case}. $\cof(\ka)=\om_1$. Let $\ka_\al$ for $\al<\om_1$ be a cofinal in $\ka$ increasing sequence. \bigskip {\bf Claim}. There exists $\al_0<\om_1$ such that $X_{\ka_\al}$ is $\bpi0{\al_0}$ in $X$ for all $\al<\om_1$. pf: Let $Q=\{(\al,\be)\;:\; \al<\om_1\rmand \be\leq\ka_\al\}\su \om_1\times\ka$. Then its complement $\sim Q=\{(\al,\be)\;:\; \ka_\al<\be\}$ has countable cross sections, so there exists partial functions $f_n:\ka\to\om_1$ for $n<\om$ such that for any $\be<\ka$ $$\{\al:(\al,\be)\in\sim Q\}=\{f_n(\be):n<\om\}$$ equivalently $$\sim Q=\bigcup_{n<\om}\graph(f_n).$$ Similar to the proof of Theorem \ref{chrectangle} we get that $$\sim Q\in\Sigma_2(\{A\times B: A\su\om_1, B\su\ka\}.$$ And therefor $Q\in\Pi_2(\{A\times B: A\su\om_1, B\su\ka\}$. Now since every rectangle in $X\times X$ is Borel in $X\times X$ we get that $\{(x_\al,x_\be)\;:\;\be\leq \ka_\al\}$ is Borel in $X\times X$. If it is $\bpi0{\al_0}$ in $X\times X$, then so are all its cross sections and so we are done. \bigskip {\bf Claim}. Suppose $\ord(X_{\ka_\al})=\be_\al$ which is countable by induction, then $\sup_{\al<\om_1}\be_\al<\om_1$. pf: Suppose not and choose $\al_i<\om_1$ for $0\al_0$ and $\be_{\al_{i+1}}>\be_{\al_i}+\om$. For each $i<\om_1$ let $Y_i=X_{\ka_{i+1}}\sm X_{\ka_{i}}$. The $Y_i$ are pairwise disjoint, $\ord(Y_i)=\be_{i+1}$, and $Y_i$ is $\bpi0{\al_0+1}$ in $X$. Choose $A_i\su Y_i$ which is not $\bpi0\al_i$ in $Y_i$. But then $A=\bigcup_{i<\om_1} A_i$ is not Borel in $X$, since $A_i=A\cap Y_i$. \bigskip It follows from the second Claim and Lemmas \ref{rectangle} and \ref{diagonal} that $\ord(X)<\om_1$. This proves Theorem \ref{qomega1}. \qed \begin{thm}\label{qalpha} (\cite{hier}) For any countable $\al$ it is consistent to have a separable metric space $X$ in which every subset is Borel and the order of $X$ is $\al$. Furthermore in this model for successor $\al=\al_0+1\geq 3$ for any $Z\su 2^\om$ if every subset of is $\bsi0{\al_0}$ in $Z$, then $Z$ is countable. \end{thm} We just prove this for countable successor ordinals $\al_0+1$ greater than two. For limit $\al$ see \cite{hier}. \begin{define} $\poset(T,Y,X)$. Fix countable $\al_0\geq 2$. This forcing is similar to $\Pi_{\al_0+1}$ forcing (Definition \ref{defpialpha}). Assume $Y\su X\su 2^\om$. Recall that definition uses a nice $\al_0+1$ tree $T$ which will remain fixed throughout the proof. We denote terminal nodes of $T$ by $T^*$ and interior nodes $T^0=T\sm(\{\langle\rangle\}\cup T^*)$. Then $p\in \poset(T,Y,X)$ iff $p=p_0\cup p_1$ finite with $p_0:T^*\to 2^{<\om}$ finite partial and finite $p_1\su T^0\times X$ subject to the consistency demands: \begin{itemize} \item if $((n),x)\in p_1$, then $x\notin Y$ \item if $(s,x)\in p_1$ and $(sn,y)\in p_1$, then $x\neq y$ \item if $(s,x)\in p_1$ and $p_0(sn)=r$, then $x\notin [r]$ \end{itemize} \end{define} Note that we only attach elements of $X$ to the interior nodes of $T$, we do not attach any reals to the top node $\langle\rangle$ of $T$, and we only attach reals from $X\sm Y$ to the rank $\al_0$ nodes of $T$, i.e., those of the form $(n)$. We remark that $\poset(T,\emptyset,2^\om)$ is the same as the direct sum of countably many copies of $\Pi_{\al_0}$-forcing. We could think of the first condition as equivalent to putting all $(\langle\rangle,y)$ for $y\in Y$ into $p_1$. \begin{define} $U^G_s$.\label{defU} Similar to before for a generic $G$ a $\poset(T,Y,X)$-filter, define $U_s^G\su 2^\om$ for $s\in T$. For $s\in T^*$ define $U^G_s=[r]$ iff $p_0(s)=r$ for some $p\in G$. For $s\in T\sm T^*$ define $U^G_s=\bigcap_{n<\om}\sim U^G_{sn}$. \end{define} \begin{lemma}\label{easy} For $G$ any generic $\poset(T,Y,X)$-filter: \begin{enumerate} \item For any $s\in T^0$ and $x\in X$ $x\in U^G_s$ iff $\{(s,x)\}\in G$. \item $U^G_{\langle\rangle}\cap X=Y$. \end{enumerate} \end{lemma} \proof For any $s\in T^0$ and $x\in X$ define $D_{s,x}\su\poset_{\al_0+1}(Y,X)$ by $p\in D_{s,x}$ iff \begin{itemize} \item $(s,x)\in p$ or \item $\exists n<\om\;\; (sn,x)\in p_1$ or \item $\exists r \in 2^{<\om}\;\; p_0(sn)=r \rmand x\in [r]$. \end{itemize} Then $D_{s,x}$ is dense. Note for $n<\om$ and $y\in Y$ you can never add $((n),y)$ however you will be add $((n,m),y)$ for some sufficiently large $m$. (1) Suppose $x\in U_s^G=\bigcap_{n<\om}\sim U_{sn}^G$, then $x\notin U_{sn}^G$ for all $n$. Hence by induction for all $n$ for all $p\in G$ ($(sn,x)\notin p$ or $x\notin [p_0(sn)]$) if $\rank_T(s)=1$. Since $D_{s,x}$ is dense we have that $\{(s,x)\}\in G$. Conversely, suppose $\{(s,x)\}\in G$. Then for every $n<\om$ and $p\in G$ $(sn,x)\notin p$ or $x\notin [p_0(sn)]$) if $\rank_T(s)=1$. So by induction $x\notin U_{sn}^G$ for all $n$ and by definition of $U_s^G$ we have that $x\in U_s^G$. (2) Suppose $y\in Y$. Fix $n$. By the definition of $\poset(T,Y,X)$ $((n),y)$ is not in any condition. Hence for any $p$ there exists $m$ sufficiently large so that $p\cup\{((n,m),y)\}$ is consistent. It follows that $y\notin U_{(n)}^G$ and so $y\in U_{\langle \rangle}^G$. Conversely, suppose $x\in X\sm Y$. Then $\{p\;:\; \exists n\;\;((n),x)\in p \}$ is dense, so $x\in U_{(n)}^G$ for some $n$ and hence $y\notin U_{\langle \rangle}^G$. \qed Let $M$ be a countable standard model of ZFC+GCH. Fix $X = 2^\om\cap M$ (or any uncountable subset of $2^\om$ in $M$) and $T$ a nice $\al_0+1$-tree in $M$. We will iterate $\poset(T,Y_\al,X)$ for $\al_<\om_2$ with finite support, diagonalizing to get all $Y\su X$. An explicit description of this model is as follows. Let $\poset^0=\poset(T,\emptyset,X)$. Inductively assume that $\poset^\al\su \Sigma_{\be<\al}\poset(T,\emptyset, X)$ (the direct sum). Suppose $\name{Y}_\al$ is a nice $\poset^\al$-name for a subset of $X$, i.e., there exists $(A_x^\al:x\in X)$ where $A_x^\al\su \poset^\al$ is countable and $$\name{Y}_\al=\{(p,\check{x})\;:\; x\in X\rmand p\in A_x^\al\}.$$ Then $p\in\poset^{\al+1}$ iff $p\res\al\in \poset^\al$, $p(\al)\in \poset(T,\emptyset,X)$, and if $p(\al)=p_0\cup p_1$, then whenever $((n),x)\in p_1$ for some $n<\om$ and $x\in X$, then $$p\res\al\forces x\notin \name{Y}_\al$$ or equivalently $(p\res\al)\perp q$ for all $q\in A^\al_x$. For $\lambda\leq\om_2$ a limit ordinal $$\poset^\lambda=\{p\;:\; \forall \al<\lambda \;\;p\res\al\in\poset^\al\rmand \supp(p)\mbox{ is finite }\}\}.$$ where $\supp(p)=^{def}\{\al<\lambda\;:\;p(\al)\neq 1\}$ is the support of $p$. Note that for any $\al<\om_2$, $\Sigma_{\be<\al}\poset(T,\emptyset,X)$ has cardinality $\om_1$. It also has ccc (in fact property K). Note that $p,q\in \poset^\al$ are compatible iff $p\cup q\in \poset^\al$ iff $p\cup q\in \Sigma_{\be<\al}\poset(T,\emptyset,X)$. For $\al<\om_2$ we may regard $$\poset^\al=\{p\in \poset^{\om_2}\;:\; p\res[\al,\om_2) \equiv 1\}.$$ By a standard dovetailing argument in $M$ we may choose the sequence of names $\name{Y}_\al$ so that for any $G$ $\poset^{\om_2}$-generic over $M$ for any $Y\su X$ in $M[G]$ there is an $\al<\om_2^M$ such that $Y_\al^G=Y$. By Lemma \ref{easy} we have that in $M[G]$ every subset of $X$ is $\bsi0{\al_0+1}$ in $X$. Recall that $\poset^0=\poset(T,\emptyset,X)$. Let $U_{(0)}^G$ be the generic $\bpi0\al_0$-set added by $\poset^0$. (Any of the other $U_{(n)}^G$ would do as well.) We will show that there is no $\bsi0\al_0$-set $V\su 2^\om$ in $M[G]$ such that $U_{(0)}^G\cap X=V\cap X$. Given $H\su X$ define $$\rank(p,H)=\max\{\rank_T(s)\;:\:\exists x\in X\sm H\;\exists\al<\om_2\;\; (s,x)\in p(\al)\}.$$ Working in $M$ suppose we are given $\Gamma\in\poset^{\om_2}$ countable and $\tau$ a nice $\poset^{\om_2}$ for an element of $2^\om$. Then by the ccc we can find a countable $H\su X$ and countable $K\su\om_2$ with the following properties: \begin{enumerate} \item $\rank(p,H)=0$ for all $p\in\Gamma$ \item $\forall n\in \om$ $\;\;\;\{p\in\poset^{\om_2}\;:\;\supp(p)\su K \rmand \rank(p,H)=0\}$ decides\footnote{Recall that a set conditions $Q$ decides a sentence $\theta$ iff every generic filter contains a condition in $Q$ which forces either $\theta$ or its negation.} ``$\tau(n)=0$''. \item $\forall x\in H\;\forall \al\in K$ $\{p\in\poset^{\al}\;:\;\supp(p)\su K \rmand \rank(p,H)=0\}$ decides ``$x\in \name{Y}_\al$''. \end{enumerate} The analogue of the meet lemma for this forcing is trivial. \begin{lemma} Meet Lemma. For any $p,q\in\poset^{\om_2}$ we have: $p$ and $q$ are compatible iff $p\cup q\in\poset^{\om_2}$. \noindent The union is defined by $(p\cup q)(\al)=^{def}p(\al)\cup q(\al)$ for each $\al<\om_2$. \end{lemma} \proof Prove by induction that $(p\cup q)\res\al\in\poset^\al$ and extends both $p\res\al$ and $q\res\al$. \qed The union operation preserves rank and support. \begin{lemma} Rank Lemma for $H,K$. Assume $H,K$ satisfy condition 3 above, i.e., $\forall x\in H\;\forall \al\in K$ $\{p\in\poset^{\al}\;:\;\supp(p)\su K \rmand \rank(p,H)=0\}$ decides ``$x\in \name{Y}_\al$''. Suppose $p\in\poset^{\om_2}$ and $1\leq\be<\al_0$. Then there exists $\hat{p}$ compatible with $p$, $\rank(\hat{p},H)\leq\be$, $\supp(\hat{p})\su K$, and for any $q\in\poset^{\om_2}$ with $\rank(q,H)<\be$ and $\supp(q)\su K$, $(p\perp q \Rightarrow \hat{p}\perp q)$. \end{lemma} \proof Extend $p$ to $\tilde{p}$ so that for any $\al,s,x,\lambda$ if $(s,x)\in p(\al)$ and $\rank_T(s)=\lambda$ is a limit ordinal, then for every $i<\om$ with $\rank_T(si)\leq\be+1<\lambda$ there exists $j$ with $(sij,x)\in \tilde{p}(\al)$. The definition of nice tree tells us there are at most finitely many such $i$. Let $G$ be $\poset^{\om_2}$-generic with $\tilde{p}\in G$. Choose $\Gamma\su G$ finite so that \begin{enumerate} \item[(a)] $\forall q\in\Gamma\;\;\rank(q,H)=0$ and $\supp(q)\su K$ \item[(b)] if $((n),x)\in p(\al)$ for some $\al\in K$ and $x\in H$, then there exists $q\in \Gamma$ such that $q\res\al\forces x\notin \name{Y}_\al$. \end{enumerate} Note that in (b) it must be that $p\res\al\forces x\notin \name{Y}_\al$. Working in $M$ define $\hat{p}$ as follows: for $\al\in K$ $$\hat{p}(\al)=\bigcup\{q(\al)\;:\;q\in\Gamma\}\cup\{(s,x)\in\tilde{p}_1(\al)\;:\; \rank_T(s)\leq\be\rmor x\in H\}\cup \tilde{p}_0(\al)$$ and $\hat{p}(\al)=1$ for $\al\notin K$. We prove that $\hat{p}\leq q$ for each $q\in\Gamma$ and $\rank_T(\hat{p})\leq\be$. Note that $\be<\al_0=\rank_T((n))$ so we have retained no conditions of the form $((n),x)$ for $x\notin H$, i.e., if $((n),x)\in\hat{p}$, then $\al\in K$ and $x\in H$. So $\hat{p}\res\al\leq q\res\al$ for some $q\in\Gamma$ such that $q\res\al\forces x\notin \name{Y}_\al$ and so $\hat{p}\res\al\forces x\notin \name{Y}_\al$. This shows that $\hat{p}$ is a condition. We check that it satisfies the Lemma. Since $\tilde{p}\leq p$ and $\tilde{p},\hat{p}$ are both in $G$, we have that $p$ and $\hat{p}$ are compatible. Suppose $\rank(q,H)<\be$ and $\supp(q)\su K$. We need to show that $p\perp q\rightarrow \hat{p}\perp q$. Assume $p\perp q$, hence $p\cup q$ is not a condition so there must be $\al\in\supp(p)\cap\supp(q)$ (so $\al\in K$) $(p\cup q)\res\al\in\poset^{\al}$, but $p(\al)\cup q(\al)\notin \poset(T,\name{Y}_\al,X)$. Therefor at least one of the following cases occurs: \bigskip Case 1. For some $s\in T^*$ we have $p_0(\al)(s)\neq q_0(\al)(s)$. \medskip\noindent But $\hat{p}_0(\al)(s)=p_0(\al)(s)$, so $\hat{p}(\al)\perp q(\al)$. \bigskip Case 2. For some $s,r,n$ with $s\in T^0$ and $sn\in T^*$ and $x\in X$: \par\noindent ($p_0(\al)(sn)=r$ or $q_0(\al)(sn)=r$) and $(s,x)\in p_1(\al)\cup q_1(\al)$, but $x\in [r]$. \medskip\noindent In this case, $\rank_T(s)=1\leq\be$ and hence $(s,x)\in\hat{p}_1(\al)$ if $(s,x)\in{p}_1(\al)$. So if $q_0(\al)(sn)=r$, then $\hat{p}(\al)\perp q(\al)$. The other possibility is that ${p}_0(sn)=r$ and $(s,x)\in q_1(\al)$. Then since $\hat{p}_0(sn)={p}_0(sn)$, we also have $\hat{p}(\al)\perp q(\al)$. \bigskip Case 3. For some $s,sn\in T^0$ and $x\in X\;\;\;$ $(s,x),(sn,x)\in p_1(\al)\cup q_1(\al)$. \medskip\noindent In this case, if $x\in H$, then $(s,x),(sn,x)\in \hat{p}_1(\al)\cup q_1(\al)$ and so $\hat{p}(\al)\perp q(\al)$. Suppose $x\notin H$, then one of the following occurs: \medskip\noindent 1. $(sn,x)\in{p}_1(\al)$ and $(s,x)\in q_1(\al)$ \par\noindent 2. $(s,x)\in{p}_1(\al)$ and $(sn,x)\in q_1(\al)$ \medskip For (1) since $\rank(q,H)<\be$ we have that $\rank_T(sn)<\rank_T(s)<\be$ and so by the definition of $\hat{p}$ we have that $(sn,x)\in\hat{p}_1(\al)$ so $\hat{p}(\al)\perp q(\al)$. For (2) we have that $\rank_T(sn)<\be$ because $\rank(q,H)<\be$. If $\rank_T(s)\leq\be$, then $(s,x)\in\hat{p}_1(\al)$ so $\hat{p}(\al)\perp q(\al)$. Finally we have the possibility that $\rank_T(s)=\lambda>\be$ a limit ordinal. In this case we choose $\tilde{p}(\al)$ so that for some $m$ we have that $(snm,x)\in\tilde{p}_1(\al)$. Since $\rank_T(snm)<\be$, $(snm,x)\in\hat{p}_1(\al)$, and therefor $\hat{p}(\al)\perp q(\al)$. \qed \begin{lemma}\label{nice} Suppose $\tau$ a nice $\poset^{\om_2}$ for an element of $2^\om$ and $H\su X$ and $K\su\om_2$ are countable satisfying \begin{enumerate} \item $\forall n\in \om$ $\;\;\{p\in\poset^{\om_2}\;:\;\supp(p)\su K, \rank(p,H)=0\}$ decides``$\tau(n)=0$''. \item $\forall x\in H\;\forall \al\in K$ $\{p\in\poset^{\al}:\supp(p)\su K, \rank(p,H)=0\}$ decides ``$x\in \name{Y}_\al$''. \end{enumerate} Suppose $B(v)$ is a $\bsi0\be$ predicate for $1\leq\be\leq\al_0$ with parameters from $M$ and $p\in\poset^{\om_2}$ satisfies: $p\forces B(\tau)$. Then there exists $\hat{p}$ compatible with $p$, $\rank(\hat{p},H)<\be$, $\supp(\hat{p})\su K$, and $\hat{p}\forces B(\tau)$. \end{lemma} Case $\be=1$. Suppose $R\su 2^{<\om}$ is in $M$ and $p\forces\exists n\in\om\;\; R(\tau\res n)$. Find $q\leq p$, $n\in\om$, $t\in 2^n$ such that $R(t)$ and $q\forces \tau\res n=\check{t}$. Take $G$ $\poset^{\om_2}$-generic with $q\in G$. By (1) we can choose finite $\Gamma\su G$ such that for all $m\al_0$. Given any $Z\su 2^\om$ of size $\om_1$ in $M[G]$ there will be $\de<\om_2$ with $Z\in M[G_\de]$. We can assume unbounded many $Y_\de$ code the empty set, so by replacing $M$ by the ground model $M[G_\de]$ and forcing with $\poset^{[\de,\om_2)}$, Lemma \ref{lemmaqset} shows that $\ord(Z)>\al_0$. \qed \begin{thm}\label{newproof} (\cite{hier}) 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$. \end{thm} \proof We sketch the proof only for the case of a countable successor $\al=\al_0+1\geq 3$. Start with a countable transitive model $M$ of ZFC+$2^\om=2^{\om_1}=\om_2$. Let $X=2^\om\cap M$. Hence $|X|=\om_2$. Do a finite support iteration (as in the proof of Theorem \ref{qalpha}) of length $\om_2$ of $\poset(T,\name{Y}_\al,X)$ for $\al<\om_2$ making sure to have names for all potential subsets of $X$ of size $\leq \om_1$. It follows from Lemma \ref{rectangle} that $\pow(\om_2\times\om_2)= \Sigma_{\al_0+1}(\{A\times B\;:\; A,B\su\om_2\}$. It also follows by a similar proof to Theorem \ref{qalpha} that in $M[G]$ there is no $Z\su 2^\om$ with $|Z|=\om_1$ such that every subset of $Z$ is $\bsi0{\al_0}$ in $Z$. So we are done by the following: \begin{lemma} (Bing, Bledsoe, Mauldin \cite{BBM}) \label{bbmlem} Suppose $\al<\om_1$, $\om<\ka$, $|2^\ka|=\cc$, and $\pow(\ka\times\cc)=\Sigma_\al(\{A\times B\;:\; A\su\ka,\; B\su\cc\}$. Then there exists $Z\su 2^\om$ with $|Z|=\ka$ and every subset of $Z$ is $\bsi0{\al}$ in $Z$. \end{lemma} \proof Let $Y_\al\su\ka$ for $\al<\cc$ list all subsets of $\ka$. Define $$Y=\{(\be,\al):\be\in Y_\al, \al<\cc\}.$$ Let $\{A_n\times B_n:n<\om\}$ be rectangles with $Y\in\Sigma_\al( \{A_n\times B_n:n<\om\})$. Take $\psi:\ka\to 2^\om$ to be the Marczewski characteristic function: $$\psi(\al)(n)=1\rmiff \al\in A_n.$$ Then $Z=\{\psi(\al)\;:\;\al<\ka\}$ has the required property. Note that the cross sections of a $\bsi0\al$-set are $\bsi0\al$. \qed \section{Universal functions} \begin{thm}\label{mainthmuniv} (Larson, Miller, Steprans, Weiss \cite{univ}) 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 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{thm} \begin{thm}(\cite{univ})\label{abstractuniv} If $2^{<\ka}=\ka$, then there is an abstract universal function $F:\ka\times\ka\to\ka$. \end{thm} \begin{thm}(\cite{univ}) It is relatively consistent with ZFC, that there is no abstract universal function $F:\cc\times\cc\to\cc$. \end{thm} \begin{thm}(\cite{univ})\label{thmborel} There does not exist a Borel function $F:2^\om\times 2^\om\to 2^\om$ such that for every Borel $G:2^\om\times 2^\om\to 2^\om$ there are $h,k:2^\om\to 2^\om$ such that $k$ is Borel and for every $x,y\in 2^\om$ $$G(x,y)=F(h(x),k(y))$$ \end{thm} The following two theorems are proved just like Theorems 8 and 9 of Bing, Bledsoe, and Mauldin \cite{BBM} who only stated it for the square case, e.g., $\ka\times\ka$. \begin{theorem}\label{bbmthm8} (Bing, Bledsoe, and Mauldin Theorem 8 for $\ka=\lambda$) \begin{enumerate} \item The following are equivalent: \begin{enumerate} \item $\bsi0\om_1(\{A\times B:A\su\ka, B\su\lambda\})=\pow(\ka\times\lambda)$ \item for every $\aa\in [\pow(\lambda)]^\ka$ there is $\bb\in[\pow(\lambda)]^\om$ and $\al<\om_1$ such that $\aa\su\bsi0\al(\bb)$ \item for every $\aa\in [\pow(\ka)]^\lambda$ there is $\bb\in[\pow(\ka)]^\om$ and $\al<\om_1$ such that $\aa\su\bsi0\al(\bb)$ \end{enumerate} \item Suppose $\al<\om_1$, then the following are equivalent: \begin{enumerate} \item $\bsi0\al(\{A\times B:A\su\ka, B\su\lambda\})=\pow(\ka\times\lambda)$. \item for every $\aa\in [\pow(\lambda)]^\ka$ there is $\bb\in[\pow(\lambda)]^\om$ such that $\aa\su\bsi0\al(\bb)$ \item for every $\aa\in [\pow(\ka)]^\lambda$ there is $\bb\in[\pow(\ka)]^\om$ such that $\aa\su\bsi0\al(\bb)$ \end{enumerate} \end{enumerate} \end{theorem} \begin{theorem} \label{bbmthm9} (Bing, Bledsoe, and Mauldin Theorem 9 for $\ka=\lambda$) The following are equivalent: \begin{enumerate} \item $\bsi0\om_1(\{A\times B:A\su\ka, B\su\lambda\})=\pow(\ka\times\lambda)$ \item for every $\aa\in [\pow(\lambda)]^\ka$ there is $\bb\in[\pow(\lambda)]^\om$ and $\al<\om_1$ such that $\aa\su\bsi0\al(\bb)$ \item there is $\al<\om_1$ such that for every $\aa\in [\pow(\lambda)]^\ka$ there is $\bb\in[\pow(\lambda)]^\om$ such that $\aa\su\bsi0\al(\bb)$ \item there exists $\al<\om_1$ such that $\bsi0\al(\{A\times B:A\su\ka, B\su\lambda\})=\pow(\ka\times\lambda)$. \end{enumerate} \end{theorem} \begin{define} $X\su 2^\om$ is a strong $Q_\al$-set iff \par\noindent letting $\bb_0=^{def}\{X\cap C\;:\; C\su 2^\om \mbox{ clopen }\}$ then \begin{itemize} \item $\pow(X)=\bsi0\om_1(\bb_0)$ ( $\si$-algebra generated by $\bb_0$ ) and \item $\forall \bb\supseteq \bb_0$ countable $\ord(\bb)=\al$, i.e. $\al$ is the least ordinal such that $\bsi0\al(\bb)=\bsi0\om_1(\bb)$. \end{itemize} \end{define} The above definition is the one we use to verify the existence of a strong $Q_\al$-set in a generic extension. When we force a generic $\bpi0\al$ set it is not $\bsi0\al$ even when we add sets from the ground model as new ``clopen'' sets. \begin{theorem}\label{strongqrectangle} The following are equivalent for a cardinal $\ka$ such that $2^\ka=\cc$ and $\al<\om_1$: \begin{enumerate} \item there exists a strong $Q_\al$-set of cardinality $\ka$ \item $\al$ is the smallest ordinal such that $$\bsi0\al(\{A\times B:A\su\ka, B\su\cc\})=\pow(\ka\times\cc)$$ \item there is a $Q_\al$-set of size $\ka$ but no $Q_\be$-set of size $\ka$ for any $\be<\al$ \item $\al$ is the minimal ordinal for which there is a countable $\bb\su\pow(\ka)$ with $\bsi0\al(\bb)=\pow(\ka)$ \end{enumerate} \end{theorem} \bigskip \proof Assume (1). First note that $\Sigma_\al\{A\times B\;: A\su\ka, B\su \cc\}=\pow(\ka\times \cc\}$. This is proved just like Lemma \ref{rectangle}. Namely, let $\{x_\be:\be<\ka\}\su 2^\om$ be a $Q_\al$-set. Fix $U\su 2^\om \times 2^\om$ a universal $\bsi0\al$ set. Then for any subset $C\su\ka\times\cc$ choose $\{y_\be\in 2^\om:\be<\cc\}$ so that for each $\ga<\ka$ and $\be<\cc$, $(x_\ga,y_\be)\in U$ iff $(\ga,\be)\in C$. Since $U$ is $\bsi0\al$ in the clopen rectangles in $2^\om\times 2^\om$, it follows that $C$ is $\bsi0\al$ in the abstract rectangles on $\ka\times\cc$. Now suppose for contraction that for some $\be<\al$ $$\;\;\Sigma_\be\{A\times B\;: A\su\ka, B\su \cc\}=\pow(\ka\times \cc\}.$$ Let $C\su\ka\times\cc$ be such that the cross sections of $C$ list $\pow(\ka)$. Suppose $C\in\bsi0\be(\{A_n\times A_m:n,m<\om\})$. Consider the Marczewski characteristic function of the sequence of sets $A_n$, i.e., $f:\cc\to 2^\om$ defined by $f(\be)(n)=1$ iff $\be\in A_n$. We can assume that the $A_n$ separate points (by adding a countable sequence of sets if necessary) so that $f$ is a 1-1 function. Let $z_\be=f(\be)$. The function $f$ maps the abstract sets $A_n$ into relatively clopen sets in $Z=\{z_\ga:\ga<\cc\}$. It follows that $\{z_\ga:\ga<\ka\}$ is a $Q_\de$-set for some $\de\leq\be<\al$ which contradicts the definition of ``strong'' $Q_\al$-set. The proof of (2) implies (1) is virtually the same. The fact that $$\bsi0\al(\{A\times B:A\su\ka, B\su\cc\})=\pow(\ka\times\cc)$$ via the Marczewski function gives us a $Q_\al$-set of cardinality $\ka$. The minimality of $\al$ gives us that there is no $Q_\be$-set of size $\ka$ for any $\be<\al$. (3) and (4) are equivalent by using the Marczewski characteristic function. (1) implies (3): Let $\{x_\ga:\ga<\ka\}$ be a strong $Q_\al$-set and suppose $\{y_\ga:\ga<\ka\}$ is a $Q_\be$-set for some $\be<\al$. For any clopen set $C\su 2^\om$ let $C'=\{x_\al:y_\al\in C\}$, then $\bb=\bb_0\cup\{C':C\mbox{ clopen }\}$ has order $\leq\be$ contradicting the definition of strong $Q_\al$-set. (3) implies (1): Any $Q_\al$-set of size $\ka$ must be strong, otherwise by using the Marczewski characteristic function we could produce for some $\be<\al$ a $Q_\be$-set of cardinality $\ka$. \qed \begin{theorem} It is consistent that for every countable $\alpha\geq 2$ there is a strong $Q_\al$-set. \end{theorem} \proof This holds in a model mentioned in \cite{hier} see Theorem 55 and 52. Theorem 55 \cite{hier} states that it is consistent that for every countable $\alpha\geq 2$ there is a $Q_\al$-set. The proof is similar to Theorem 52 in that these sets are all of different cardinality. By an analogous argument to Theorem \ref{qalpha}, in fact, those $Q_\al$-sets are strong $Q_\al$-sets. \qed \begin{thm}\label{remark4.6} Remark 4.6 \cite{univ}. It is consistent that the Borel subsets of the plane are not contained in any bounded level of the $\sigma$-algebra generated by the abstract rectangles. The proof of Theorem \ref{mainthmuniv} shows that in this situation, there does not exist a Borel function $$F:2^\om\times 2^\om\to 2^\om$$ such that for every Borel $H:2^\om\times 2^\om\to 2^\om$ there exist functions $g$ and $h$ from $2^\om$ to $2^\om$ such that $$H(x,y)=F(g(x),h(y))$$ for all $x,y\in 2^\om$. Hence, if we drop the condition that $k$ is Borel in Theorem \ref{thmborel} it is consistent that there be no such Borel $F$. \end{thm} We show that: \begin{theorem} If for unboundedly many $\al<\om_1$ there is a strong $Q_\al$-set, then there is no countable $\al_0$ such that $$ \mbox{Borel}(2^\om\times 2^\om)\su\Sigma_{\al_0}(\{A\times B\;:\; A,B\su 2^\om\}).$$ \proof Let $U\su 2^\om\times 2^\om$ be a universal $\bsi0{\al_0+1}$-set and $X$ a strong $Q_{\al_0+1}$-set. Choose $A_n\times B_n\su 2^\om\times 2^\om$ for $n<\om$ so that $U\in\Sigma_{\al_0}(\{A_n\times B_n\;:\; n<\om\}).$ \end{theorem} Define $$\hh=\{X\cap C\;:\;C \mbox{ clopen }\su 2^\om\}\cup \{B_n\cap X:n<\om\}.$$ \bigskip\noindent {\bf Claim}. $\ord(\hh)\leq\al_0$, so $X$ is not a strong $Q_{\al_0+1}$-set. \proof For any $Y\su X$ there exists $z\in 2^\om$ such that $U_z\cap X=Y$, because $U$ is a universal $\Sigma_{\al_0+1}$-set and $X$ is a $Q_{\al_0+1}$-set. But any cross section of set in $\Sigma_{\al_0}(\{A_n\times B_n\;:\; n<\om\})$ is a set in $\Sigma_{\al_0}(\{B_n\;:\; n<\om\})$. It follows that $Y\in\Sigma_{\al_0}(\hh)$. Hence $\pow(X)=\Sigma_{\al_0}(\hh)$ and so $\ord(\hh)\leq\al_0$. This proves the Claim and hence the Theorem. \qed The following theorem was proved in May 2017. It answers negatively the rectangular form of a question asked by Bing, Bledsoe, and Mauldin \cite{BBM} in the paragraph just before Theorem 10, namely, in Theorem \ref{bbmthm9} (2,3) can we replace ``$\aa\su\bsi0\al(\bb)$'' with ``$\aa\su\bsi0\om_1(\bb)$''? I want to thank Ashutosh Kumar for bringing the problem to my attention. I do not know the answer for the square version of this question. \begin{theorem}\label{bbmanswer} Suppose for unboundedly many $\al<\om_1$ there exists a strong $Q_\al$-set, then there exists an uncountable cardinal $\ka<\cc$ such that \begin{enumerate} \item every family of size $\ka$ of sets of reals is included in a countably generated $\si$-algebra, $\forall \aa\in [\pow(\cc)]^\ka$ $\;\;\exists\bb\in[\pow(\cc)]^\om$ $\;\;\aa\su\bsi0\om_1(\bb)$. \item there is a family of size $\ka$ of sets of reals which is not include in a bounded level of any countably generated $\si$-algebra. $\exists \aa\in [\pow(\cc)]^\ka$ $\;\;\forall\bb\in[\pow(\cc)]^\om$ $\forall \al<\om_1$ $\;\;\aa\not\su\bsi0\al(\bb)$. \end{enumerate} \end{theorem} \proof Let $\Gamma\su\om_1$ be unbounded so that for every $\al\in\Gamma$ there exists a strong $Q_\al$-set $X_\al\su 2^\om$. Note that for $\al<\be$ elements of $\Gamma$ that $|X_\al|<|X_\be|$. Let $\ka_\al=|X_\al|$ and put $\ka=\sup_{\al\in \Gamma}\ka_\al$. Given any family $\aa\su \pow(\cc)$ of size $\ka$ of write $\aa=\bigcup\{\aa_\al:\al\in\Gamma\}$ where $|\aa_\al|=\ka_\al$. By Theorems \ref{bbmthm9},\ref{strongqrectangle} $\aa_\al$ is included in the $\si$-algebra generated by a countable set $\bb_\al$, i.e., $\aa_\al\su \bsi0\al(\bb_\al)$. but then $\bigcup\{\bb_\al:\al\in\Gamma\}$ is included in a countably generated $\si$-algebra and hence so is $\aa$. This proves item (1). To prove (2) note that for each $\al\in\Gamma$ there is $\aa_\al\su\pow(\cc)$ of cardinality $\ka_\al$ which is not in any countably generated $\si$-algebra at a level before $\al$, i.e., $\aa_\al\not\su \bsi0\be(\bb)$ for any countable $\bb\su\pow(\cc)$ and $\be<\al$. It follows that $\aa=\bigcup_{\al\in\Gamma}\aa_\al$ satisfies (2). \qed \section{Universal Functions of Higher Dimension} The main result of this section is from (\cite{univ}). Universal functions $F$ of higher dimensions reduce to countably many cases where the only thing that matters is the arity of the parameter functions, e.g., one of the forms: $G(x,y)=F(h(x),k(y))$ $G(x,y,z)=F(h(x,y),k(y,z),l(x,z))$ $G(x_1,x_2,x_3,x_4)=F(h(x_2,x_3,x_4),k(x_1,x_3,x_4), l(x_1,x_2,x_4),i(x_1,x_2,x_3))$ $\ldots$ $G(x_0,\ldots,x_{n})=F(\vec{x}_s:s\in [n+1]^n)$ $\ldots$ \medskip\noindent Furthermore, each of these forms is consistently weaker than the preceding one. \def\cantor{{2^\om}} \begin{define} A $k$-dimensional universal function is a function $$F:(\cantor)^k \to \cantor$$ such that for every function $G:(\cantor)^k \to \cantor$ there is $h:\cantor \to \cantor$ such that $$G(x_1,x_2,\ldots,x_k) = F(h(x_1),h(x_2),\ldots,h(x_k))$$ for all $(x_1,x_2,\ldots,x_k) \in (\cantor)^k$. \end{define} \begin{prop} Suppose $F(x,y)$ is a universal function, then $F(F(x,y),z)$ is a 3-dimensional universal function. Similarly the existence of a universal function in dimension 2 is equivalent to the existence of a universal function in dimension k for any $k>1$. \end{prop} \proof Given $G(x,y,z)$ define $G_0(u,z)=G(u_0,u_1,z)$ using unpairing, $u=\pair(u_0,u_1)$. By universality of $F$ there are $g,h$ with $G_0(u,z)=F(g(u),h(z))$. Again by universality of $F$ there are $g_0,g_1$ with $g(\pair(u_0,u_1))=F(g_0(u_0),g_1(u_1))$ and hence $G(x,y,z)=F(F(g_0(x),g_1(y)),h(z))$. To prove a 3-dimensional implies a 2-dimensional use unpairing, i.e., put $\hat{F}(u,y)= F(u_1,y,u_2)$ so if $G(x,y)=F(h(x),k(y),j(z))$, then putting $\hat{h}(x)=\langle h(x),j(0)\rangle$ we have $G(x,y)=F(h(x),k(y),j(0))=\hat{F}(\hat{h}(x),k(y)).$ \qed This proposition is true for either Borel or abstract universal functions, but note however that the Baire complexity of $F(F(x,y),z)$ is higher than that of $F$. The question ``Is it consistent that the Borel rank in different dimensions is different ?'', is open. Juris Steprans recently pointed out (Feb 2017) that the obvious attempt to prove that a 3-dimensional universal function implies the existence of a 2-dimensional universal function, namely freezing a coordinate, may not work; i.e., putting $\hat{F}(x,y)=F(x,y,z_0)$, because different $G$ might require different $z_0$. However, it almost works. Here is his proof: Suppose $F:\ka^3\to\ka$ is universal, i.e., for every $G:\ka^3\to\ka$ there are $h,k,j:\ka\to\ka$ such that $G(x,y,z)=F(h(x),k(y),j(z))$ for all $x,y,z\in\ka$. Let $A_z\su\ka$ for $z\in\ka$ partition $\ka$ into sets of size $\ka$. Define $F_z(x,y)=F(x,y,z)$. Then we claim that for some $z$ the map $F_z$ restricted to $A_z\times A_z$ is universal for all maps from $A_z\times A_z$ to $\ka$. Suppose not. For each $z$ let $G_z:A_z\times A_z \to \ka$ witness that it is not universal. Take any $G:\ka\times\ka\to\ka$ which extends all $G_z$. Since $F$ is universal there are $h,k,j$ with $G(x,y)=F(h(x),k(y),j(z))$ all $x,y,z\in\ka$. Letting $z_0=j(0)$ gives us that $$G_{z_0}(x,y)=G(x,y)=F(h(x),k(y),z_0)=F_{z_0}(h(x),k(y)) \mbox{ for all } x,y\in A_{z_0}$$ which contradicts the choice of $G_{z_0}$. This argument requires that we restrict to a subset $A_z$ of $\ka$, we don't know if there could be a 3-dimensional universal $F$ such no $F_z$ is 2-dimensional universal with respect to maps on all of $\ka^2$. We may also consider universal functions $F$ where the parameters functions are functions of more than one variable, for example: $$\forall G\;\exists g,h,k\;\forall x,y,z\;\;\; G(x,y,z)=F(g(x,y),h(y,z),k(z,x)).$$ This form easily follows from the existence of a dimension 3 universal. Note that by using pairing functions we can always combine parameter functions which have the same sequence of variables. The reader can imagine many variants. For example, $G(x,y,z)=F(g(x,y),h(y,z))$ $G(x_1,x_2,x_3,x_4)=F(g_1(x_1,x_2),g_2(x_2,x_3),g_3(x_3,x_4),g_4(x_4,x_1))$ \noindent where we have omitted quantifiers for clarity. These two variants are equivalent to the existence of 2-dimensional universal function. To see this in the first example put $y=0$ and get $G(x,z)=F(g(x,0),h(0,z))$. \noindent In the second example put $x_2=x_4=0$ and get $G(x_1,x_3)=F(g_1(x_1,0),g_2(0,x_3),g_3(x_3,0),g_4(0,x_1))$. \noindent More generally, suppose $F$ and $\vec{x_k}$'s have the property that for every $G$ there are $g_k$'s such that for all $\vec{x}$ $$G(\vec{x})=F(g_1(\vec{x}_1),\ldots,g_n(\vec{x}_n)).$$ Suppose there are two variables $x$ and $y$ from $\vec{x}$ which do not simultaneously belong to any $\vec{x}_k$. Then we get a universal 2-dimensional function simply by putting all of the other variables equal to zero. \begin{prop} If there is a $(3,2)$-dimensional universal function, i.e., an $F(x,y,z)$ such that for every $G$ there is $h$ with $$G(x,y,z)=F(h(x,y),h(y,z),h(z,x))\mbox{ all }x,y,z$$ then for every $n>3$ there is a $(n,2)$-dimensional universal function $F$, i.e., for every $G$ n-ary there is a binary $h$ with $$G(x_1,x_2,\ldots,x_n)=F(\la h(x_i,x_j):1\leq i3$, then there is a $(3,2)$-dimensional universal function. \end{prop} \proof Consider the case for $n=4$. Suppose that $F$ is $(3,2)$-dimensional universal function. Given a 4-ary function $G(x,y,z,w)$ for each fixed $w$ we get a function $h_w(u,v)$ with $$G(x,y,z,w)=F(h_w(x,y),h_w(y,z),h_w(z,x))\mbox{ for all } x,y,z.$$ But now considering $h(u,v,w)=h_w(u,v)$ we get a function $k(s,t)$ with $h(u,v,w)=F(k(u,v),k(v,w),k(w,u))$. Note that \noindent $\;\;\;\;\;\;G(x,y,z,w)=$ $\;\;\;\;\;\;F(F(k(x,y),k(y,w),k(w,x)),$ $\;\;\;\;\;\;\;\;\;\;\;\;F(k(y,z),k(z,w),k(w,y)),$ $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;F(k(z,x),k(x,w),k(w,z))).$ \noindent Note that $k(s,t)$ and $k(t,s)$ can be combined by pairing and unpairing into a single function $k_1(s,t)$. From this one can define a $(4,2)$-dimensional universal function. For the converse, if $F$ is a $(4,2)$-dimensional universal function, then for every $G$ 3-ary, there exists $h$ binary with $$G(x,y,z)=F(h(x,y),h(y,z),h(x,z),h(x,0),h(y,0),h(z,0)).$$ But note that, for example, $h(x,y)$ and $h(x,0)$ can be combined into a single function of $h_1(x,y)$. Hence we can get a $(3,2)$-dimensional universal function. \qed To state the generalization of these ideas \begin{define}\label{def29} Let $U(\ka,m,n)$ mean that we have a $(m,n)$-dimensional universal function on $\ka$. This means for $k=\comb(n,m)$ there exists $F:\ka^{k}\to\ka$ such that for every $G:\ka^m\to\ka$ there is $h:\ka^n\to\ka$ such that $$G(x_0,x_1,\ldots,x_{m-1})=F\left(h(x_j:j\in Q):Q\in [m]^n\right) \mbox{ for all } \vec{x}\in \ka^m. $$ \end{define} Then the last two propositions can be generalized to show: \begin{prop}\label{propmn} For any infinite cardinal $\ka$ and positive integer $n$ \begin{enumerate} \item $U(\ka,n+1,n)$ implies $\forall m>n\;\; U(\ka,m,n)$. \item ($\exists m>n\;\; U(\ka,m,n)$) implies $U(\ka,n+1,n)$. \item $U(\ka,n+1,n)$ implies $U(\ka,n+2,n+1)$ \end{enumerate} \end{prop} We show that $U(\ka,n+1,n)$ are the only generalized multi-dimensional universal functions properties. \begin{define}\label{def31} Suppose $\Sigma\su \pow(\{0,1,2,\ldots,n-1\})=\pow(n)$ (the power set of $n$). Define $U(\ka,n,\Sigma)$ to mean that there exists $F:\ka^{\Sigma}\to\ka$ such that for every $G:\ka^n\to\ka$ there are $h_Q:\ka^{|Q|}\to\ka$ for $Q\in\Sigma$ such that $$G(x_0,x_1,\ldots,x_{n-1})=F\left(h_Q(x_j:j\in Q):Q\in\Sigma\right) \mbox{ for all } \vec{x}\in \ka^n. $$ \end{define} \begin{prop} Let $\ka$ be an infinite cardinal, $n\geq 2$, and $\Sigma,\Sigma_0,\Sigma_1$ subsets of $\pow(n)$. \begin{enumerate} \item If $\Sigma_0\su \Sigma_1$ , then $U(\ka,n,\Sigma_0)$ implies $U(\ka,n,\Sigma_1)$. \item If $Q_0\su Q_1\in\Sigma$, then $U(\ka,n,\Sigma)$ is equivalent to $U(\ka,n,\Sigma\cup\{Q_0\})$. \item Suppose $\Sigma$ is closed under taking subsets, every $k0$ let $\de=\{\de_i:i<\om\}$. Define $$F_0(\de,n,m)=\de_{f(n,m)}.$$ Now suppose $G:\om_1^3\to\om_1$. Define $$k(\de)=\sup\{G(\al,\be,\ga)\;:\;\al,\be,\ga\leq\de\}+1$$ For any $\ga<\om_1$ let $\ga^*=k(\ga)$. Define $g:\om^2\to\om$ by $$G((\ga+1)_n,(\ga+1)_m,\ga))=\ga^*_{g(n,m)}.$$ By the universality property of $f$ there exists $h:\om\to\om$ with $$g(n,m)=f(h(n),h(m)) \mbox{ for every } n,m\in\om.$$ For $\de\leq \ga$ define $h_1(\de,\ga)=h(k)$ where $\de=(\ga+1)_k$. Then we have that $$\forall \al,\be\leq\ga<\om_1\;\;\; G(\al,\be,\ga)=F_0(k(\ga),h_1(\al,\ga),h_1(\be,\ga)).$$ Define $F$ as follows: \medskip \noindent $F(\al,\be,\ga,\al^*,\be^*,\ga^*,n_1,m_1,n_2,m_2,n_3,m_3)=$ $$ \left\{ \begin{array}{ll} F_0(\ga^*,n_1,m_1) & \rmif \al,\be\leq\ga \\ F_0(\be^*,n_2,m_2) & \rmif \ga < \be \rmand \al\leq\be \\ F_0(\al^*,n_3,m_3) & \rmif \be,\ga < \al \\ \end{array}\right. $$ Then given $G$ we can find $k,h_1,h_2,h_3$ so that \noindent $G(\al,\be,\ga))=$ $F(\al,\be,\ga,k(\al),k(\be),k(\ga),$ $\;\;\;\;\;\;\;\;\; h_1(\al,\ga),h_1(\be,\ga),\;\; h_2(\al,\be),h_2(\ga,\be),\;\; h_3(\be,\al),h_3(\ga,\al)). $ \qed The $\ka$-Cohen real model is any model of ZFC obtained by forcing with the poset of finite partial functions from $\ka$ to 2 over a countable transitive ground model satisfying ZFC. \begin{prop}\label{prop34} In the $\om_2$-Cohen real model we have that $U(\om_1,2,1)$ fails. Similarly, $U(\om_2,3,2)$ fails in the $\om_3$-Cohen real model. More generally, we have that $U(\ga,n+1,n)$ fails in the $\ka$-Cohen real model when $\ka>\ga\geq \om_n$. \end{prop} \proof We show that $U(\om_2,3,2)$ fails in the $\om_3$-Cohen real model, leaving the rest to the reader. Let $M$ be a countable transitive model of ZFC and in $M$ define $\poset$ to be the poset of finite partial maps from $\om_3\times\om_3\times\om_3$ into 2. We claim that if $G$ is $\poset$-generic over $M$, then there is no map $F:\om_2\times\om_2\times\om_2\to \om_2$ which is (3,2)-universal for maps of the form $H:\om\times\om_1\times\om_2\to 2$. Suppose for contradiction that $F$ is such a map. By the ccc we may find $\ga_0<\om_3$ with $F\in M[G\res\ga_0^3]$. Hence we may find maps $h_1:\om\times\om_1\to\om_3$, $h_2:\om\times\om_2\to\om_3$, and $h_3:\om_1\times\om_2\to\om_3$ such that $$H(n,\be,\ga)=^{def}G(n,\be,\ga_0+\ga)=F(h_1(n,\be),h_2(n,\ga),h_3(\be,\ga)).$$ for every $n<\om,\be<\om_1,\ga<\om_2$. By ccc we can choose $\ga_1<\om_2$ such that $h_1\in M[G^*]$ where $G^*$ is $G$ restricted $\{(\al,\be,\rho)\in\om^3\;:\;\rho\neq \ga_0+\ga_1\}$. Define $g:\om\times\om_1\to 2$ by $$g(n,\al)=G(n,\al,\ga_0+\ga_1)$$ Note that we have that $F,h_1\in M[G^*]$, $g$ is Cohen generic over $M[G^*]$, and $$g(n,\al)=F(h_1(n,\al),h_2(n,\ga_0+\ga_1),h_3(\al,\ga_0+\ga_1)).$$ Since the extension by $g$ is ccc, we may find $\al_0<\om_1$ such that $$h_2\in M[G^*][g\res (\om\times\al_0)]=^{def}N.$$ But this is a contradiction because $g_{\al_0}$ defined by $g_{\al_0}(n)=g(n,\al_0)$ is Cohen generic over $N$. But $F,h_1,h_2\in N$ and for any $\ga_2<\om_2$ the map $k$ defined by $$k(n)=F(h_1(n,\al_0),h_2(n,\ga_0+\ga_1),\ga_2) \mbox{ for all } n<\om$$ is in $N$ and so can never be equal to $g_{\al_0}$. Thus $h_3(\al_0,\ga_0+\ga_1)=\ga_2$ cannot be defined. \qed \begin{cor} (\cite{univ}) Let $\aleph_\om\leq\ga<\ka$. In the $\ka$-Cohen real model we have that $$U(\om_n,n+2,n+1)+\neg U(\om_n,n+1,n) \mbox{ for all }n>0,$$ and $$\neg U(\ga,n+1,n) \mbox{ for all }n>0 .$$ Hence, 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{cor} \section{Model Theoretic Universal} \begin{thm}\label{answer7.13} (Remark 7.13 \cite{univ}.) If $2^{<\cc}=\cc$ and there is a Borel universal map, i.e. Borel $F:2^\om\times 2^\om\to 2^\om$ such that for every $G:2^\om\times 2^\om\to 2^\om$ there is $h$ such that $G(x,y)=F(h(x),h(y))$ for all $x\in 2^\om$, then there is a Borel map $H$ such that for every cardinal $\ka<\cc$ for every $G: \ka \times \ka \to \ka$ there are $x_\al\in 2^\om$ for $\al <\ka$ such that for $\al,\be,\ga<\ka$ $$G(\al,\be)=\ga \rmiff H(x_\al,x_\be)=x_\ga$$ \end{thm} \proof By Theorems \ref{bbmbdd}, Lemma \ref{bbmlem}, and Theorem \ref{mainthmuniv} there exists $\al<\om_1$, $Z\su 2^\om$ with $|Z|=\cc$ and every $Y\in [Z]^{<\cc}$ is $\bsi0\al$ in $Z$. Note that by Lemma \ref{rectangle} $\;\;\pow(\cc\times\cc)=\si(\{A,B:A,B\su\cc\})$, so if $X\su Z$ of size $\ka$ then every subset of $X^2$ is $\bsi0{\al_0}$ in $X^2$ where $\al_0=\al+\al$. Let $X=\{x_\al:\al<\ka\}$. Given any map $G:\ka\times\ka\to\ka$ define $$Y_n=\{(x_\al,x_\be)\;:\; G(\al,\be)=\de \rmand x_\de(n)=1\}$$ for each $n$. Let $B_n\su 2^\om\times 2^\om$ be $\bsi0{\al_0}$ so that $Y_n=B_n\cap(X\times X)$. Define the Borel map $K$ by $K(u,v)(n)=1$ iff $(u,v)\in B_n$. Note that $$G(\al,\be)=\de\rmiff K(x_\al,x_\be)=x_\de.$$ Let $L$ be Borel and universal for all such maps $K$, i.e., For all Borel $K$ of rank less than $\al_0+1$ there is a $y$ such that $\forall u,v \; K(u,v)=L(y,u,v)$. Now define $H((y,u),(y,v))=(y,L(y,u,v))$. Putting $\hat{x}_\al=(y,x_\al)$ we have that for every $\al,\be,\de$ $$H(\hat{x}_\al,\hat{x}_\be)=\hat{x}_\de \rmiff G(\al,\be)=\de.$$ \qed \section{Generic Souslin sets} \begin{thm} (Marczewski see Miller\cite{ramsey}) If $I$ is a ccc $\si$-ideal in the Borel sets then the family of $I$-measurable sets is closed under the Souslin operation. \end{thm} \begin{thm}(\cite{dstfor}) (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{thm} \begin{thm} (Miller \cite{gensous}) It is consistent to have $X\su 2^\om$ such that every subset of $X$ is Souslin in $X$ and the Borel order of $X$ is $\om_1$. \end{thm} The set $X$ also has the property that $\pow(X)$ is not a countably generated $\si$-algebra. \begin{thm} (\cite{gensous}) It is relatively consistent with ZFC 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 not every subset of $2^\om\times 2^\om$ is in the $\si$-algebra generated by the abstract rectangles. \end{thm} \section{Products and Unions} \begin{thm} (Sierpinski 1935) Assume CH. There Luzin sets and Sierpinski sets whose square can be continuously mapped onto $2^\om$. \end{thm} \begin{cor} (CH) For any $\al$ with $2\leq \al<\om_1$ there is $X\su 2^\om$ such that $$\ord(X)=\al \rmand \ord(X^2)=\om_1$$ \end{cor} \proof Let $S\su 2^\om$ be a Sierpinski set whose square continuously maps onto $2^\om$. Let $X_\al$ have order $\al$ (which exists by CH \cite{hier}), then the clopen separated union $X=S\oplus X_\al$ has order $\al$ and its square has order $\om_1$ by Reclaw \ref{rec}. \begin{thm} (Miller \cite{special}) (CH) There is an uncountable $\si$-set $X\su 2^\om$ which is concentrated on a countable set. ($\si$-set means $\ord(X)=2$.) \end{thm} \begin{thm} (Fleissner, Miller \cite{qsets}) It is relatively consistent with ZFC to have an uncountable Q-set which is concentrated on a countable set. \end{thm} \def\dom{\mbox{dom}} \begin{thm}\label{newunion} (CH) For any $\al_0$ with $3\leq \al_0<\om_1$ there are $X_0,X_1\su 2^\om$ with $\ord(X_0)=\al_0=\ord(X_1)$ and $\ord(X_0\cup X_1)=\al_0+1$. \end{thm} \proof Let $T$ be a nice $\al_0$-tree (see Definition \ref{nicetree}). \begin{define} Define $\poset_T$ by $p\in\poset_T$ iff $p:T\to 2$ is a finite partial function such that for all $s\in T^0$ and $n<\om$ if $s,sn\in\dom(p)$ and $p(s)=1$, then $p(sn)=0$. Define the rank of $p$: $|p|=\max\{\rank_T(s)\;:\; s\in\dom(p)\}.$ \end{define} \begin{lemma} Rank Lemma. For all countable $\be\geq 1$ for all $p\in\poset_T$ there exists $\hat{p}\in\poset_T$ compatible with $p$, $|\hat{p}|\leq\be$, and for all $q\in\poset_T$ with $|q|<\be$, $({p}\perp q) \rightarrow (\hat{p}\perp q)$. \end{lemma} \proof As usual $\perp$ stands for incompatible. First extend $p$ to $p^*$ which has the property that for any $s\in\dom(p)$ with $p(s)=1$ and $\rank_T(s)=\lambda$ a limit ordinal greater than $\be$ and $n$ such that $\rank_T(sn)<\be$ there exists $m$ such that $p^*(snm)=1$. Note that by the definition of nice tree there are at most finitely many $sn$. Now define $\hat{p}=p*\res\{s\in\dom{p^*}:\rank_T(s)\leq\be\}$. Suppose $|q|<\be$ and $p\perp q$. So one of the following must be true: \begin{enumerate} \item There exists $s\in\dom(q)\cap\dom(p)$ with $p(s)\neq q(s)$. \item There exists $s\in\dom(q)$ and $sn\in\dom(p)$ with $q(s)=1$ and $p(sn)=1$. \item There exists $s\in\dom(p)$ and $sn\in\dom(q)$ with $p(s)=1$ and $q(sn)=1$. \end{enumerate} In the first case since $|q|<\be$ we have that $s\in\dom(\hat{p})$ so $\hat{p}\perp q$. In the second case $\rank_T(sn)<\rank_T(s)<\be$ so again $\hat{p}\perp q$. In the third case $\rank_T(sn)<\be$ so either $\rank_T(s)\leq \be$ (so $\hat{p}\perp q$) or $\rank_T(s)=\lambda>\be$ a limit ordinal. By the construction of $p^*$ there is some $m$ with $p^*(snm)=1$. Since $\hat{p}(snm)=1$ and $q(sn)=1$ it follows that $\hat{p}\perp q$. \qed \begin{define} For $G$ sufficiently $\poset_T$-generic, its union, $\bigcup G$, will be a map from $T$ into $2$. Let $g$ be the restriction of $\bigcup G$ to $T^*$, the terminal nodes of $T$. So $g:T^*\to 2$ is defined by $g(s)=i$ iff $\exists p\in G$ with $p(s)=i$. \end{define} \begin{lemma}\label{neat} Suppose $\al\geq 1$, $B(v)$ is a $\bsi0\al$ predicate on $2^{T^*}$ coded in $M$, and $p\in\poset_T$. If $p\forces B(\name{g})$, then there exists $\hat{p}$ compatible with $p$, $|\hat{p}|<\al$, and $\hat{p}\forces B(\name{g})$. \end{lemma} \proof Case $\al=1$. Suppose ($B(v)\iff \exists n \;C_n(v)$) where $C_n$ are clopen. Take $q\leq p$ and $n$ so that $q\forces C_n(\name{g})$. By extending $q$ we may assume that $C_n(f)$ holds for all $f\in T^*$ with $q\res T^*\su f$. Then $\hat{p}=^{def}q\res T^*$ is as required. Case $\al>1$. Suppose ($B(v)\iff \exists n \;B_n(v)$) where $B_n$ is $\bpi0{\be_n}$ for some $\be_n<\al$. Let $p_1\leq p$ and $n<\om$ be such that $p_1\forces B_n(\name{g})$. Let $\hat{p_1}$ be obtained from the Rank Lemma for $\be=\be_n$. Then it must be that $\hat{p_1}\forces B_n(\name{g})$. Otherwise there exists $p_2\leq \hat{p}_1$ such that $p_2\forces \neg B_n(\name{g})$. By induction there $q$ compatible with $p_2$ (and hence with $\hat{p_1}$), $|q|<\be_n$ and $q\forces \neg B_n(\name{g})$. But by the Rank Lemma such a $q$ would be compatible with $p_1$, contradiction. \qed \begin{lemma} If $B(v)$ is a $\bsi0\al_0$ predicate on $2^{T^*}$ coded in $M$, then there exists $G$ $\poset_T$-generic over $M$ such that $B(g)$ iff $G(\langle\rangle)=0$. \end{lemma} \proof If not, $1\forces$ ``$B(\name{g})\rmiff G(\langle\rangle)=1$''. Let $p=(\langle\rangle,1)$, so $p\forces G(\langle\rangle)=1$ and therefor $p\forces B(\name{g})$. By the Lemma \ref{neat} there is $q$ compatible with $p$, $|q|<\al_0$ and $q\forces B(\name{g})$. But note that $q^*=q\cup \{(\langle\rangle,0)\}$ is a condition because $\langle\rangle$ is not in the domain of $q$ since it has rank $\al_0$. But $q^*\forces$`` $G(\langle\rangle)=0\rmand B(\name{g})$'' which is a contradiction. \qed Now we prove Theorem \ref{newunion}. Let $M_\be\elemsub H_\ka$ for $\be<\om_1$ be countable elementary substructures of $H_\ka$ for some sufficiently large regular $\ka$, so that $\be<\ga$ implies $M_\be\elemsub M_\ga$ and $\pow(\om)\su \bigcup_{\be<\om_1}M_\be$. Choose $G_\al$ $\poset_T$-generic over $M_\al$ with the property that for any $B(v)$ a $\bsi0\al_0$ predicate on $2^{T^*}$ for some $\al$ $B(g_\al)$ iff $G_\al(\langle\rangle)=0$. Let $X=\{g_\al\in 2^{T^*}:\al<\om_1\}$ and for $i=0,1$ let $X_i=\{g_\al\;:\; G_\al(\langle\rangle)=i\}$. Define $U_s\su 2^{T^*}$ for $s\in T$ as follows. $U_s=\{x\in 2^{T^*}\;:\; x(s)=1\}$. For $s\in T^0$ $\;\;\;U_s=\bigcap_{n<\om}\sim U_{sn}$. Note that if $\rank_T(s)=\be$ then $U_s$ is $\bpi0\be$. Therefor since $U_{\langle\rangle}\cap X= X_1$ we have that $X_1$ is a $\bpi0{\al_0}$ subset of $X$ which by construction is not $\bsi0\al_0$. So $\ord(X)\geq\al_0+1$. Define for $p\in\poset_T$ $[p]=\bigcup\{U_s\;:\; p(s)=1\}\cup\bigcup\{\sim U_s\;:\; p(s)=0\}$. Note that $[p]$ is $\bde0{\al_0+1}$. For any Borel $B\su 2^{T^*}$ there is an $\al<\om_1$ with $B$ coded in $M_\al$. For all $\ga\geq\al$ $G_\ga$ is $\poset_T$-generic over $M_\ga$ and hence $$g_\ga\in B\rmiff \exists p\in G_\ga\;\; p\forces g_\ga\in B.$$ Note that by Borel absoluteness $g_\ga\in B\rmiff M_\ga[g_\ga]\models g_\ga\in B.$ Let $$\Sigma=^{def}\{p\in\poset_T\;:\;p\forces \name{g}\in B\}.$$ Let $X^{\geq\al}=\{g_\ga\;:\;\ga\geq\al\}$. Then $$X^{\geq\al}\cap B= X^{\geq\al}\cap \bigcup_{p\in\Sigma}[p].$$ Since we add and subtract a countable set from any $\bde0{\al_0+1}$ set and remain $\bde0{\al_0+1}$, we see that $\ord(X)\leq\al_0+1$. For any $p\in\poset_T$ and $i=0,1$ we have that $[p]\cap X_i$ is $\bde0\al_0$ since it is either empty (if $p(\langle\rangle)=1-i$) or equal to $[p^*]\cap X_i$ where $p^*=p\sm\{(\langle\rangle,i)\}$. It follows that $\ord(X_i)\leq \al_0$. To get an example with order exactly $\al_0$: Either by modifying the above construction or using the Luzin set argument from \cite{hier} Thm 18, we can get $Y\su 2^\om$ with order exactly $\al_0$. Let $X^+_i=^{def}X_i\oplus Y$ where $\oplus$ means to take a clopen separated union. Then $\ord(X_i^+)=\al_0$ and $X_0^+\cup X_1^+=X\oplus Y$ has order $\al_0+1$. This proves Theorem \ref{newunion}. Note that in case $\al_0$ is a successor order we can use the above proof to get $Z_0,Z_1$ such that $\ord(Z_0)=\al_0$, $\ord(Z_1)=\al_0-1$, and $\ord(Z_0\cup Z_1)=\al_0+1$. To see this note that since $p(\langle\rangle)=1$ implies $p(\langle n\rangle)=0$ for all $\langle n\rangle\in\dom(p)$ we have that $\ord(X_1)\leq\al_0-1$. Take $Y^\prime$ with $\ord(Y^\prime)=\al_0-1$ and put $Z_0=X_0\oplus Y \oplus \emptyset$ and $Z_1=X_1\oplus \emptyset \oplus Y^\prime$. \section{Invariant Descriptive Set Theory} For $\rho$ a countable similarity type let $X_\rho$ be the Polish space of $\rho$-structures with universe $\om$. For example if $\rho=\{R,f,U,c\}$ where $R$ is a binary relation symbol, $f$ a binary operation symbol, $U$ a unary operation symbol and $c$ a constant symbols then $$X_\rho= 2^{\om\times\om}\times \om^{\om\times\om}\times 2^\om \times \om.$$ The language $L_{\om_1,\om}(\rho)$ is obtained by adding countably infinite conjunctions and disjunctions to the usual first order logical axioms. For example: $$\forall y \disj_{n<\om} \exists x_1,x_2,\ldots x_n\; \forall z (R(z,y)\to \vee_{i=1}^n z=x_i)$$ which says that for every $y$ there are at most finitely many $z$ with $R(z,y)$. We consider only formulas with at most finitely many free variables. Inductively define $\Sigma_\al$ and $\Pi_\al$ formulas as follows: $\Sigma_0=\Pi_0$ formulas are the ordinary first-order quantifier free finite formulas. For $\al>0$ a formula $\phi(\vec{y})$ is $\Sigma_\al$ iff there are $\phi_n(\vec{x_n},\vec{y})$ each a $\Pi_{<\al}$ formula and $$\phi(\vec{y})=\disj_{n<\om}\exists \vec{x_n}\phi_n(\vec{x_n},\vec{y}).$$ A formula $\phi(\vec{y})$ is $\Pi_\al$ iff there are $\phi_n(\vec{x_n},\vec{y})$ each a $\Sigma_{<\al}$ formula and $$\phi(\vec{y})=\conj_{n<\om}\forall \vec{x_n}\phi_n(\vec{x_n},\vec{y})$$ \begin{thm} (Mostowski see Kuratowski \cite{kur} page ???) If $\theta$ is a $\Sigma_\al$ sentence of $L_{\om_1,\om}(\rho)$, then the set of models of $\theta$ is a $\Sigma_\al^0$ Borel subset of $X_\rho$. \end{thm} \proof For any $n$ and formula $\theta(\vec{x})$ where $\vec{x}=x_0,\ldots,x_{n-1}$ includes all free variable of $\theta$ and any $s\in \om^n$ consider the models of $\theta(s)$: $$\{M\in X_\rho \;:\; M\models \theta(s(0),s(1),\ldots,s(n-1))\}$$ Details left to reader. \qed \begin{thm} (Scott 1964 see Barwise \cite{barwise}) For any countable structure $A$ in a countable similarity type $\rho$, there is a sentence $\theta$ of $L_{\om_1,\om}(\rho)$ such that for any countable $\rho$-structure $B$ $$A\simeq B \rmiff B\models \theta$$ \end{thm} A subset of $X_\rho$ is invariant iff it is closed under isomorphism. Lopez-Escobar (1965) showed that invariant Borel subsets of $X_\rho$ are the models of an $L_{\om_1,\om}(\rho)$-sentence. Vaught proved a hierarchy version of this: \begin{thm}\label{vaug} (Vaught \cite{vaught}) Any $\Pi_\al^0$ subset of $X_\rho$ which is closed under isomorphism is the set of models of a $\Pi_\al$ sentence of $L_{\om_1,\om}(\rho)$ \end{thm} \proof Let $S_\infty\su \om^\om$ be the Polish group of bijections of $\om$. It's action on $X_\rho$ is isomorphism. For example, given $\pi\in S_\infty$ and $R\su\om\times\om$ a binary relation, then $(\om,R)$ is isomorphic to $(\om,S)$ via $\pi$ where $S$ is defined by $R(x,y)$ iff $S(\pi(x),\pi(y))$. $S_\infty \times X_\rho \to X_\rho$ $(\pi, R)\mapsto S$ is a continuous action. The following is the Vaught transform: For each $n\in\om$ and one-to-one map $s:n\to\om$ define $(A,s)\in \bb^{*n}$ iff there are comeagerly many $\pi\in [s]$ such that $\pi^{-1}(A)\in \bb$. For $n=0$ then $\bb^*$ is the set of all $A\in X_\rho$ for which there are comeagerly many $\pi\in S_\infty$ such that $\pi^{-1}(A)\in \bb$ (or equivalent comeagerly many $\pi$ with $\pi(A)\in \bb$). \begin{lemma} \label{countablestar} Suppose $(\bb_n\su X_\rho:n<\om)$ and $m<\om$, then $$(\bigcap_{n<\om}\bb_n)^{*m}=\bigcap_{n<\om}\bb_n^{*m}$$ \end{lemma} \proof The countable intersection of comeager sets is comeager. \qed \begin{lemma} \label{complement} Suppose $\bb\su X_\rho$ is Borel and $n<\om$, then for any $s:n\to\om$ one-to-one, $$(A,s)\in \bb^{*n} \;\;\rmiff\;\; \neg \exists t \supseteq s \;\; (A,t)\in (\sim\bb)^{*|t|}$$ where $\sim\bb$ is the complement of $\bb$. \end{lemma} \proof For any $(A,s)$ the set $\{\pi\in S_\infty \;:\; \pi^{-1}\in\bb\}$ is the continuous preimage of a Borel set and hence is Borel and so has the property of Baire. For a set with the property of Baire, it either is comeager or its complement is somewhere comeager. \qed \begin{lemma} For any $n,\al\geq 1$ and $\bb\su X_\rho$ a $\Pi^0_\al$ set, there is a $\Pi_\al$ formula $\theta(\vec{v})$ such that for any $A\in X_\rho$ and $s:n\to\om$ one-to-one $$(A,s)\in \bb^{*n} \rmiff (A,s)\models \theta(s(0),\ldots,s(n-1)).$$ \end{lemma} \proof First assume $\al=1$ and $\bb\su X_\rho$ is clopen. Then for some quantifier-free finite formula $$\bb=\{A\in X_\rho\;:\; A\models \theta(0,1,2,\ldots, m)\}$$ Without loss, we may assume $m>n$. Then by definition $(A,s)\in \bb^{*n}$ iff $\{\pi\;:\pi^{-1}(A)\in \bb\}$ is comeager in $[s]$. But since $\bb$ is clopen, $\{\pi\;:\pi^{-1}(A)\in \bb\}$ is comeager in $[s]$ iff $\pi^{-1}(A) \in \bb$ for all $\pi\supseteq s$. But now $\pi^{-1}(A) \in \bb$ iff $\pi^{-1}(A)\models \theta(0,1,2,\ldots, m)$. iff $A\models \theta(\pi(0),\pi(1),\ldots,\pi(m)$. Hence we get that $(A,s)\in \bb^{*n}$ iff \noindent $(A,s)\models \forall v_{n},\ldots, v_m \;\; (D(s,\vec{v})\rightarrow \theta(s(0),\ldots, s(n-1), v(n),\ldots, v(m)))$ where $D$ is the first-order formula saying that the $v_i$ are distinct and different from all the $s(j)$. To finish the case of $\al=1$ just use that if $\bb$ is $\Pi^0_1$ then $\bb=\bigcap_{m<\om}\bb_m$ where each $\bb_m$ is clopen and $\bb^{*n}=\bigcap_{m<\om}\bb_m^{*n}$ by Lemma \ref{countablestar}. Now assume $\al>1$ and $\bb\su X_\rho$ is $\Sigma^0_\be$ for some $\be<\al$. Then $\sim \bb$ is $\Pi^0_\be$ and so by Lemma \ref{complement}: $(s,A)\in \bb^{*n}$ iff $\neg\exists t\supseteq s\; (A,t)\in (\sim \bb)^{*|t|}$ By induction hypothesis $(A,t)\in (\sim \bb)^{*|t|}$ iff $(A,t)\models \theta_m(t(0),\ldots, t(m))$ for some $\Pi_\be$ formula $\theta_m$. And so, $(A,s)\in \bb^{*n}$ iff \noindent $(A,s)\models \forall v_{n},\ldots, v_m \;\; (D(s,\vec{v})\rightarrow \neg\theta(s(0),\ldots, s(n-1), v(n),\ldots, v(m)))$ Note that this is a $\Pi_{\be+1}$ formula and so a $\Pi_\al$ formula. To finish this case if $\bb$ is $\Pi^0_\al$ then $\bb=\bigcap_{m<\om}\bb_m$ where $\bb_m$ is $\Sigma^0_{\be_m}$ for some $\be_m<\al$. Hence applying Lemma \ref{countablestar} us the result since the countable conjunction of $\Pi_\al$ formulas is a $\Pi_\al$ formula. \qed Vaught's Theorem \ref{vaug} follows immediately from the Lemma for the case $n=0$ and $\bb$ invariant, i.e., $\bb^*=\bb$. It also the case that invariant $\Sigma^0_\al$ sets are the models of a $\Sigma_\al$ sentence by considering complements. \begin{thm} (Hausdorff Difference Hierarchy) $\bb\in \Delta_{\al+1}^0$ iff there exists a countable sequence of decreasing $\Pi_\al^0$ sets $\bb_\be$ for $\be<\ga$ such that $$\bb=\bigcup_{\be \mbox{ even }<\ga} \bb_\be\sm \bb_{\be+1}$$ \end{thm} For a proof see Kuratowski \cite{kur} page-section ???. \begin{thm} (Douglas E. Miller \cite{doug}) If $\bb$ is also invariant, then $$\bb=\bigcup_{\be \mbox{ even }<\ga} \bb_\be^*\sm \bb_{\be+1}^*$$ \end{thm} \proof The dual of the Vaught *-transform is $\bb^\triangle=\sim(\sim \bb^*)$. Equivalently $A\in \bb^\triangle$ iff $\pi(A)\in \bb$ for non-meagerly many $\pi\in S_\infty$. Two other transforms are $$\bb^+=\{A\;:\; \exists \pi\in S_\infty\;\; \pi(A)\in \bb \}\;\;\rmand\;\; \bb^-=\{A\;:\; \forall \pi\in S_\infty\;\; \pi(A)\in \bb\}.$$ Note that \begin{enumerate} \item $\bb^-\su \bb^*\su \bb^\triangle \su \bb^+$ \item $\bb$ is invariant iff $\bb^-=\bb^+$ \item $(\bigcup_{n<\om}\bb_n)^\triangle = \bigcup_{n<\om}\bb_n^\triangle$ \item $\bb_1^*\cap \bb_2^\triangle\su (\bb_1\cap \bb_2)^\triangle$ \item $(\sim \bb)^*=\sim \bb^\triangle$ \item $\bb_1^*\sm \bb_{2}^*=\bb_1^*\;\cap\; \sim( \bb_{2}^*) =\bb_1^*\cap (\sim \bb_{2})^\triangle\su (\bb_1\sm \bb_{2})^\triangle $ \end{enumerate} To prove the theorem note that $$\bigcup_{\mbox{ even }\be <\ga} \bb_\be^*\sm \bb_{\be+1}^*\su \bigcup_{\be} (\bb_\be\sm \bb_{\be+1})^\triangle =(\bigcup_{\be} \bb_\be\sm \bb_{\be+1})^\triangle =\bb^\triangle=\bb$$ where these unions are all taken over even $\be<\ga$. Hence if we let $$\diffeven(\bb_\al:\al<\ga)=^{def}\bigcup\{\bb_{\al}\sm \bb_{\al+1} \;:\;\mbox{ even }\al<\ga\}$$ Then we conclude that $$\diffeven(\bb_\al^*:\al<\ga)\su \bb.$$ To get the reverse inclusion note that the complement of a difference set is also a difference set. To see this we may without loss of generality assume that $\ga$ is a limit ordinal by padding with the empty set if necessary. Then $\sim \bb=\sim (\bigcup\{\bb_\be\sm \bb_{\be+1}\;:\;\be\mbox{ even }<\ga\}$ is the union of the following sets: \begin{itemize} \item $X_\rho\sm \bb_0$ \item $\bb_\be\sm \bb_{\be+1}$ for odd $\be <\ga$ \item $(\cap_{\al<\lambda}\bb_\al)\sm \bb_\lambda$ for limit $\lambda<\ga$ \item $\cap_{\al<\ga}\bb_\al$ \end{itemize} Let us denote this union as $\diffodd(\bb_\al:\al<\ga)$. Then by the argument above we get that $$\diffodd(\bb_\al^*:\al<\ga)\su\sim\bb$$ But since $\diffeven(\bb_\al^*:\al<\ga)$ and $\diffodd(\bb_\al^*:\al<\ga)$ are complements, it follows that $\bb=\diffeven(\bb_\al^*:\al<\ga)$. \qed \begin{cor} If the isomorphism class of a countable structure is $\Delta_{\al+1}^0$ then it must be either $\Pi_\al^0$, $\Sigma_\al^0$, or the difference of two invariant $\Pi_\al^0$ sets. \end{cor} \begin{thm} (Miller \cite{ctblmod}) The isomorphism class of a countable model cannot be properly $\Sigma_1^0$ or properly $\Sigma_2^0$. For $\lambda$ a countable limit ordinal, it cannot be properly $\Sigma_\lambda^0$ or properly the difference of two $\Pi_\lambda^0$ sets. \end{thm} \begin{thm} (Miller \cite{ctblmod}, Hjorth \cite{hjorth}) In all other cases of there are examples of countable structures whose isomorphism class is properly of that Borel class. \end{thm} %\section{Other results on Borel hierarchies} %In this section we enumerate some results on the length of hierarchies which %were not lectured on. long borel hierarchies, %proj set hierarchies, podge 6.1, re-anal, results in lecture notes \begin{thebibliography}{99} \bibitem{barwise} Barwise, Jon; Back and forth through infinitary logic. Studies in model theory, pp. 5-34. MAA Studies in Math., Vol. 8, Math. Assoc. Amer., Buffalo, N.Y., 1973. \bibitem{BBM} Bing, R. H.; Bledsoe, W. W.; Mauldin, R. D.; Sets generated by rectangles. Pacific J. Math. 51 (1974), 27-36. \bibitem{carlson} Tim Carlson, On $\om_1$-Borel sets, unpublished 1982. \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{hjorth} Hjorth, G.; An orbit that is exactly $\Sigma_{\lambda +1}$, handwritten note Feb 1995. \par\url{http://www.math.wisc.edu/~miller/res/unpub/hjorth.pdf} \bibitem{kechris} Kechris, Alexander S.;{\bf Classical descriptive set theory.} Graduate Texts in Mathematics, 156. Springer-Verlag, New York, 1995. xviii+402 pp. ISBN: 0-387-94374-9 \bibitem{kunen} Kunen, Kenneth; INACCESSIBILITY PROPERTIES OF CARDINALS. Thesis (Ph.D.) Stanford University. 1968. \bibitem{kur} Kuratowski, topology \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/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{ctblmod} Miller, Arnold W.; The Borel classification of the isomorphism class of a countable model, Notre Dame Journal of Formal Logic, 24(1983), 22-34. \par\url{http://www.math.wisc.edu/~miller/res/ctblmod.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{ramsey} Miller, Arnold W.; Ramsey Theory \par\url{http://www.math.wisc.edu/~miller/old/m873-96/ramsey.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{doug} Miller, Douglas E.; The invariant $\Pi_\al^0$ separation principle. Trans. Amer. Math. Soc. 242 (1978), 185-204. \bibitem{univ} Larson, Paul B.; Miller, Arnold W.; Steprans, Juris; Weiss, William A.R.; {\bf Universal Functions} eprint Apr 2012 \par\url{http://www.math.wisc.edu/~miller/res/univ.pdf} \bibitem{rao} Rao, B.V.; On discrete Borel spaces and projective sets. Bull. Amer. Math. Soc. 75 1969 614-617. \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. \bibitem{vaught} Vaught, Robert; Invariant sets in topology and logic. Collection of articles dedicated to Andrzej Mostowski on his sixtieth birthday, VII. Fund. Math. 82 (1974/75), 269-294. \bibitem{willard} Willard, Stephen Some examples in the theory of Borel sets. Fund. Math. 71 (1971), no. 3, 187-191. \end{thebibliography} \end{document}