% LaTeX2e % On relatively analytic sets % A. Miller February 2003 last revised Sept 15, 2004 \documentclass[12pt]{article} \usepackage{amssymb} \def\appendix{\par} % to see appendix %\def\appendix{\end{document}} %% to hide appendix \def\sn{{\mathfrak s \mathfrak n}} \def\zz{{\mathfrak z}} \def\cc{{\mathfrak c}} \def\sqbdd{{\sqsubseteq^{{\rm bounded}}}} \def\graph{{\rm graph}} \def\Sig{{\bf \Sigma_1^1}} \def\Sigtwo{{\bf \Sigma_2^0}} \def\Sigthree{{\bf \Sigma_3^0}} \def\Pig{{\bf \Pi_1^1}} \def\Pigtwo{{\bf \Pi_2^0}} \def\Pigthree{{\bf \Pi_3^0}} \def\trees{{\mathcal T}} \def\poset{{\mathbb P}} \def\pos{{\mathbb P}(B)} \def\lq{\mbox{``}} \def\rq{\mbox{''}} \def\sq{\subseteq} \def\bb{{\mathfrak b}} \def\zz{{\mathfrak z}} \def\om{\omega} \def\infsub{[\om]^\om} \def\finsub{[\om]^{<\om}} \def\proof{\par\noindent Proof\par\noindent} \def\name#1{\stackrel{\circ}{#1}} \def\reals{{\mathbb R}} \def\forces{{| \kern -2pt \vdash}} \def\force{\forces} \def\res{\upharpoonright} \def\qed{\par\noindent QED\par} \def\rmand{\mbox{ and }} \def\rmor{\mbox{ or }} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{cor}[theorem]{Corollary} \newtheorem{claim}[theorem]{Claim} \newtheorem{question}[theorem]{Question} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{prop}[theorem]{Proposition} \begin{document} \begin{center} {\large On relatively analytic and Borel subsets} \end{center} \begin{flushright} Arnold W. Miller\footnote{ Thanks to University of Florida, Gainesville and to Boise State University, Idaho for their hospitality during the time this paper was written and to J.Zapletal and T.Bartoszynski for some helpful discussions. \par Mathematics Subject Classification 2000: 03E35; 03E17; 03E15 } \end{flushright} \begin{center} Abstract \end{center} \begin{quote} Define $\zz$ to be the smallest cardinality of a function $f:X\to Y$ with $X,Y\sq 2^\om$ such that there is no Borel function $g\supseteq f$. In this paper we prove that it is relatively consistent with ZFC to have $\bb<\zz$ where $\bb$ is, as usual, smallest cardinality of an unbounded family in $\om^\om$. This answers a question raised by Zapletal. We also show that it is relatively consistent with ZFC that there exists $X\sq 2^\om$ such that the Borel order of $X$ is bounded but there exists a relatively analytic subset of $X$ which is not relatively coanalytic. This answers a question of Mauldin. \end{quote} The following is an equivalent definition of $\zz$: $$\zz=\min\{|X|:X\sq 2^\om, \exists Y\sq X\;\;\; Y \mbox{ is not Borel in }X\}$$ For one direction we can use for each $Y\subseteq X$ its characteristic function $f:X\to 2$. For the other direction use that a function is Borel iff the inverse image of each basic open set is Borel. The following answers a question raised by Zapletal \cite{zap} see appendix A. \begin{theorem}\label{zapletal} It is relatively consistent with ZFC that $\bb<\zz$. \end{theorem} Define $p\in \poset(A)$ for $A\sq 2^\om$ iff $p$ is a finite set of consistent sentences of the form: \begin{enumerate} \item $\lq x\in \cap_{m<\om}U_{nm}\rq $ where $x\in A$, $n\in\om$, or \item $\lq x\notin U_{nm}\rq $ where $x\in 2^\om$, $n,m\in\om$, or \item $\lq [s]\sq U_{nm}\rq $ where $s\in 2^{<\om}$, $n,m\in\om$. \end{enumerate} By consistent we simply mean the following: \begin{itemize} \item $p$ cannot contain both $\lq x\in \cap_{m<\om}U_{nm}\rq$ and $\lq x\notin U_{nk}\rq$ for some $x,n,k$, and \item $p$ cannot contain both $\lq x\notin U_{nm}\rq$ and $\lq [x\res k]\sq U_{nm}\rq$ for some $x.n,m,k$. \end{itemize} The ordering on $\poset(A)$ is given by inclusion: $p\leq q$ iff $p\supseteq q$. Note that the set $A$ enters into the picture only in sentence of type (1). This partial order is from Miller \cite{borhier} where there are versions for all countable Borel orders (this is for $\Sigthree$). It can be looked on as a generalization of almost disjoint forcing of Jensen and Solovay. I learned about describing almost disjoint forcing as sets of sentences from Jack Silver. Now suppose that $G$ is $\poset(A)$-generic over $V$. Define $$U^G_{nm}=\cup\{[s]: \lq [s]\sq U_{nm}\rq\in G\} \rmand W^G_n=\cap_{m<\om}U_{nm}^G$$ \begin{lemma}\label{one} For any $x\in V\cap 2^\om$ \begin{enumerate} \item $x\notin U^G_{nm}$ iff $\lq x\notin U_{nm}\rq\in G$ \item $x\in W_n^G$ iff $\lq x\in\cap_{m<\om} U_{nm}\rq\in G$ \item $x\in A$ iff $x\in \cup_{n<\om}W_n^G$ \end{enumerate} \end{lemma} \proof To prove $(1)$ working in $V$, fix $x\in 2^\om$ and $n,m<\om$. The following set is dense: $$D_{x,n,m}=\{p\in\poset(A): \exists k\;\; \lq[x\res k]\sq U_{nm}\rq\in p\rmor \lq x\notin U_{nm}\rq\in p\}$$ To see this note that if $\lq x\notin U_{nm}\rq$ is not in $p$ we can always find $k$ large enough so that $p\cup \{\lq [x\res k]\sq U_{nm}\rq\}$ is a consistent set of sentences. Now suppose $x\in U^G_{nm}$, then for some $k$ we have that $\lq[x\res k]\sq U_{nm}\rq\in G$ and hence by consistency, $\lq x\notin U_{nm}\rq\notin G$. On the other hand, if $\lq x\notin U_{nm}\rq\notin G$, then since $D_{x,n,m}$ is dense for some $k$ we have that $\lq[x\res k]\sq U_{nm}\rq\in G$ and hence $x\in U^G_{nm}$. To prove $(2)$ note that the following set is dense: $$D_{x,n}=\{p\in\poset(A)\;:\; \exists k\;\; \lq x\notin U_{nk}\rq \in p\rmor \lq x\in\cap_{m<\om}U_{nm}\rq\in p\}$$ To see this note that if $\lq x\in\cap_{m<\om}U_{nm}\rq\notin p$, then for large $k$ (so that $U_{nk}$ is not mentioned in $p$), the sentences $p\cup \{\lq x\notin U_{nk}\rq\}$ are consistent. To prove $(3)$ note that if $x\in A$ then the following is dense: $$D_{x}=\{p\in\poset(A)\;:\; \exists n\; \lq x\in\cap_{m<\om}U_{nm}\rq\in p\}$$ and we can only assert $\lq x\in\cap_{m<\om}U_{nm}\rq$ for $x\in A$. \qed Note that it follows from the Lemma that $A\cap V=(\cup_{n<\om}W_n^G)\cap V$ and so that $A$ is a $\Sigthree$ relative to the ground model reals. \begin{lemma}\label{lemccc} $\poset(A)$ is ccc. \end{lemma} \proof This is a standard $\Delta$-systems argument. Suppose two conditions $p$ and $q$ agree on all sentences of the form: $$\lq [s]\sq U_{nm}\rq $$ and also they agree on all sentences of the form: $$\lq x\in \cap_{m<\om}U_{nm}\rq \rmor \lq x\notin U_{nm}\rq $$ whenever $x$ is mentioned in both $p$ and $q$. Then $p\cup q$ is consistent. \qed \bigskip Next we must prove that $\poset(A)$ does not add a dominating real. Working in $V$, for $Y\sq 2^\om$ countable define $p\in \poset(A)_Y$ iff $p\in\poset(A)$ and $$\forall x,n,k\;\; (\lq x\notin U_{nk}\rq \in p\rmor \lq x\in\cap_{m<\om} U_{nm}\rq \in p)\to x\in Y\}.$$ Or in other words, $\poset(A)_Y$ are the conditions in $\poset(A)$ which only mention elements of $Y$. \begin{lemma}\label{easy} Suppose $p\in\poset(A)$ and $q\in\poset(A)_Y$. Then $p$ and $q$ are compatible iff $r$ and $q$ are compatible where $$r=p\setminus\{\lq x\in\cap_{m<\om}U_{nm}\rq \;:\; x\notin Y, n<\om\}$$ \end{lemma} \proof Incompatibility cannot arise between sentences of type (1) and (3). That is, any pair of the form: $$\lq [s]\sq U_{nm}\rq,\;\; \lq x\in\cap_{m<\om}U_{nm}\rq$$ is consistent. It follows that the $\lq x\in\cap_{m<\om}U_{nm}\rq\in p$ for which $x\notin Y$ cannot conflict with the sentences of $q$ since by definition $q$ cannot mention any $x$ which is not in $Y$. \qed \bigskip\noindent Define. $T=(p,(t_i,n_i,m_i:il_0 \;\;x(l)<\tau(l)$ and $$p_0=p\cup\{z_i\in \cap_{m<\om}U_{n'_i,m}: i< N'\}\cup \{x_i\notin U_{n_im_i}\;:\; i< N\}$$ where $p\in \poset(A)_Y$ and $z_i,x_i\notin Y$. Take $t_i$ sufficiently long so that $t_i\sq x_i$ and $$T=(p, (t_i,n_i,m_i:il_0$, there exists $q\in\poset(A)_Y$ such that $p(\vec{x})\cup q\in\poset(A)$ and $q\forces \tau(l)\kappa$ \item For all $X\sq 2^\om$ with $|X|\leq\kappa$ and for all $\Sig$ sets $A\sq 2^\om$ there exists a $\Sigtwo$ set $B\sq 2^\om$ such that $X\cap A=X\cap B$. \item For all $X\sq 2^\om$ with $|X|\leq\kappa$ and for all $\Sigtwo$ sets $A\sq 2^\om$ there exists a $\Pigtwo$ set $B\sq 2^\om$ such that $X\cap A=X\cap B$. \item For all $X\sq 2^\om$ with $|X|\leq\kappa$ and for all countable $A\sq X$ there exists a $\Pigtwo$ set $B\sq 2^\om$ such that $A=X\cap B$. \end{enumerate} \end{prop} \proof $(2)\to (3)$ and $(3)\to (4)$ are trivial. To see $(1)\to (2)$ let $$A=\{x\in 2^\om\;:\; \exists y\in \om^\om\;\;(x,y)\in C\}$$ where $C\sq 2^\om\times \om^\om$ is closed. Suppose that $A\cap X=\{x_\alpha:\alpha<\kappa\}$. Choose $y_\alpha\in \om^\om$ so that $(x_\alpha,y_\alpha)\in C$ for each $\alpha<\kappa$. Since $\bb>\kappa$ we can choose $z_n\in\om^\om$ for $n<\om$ so that for all $\alpha<\kappa$ there exists $n<\om$ with $y_\alpha\leq z_n$ (pointwise). Define $$C_n=\{(x,y)\in C: y\leq z_n\}$$ $C_n$ is compact and therefore so is its projection: $$A_n=\{x\in 2^\om \;:\;\exists y \;(x,y)\in C_n\}$$ But $A\cap X=(\cup_{n<\om}A_n)\cap X$. To see $(4)\to (1)$ let $X\sq \om^\om$ with $|X|=\kappa$. Now since $\om^\om$ is homeomorphic to $\infsub$ and $\infsub\sq P(\om)\simeq 2^\om$ by applying $(4)$ we can find a $\Pigtwo$ set $G\sq P(\om)$ such that $$G\cap (X\cup \finsub)=\finsub$$ But note that $F=P(\om)\setminus G$ is a $\sigma$-compact set which is disjoint from $\finsub$, i.e. a subset of $\infsub\simeq \om^\om$ and covers $X$. But is easy to show that for any $\sigma$-compact subset $F$ of $\om^\om$ there exists $f\in \om^\om$ such that $g\leq^*f$ for all $g\in F$. \qed \bigskip Remark. One way to get the consistency of $\bb<\zz<\sn$ is as follows: Start with a ground model of $2^\om=\om_1$, $2^{\om_1}=\om_2$, and $2^{\om_2}=\om_{17}$. Do a finite support iteration of $\poset(A_\alpha)$ for $\alpha<\om_3$, so that for limit ordinals $\alpha$ we take $A_{\alpha}=A$ (the universal $\Sig$-set) and for successor ordinals $\alpha$ we take $|A_\alpha|=\om_1$ as in the above proof. In the final model we will have $\bb=\om_1$ since it is an iteration of really $\sqbdd$-good ccc partial orders. Also we will have $\zz\leq \om_2$ because $2^{\om_2}=\om_{17}$ and $2^\om=\om_3$. We also have $\zz\geq\om_2$ because of dovetailing over all $A$ of size $\om_1$. And we will have $\sn=\om_3=\cc$ because we have cofinally often used the universal $\Sig$-set. \bigskip \bigskip The following Theorem answers a question of Dan Mauldin (see \cite{prob} problem 7.8 and \cite{survey} p.212). \begin{theorem}\label{mauldin} It is relatively consistent with ZFC that there exist a separable metric space $X$ such that the Borel order of $X$ is bounded, but not every relatively analytic subset of $X$ is Borel in $X$. \end{theorem} \proof We use almost exactly the same partial order but with one crucial difference. Instead of using arbitrary subsets $A\sq 2^\om$ we let $B\sq 2^\om$ be a fixed universal $\Pigthree$ set. The partial order $\pos$ is Borel, ccc, and adds a generic $\Sigthree$ set whose intersection with the ground model is the same as $B$'s with the ground model. \bigskip\noindent Define. A partially ordered set $\poset$ is very Souslin iff \begin{enumerate} \item $\poset$ is ccc, \item $\poset$, $\;\leq$, $\;\{(p,q)\in \poset^2: p, q \mbox{ incompatible } \}$ are $\Sig$, and \item $\{\Sigma\in \poset^\om \;:\; \Sigma \mbox{ enumerates a maximal antichain }\}$ is $\Sig$. \end{enumerate} \bigskip We will need the following Lemma: \begin{lemma} (Zapletal \cite{zap} see Appendix C, Lemmas C.0.14 and C.0.17)\label{zaptwo} Suppose $\poset$ is a very Souslin real partial order and $\poset^{\om_2}$ the countable support iteration of $\poset$. Then $$V^{\poset^{\om_2}}\models \sn =\om_1.$$ \end{lemma} Lemma \ref{zaptwo} does not require large cardinals (LC) as many of Zapletal's results do. It does mean that partial order $\poset(A)$ is not very Souslin even when $A$ is taken to be analytic. However, if we change $A$ to make it Borel, then it is very Souslin: \begin{lemma} For $B$ Borel the partial order $\pos$ is very Souslin. \end{lemma} \proof The following sets are Borel: \begin{enumerate} \item $\pos$ \item $\{(p,q)\in \pos\times\pos\;:\; p\sq q\}$ \item $\{(p,q)\in \pos\times\pos\;:\; \mbox{ $p$ and $q$ are incompatible } \}$ \item $\{(p,Y)\;:\; Y\in [2^\om]^\om \rmand p\in \pos_Y\}$ \item $\{((T_n:n<\om),Y)\;:\; Y\in [2^\om]^\om $ and $\{T_n:n<\om\}=$ all $Y$-templates $\}$ \end{enumerate} \bigskip \noindent Next we verify that being a maximal antichain in $\pos$ is $\Sig$. \bigskip\noindent{\bf Claim}. $\Sigma\sq\pos$ is a maximal antichain iff \begin{enumerate} \item $\Sigma$ is an antichain and \item there exists $Y\sq 2^\om$ countable and $(T_n:n<\om)$ such that \begin{itemize} \item $\Sigma\sq \pos_Y$ and \item $(T_n:n<\om)$ enumerates the set of all $Y$-templates \end{itemize} and for all $n$ if $T_n=(p,(t_i,n_i,m_i:i