% Half of an inseparable pair, A.Miller % Mar 2004 LaTeX 2e last revised 8-31-2006 \documentclass[12pt]{article} \usepackage{amssymb} \def\appendix{\par} % to see appendix %\def\appendix{\end{document}} %% to hide appendix \def\res{\upharpoonright} \def\om{\omega} \def\al{\alpha} \def\be{\beta} \def\ga{\gamma} \def\de{\delta} \def\sq{\subseteq} \def\ss{\setminus} \def\sep{{\rm Sep}} \def\emp{\emptyset} \def\bPi{{\bf \Pi}} \def\bSig{{\bf \Sigma}} \def\bDel{{\bf \Delta}} \def\proof{\par\noindent Proof\par\noindent} \def\qed{\par\noindent QED\par} \def\rmiff{\mbox{ iff }} \def\rmand{\mbox{ and }} \def\nembed{\not\hookrightarrow} \def\reals{{\mathbb R}} \def\rationals{{\mathbb Q}} \def\adm{{\mathbb A}} \def\ll{{G{\cal N}}} \def\rank{{\mbox{ rank}}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{question}[theorem]{Question} \newtheorem{prop}[theorem]{Proposition} \begin{document} \begin{center} Half of an inseparable pair \end{center} \begin{flushright} Arnold W. Miller\footnote{ Thanks to Jindrich Zapletal who organized the SEALS meeting at the University of Florida, Gainesville in March 2004 during which part of these results were obtained. \par Mathematics Subject Classification 2000: 03E15, 03E35, 03E60. \par LaTeX2e - texed on \today } \end{flushright} \begin{quote} Abstract: A classical theorem of Luzin is that the separation principle holds for the $\bPi^0_\al$ sets but fails for the $\bSig^0_\al$ sets. We show that for every $\bSig^0_\al$ set $A$ which is not $\bPi^0_\al$ there exists a $\bSig^0_\al$ set $B$ which is disjoint from $A$ but cannot be separated from A by a $\bDel^0_\al$ set $C$. Assuming $\bPi^1_1$-determancy it follows from a theorem of Steel that a similar result holds for $\bPi^1_1$ sets. On the other hand assuming V=L there is a proper $\bPi^1_1$ set which is not half of a Borel inseparable pair. These results answer questions raised by F.Dashiell. \end{quote} The separation principle is a classical property of point classes in descriptive set theory. For every countable ordinal $\al$ and every pair of disjoint sets $A,B\sq 2^\om$ in the multiplicative class $\al$ ($\bPi^0_\al$) there exists a set $C$ in ambiguous class $\al$ ($\bDel^0_\al$) which separates them, i.e., $A\sq C$ and $C\cap B=\emp$. It is also a classical result of Luzin that the separation principle must fail for the dual classes $\bSig^0_\al$. For proofs, see Kechris \cite{kechris} \S 22. For $\Gamma$ a class of subsets of $\om^\om$, define the dual class $\widetilde{\Gamma}=\{\om^\om\ss A:A\in\Gamma\}$, $\Delta=\Gamma\cap \widetilde{\Gamma}$, and $\sep(\Gamma)\equiv \forall A,B\in \Gamma\;\; A\cap B=\emp\to \exists C\in \Delta\;\; A\sq C \rmand A\cap B=\emp$. \noindent $\Gamma$ is continuously closed iff for all continuous $f:\om^\om\to \om^\om$ if $A\in \Gamma$ then $f^{-1}(A)\in\Gamma$. $\Gamma$ is nonselfdual iff $\Gamma\neq\widetilde{\Gamma}$. Van Wesep and Steel \cite{vanwesep} \cite{vanwesep2} \cite{steelsep} proved that for continuously closed nonselfdual $\Gamma$ in the Borel subsets of $\om^\om$ either ($\neg \sep(\Gamma)$ and $\sep(\widetilde{\Gamma}))$ or ($\neg\sep(\widetilde{\Gamma})$ and $\sep(\Gamma)$), i.e., separation holds on one side and fails on the other. This result is true for all continuously closed nonselfdual classes, if the Axiom of Determinacy holds. In Dashiell \cite{dashiell}, Luzin's theorem on the failure of separation for ${\bSig}^0_\al$ is used to prove that the Banach space, ${\mathcal B}_\al$, of Baire class $\al$-functions is not isomorphic to the space ${\mathcal B}_{\om_1}$ of Baire functions. The following Theorem settles a question raised by F. Dashiell. He already knew the result for ${\bSig}^0_1$ and ${\bSig}^0_2$. It was also asked by Luzin \cite{luzin} in 1930, see the top of page 73, ``Un autre probl\`eme \ldots '' and the last paragraph on page 76. Henryk Torunczyk informs me that Theorem \ref{one} follows from the results in the paper Louveau and Saint-Raymond \cite{lsr}. \begin{theorem}\label{one} Suppose $X$ is a Polish space and $A\sq X$ is ${\bSig}^0_\al$ but not ${\bPi}_\al^0$. Then there exists $A^*\sq X$ which is ${\bSig}^0_\al$ such that $A\cap A^*=\emp$ but there does not exist a ${\bDel}_\al^0$ set $C$ which separates $A$ and $A^*$, i.e., $A\sq C$ and $C\cap A^*=\emp$. \end{theorem} \proof For $\al=1$, if $A$ is any open set which is not closed, then it cannot be separated from the interior of $X\ss A$. So we may assume $\al\geq 2$. By Theorem 4 of Kunen-Miller \cite{km}, there exists a set $P\sq X$ such that $P$ is homeomorphic to a closed subset of $2^\om$ and $P\cap A$ is ${\bSig}^0_\al\ss {\bDel}_\al^0$. So without loss of generality we may assume $A\sq 2^\om$. For subsets $B,C\sq 2^\om$ define $B\leq_W C$ (Wadge reducible) iff there exists a continuous map $f:2^\om\to 2^\om$ such that $f^{-1}(C)=B$. Associated with Wadge reducibility is the Wadge game whose payoff set is of roughly the same complexity as $B$ and $C$. It follows from Borel determinacy, see Martin \cite{martin}, that for every pair of Borel sets $B$ and $C$ that either $B\leq_W C$ or $C\leq_W (2^\om\ss B)$, see for example Van Wesep \cite{vanwesep}. It follows from this that for any $B\sq 2^\om$ which is ${\bSig}^0_\al$ we have that $B\leq_W A$, since otherwise $A\leq_W(2^\om\ss B)$ would make $A$ a ${\bPi}^0_\al$ and hence ${\bDel}^0_\al$, which is contrary to our assumption. Now assume $\al=2$. Let $D ,D^*\sq 2^\om$ be countable dense and disjoint. Note that they are ${\bSig}^0_2$ sets which cannot be separated, since dense ${\bPi}^0_2$, i.e., $G_\de$, sets must intersect by the Baire Category Theorem. Since $D \leq_W A$ there exists a continuous map $f:2^\om\to 2^\om$ with $f^{-1}(A)=D $. Let $A^*=f(D^*)$. Since it is countable, $A^*$ is a ${\bSig}^0_2$ set. It cannot be separated from $A$, because if $C$ is a ${\bDel}^0_2$ with $A\sq C$ and $A^*\cap C=\emp$, then $D \sq f^{-1}(C)$ and $D^*\sq f^{-1}(2^\om\ss C)$ would separate $D $ and $D^*$. Now assume $\al>2$. By a result of Harrington, see Steel \cite{steel} or Van Engelen, Miller, Steel \cite{vms}, for any $B$ which is ${\bSig}^0_\al$ there exists a one-to-one continuous map $f:2^\om\to 2^\om$ such that $f^{-1}(A)=B$. By a classical theorem of descriptive set theory (see Kechris \cite{kechris}) there exists disjoint $B,B^*\sq 2^\om$ ${\bSig}^0_\al$ sets which cannot be separated by a ${\bDel}^0_\al$ set. Let $f$ be one-to-one and continuous with $f^{-1}(A)=B$. Let $A^*=f(B^*)$. Since $f$ is one-to-one, it is a homeomorphism onto its range and hence $A^*$ is a ${\bSig}^0_\al$ set disjoint from $A$. The set $A^*$ cannot be separated from $A$ because the preimage of a separating set would separate $B$ and $B^*$. \qed Dashiell's proof of Theorem \ref{one} for $\al=2$ is as follows. Suppose $X$ is a Polish space and $A\sq X$ is some $F_\sigma$ set which is not a $G_\de$. By Baire's theorem on functions of the first class, there exists a closed $F \sq X$ on which the characteristic function of $A$ has no point of continuity relative to $F$. That is, both $A\cap F$ and $A\ss F$ are dense in F. Let $A^*$ be a countable dense set in $A\ss F$ (hence an $F_\sigma$). Clearly now $A$ and $A^*$ can not be separated by disjoint $G_\de$ sets of X, because intersecting with $F$ would give two dense $G_\de$ subsets of the complete metric space $F$, which must meet. Dashiell pointed out that for a fixed countable ordinal $\al$ if we let $X_\al$ be the Stone space of the Boolean algebra of $\bDel_\al^0$ subsets of the reals, then the cozero sets in $X_\al$ whose closures are not open (i.e., not clopen) correspond to the proper $\bSig^0_\al$ sets. (Recall that a zero set is a closed set which the preimage of singleton zero under a real-valued continuous map and a cozero set is the complement of a zero set.) Hence, by Theorem \ref{one}, we know that every cozero set $A$ whose closure is not open has an inseparable disjoint sibling, i.e., a cozero set $B$ disjoint from $A$ but the closures of $A$ and $B$ must meet. Dashiell tells us that the question from \cite{dashiell} of whether ${\cal B}_\al$ and ${\cal B}_\be$ can be isomorphic Banach spaces for some $1<\al<\be<\om_1$ is still open. Dashiell also raised the same question for the coanalytic sets, $\bPi^1_1$. The classic result (see Kechris \cite{kechris} \S 34,35) is that any pair of disjoint analytic sets ($\bSig_1^1$) can be separated by a Borel set ($\bDel^1_1$), but separation fails for $\bPi^1_1$. Luzin proved this by applying the reduction principle to a pair of doubly universal sets. \begin{theorem}\label{two} Suppose $\bPi^1_1$-determinacy holds, then for any $\bPi^1_1$ set $A$ in a Polish space $X$, if $A$ is not $\bSig^1_1$, then there exists $A^*\sq X$ a $\bPi^1_1$ set disjoint from $A$ which cannot be separated from $A$ by a Borel set ($\bDel^1_1$). \end{theorem} \begin{theorem}\label{three} Suppose $V=L$, then there exists a $\Pi^1_1$ set $A\sq 2^\om$ which is not $\bSig^1_1$ with the property that for any $B\sq 2^\om$ a $\bPi^1_1$ set disjoint from $A$ there exists a Borel set $C$ with $A\sq C$ and $C\cap B=\emp$. \end{theorem} \proof For Theorem \ref{two} note that since there is a Borel bijection between $X$ and $2^\om$ we may assume that $X=2^\om$. Theorem \ref{two} is an immediate corollary of a Theorem of Steel \cite{steel}, who showed that $\bPi^1_1$-determinacy implies that for any two properly $\bPi_1^1$ subsets $A_1,A_2$ of $2^\om$ there exists a Borel automorphism $f:2^\om\to 2^\om$ such that $f(A_1)=A_2$. Hence if we take $C,C^*\sq 2^\om$ to be any disjoint pair of $\bPi^1_1$ sets which are not Borel separable and $f:2^\om\to 2^\om$ a Borel automorphism with $f(A)=C$, then $f^{-1}(C^*)=A^*$ will be the required set. For Theorem \ref{three} we use for $A$ the self-constructible reals studied by Guaspari, Kechris, and Sacks, see Kechris \cite{kechris2} \S 2, where the self-constructible reals $A$ are denoted ${\mathcal C}_1$. Define $$A=\{x\in 2^\om\; :\; x\in L_{\om_1^x}\}$$ where $\om_1^x$ is the least ordinal which is not the order type of a relation recursive in $x$. It is also the least ordinal $\al$ such that $L_\al[x]$ is an admissible set. Suppose that $B$ is a $\bPi^1_1$ set disjoint from $A$. Then we may assume that $B$ is $\Pi^1_1(x_0)$ for some $x_0\in A$ since by Kechris \cite{kechris2} 2A, every real in $L$ is recursive in some $x_0\in A$. Let $\ga<\om_1^{x_0}$ be the least ordinal so that $x_0\in L_\ga$. For any $y\in 2^\om$ define $\ga^+(y)$ to be the least $\al>\ga$ such that $L_\al[y]$ is an admissible set. \begin{lemma}\label{mainlemma} For any $C\sq 2^\om$ a nonempty $\Pi^1_1(x_0)$ set there exists $y\in C$ such that $y\in L_{\ga^+(y)}$. \end{lemma} \proof The proof is a slight generalization of Sacks \cite{sacks} III Lemma 9.3 p. 82. Recall that a binary relation $(X,R)$ is well-founded iff every nonempty subset of $X$ has an $R$-minimal element. A map $f:X\to $ Ordinals is called a rank function iff $$\forall s,t\in X\;\; sRt \to f(s)\om$ is a limit ordinal. For each $s\in T$ define $T_s=\{t\in T\;:\; s\sq t\}$. For each ordinal $\al<\de_2$ if $\rank(T_s)=\al$ then the canonical rank function, on $T_s$, i.e., $t\mapsto\rank(T_t)$ is an element of $L_{\de_2+\al+1}$. \proof Note that $(T\times\al)\in L_{\de_2}$ since $\al$ is small. Fix $\al$ and $s\in T$ with $\rank(T_s)=\al$. For each $\de<\de_1$ if $s\de\in T$ and $\rank(T_{s\de})=\beta$, then the canonical rank function on $T_{s\de}$ is in $L_{\de_2+\be+1}\sq L_{\de_2+\al}$ and is uniformly definable from $T_{s\de}$, hence the canonical rank function on $T_s$ is in $L_{\de_2+\al+1}$. \qed \bigskip\noindent {\bf Claim \ref{mainlemma}.2}. Suppose $T$, $\de_1$ and $\de_2$ satisfy the hypothesis of Claim 1. For any ordinal $\al$ define $$T(\al)=\{s\in T\;:\; \rank(T_s)<\al\}.$$ Then $T(\al)\in L_{\de_2+\al+1}$. \proof This follows from the previous claim since the canonical rank functions are elements of $L_{\de_2+\al}$. \qed By the Addison-Kondo Theorem we may assume that $C$ is a $\Pi^1_1(x_0)$ singleton, i.e. $C=\{y_0\}$. Now by standard arguments there exists a tree $T\sq \cup_{n<\om} (\om^{n}\times 2^{n})$ which is recursive in $x_0$ such that for every $y\in 2^\om$ we have that $$y=y_0 \rmiff T\langle y\rangle =^{def}\{s\;:\; (s,y\res |s|)\in T\}\sq \om^{<\om} \mbox{ is well-founded. }$$ Now since the tree $(T\langle{y_0}\rangle,\supset)$ is well-founded and it is an element of the admissible set $L_{\ga^+(y)}[y]$, its rank $\de_0$ is strictly less than $\ga^+(y)$ and its canonical rank function $R:T\langle{y_0}\rangle\to \de_0$ is in $L_{\ga^+(y)}[y]$. Now define a tree $$T^*\sq \cup_{n<\om} (\de_0^{n}\times 2^{n})$$ which basically consists of attempts at a rank function into $\de_0$ for $T\langle{y_0}\rangle$. More formally, suppose $\{t_i:i<\om\}$ is a reasonable recursive listing of $\om^{<\om}$, e.g., it should have the properties that $|s_i|\leq i$ and if $s_i\subset s_j$ then $i\ga$ hence $y\in L_{\om_1^y}$ which contradicts $A\cap B=\emp$. It follows that $$B\sq \{y: x_0\notin \Delta^1_1(y)\}\sq \{y: \om_1^y < \ga\}$$ The second inclusion is true since every element of $L_{\om_1^y}$ is in $\Delta_1^1(y)$. It is well known that for any countable $\ga$ the set $D=\{y\in 2^\om: \om_1^y < \ga\}$ is Borel. For example, a $\bSig^1_1$ definition and $\bPi_1^1$ definition are given by: \begin{enumerate} \item $y\in D$ iff there exists $\al<\ga$ such that $\forall e\in \om $ if $\{e\}^y$ is characteristic function of a well-ordering $(\om,\leq_e^y)$, then $\;\;$ order-type$(\om,\leq_e^y)<\al$. \item $y\in D$ iff there does not exist $e\in\om$ and $f:(\om,\leq_e^y)\to(\ga,<)$ an isomorphism where $\{e\}^y$ is the characteristic function of the relation $(\om,\leq_e^y)$. \end{enumerate} But note that $D\cap A\sq L_\ga$ is countable and $B\sq D$, so $A$ and $B$ can be separated by a Borel set. This proves Theorem \ref{three}. \qed Martin and Solovay \cite{ms} have shown that assuming Martin's Axiom, not CH, and $\om_1=\om_1^L$ that every set of reals of cardinality $\om_1$ is $\bPi_1^1$. This result also appears in Fremlin \cite{fremlin} 23J. Henryk Torunczyk informs me that under these assumptions any set of reals of cardinality $\om_1$ cannot be half of an inseparable pair of $\bPi^1_1$ sets. \begin{question} If every non Borel $\bPi^1_1$ set is half of an inseparable pair, then is $\bPi_1^1$-determinacy true? \end{question} See Harrington \cite{harrington} for some properties of coanalytic sets which imply $\bPi_1^1$-determinacy. Cliff Weil raised the question of whether we can get a large number of examples in Theorem \ref{three}, e.g., \begin{question} Assuming V=L, does there exist continuum many coanalytic sets which are pairwise non Borel isomorphic and each of which is not half of an inseparable pair? \end{question} In Cenzer and Mauldin \cite{cenzer} it is shown that assuming V=L there are continuum many coanalytic sets no two of which are Borel isomorphic. \begin{center} Separation for subsets of $\om$. \end{center} We could also consider the failure of separation for (lightface) classes of subsets of $\om$. Addison \cite{addison} shows that separation holds for the class of $\Pi_n^0$ and fails for the class $\Sigma_n^0$ subsets of $\om$. However, not every proper $\Sigma_1^0$ subset of $\om$ is half of an inseparable pair. A set $A\sq\om$ is simple iff it is recursively enumerable (equivalently $\Sigma^0_1$), coinfinite, but its complement does not contain an infinite recursively enumerable subset. Simple sets were first constructed by Post \cite{post} (or see Soare \cite{soare}), and clearly a simple set cannot be half of an inseparable pair. We are not sure exactly which recursively enumerable sets are half of inseparable pair, perhaps just the complete ones. Post also showed that a subset of $\om$ is $\Sigma^0_{n+1}$ iff it is $\Sigma^0_1(0^{(n)})$ (see Soare\cite{soare} IV 2.2). By relativizing his construction of a simple set to the oracle $0^{(n)}$ we get a properly $\Sigma^0_{n+1}$ subset of $\om$ which is not half of an inseparable pair. Classically, separation holds for the class of $\Sigma^1_1$ subsets of $\om$ and fails for $\Pi^1_1$. A proof analogous to the simple set type construction will give a proper $\Pi^1_1$ subset of $\om$ which is not half of an inseparable pair (see the proof of Sacks \cite{sacks} VI Theorem 2.1 or 2.4). Another ``natural'' example of such a $\Pi^1_1$-set can be given as follows. Let $(\om,\preceq)$ be a recursive linear ordering whose well-ordered initial segment is isomorphic to $\om_1^{CK}$, the first non recursive ordinal. The existence of such a linear ordering is due to Feferman \cite{feferman} or perhaps Harrison \cite{harrison} see also Ash and Knight \cite{ash} 8.11. Now let $A$ be the initial well-ordered segment of $\preceq$, i.e., $$A=\{n\in\om: \{m: m\prec n\}\mbox{ is well-ordered by } \preceq\}.$$ Then $A$ is a proper $\Pi^1_1$ set. It cannot be half of an inseparable pair because if $B\sq\om$ is $\Pi^1_1$ and disjoint from $A$ then there must exists some $n_0\notin A$ such that $k\succeq n_0$ for every $k\in B$. Otherwise $$\om\ss A=\{m\in \om\::\; \exists k\in B\;\; k\preceq m\}$$ but $A$ is not a $\Delta^1_1$ set. Another light-face question one might ask is the following. Suppose $A$ and $B$ are disjoint $\Pi^1_1$ subsets of $\om^\om$ which cannot be separated by a $\Delta_1^1$-set, then can they be separated by a $\bDel^1_1$-set? Here is a counterexample. Let $A,B\sq \om$ be disjoint $\Pi^1_1$ sets which cannot be separated by $\Delta^1_1$ subset of $\om$. Define $A^*=\{f\in\om^\om:f(0)\in A\}$ and $B^*=\{f\in\om^\om:f(0)\in B\}$. Then $A^*$ and $B^*$ are disjoint $\Pi^1_1$ which are clopen and hence separable by clopen sets. But they cannot be separated by a $\Delta^1_1$ subset of $\om^\om$. Suppose $C\sq\om^\om$ is $\Delta_1^1$ and $A^*\sq C$ and $B^*\cap C=\emp$. For each $n<\om$ let $x_n\in\om^\om$ be the constant function $n$. Then $$C^*=\{n<\om\;:\;x_n\in C\}$$ is a $\Delta_1^1$ set separating $A$ and $B$. \begin{center} Natural pairs of inseparable sets. \end{center} A number of authors have given natural examples of inseparable pairs of $\bPi^1_1$ sets. \medskip\noindent Luzin \cite{luzinbook} p.263 gives the following example. Let $$\phi:\om^\om\times\om^\om\to\om^\om$$ be a Borel function such that for every $f:\om^\om\to\om^\om$ continuous there exists $x$ such that $\forall y\;\;\phi(x,y)=f(y)$. Let $$E=\{(x,z):\exists ! y\; \phi(x,y)=z\}$$ $$E_0=\{(x,z)\in E:\exists ! y\; \phi(x,y)=z \rmand y(0)\mbox{ is even }\}$$ $$E_1=\{(x,z)\in E:\exists ! y\; \phi(x,y)=z \rmand y(0)\mbox{ is odd }\}$$ Then $E_0$ and $E_1$ are disjoint inseparable $\bPi^1_1$ sets. \medskip\noindent Sierpinski \cite{sier} gives the following pair of inseparable $\bPi^1_1$ sets. Let $U\sq \reals^3$ be a universal $G_\de$ set for subsets of the plane, i.e., $U$ is $G_\de$ and for every $G_\de$ set $V\sq \reals^2$ there exists an $x\in\reals$ with $U_x=V$. Then $S_1=\{(x,y)\;:\;\neg\exists z\; (x,y,z)\in U\}$ $S_2=\{(x,y)\;:\;\exists!\; z\; (x,y,z)\in U\}$ \noindent are a pair of inseparable $\bPi^1_1$ subsets of the plane. \medskip\noindent Dellacherie and Meyer \cite{del} give the following pair of inseparable $\bPi^1_1$ sets (or perhaps the analogous families of trees): Let $LO$ be the space of linear orderings on $\om$ which we can regard as a closed subspace of $P(\om\times\om)\equiv 2^{\om\times\om}$. Let $WO\sq LO$ be the well-orderings. For two linear orderings let $L_1\nembed L_2$ mean that $L_1$ cannot be order embedded into $L_2$. The following two sets cannot be separated by a Borel set: $D_1=\{(L_1,L_2)\in LO^2\;:\;$ $L_1\in WO$ and $L_2\nembed L_1 \}$ $D_2=\{(L_1,L_2)\in LO^2\;:\;$ $L_2\in WO$ and $L_1\nembed L_2 \}$ \noindent To see that these sets are not separable by a Borel set, first note that for any $\bPi^1_1$ set $A\sq 2^\om$ there exists a continuous map $f:2^\om\to LO$ such that $f^{-1}(WO)=A$. (Such a map can be obtained by using the Kleene-Brouwer ordering on a possible well-founded tree $T\sq \om^{<\om}$ and mapping $\om^{<\om}\ss T$ to and $\om$ sequence at the end.) Similar, for any $\bPi^1_1$ set $B\sq 2^\om$ there exists a continuous map $g:2^\om\to LO$ such that $g^{-1}(WO)=B$. Now if $A$ and $B$ happen to be an inseparable disjoint pair, then the map $h(x)=(f(x),g(x))$ has the property that $h(A)\sq D_1$ and $h(B)\sq D_2$. Hence if $C$ separated $D_1$ and $D_2$, then $h^{-1}(C)$ would separate $A$ and $B$. \medskip\noindent Maitra \cite{maitra} uses an open game $G(x)$ on $\om^\om$ due to Blackwell and shows that $I= \{x\sq\om^{<\om}\;:\; G(x)$ is won by player I $\}$ $II=\{x\sq\om^{<\om}\;:\; G(x)$ is won by player II $\}$ \noindent are disjoint inseparable $\bPi^1_1$ sets. They are not complementary sets because in the game considered there may be `ties'. \medskip\noindent Becker \cite{becker},\cite{becker2} contains several examples of inseparable $\bPi^1_1$ sets, for example, $B_1=\{f\in C([0,1])\;:\; f \mbox{ is nowhere differentiable }\}$ $B_2=\{f\in C([0,1])\;:\; \exists! x\; f^\prime(x) \mbox{ exists }\}$ \noindent are inseparable $\bPi^1_1$ sets. He gives other examples in the compact subsets of the plane: $C_1=\{K\in {\cal K}({\mathbb R}^2)\::\; K \mbox{ is path-connected and simply connected}\}$ $C_2=\{K\in {\cal K}({\mathbb R}^2)\::\; K \mbox{ is path-connected and has exactly one hole}\}$ \medskip\noindent Milewski \cite{milewski} shows that the following pair of $\bPi^1_1$ sets in the space of compact subsets of the Hilbert cube, $[0,1]^\om$, are inseparable: $M_1=\{K\in {\cal K}([0,1]^\om)\;:\;$ all components of $K$ are finite dimensional $\}$ $M_2=\{K\in {\cal K}([0,1]^\om)\;:\;$ exactly one component of $K$ is $\infty$-dim $\}$ \medskip\noindent Camerlo and Darji \cite{cd} give several families of pairwise inseparable coanalytic sets. For any compact set $K\sq \om^\om$ let $CD(K)=\{T\sq \om^{<\om}\;:\; \{x\in\om^\om:\forall n \;x\res n\in T\}$ is homeomorphic to $K\}$ \noindent Then for any two nonhomeomorphic compact set $K_1$ and $K_2$ the sets $CD(K_1)$ and $CD(K_2)$ are inseparable $\bPi^1_1$ sets. \medskip\noindent One schema for obtaining natural disjoint inseparable pairs is to take a naturally defined filter $F$ on $\om$ and its dual ideal $F^*=\{\om\ss X: X\in F\}$. Note that $F$ and $F^*$ have the same complexity since there exists a recursive homeomorphism taking one to other, i.e., $X\mapsto \om\ss X$. The cofinite filter $COF$ and its dual ideal $FIN$ are naturally inseparable $\bSig^0_2$ sets in $P(\om)$. Louveau's filter $\ll$ \cite{louveau} is an example of a $\bPi^1_1$ filter which cannot be separated from its dual ideal by a Borel set. This filter is on the subsets of $\om^{<\om}$ and is defined as follows: $$A\in \ll \mbox{ iff Player I has a winning strategy in the game $J(A)$.}$$ where $J(A)$ is the game: $$ \begin{array}{llllllll} \mbox{Player I: } & n_0 & & n_1 & & n_2 & & \cdots \\ \mbox{Player II: } & & m_0\geq n_0 & & m_1\geq n_1 & & m_2\geq n_2 & \cdots \\ \end{array} $$ Player I wins iff for some $k$ all $s\supseteq (m_i:iN_0$ we have that there exists $m$ with $f(x)(n,m)=1$ and there is $N_1>N_0$ so that $g(x)(N_1,m)=0$ for all $m$. (There are infinitely many such columns $N_1$ so just choose the smallest one bigger than $N_0$.) We claim that for all $n>N_1$ the set $h(x)\cap \{n\}\times \om$ is cofinite in $\{n\}\times \om$. This is because for a sufficiently large stage $n_0>n$ in the game the witnesses $m$ will have shown up, i.e. be less than $n_0$ and so $i_1^n$ will be less than or equal to $N_0$ but $i_2^n$ will never be less than $N_1$ and so we will always put $(n,n_0)$ into $h^*(x\res n_0)$. The proof that $h(B)\sq F^*$ is analogous. \qed The Lemma implies that $F$ and $F^*$ cannot be separated by a $\bDel^0_3$ set, since separation fails for $\bSig^0_3$. \qed \newpage \begin{center} Appendix B \\ \end{center} This is not intended for publication but only for the electronic version. \begin{center} Lecture notes from \\ Slippery Rock conference \\ Summer Symposium XXVIII June 2004 \end{center} For $X$ a Polish space, i.e., separable completely metrizable, define the Borel classes $\bSig^0_\al$, $\bPi^0_\al$, and $\bDel^0_\al$ inductively for countable ordinals $\al$ as follows: \begin{itemize} \item $\bSig^0_1$ is the family of open sets in $X$ \item $\bSig^0_\al$ is the family of all countable unions of sets from $\bigcup_{\be<\al}\bPi_\be^0$ \item $\bPi_\al=\{X\ss A:A\in\bSig^0_\al\}$ \item $\bDel_\al=\bSig^0_\al\cap \bPi^0_\al$ \end{itemize} The Borel subsets of $X$ are those in $\bigcup_{\al<\om_1}\bSig^0_\al$. Lebesgue proved that for any uncountable Polish $X$ that $\bSig^0_\al\neq \bPi^0_\al$ for any $\al<\om_1$. For $\Gamma=\bSig^0_\al$ or $\Gamma=\bPi^0_\al$ define the classical separation principle: \bigskip $\sep(\Gamma)\equiv \forall A,B\in \Gamma\;\; A\cap B=\emp\to \exists C\in \Delta\;\; A\sq C \rmand A\cap B=\emp$. \bigskip \noindent Luzin \cite{luzin} proved that $\sep(\bPi^0_\al)$ holds for $1<\al<\om_1$ (also $\sep(\bPi^0_1)$ if $X$ is zero dimensional). He also proved that $\neg\sep(\bSig^0_\al)$. He gets an inseparable pair by applying the reduction principle to a pair of a doubly universal sets, see Kechris \cite{kechris} \S 22 p.171. The following result answers a question of Dashiell. It came up when he was studying Banach spaces of Baire classes of functions \cite{dashiell} although the question does not appear there. \setcounter{theorem}{0} \begin{theorem}\label{o} Suppose $X$ is a Polish space and $A\sq X$ is ${\bSig}^0_\al$ but not ${\bPi}_\al^0$. Then there exists $A^*\sq X$ which is ${\bSig}^0_\al$ such that $A\cap A^*=\emp$ but there does not exist a ${\bDel}_\al^0$ set $C$ which separates $A$ and $A^*$, i.e., $A\sq C$ and $C\cap A^*=\emp$. \end{theorem} Define $\bSig^1_1$ (or analytic) subsets of $X$ to be the smallest family of subsets of $X$ which contains the Borel sets and is closed under continuous images. $\bPi^1_1$ is the family of coanalytic sets or complements of analytic. Suslin showed that disjoint analytic subsets of $X$ can be separated by Borel sets and so $\sep(\bSig^1_1)$ holds and $\bDel_1^1=$Borel. Luzin's argument goes thru to show that $\neg\sep(\bPi^1_1)$. Dashiell also raised the same question for the coanalytic sets $\bPi^1_1$. In this case the answer is independent. \begin{theorem}\label{t} Suppose $\bPi^1_1$-determinacy holds, then for any $\bPi^1_1$ set $A$ in a Polish space $X$, if $A$ is not $\bSig^1_1$, then there exists $A^*\sq X$ a $\bPi^1_1$ set disjoint from $A$ which cannot be separated from $A$ by a Borel set. \end{theorem} \begin{theorem}\label{r} Suppose $V=L$, then there exists a $A\sq 2^\om$ and $\bPi^1_1$ set which is not $\bSig^1_1$ with the property that for any $B\sq 2^\om$ a $\bPi^1_1$ set disjoint from $A$ there exists a Borel set $C$ with $A\sq C$ and $C\cap B=\emp$. \end{theorem} Theorem~\ref{t} is an easy corollary of a result of Steel \cite{steel}: \begin{theorem} (Harrington \cite{harrington}, Steel \cite{steel}) The following are equivalent: (a) $\bPi^1_1$-determinacy (b) For all $A\sq X$ and $B\sq Y$ if $X$ and $Y$ are Polish and $A$ and $B$ are properly analytic, then there exists a Borel bijection $f:X\to Y$ such that $f(A)=B$. \end{theorem} Theorem~\ref{r} uses the self-constructible reals $A$ studied by Guaspari, Sacks, and Kechris, see \cite{kechris2}. $$A=\{x\in 2^\om\;:\; x\in L_{\om_1^x}\}$$ where $\om_1^x$ is the smallest ordinal not recursive in $x$. \begin{question} If every non Borel $\bPi^1_1$ set is half of an inseparable pair, then is $\bPi_1^1$-determinacy true? \end{question} Cliff Weil raised the question after the talk of whether we can get a large number of examples in Theorem \ref{r}, e.g., \begin{question} Assuming V=L, does there exist continuum many coanalytic sets which are pairwise non Borel isomorphic and each of which is not half of an inseparable pair? \end{question} A number of authors have given natural examples of inseparable pairs of $\bPi^1_1$ sets, Luzin \cite{luzinbook}, Novikov \cite{novikov}, Sierpinski \cite{sier}, Dellacherie and Meyer \cite{del}, Maitra \cite{maitra}, Becker \cite{becker},\cite{becker2}, Milewski \cite{milewski}, and Camerlo and Darji \cite{cd}. Another method for obtaining a disjoint inseparable pair is to take a filter $F$ on $\om$ and its dual ideal $F^*=\{\om\ss X: X\in F\}$. Note that $F$ and $F^*$ have the same complexity since there exists a recursive homeomorphism taking one to other, i.e., $X\mapsto \om\ss X$. This was suggested by the results in Solecki \cite{solecki}. The cofinite filter $COF$ and its dual ideal $FIN$ are naturally inseparable $\bSig^0_2$ sets in $P(\om)$. Louveau's filter $\ll$ \cite{louveau} is an example of a proper $\bPi^1_1$ filter. Louveau proves that the Borel real valued function on a compact metric space are exactly the $\ll$-limits of sequences of continuous functions. Hence $\ll$ is a kind of ultimate generalization of the cofinite filter. \begin{prop} $\ll$ cannot be separated from its dual ideal $\ll^*$ by a Borel set. \end{prop} \end{document}