% LaTeX Article Template - using defaults \documentclass{article}[12pt] \usepackage{amssymb} \usepackage{latexsym} \pagestyle{myheadings} \markright{G. Hjorth} \usepackage{amssymb} \usepackage{latexsym} % Set left margin - The default is 1 inch, so the following % command sets a 1.25-inch left margin. \setlength{\oddsidemargin}{-0.15in} % Set width of the text - What is left will be the right margin. % In this case, right margin is 8.5in - 1.25in - 6in = 1.25in. \setlength{\textwidth}{6.5in} % Set top margin - The default is 1 inch, so the following % command sets a 0.75-inch top margin. \setlength{\topmargin}{-0.1in} % Set height of the header \setlength{\headheight}{0.3in} % Set height of the text \setlength{\textheight}{8.1in} % Set vertical distance between the text and the % bottom of footer \setlength{\footskip}{0.8in} % Set the beginning of a LaTeX document \begin{document} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newenvironment{proof}[1][Proof]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\hfill$\Box$\end{trivlist}} \newenvironment{definition}[1][Definition]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{example}[1][Example]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{remark}[1][Remark]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{notation}[1][Notation]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{question}[1][Question]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}} \def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}} \def\R{{\mathbb R}} \def\C{{\mathbb C}} \def\V{{\mathbb V}} \def\N{{\mathbb N}} \def\Z{{\mathbb Z}} \def\K{{\mathbb K}} \def\B{{\mathbb B}} \def\o{{\omega}} \def\oo{{\omega^{\omega}}} \def\lo{{\omega^{<\omega}}} \def\d{{\dot{\bigcup}}} \def\h{{\cal H}} \def\no{\noindent} \def\a{{\mathcal A}} \def\b{{\mathcal B}} \def\l{{\mathcal L}} \def\n{{\mathcal N}} \def\m{{\mathcal M}} \def\p{{\mathcal P}} \def\h{{\mathcal H}} \def\co{{\mathcal O}} \def\t{{\mathcal T}} \def\c{{\mathcal C}} \title{\huge Cardinalities in the projective hierarchy} \author{Greg Hjorth} % Enter your name between curly braces \date{2000} % Enter your date or \today between curly braces \maketitle \tableofcontents \section{Introduction} \label{introduction} We show that the ``effective cardinality" of the collection of $\Ubf{\Pi}^1_{n+1}$ sets is strictly bigger than the effective cardinality of the $\Ubf{\Pi}^1_n$. The phrase {\it effective cardinality} is vague but can be made exact in the usual ways. For instance: \begin{theorem} Assume ${\rm AD}^{L(\R)}$. Then in $L(\R)$ there is no injection \[i: \Ubf{\Pi}^1_{n+1}\hookrightarrow \Ubf{\Pi}^1_n.\] \end{theorem} A few years ago Tony Martin showed a similar result, establishing the non-existence of an injection from $\Ubf{\Pi}^1_m$ to $\Ubf{\Pi}^1_n$ for $m$ sufficiently larger than $n$. His method did not seem to work for $m=n+1$. This present paper gives level by level calculations for the projective hierarchy, but it too falls short of a complete analysis, in as much as it leaves the position of the effective cardinals in the Wadge degrees largely obscure. At the low levels it takes some time for any new cardinals to appear. Whenever $\Gamma_1, \Gamma_2$ are non-trivial Wadge degrees strictly included in $\Ubf{\Delta}^0_2$ one has \[|\Gamma_1|_{L(\R)} = |\Gamma_2|_{L(\R)}.\] Beyond $\Ubf{\Delta}^0_2$ it is known from \cite{hjorth} that the different levels of the Borel hierarchy have distinct effective cardinalities. It is unclear whether there might be cardinals lying strictly between say $\Ubf{\Pi}^0_2$ and $\Ubf{\Pi}^0_3$, though Itay Neeman has proved that there is no $L(\R)$ injection from $\Ubf{\Pi}^0_{\alpha+2}$ to $\Ubf{\Delta}^0_{\alpha+2}$. Thus as a landmark of our ignorance: \begin{question} Is $|\Ubf{\Pi}^0_2|_{L(\R)}<|\Ubf{\Delta}^0_3|_{L(\R)}$? \end{question} \cite{andretta} provides a reference for virtually every known fact about the Wadge degrees, as well as all the general theory of $L(\R)$ required below. \cite{moschovakis} is the established text book for this kind of descriptive set theory. One can also refer to \cite{mamost} and \cite{martinsteel} for basic facts about scales in $L(\R)$ as well as the basis theorem for $\Ubf{\Sigma}^2_1$. $\S$9.2 of \cite{classification} overviews some of this material and along with \cite{dichotomy} presents an introduction to the theory of cardinality for non-wellorderable sets in $L(\R)$. \newpage \section{Outline} The plan is something like this. We suppose for a contradiction that there is an $L(\R)$ injection from $\Ubf{\Pi}^1_2$ into $\Ubf{\Pi}^1_1$. Formally speaking we are only working with the case $n=1$, but it will be clear that the proof generalizes. We then want to find some suitable forcing notion for introducing codes for $\Ubf{\Pi}^1_2$ sets, $\p_\h$, and some suitable Polish space of codes for $\Ubf{\Pi}^1_1$ sets, call it $\c_1$, and we argue from uniformization$(\Ubf{\Sigma}^2_1)$ that there must be an actual $L(\R)$ function \[\theta: {\rm Filters \: for\: } \p_\h\rightarrow \c_1\] such that for all sufficiently generic $G_1, G_2\subset \p_\h$ we have that $G_1$ and $G_2$ give rise to the same $\Ubf{\Pi}^1_2$ sets if and only if $\theta(G_1)$ and $\theta(G_2)$ code the same $\Ubf{\Pi}^1_1$ sets\footnote{In $\S$\ref{finishing} when the details are finally played out, we will use the Polish space of all downward closed subsets of $\{0,1\}^{<\omega}\times \omega^{<\omega}$ as our space $\c_1$ of codes; in the usual way this can be identified with a closed subset of $\{0,1\}^{(\{0,1\}^{<\omega}\times \omega^{<\omega})}$. $\p_\h$ is given in section \ref{hairy}, and will analogously consist of finite partial attempts to build a downward closed subset of $\{0,1\}^{<\omega}\times (\omega\times\omega)^{<\omega}$.}. Since all functions in $L(\R)$ are continuous on a comeager set we obtain that \[G\mapsto \theta(G)\] will be continuous for any sufficiently generic $G$. Given codes $C_1, C_2$ for $\Ubf{\Pi}^1_2$ we want to {\it continuously} assign generics \[G_1(C_1, C_2), G_2(C_1, C_2)\subset\p_\h\] such that $G_1$ and $G_2$ give rise to the same $\Ubf{\Pi}^1_2$ sets if and only if $C_1$ and $C_2$ give rise to the same $\Ubf{\Pi}^1_2$. Then by composing with $\theta$ we have that \[(C_1, C_2)\mapsto (\theta(G_1(C_1, C_2)), \theta(G_2(C_1, C_2)))\] continuously reduces equality on pairs of codes for $\Ubf{\Pi}^1_2$ sets into equality on pairs of codes for $\Ubf{\Pi}^1_1$ sets. Since the former is $\Ubf{\Pi}^1_3$ complete and the later is only $\Ubf{\Pi}^1_2$ we have a contradiction. In $\S$\ref{hairy} we present the notion of forcing $\p_\h$ for introducing generic $\Ubf{\Sigma}^1_1$ subsets of $\oo\times\oo$, which will then in turn give us a $\Ubf{\Pi}^1_2$ set by universally quantifying out the second coordinate. The point here is that the forcing gives rise to such ``hairy" and unruly $\Ubf{\Sigma}^1_1$ sets that for any generic $G$ and $\Ubf{\Sigma}^1_1$ set $A_S$ we will have room to find many ways to hide a copy of $A_S$ inside the $\Ubf{\Sigma}^1_1$ set given by $G$. $\S$\ref{amalgam} defines a method to ``amalgamate" two copies of $\p_\h$ relative to some given $\Ubf{\Sigma}^1_1$ sets. Given $A_{S_1}, A_{S_2}\subset 2^\o\times \oo$, both $\Ubf{\Sigma}^1_1$, we can continuously from some space of codes find a forcing \[\p_\h\otimes_{S_1, S_2}\p_\h;\] the generic object on this amalgamated forcing will provide a pair of generic (but not necessarily mutually generic) $G_1, G_2\subset \p_\h$, giving rise to \[A_{G_1}, A_{G_2}\subset \oo\times\oo\] \[\Phi: 2^\o\rightarrow \oo\] such that for all $(x, y)\in 2^\o\times\oo$ we have \[(x, y)\in A_{S_i}\Leftrightarrow (\Phi(x), y)\in A_{G_i}\] $i=1, 2,$ and for all $z$ not in the range of $\Phi$ \[(z, y)\in A_{S_1}\Leftrightarrow (z, y)\in A_{S_2}.\] The technical part of the proof is to verify in $\S$\ref{dense} that the various open dense sets in $\p_\h$ appropriately lift up to open dense sets in $\p_\h\otimes_{S_1, S_2}\p_\h$ and that the generic object on this amalgamated forcing will have the various properties claimed in the paragraph before. The details in this technical part of the proof are numerous. Perhaps there are too many. \newpage \section{Notational issues} \label{notation} \begin{notation} For us $\omega$ denotes the set of natural numbers, and we begin counting at 0:- $\omega=\{0,1,2,...\}$. In this controversial issue we follow the usual practice of set theorists. We use $\lo$ to denote \[\bigcup_{k\in\o}\omega^k,\] where \[\omega^k=\{f:\{0, 1,...,k-1\}\rightarrow \omega\},\] $2^{<\o}$ for \[\bigcup_{k\in\o}\{0,1 \}^k,\] and $(\o\times \o)^{<\omega}$ for \[\bigcup_{k\in\o}\omega^k\times \omega^k.\] We view $\lo$ as ordered by inclusion in the usual way. For $u, v\in \lo$ we write $u^\smallfrown v$ for the concatenation, obtained by letting the second sequence be adjoined onto the end of the first. For $j\in\o$ we write $u^\smallfrown j$, rather than $u^\smallfrown \langle j\rangle$, for the result of adjoining the sequence $\langle j \rangle $ of length one to $u$. Cheating ever so slightly, we shall describe the natural ordering on $(\o\times\o)^{<\omega}$ as inclusion and accordingly write \[(u, v)\subset (u', v')\] for $(u, v), (u', v')\in (\o\times\o)^{<\omega}$ when $u\subset u'$, $v\subset v'$. Very often we will use $s$ for an arbitrary element $s\in (\o\times\o)^{<\o}$ of the form $s=(u, v)$. For $s=(u, v)$, $t=(w, r)\in (\o\times \o)^{<\o}$ we let \[s^\smallfrown t=_{\rm df} (u^\smallfrown w, v^\smallfrown r).\] $\ell(u)$ denotes the length of $u$, so that $u\in \o^{\ell (u)}$. For $u\in \lo$ of non-zero length, we let $u^-$ denote its predecessor: So that $u^-\subset u$ and $\ell (u^-)=\ell(u)-1$. If $s=(u, v)\in (\o\times\o)^{<\o}$ then $s^-=(u^-, v^-)$. \end{notation} \begin{definition} A set $T\subset \lo\times (\o\times\o)^{<\o}$ is said to be {\it downwards closed} if whenever \[(u, (v, w))\in T\] and $u'\subset u$, $(v', w')\subset (v, w)$ then \[(u', (v', w'))\in T.\] Given such a $T$ we let $A_T$ be the $\Ubf{\Sigma}^1_1$ set of $(x, y)\in \oo\times \oo$ for which there exists $f\in \oo$ such that at each $n, m\in \o$ \[(x | _n, (y| _m, f| _m))\in S.\] \end{definition} Note that by the assumption of being downward closed, we in fact obtain that \[A_T=\{(x, y): \exists f\forall n(x| _n, (y| _n, f| _n))\in T\}.\] \def\t{{\mathcal T}} \begin{notation} For $(u,s)\in \lo\times (\o\times\o)^{<\o}$ we let \[\t_{(u,s)}=\{(u',s')\in\lo\times (\o\times\o)^{<\o}| u\subset u', s\subset s'\}.\] \end{notation} \newpage \section{Hairy $\Ubf{\Sigma}^1_1$ set forcing: $\p_\h$} \label{hairy} We describe a forcing notion which produces a complicated $\Ubf{\Sigma}^1_1$ set. \begin{definition} We let $\p_\h$ denote the set of pairs $(T, p)$ such that \begin{enumerate} \item \[T\subset \lo\times (\o\times \o)^{<\o}\] is finite and closed downwards; \item \[p: T\rightarrow \{0, 1\}\] has the property that if \[p(u, s)=0\] and $u\subset u',$ $ s\subset s',$ then \[p(u', s')=0;\] \item $p(u,(0,0))\neq 0$ all $u\in\lo$. \end{enumerate} We order $\p_\h$ by extension, so that \[(T', p')\leq (T, p)\] if $T'\supset T$ and $p'\supset p$. \end{definition} \begin{lemma} \label{compatible} $(T, p), (T', p')\in \p_\h$ are such that \[p|_{T\cap T'}=p'|_{T \cap T'}\] then $(T, p), (T',p')$ are compatible, in the sense that there is some $(T^*, p^*) \in \p_\h$ with \[(T^*, p^*)\leq (T, p), (T',p').\] \end{lemma} \begin{proof} We let $T^{*}=T'\cup T$ and $p^{*}=p'\cup p$. We need to see that this pair $(T^{*}, p^{*})$ is an element of $\p_\h$. The first and last conditions in the definition of $\p_\h$ immediately hold, and for the second we see that if $(u, s)\in T^{*}$ with $p^{*}(u,s)=1$ then we may assume without loss that $(u, s)\in T$, and so for all $(u', s')\subset (u, s)$ we have $p(u',s')=1$ by $(T, p)\in \p_\h$, and hence $p^{*}(u',s')=1$. \end{proof} \begin{lemma} \label{extend} Suppose $(T', p')\leq (T, p)$, $(T',p')\neq (T, p)$. Then there is a condition $(T^*, p^*)$ with \[(T',p')\leq (T^*, p^*)\leq (T, p)\] and \[|T^*|=|T|+1.\] \end{lemma} \begin{proof} Choose some $(u, s)\in T'\setminus T$. Choose $(u_0, s_0)$ with $lh(u_0)+lh(s_0)$ minimal subject to the constraint that \[u_0\subset u\] \[s_0\subset s\] \[(u_0, s_0)\notin T.\] Thus for any other $u_1\subset u_0$, $s_1\subset s_0$ with $(u_1, s_1)\neq (u_0, s_0)$ we have $(u_1, s_1)\in T$. Then let $T^*=T\cup\{(u_0, s_0)\}$ and $p^*=p'|_{T^*}$. \end{proof} \begin{definition} For $G\subset \p_\h$ a sufficiently generic filter we obtain a downward closed set $T_G\subset \lo\times (\o\times \o)^{<\o}$ by \[T_G=\{(u, s): \exists p\in G(p(u, s)=1)\}\] and a corresponding $\Ubf{\Sigma}^1_1$ set $A_G$ by taking the definition of $A_{T_G}$ from the previous section: \[A_G=_{\rm df}A_{T_G}=\{(x, y): \exists f\forall n(x| _n, (y| _n, f| _n))\in T_G\}.\] \end{definition} \newpage \section{And its amalgam: $\p_\h\otimes_{S_1, S_2}\p_\h$} \label{amalgam} \label{amalgamation} \begin{definition} Let $S_1, S_2\subset 2^{<\o}\times(\o\times\o)^{<\o}$ be two sets that are closed downwards. We then define $\p_\h\otimes_{S_1, S_2}\p_\h$ to be the set of sequences \[q=(T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\] satisfying the following conditions (for which we parenthetically provide some brief motivation along the way): \leftskip 0.4in \noindent (1) $(T, p_i)\in\p_\h$ for $i=1, 2$; (ultimately the forcing will try to generate two generics in $\p_\h$); \noindent (2) $U\subset 2^{<\o}$ is a finite non-empty subtree and \[\varphi: U\rightarrow \lo\] is an ordering preserving injection; \noindent (3) $V\subset (\o\times\o)^{<\o}$ is a finite non-empty subtree and \[\psi: V\rightarrow (\o\times \o)^{<\o}\] is an order and length preserving injection, with the property that each \[\psi(v, w)=(v, \psi_0(v, w)),\] some $\psi_0(v, w)\in \o^{<\o}$; ($\varphi, \psi$ are partial attempts to describe a copy of $2^{<\o}\times (\o\times\o)^{<\o}$ inside $\o^{<\o}\times (\o\times\o)^{<\o}$); \noindent (4) if we define \[\hat{U}(q)=\{u|\exists u'\in U(u\subset \varphi(u'))\},\] \[\hat{V}(q)=\{s|\exists s'\in V(s\subset \psi(s'))\},\] then \leftskip 0.6in \noindent (a) $\hat{U}(q)\cap A=0;$ \noindent (b) $\hat{V}(q)\cap B=0$; \noindent (c) $\hat{U}(q)\times \hat{V}(q)\subset T\subset (\hat{U}(q)\cup A)\times (\hat{V}(q)\cup B)$, and in turn \[(\hat{U}(q)\cup A)\times (\hat{V}(q)\cup B) \subset \{(u, s)|\exists u', s' ((u, s')\in T, (u', s)\in T)\},\] so that in particular $A$ and $B$ are finite; \leftskip 0.4in \no note that (3) actually implies $\hat{V}(q)=\psi[V]$; ($A$ and $B$ describe ``forbidden" sets on which the copying functions $\varphi$ and $\psi$ can never extend; $T$ in turn at (c) includes everything necessitated by $A$, $B$, and the ranges of $\varphi$ and $\psi$); \noindent (5) for all $u\in U$, $s\in V$ we have $p_i(\varphi(u), \psi(s))=1$ if and only if $(u, s)\in S_i$, $i=1, 2$; \noindent (6) if we let $E_1(q)$ be the set of $(u, s)$ such that \leftskip 0.9in \noindent (i) $u\in A$ \noindent (ii) $u^-\in \hat{U}(q)$ \noindent (iii) $p_1(u, s^-)=p_2(u, s^-)=1$ \noindent (iv) $p_1(u, s)=1$ \noindent (v) $p_2(u, s)=0$ \noindent (so that $E_1(q)$ refers to certain nodes on which the generic below $(T, p_2)$ is unable to produce any infinite branches, while the generic below $(T,p_1)$ is still open to do so; ultimately we want that the generic objects should give rise to $\Ubf{\Sigma}^1_1$ sets which agree outside the ranges of $\psi$, and hence the function $\sigma$ below at (a)-(g) is intended to busily run around and even up this possible imbalance); \leftskip 0.4in and if we similarly let $E_2(q)$ be the set of $(u, s)$ such that \leftskip 0.9in \noindent (i) $u\in A$ \noindent (ii) $u^-\in \hat{U}(q)$ \noindent (iii) $p_1(u, s^-)=p_2(u, s^-)=1$ \noindent (iv) $p_1(u, s)=0$ \noindent (v) $p_2(u, s)=1$ \leftskip 0.4in \noindent then we obtain that \leftskip 0.6in \noindent (a) Domain$(\sigma)=\bigcup\{\t_{(u, s)}| (u, s)\in E_1(q)\}\cap T$; \noindent (b) Range$(\sigma)=\bigcup\{\t_{(u, s)}| (u, s)\in E_2(q)\}\cap T$; \noindent (c) if $(u, s)\in E_1(q)$ with $s=(v, w^\smallfrown j)$, then \[\sigma(u, s)=(u, (v, w^\smallfrown k))\] some $k$ with $(u, (v, w^\smallfrown k))\in E_2(q)$; \noindent (d) for each $u\in A$ with $u^-\in \hat{U}(q)$ there is a corresponding function \[\sigma_u: \bigcup\{\t_{(u, s)}| (u, s)\in E_1(q)\}\rightarrow \lo\] such that for all $(u, (v, w))\in E_1(q)$ and $(u', (v', w^\smallfrown r))\in \t_{(u, (v, w))}$ we have \[\sigma(u', (v', w^\smallfrown r))=(u', (v', w^\smallfrown \sigma_u(v', w^\smallfrown r)));\] so the $\sigma$ acting on some point $(u', s')$ above $(u, s)\in E_1(q)$ leaves $u'$ untouched, leaves the first coordinate of $s'$ untouched, and its value on the second coordinate of $s'$ is a function solely of $u$ and $s'$; \noindent (e) for each $(u, s)\in E_1(q)$ \[\sigma|_{\t_{(u, s)}}: \t_{(u, s)}\cong \t_{\sigma(u, s)}\] is an isomorphism of partially ordered sets; \noindent (f) for each $(u, s)\in E_1(q)$ and $u'\supset u$, $s'\supset s$ we have \[p_1(u',s')=p_2(\sigma(u',s'));\] \noindent (g) if $u\in A$ and \[p_1(u, s)\neq p_2(u, s)\] then there are $u'\subset u, s'\subset s$ with \[(u', s')\in E_1(q)\cup E_2(q).\] \leftskip 0in We order $\p_\h\otimes_{S_1, S_2}\p_\h$ by coordinate wise extension, except on the $\varphi$ coordinate where we permit on terminal nodes of $U$ lengthening of the value of $\varphi(u)$. In other words, \[(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\leq (T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\] in $\p_\h\otimes_{S_1, S_2}\p_\h$ if \begin{enumerate} \item $T'\supset T$, \item $p_1'\supset p_1$, \item $p_2'\supset p_2$, \item $U'\supset U$, \item $A'\supset A$, \item $V'\supset V$, \item $B'\supset B$, \item $\sigma'\supset \sigma$, \item $\psi'\supset \psi$, \item for $u\in U$ not terminal we have \[\varphi'(u)=\varphi(u)\] while for $u\in U$ terminal in $U$ we have \[\varphi'(u)\supset \varphi(u){\rm .}\] \end{enumerate} The idea of the forcing is this: On $\hat{U}(q)\times \hat{V}(q)$ we have $p_1$ and $p_2$ constrained by the sets $S_1$ and $S_2$ respectively. Outside of $\hat{U}(q)\times \hat{V}(q)$ we try to make $p_1$ and $p_2$ match up as far as possible. Sometimes the commitments previously made on $\hat{U}(q)\times \hat{V}(q)$ prevent us, and this is tracked by the sets $E_1(q)$ and $E_2(q)$; and so below these bad points we use the $\sigma_u$ isomorphisms to at least ensure that the resulting $\Ubf{\Sigma}^1_1$ sets defined by the generic object $G$ will be the same outside the tree defined by projecting $\bigcup_{q\in G}\hat{U}(q)\times \hat{V}(q)$ to the set \[\{(u, v): \exists w\exists q\in G ((u, (v, w))\in \hat{U}(q)\times \hat{V}(q))\}.\] There is an assymetry between the requirements on $\varphi$ at (2) and $\psi$ at (3). $\psi$ is as a matter of law length preserving; $\varphi$ need not be. This shows up at \ref{claim3} below; it is technically convenient to have the ability to extend $\varphi$ so that \[p_1(\varphi(u), s)=p_2(\varphi(u), s)=0\] for any $s \in B$ and $u$ terminal in $U$. \end{definition} \newpage \section{Some dense sets for $\p_\h\otimes_{S_1, S_2}\p_\h$} \label{dense} For this section fix $S_1, S_2\subset 2^{<\o}\times (\o\times\o)^{<\o}$ downward closed. \begin{lemma} \label{5.0} Suppose \[q=(T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\] is in $\p_\h\otimes_{S_1, S_2}\p_\h$ and that we have conditions \[(T'',p'')\leq (T', p')\leq (T, p_1)\] with $|T'|=|T|+1$. Then there is \[q^*=(T^*, p_1^*, p_2^*, U^*, A^*, \varphi^*, V^*, B^*, \psi^*, \sigma^*)\] with \[(T^*, p_1^*)\leq (T',p')\] and $(T^*, p_1^*)$ still compatible with $(T'', p'')$. \end{lemma} \begin{proof} Let $(u, s)$ be such that $T'=T\cup{(u, s)}$. \smallskip Case(1) $u\in \hat{U}(q)$. \smallskip In this case it follows from $(u, s)\notin T$ that we have $s\notin \hat{V}(q)$. So we let \[T^*=T'=T\cup\{(u, s)\}\] \[p_1^*(u,s)=p''(u, s)=p'(u,s)\] \[p_2^*(u, s)=0\] \[p_1^*|_T=p_1\] \[p_2^*|_T=p_2\] \[U^*=U\] \[\varphi^*=\varphi\] \[V^*=V\] \[\psi^*=\psi\] \[A=A^*\] \[B^*=B\cup\{s\}\] \[\sigma^*=\sigma\] \[q^*=(T^*, p_1^*, p_2^*, U^*, A^*, \varphi^*, V^*, B^*, \psi^*, \sigma^*).\] Since $u\in \hat{U}(q)$ and $s\notin \hat{V}(q)$ we have no possibility of violating (5) and (6) in the definition of $\p_\h\otimes_{S_1, S_2}\p_\h$. $\hat{U}(q^*)=\hat{U}(q)$ and $\hat{V}(q^*)=\hat{V}(q)$, and so we maintain (4). $\varphi^*=\varphi$ and $\psi^*=\psi$ easily give (2) and (3). We have (1) by assumption of $(T', p')\in \p_\h$ and choice of $p_2^*$; here it is important that $s\neq (0,0)$ by case assumption and the part (3) of the amalgam forcing stating $V\neq \emptyset$, and so $p_2^*(u, s)=0$ creates no conflict with the definition of $\p_\h$. Finally since $(T^*, p_1^*)=(T',p')$ we obtain \[(T'', p'')\leq (T^*, p_1^*),\] which is certainly enough to show these two conditions compatible. \smallskip Case(2) $u^-\in \hat{U}(q)$, $u\notin \hat{U}(q)$. \smallskip Here we may as well assume that $s\neq (0, 0)$, since otherwise we would have $p'(u, s)=1$, and we could extend $q$ in a care free manner, with $p_1^*(u,s)=p_2^*(u, s)=1$, $A^*=A\cup\{u\}$, $B=B^*$, $\varphi^*=\varphi$, $\psi^*=\psi$, and as in case(1) the various conditions in the definition of the forcing follow easily. So we make this assumption. In particular then since $T'=T\cup\{(u, s)\}$ is downward closed, it follows that $(u,s^-)\in T$, and thus from the case assumption that $u\in A$. Similarly $(u^-, s)\in T$ so $s\in B\cup\hat{V}(q)$. \smallskip Subcase(2a) $p_1(u^-, s)=p_2(u^-, s)$ and for all $s^*\subset s$ we have $p_1(u, s^*)=p_2(u, s^*)$. \smallskip Then just let \[T^*=T'=T\cup\{(u, s)\}\] \[p_1^*(u,s)=p_2^*(u,s)=p''(u, s)=p'(u,s)\] \[p_1^*|_T=p_1|_T\] \[p_2^*|_T=p_2|_T\] \[U^*=U\] \[\varphi^*=\varphi\] \[V^*=V\] \[\psi^*=\psi\] \[A^*=A\] \[B^*=B\] \[\sigma^*=\sigma\] \[q^*=(T^*, p_1^*, p_2^*, U^*, A^*, \varphi^*, V^*, B^*, \psi^*, \sigma^*).\] Since $(u^-, s)\in T$ we have no trouble with clause (c) of part (4) of the definition of $\p_\h\otimes_{S_1, S_2}\p_\h$, while (4)(a) and (4)(b) follow as in the last case. (6) is no problem, since we have added no new elements to $E_1(q^*)$, $E_2(q^*)$ nor any new elements to $T^*$ extending a point in $E_1(q)\cup E_2(q)$. (5) is for free since $U, \varphi, V, \psi$ are left unchanged. Similarly (2) and (3) continue to hold almost vacuously. We obtain (1) by assumption on $(T', p')$ along with our case hypothesis. As in the first case of the proof, we have $(T^*, p_1^*)\leq (T'',p'')$. \smallskip Subcase(2b) $p_1(u^-, s)\neq p_2(u^-, s)$ but for all $s^*\subset s,$ $s^*\neq s$, we have $p_1(u, s^*)=p_2(u, s^*)$. \smallskip If $p'(u,s)=0$ then we can go ahead and let \[p^*_1(u,s)=p^*_2(u,s)=0,\] and the whole thing finishes up as in the earlier cases. So suppose instead that $p'(u,s)=1$. Then the definition of $\p_\h$ and the assumptions of this subcase entail \[p_1(u^-, s)=1,\] \[p_2(u^-, s)=0.\] Here we have $s\neq(0,0)$. Thus we may write \[s=(v, w^\smallfrown j)\] for some $j\in\o$. Choose $k$ with \[(\hat{u}, (v, w^\smallfrown k))\notin T''\] all $\hat{u}\in\lo$. We define $\sigma^*$ to be the extension of $\sigma$ obtained by adding $(u, (v, w^\smallfrown j))$ to its domain and setting \[\sigma^*(u, (v, w^\smallfrown j))=(u, (v, w^\smallfrown k)).\] We let \[T^*=T\cup\{(u,s)\}\cup \{(\hat{u},(v, w^\smallfrown k))|\hat{u}\subset u\}.\] We extend $p_1$ and $p_2$ to $p_1^*$ and $p_2^*$ both having domain $T^*$ with \[p_1^*(u, s)=1\] \[p_2^*(u,s)=0\] and for all $\hat{u}\subset u$ \[p_1^*(\hat{u}, (v, w^\smallfrown k))=0\] \[p_2^*(\hat{u}, (v, w^\smallfrown k))=1.\] This clearly guarantees our $q^*$ will satisfy (1) from the definition of the forcing. As before we can let \[\varphi^*=\varphi\] \[U^*=U\] \[\psi^*=\psi\] \[V^*=V\] and obtain (2), (3), and (5) without any work. Letting $A^*=A$ and $B^*=B\cup\{(v, w^\smallfrown k)\}$ we obtain (4). Our choice of $\sigma^*$ maintains (6). We have $(T^*, p_1^*)$ compatible with $(T'', p'')$ by \ref{compatible}. \smallskip Subcase(2c) There is some $s^*\subset s$, $s^*\neq s$, with $p_1(u, s^*) \neq p_2(u, s^*)$. \smallskip Then by (6)(g) of the definition of $\p_\h\otimes_{S_1, S_2}\p_\h$ we have some $s^*\subset s$, $s^*\neq s$ with \[(u, s^*)\in E_1(q)\cup E_2(q).\] We us assume the $(u,s^*)$ in $E_1(q)$, since the case of $(u,s^*)$ in $E_2(q)$ is similar, just with $\sigma^{-1}$ instead of $\sigma$. Let $s=(v, w^\smallfrown j)$. Fix $\hat{w}$ with \[\sigma(u, (v^-, w))=(u, (v^-, \hat{w})).\] We then choose $k$ with \[(\hat{u}, (\hat{v}, \hat{w}^\smallfrown k))\notin T''\] for any $\hat{u}, \hat{v}$. By assumption on $\sigma$ we must have \[p_1(u, s^-)=p_2(\sigma (u, s^-))=p_2(u, (v^-, \hat{w}))=1\] \[p_2(u, s^-)=0=p_1(\sigma(u, s^-)).\] We then let $T^*=T\cup \{(u, s)\}\cup \{(\hat{u}, (v, \hat{w}^\smallfrown k))| \hat{u}\subset u\}$ and we define $p_1^*, p_2^*$ to have domain $T^*$, extending $p_1, p_2$ by \[p^*_1(u, s)=p_2^*(u, (v, \hat{w}^\smallfrown k))=p'(u, s)=1\] \[p_2^*(u, s)=p_1^*(u, (v, \hat{w}^\smallfrown k))=0\] and for all $\hat{u}\subset u$ \[p_1^*(\hat{u}, (v, \hat{w}^\smallfrown k))=0\] \[p_2^*(\hat{u}, (v, \hat{w}^\smallfrown k))=p'(\hat{u}, s)=1.\] It is pretty clear that $(T^*, p_1^*)\in \p_\h$ for $i=1, 2$ and \[(T^*, p_1^*)\leq (T', p'),\] and by \ref{compatible} we have $(T^*, p^*_1)$ and $(T'', p'')$ compatible in $\p_\h$. Now we can continue on in the usual way, letting $\psi^*=\psi$, $\varphi^*=\varphi$, $U^*=U$, $V^*=V$, $A^*=A$, $B^*=B\cup \{(v, \hat{w}^\smallfrown k) \}$, and define $\sigma^*$ to be the extension of $\sigma$ to the domain$(\sigma)\cup \{(u,s)\}$ with \[\sigma^*(u,s)=(u, (v, \hat{w}^\smallfrown k)).\] Then take \[q^*=(T^*, p_1^*, p_2^*, U^*, A^*, \varphi^*, V^*, B^*, \psi^*, \sigma^*).\] As remarked above we have (1) in the definition of $\p_\h\otimes_{S_1, S_2}\p_\h$ since we still have each $(T^*, p_i^*)\in \p_\h$. (2), (3), (4), and (5) follow more or less for free. (6) follows from our exact choice of $\sigma^*$ and the construction above. \smallskip Case(3) $u, u^-\notin \hat{U}(q)$. \smallskip Subcase (3a) For all $\hat{u}\subset u$, $\hat{s}\subset s$, if $\hat{u}\in A$ and $(\hat{u}, \hat{s})\in T$ then \[p_1(\hat{u}, \hat{s})=p_2(\hat{u}, \hat{s}).\] \smallskip In particular this gives first of all that \[p_1(u^-, s)=p_2(u^-, s)\] \[p_1(u, s^-)=p_2(u, s^-)\] and secondly that no $(\hat{u}, \hat{s})\subset (u, s)$ is in the domain of $\sigma$. Then we proceed as in subcase(2a). \smallskip Subcase(3b) There exists $(\hat{u}, \hat{s})$ with \[\hat{u}\subset u\] \[\hat{s}\subset s\] \[\hat{u}\in A\] \[p_1(\hat{u}, \hat{s})\neq p_2(\hat{u}, \hat{s}).\] \smallskip It follows then from the definition of $q\in \p_\h\otimes_{S_1, S_2}\p_\h$ that for $u_0\subset u$ minimal with $u_0\in A$ we must have some $s_0\subset s$ with \[(u_0, s_0)\in E_1(q)\cup E_2(q);\] let us assume $(u_0, s_0)\in E_1(q)$, since the situation with $(u_0, s_0)\in E_2(q)$ is a mirror image of this one. Then $(u^-, s)\in $ domain$(\sigma)$, and so there is some $\hat{w}$ with \[\sigma(u^-, s)=(u^-, (v, \hat{w})),\] where $s=(v, w)$. This forces onto us the definition of $\sigma^*$: Its domain is domain$(\sigma)\cup \{(u, s)\}$ and $\sigma^*(u, s)=(u, (v, \hat{w}))$. The assumption on $\sigma$, that it accords with (6), implies that for all $\hat{u}$ with $u_0\subset \hat{u}\subset u$, $\hat{u}\neq u$ \[p_1(\hat{u}, s)=p_2(\hat{u}, (v, \hat{w}));\] similarly \[p_1(u, s^-)=p_2(u, \sigma(s^-))=p_2(u, (\sigma(s))^-) =p_2(u, (v^-, \hat{w}^-)).\] Therefore we can let $T^*=T\cup\{(u, s), (u, (v, \hat{w}))\}$ and let $p_1^*, p^*_2$ be the extensions of $p_1, p_2$ to $T^*$ with \[p_1^*(u, s)=p'(u,s)\] \[p_2^*(u, (v, \hat{w}))=_{\rm df} p_2^*(\sigma^*(u, s))=p'(u, s)\] \[p_1^*(u, (v, \hat{w}))=_{\rm df} p_1^*(\sigma^*(u, s))=p_2(u, s)=0.\] We let $\varphi^*=\varphi$, $\psi^*=\psi$, $U^*=U$, $V^*=V$, $A^*=A$, $B^*=B$, and \[q^*=(T^*, p_1^*, p_2^*, U^*, A^*, \varphi^*, V^*, B^*, \psi^*, \sigma^*).\] We obtain (1) in the definition of the amalgamated forcing notion by assumption on $p'$ and from $\sigma$ satisfying (6) for $q$. (2), (3), (4), and (5) are again automatic. (6) follows from the assumption on $\sigma$ and our definition of $\sigma^*$, $p_i^*(u, s)$, $p_i(\sigma^*(u, s))$, $i=1, 2$. Finally we need to see that $(T^*, p_1^*)$ is still compatible with $(T'', p'')$. For this we need to check that they agree on their common domain. We first obtain that $p_1^*(u, s)=p'(u, s)=p''(u,s)$ by assumption on $p'$. On the other new element of $T^*$ we have $p_1^*(u, (v, \hat{w}))=0$, and we need to see that this does not differ from $p''(u, (v, \hat{w}))$. But by assumption $\sigma(u_0, s_0)\subset (u, (v, \hat{w}))$ we must have some $w_0\subset \hat{w}, v_0\subset v$ with \[p_1(u_0, (v_0, w_0))=0\] and hence by our assumption $p''\leq p_1$ \[p''(u_0, (v_0, w_0))=0\] hence \[p''(u, (v, \hat{w}))=0.\] \end{proof} \begin{corollary} \label{claim1} If $\co\subset \p_\h$ is open dense, then the set $(\co)^*$ of \[(T^*, p_1^*, p_2^*, U^*, A', \varphi^*, V^*, B^*, \psi^*, \sigma^*)\in \p_\h\otimes_{S_1, S_2}\p_\h\] with $(T^*, p_1^*)\in \co$ is again open dense in $\p_\h\otimes_{S_1, S_2}\p_\h$. \end{corollary} \begin{proof} We successively apply \ref{5.0} and \ref{extend} to extend $(T_1, p_1)$ until we at last have a condition \[(T^*, p_1^*, p_2^*, U^*, A', \varphi^*, V^*, B^*, \psi^*, \sigma^*)\] with $(T^*, p_1^*)$ actually extending some $(T'', p'')\in \co$. \end{proof} \begin{corollary} \label{corollary1} For each $u\in\lo$ and $s\in (\o\times\o)^{<\o}$ we have that the set of \[(T^*, p_1^*, p_2^*, U^*, A^*, \varphi^*, V^*, B^*, \psi^*, \sigma^*)\in \p_\h\otimes_{S_1, S_2}\p_\h\] with \[(u, s)\in T^*\] is open dense. \end{corollary} \begin{lemma} \label{claim1a} If $\co\subset \p_\h$ is open dense, then the set $(\co)_*$ of \[(T^*, p_1^*, p_2^*, U^*, A^*, \varphi^*, V^*, B^*, \psi^*, \sigma^*)\in \p_\h\otimes_{S_1, S_2}\p_\h\] with $(T^*, p_2^*)\in \co$ is again open dense in $\p_\h\otimes_{S_1, S_2}\p_\h$. \end{lemma} \begin{proof} The proof is exactly symmetrical to \ref{claim1}. \end{proof} \def\amalg{\p_\h\otimes_{S_1, S_2}\p_\h} \begin{lemma} \label{claim2a} For each $u\in 2^{<\o}$ and $j\in \{0,1\}$, the set of \[(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\in \p_\h\otimes_{S_1, S_2}\p_\h\] such that if $u\in U'$ then $u^\smallfrown j\in U'$ is dense. \end{lemma} \begin{proof} Choose some \[q=(T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in \p_\h\otimes_{S_1, S_2}\p_\h.\] If $u\not\in U$ then we are already done, so suppose instead $u\in U$ and $u^\smallfrown j\notin U$. Then we can simply extend $\varphi$ to $\varphi'$ with \[\varphi'(u^\smallfrown j)=\varphi(u)^\smallfrown k\] for some \[\varphi(u)^\smallfrown k\not\in A\cup \hat{U}(q).\] For $s\in V$ we can set $p_i'(\varphi(u)^\smallfrown k, \psi(s))=1$ if $(u^\smallfrown j, s)\in S_i$ and $=0$ if $(u^\smallfrown j, s)\not\in S_i$. We let $\psi'=\psi$, $V'=V$, $A'=A$, $B'=B$, $U'=U\cup\{(u^\smallfrown j)\}$. We let $\hat{U}'=\{\hat{u}| \exists u\in U'(\hat{u}\subset \varphi'(u)\}$, $T'=T\cup \hat{U}'\times \hat{V}(q)$. \end{proof} \begin{corollary} \label{corollary2a} For each $u\in 2^{<\o}$, the set of \[(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\in \p_\h\otimes_{S_1, S_2}\p_\h\] with $u\in U'$ is open dense. \end{corollary} \begin{lemma} \label{claim2b} For each $(v, w)\in(\o\times\o)^{<\o}$ and $j, k\in\o$, the set of \[(T', p_1', p_2', U', A', \varphi', V', B', \psi', \hat{V'} \sigma')\in \p_\h\otimes_{S_1, S_2}\p_\h\] such that if $(v, w)\in V'$ then $(v^\smallfrown j, w^\smallfrown k)\in V'$ is dense. \end{lemma} \begin{proof} This is similar to \ref{claim2a}. \end{proof} \begin{corollary} \label{corollary2b} For each $s\in (\o\times\o)^{<\o}$, the set of \[(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\in \p_\h\otimes_{S_1, S_2}\p_\h\] with $s\in V'$ is open dense. \end{corollary} \begin{lemma} \label{help} For all \[q=(T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in \p_\h\otimes_{S_1, S_2}\p_\h\] and $W\supset U$ a subtree of $2^{<\o}$, there is \[(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\leq (T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\] with $U'=W$. \end{lemma} \begin{proof} We let $U'=W$, $V'=V$, $\psi'=\psi$, $A'=A$, $B'=B$, and then let \[\varphi': W\rightarrow \lo\] be any one to one order preserving function extending $\varphi$ such that for all $u\in W\setminus U$ we have \[\varphi'(u) \notin \hat{U}(q)\cup A.\] We define \[\hat{U}'=\{\hat{u}|\exists u\in W(\varphi(u)\supset \hat{u})\}\] and \[T'=T\bigcup \hat{U'}\times \hat{V}(q),\] and we require that on each $(\varphi'(u), \psi(s))$ for $u\in W, s\in V$, and $i=1, 2$ \[p_i'(\varphi'(u), \psi(s))=1\Leftrightarrow (u, s)\in S_i,\] \[p_i'(\varphi'(u), \psi(s))=0\Leftrightarrow (u, s)\not\in S_i.\] For other arguments $(u,s)\in \hat{U}'\times \hat{V}(q)$, not in $T\cup (\varphi'[W]\times \psi[V])$, we go to the maximal $\hat{u}\subset u$ with $\hat{u}\in \varphi[W]$ and let \[p_i'(u, s)=p_i'(\varphi'^{-1}(\hat{u}), \psi^{-1}(s)).\] (The properties of $\psi$ given at (3) in the definition of the forcing notion are already enough to imply $s$ is in the range of $\psi$). \end{proof} \begin{lemma} \label{claim3} The set of \[(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\in \p_\h\otimes_{S_1, S_2}\p_\h\] such that \leftskip 0.5in \noindent (1) for some $\ell $, \[U'=\{0,1\}^\ell =_{\rm df}\{u\mid u: \{0, 1, ...\ell -1\}\rightarrow \{0, 1\}\}{\rm ,}\] and \noindent (2) for all $u\in \{0,1\}^\ell $ and $s\in B'$ \[p_1'(\varphi'(u), s)=p_2'(\varphi'(u), s)=0\] \leftskip 0in \noindent is dense. \end{lemma} \begin{proof} Fix \[q=(T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in \p_\h\otimes_{S_1, S_2}\p_\h.\] Applying \ref{help} we can assume $U$ has the indicated form $U=\{0,1\}^\ell $ for some $\ell $. Let $u_1, u_2,...u_k$ ($k=2^\ell $) enumerate the terminal vertices in $U$. For each $i\leq k$ choose some $n(i)$ with \[\varphi(u_i)^\smallfrown n(i)\not\in A.\] Then let \[\varphi'(u_i) =\varphi(u_i)^\smallfrown n(i)\] and \[\varphi'(u)=\varphi(u)\] for $u\in U$ not terminal. Let \[T'=T\cup\{(\varphi(u_i)^\smallfrown n(i), s)\mid i\leq k, s\in B\cup \hat{V}(q)\}.\] We let $A'=A$ and $B'=B$. For $(u, s)\in T$ we of course let $p_i'(u, s)=p_i(u, s)$, $i=1, 2$. For \[(\varphi(u_i)^\smallfrown n(i), s)\in T'\setminus T\] we let \[p_i'(\varphi(u_i)^\smallfrown n(i), s)=0\] if $s\in B$ and \[p_i'(\varphi(u_i)^\smallfrown n(i), t)=p_i(\varphi(u_i), t)\] for $t=\hat{V}(q)$. \end{proof} \begin{corollary} \label{corollary3} For $s\in (\o\times\o)^{<\o}$, the set of \[q'=(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\in \p_\h\otimes_{S_1, S_2}\p_\h\] for which there exists $l\in \o$ with \leftskip 0.5in \noindent (1) $s\in \hat{V'}\cup B'$, and \noindent (2) $U'\supset \{0,1\}^l$, and \noindent (3) and we have either $s\in \hat{V}(q')$ or for all $u\in \{0, 1\}^l$ \[p_1'(\varphi(u), s)=p_2'(\varphi(u), s)=0\] \leftskip 0in \noindent is open dense. \end{corollary} \newpage \section{Some things to do with a generic} \label{things} \begin{definition} For $G\subset \p_\h\otimes_{S_1, S_2}\p_\h$ meeting all the dense open sets from corollaries \ref{corollary2a} and \ref{corollary2b} we define \[\varphi_G: 2^{<\o}\rightarrow \lo\] by \[\varphi_G(u)=\hat{u}\] if there exists \[(T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in G\] with $\varphi(u)=\hat{u}$ and $u$ not terminal in $U$. Similarly, \[\psi_G: (\o\times\o)^{<\o}\rightarrow (\o\times\o)^{<\o}\] is given by \[\psi_G(s)=\hat{s}\] if \[\exists (T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in G [\psi(s)=\hat{s}]{\rm .}\] We then define \[\Phi_G:2^\omega\rightarrow \oo\] \[\Phi_G:x\mapsto \bigcup_{n\in\o} \varphi_G(x|_n)\] and \[\Psi_G:\oo\times\oo\rightarrow \oo\times\oo\] \[\Psi_G: (y,f)\mapsto \bigcup_{m\in\o} \psi_G(y|_m,f|_m).\] We let \[\a_G=\bigcup\{x\in \oo\mid \exists (T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in G \exists n\in\o (x|_n\in A)\}{\rm .}\] We then let $\pi_1(G)\subset \p_\h$ be the set \[\{(T', p')\in \p_\h\mid \exists (T, p_1, p_2, U', A, V, B, \psi, \sigma)\in G (T'\subset T, p'\subset p_1)\}{\rm ,}\] and we let $\pi_2(G)\subset \p_\h$ be the set \[\{(T', p')\in\p_\h\mid \exists (T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in G (T'\subset T, p'\subset p_2)\}{\rm .}\] We let \[T_{\pi_1(G)}, T_{\pi_2(G)}\subset \lo\times(\o\times \o)^{<\o}\] be the subtrees indicated in section \ref{hairy}, from which we then obtain the corresponding $\Ubf{\Sigma}^1_1$ sets \[A_{\pi_i(G)}=_{\rm df} A_{T_{\pi_i(G)}}=\{(x, y)\mid \exists f\forall n \forall (T, p)\in \pi_i(G)(p(x|_n , (y|_n, f|_n))\neq 0)\}.\] \end{definition} \begin{lemma} \label{claim4} For all $G\subset \p_\h\otimes_{S_1, S_2}\p_\h$ meeting the dense sets of \ref{corollary1}, \ref{corollary2a}, \ref{corollary2b}, \ref{corollary3}, and all $x\in\a_G$, and all $y\in \oo$, if \[(x, y)\in A_{\pi_1(G)}\] then \[(x, y)\in A_{\pi_2(G)}.\] \end{lemma} \begin{proof} Choose $f\in \oo$ with \[(x|_n, (y|_m, f|_m))\in T_{\pi_1(G)}\] all $n, m$. If every such $(x|_n, (y|_m, f|_m))\in T_{\pi_2(G)}$ then we are done, so instead suppose that there is some \[(T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in G\] with $p_2(x|_n, (y|_m, f|_m))=0$ while that $p_1(x|_n, (y|_m, f|_m))=1$ by assumption on $T_{\pi_1(G)}$. By clause (6)(g) of the definition of $\amalg$ we may assume that $n$ is least with $x|_n\in A$ and $m$ is then least with $p_2(x|_n, (y|_m, f|_m))=0$. It then follows from clauses (6)(a) and (6)(b) of the definition of $\p_\h\otimes_{S_1, S_2}\p_\h$ that $(x|_n, (y|_m, f|_m))$ is in the domain of $\sigma$, \[\sigma(x|_n, (y|_m, f|_m))=(x|_n,(y|_m, w_0))\] for some $w_0\in \o^m$, and for all \[(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\leq (T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\] and $(x|_n^\smallfrown u_1, (y|_m^\smallfrown v_1, f|_m^\smallfrown w_1))\in T'$ we have \[p_1'(x|_n^\smallfrown u_1, (y|_m^\smallfrown v_1, f|_m^\smallfrown w_1)) =p_2'( \sigma'(x|_n^\smallfrown u_1, (y|_m^\smallfrown v_1, f|_m^\smallfrown w_1) )\] \[=p_2'(x|_n^\smallfrown u_1, (y|_m^\smallfrown v_1, \sigma'_{x|_n} ( y|_m^\smallfrown v_1, f|_m^\smallfrown w_1))).\] In particular if we define $h\in\oo$ by \[h|_k=\hat{w}\] if and only if there is some \[(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\in G\] with \[\sigma'_{x|_n}(y|_k, f|_k)=\hat{w}\] then \[(x|_n, (y|_m, h|_m))\in T_{\pi_2(G)}\] all $n, m$. \end{proof} \begin{lemma} \label{claim5} For all $G\subset \p_\h\otimes_{S_1, S_2}\p_\h$ meeting the dense sets of \ref{corollary1}, \ref{corollary2a}, \ref{corollary2b}, \ref{corollary3}, and all $x\in\a_G$, and all $y\in \oo$, if \[(x, y)\in A_{\pi_2(G)}\] then \[(x, y)\in A_{\pi_1(G)}.\] \end{lemma} \begin{proof} Exactly symmetrical to the proof of \ref{claim4}, but with $\sigma^{-1}$ taking up the part of $\sigma$. \end{proof} \begin{lemma} \label{7.3} For all $G\subset \p_\h\otimes_{S_1, S_2}\p_\h$ meeting the dense sets of \ref{corollary1}, \ref{corollary2a}, \ref{corollary2b}, \ref{corollary3}, and for all $x\in \oo$, \[x\in \a_G\] if and only if \[x\notin \Phi_G[2^\o].\] \end{lemma} \begin{proof} %This follows from the fact that for any %\[q=(T, p_1, p_2, U, A, \varphi, V, B, \psi, %\sigma)\in \p_\h\otimes_{S_1, S_2}\p_\h\] %we must have $\varphi$ one to one. If $x\notin \a_G$ then by \ref{corollary1} we may successively find \[q=(T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in G\] and longer and longer $u \in U$ such that for any \[q'=(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\leq p\] we must have $\varphi'(u)\subset x$. Since any such $\varphi'$ must be one to one, we can obtain a unique $\hat{x}\in 2^\o$ which is the union of all the $u$'s as above, and hence satisfies $\Phi_G(\hat{x})=x$. Conversely if $x\in \a_G$ then from (4)(a) of the definition of the amalgamated forcing we have $x\notin \Phi_G[2^\o]$. \end{proof} \begin{lemma} \label{claim6} For $i=1, 2$, and $G\subset \p_\h\otimes_{S_1, S_2}\p_\h$ meeting the dense sets of \ref{corollary1}, \ref{corollary2a}, \ref{corollary2b}, \ref{corollary3}, and $x, y, f\in\oo$, if \[\forall n, m\in \o((\Phi(x)|_n, (y|_m, f|_m))\in T_{\pi_i(G)})\] then \[(y, f)=\Psi(y, f')\] for some $f'\in \oo$. \end{lemma} \begin{proof} For this we need an observation. \noindent{\bf Claim:} $f$ is in the image of $\Psi$ if and only if whenever $m\in\o$ and \[(T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in G\] then \[(y|_m, f|_m) \notin B.\] \smallskip \noindent{\bf Proof of claim:} This equivalence follows the argument of \ref{7.3}. \hfill (Claim$\square$) \smallskip This claim granted, we apply \ref{corollary3} to see that if $s=(y|_m, f|_m)\in B$ for some \[(T, p_1, p_2, U, A, \varphi, V, B, \psi, \sigma)\in G\] then there would be some $l\in \o$ and \[(T', p_1', p_2', U', A', \varphi', V', B', \psi', \sigma')\in G\] with \[p_i'(\varphi(x|_l), s)=0.\] \end{proof} Putting together the last few claims we finally have:- \begin{proposition} \label{finally} There is a countable collection $({\mathcal D}_i)_i$ of open dense subsets of $\amalg$ such that for any filter $G$ meeting all these dense open sets we have:- (1) For all $z\in\oo\setminus \Phi_G[2^\o]$ and for all $y\in\oo$ \[(z, y)\in A_{\pi_1(G)}\Leftrightarrow (z, y)\in A_{\pi_2(G)}.\] (2) If $z=\Phi_G(x)\in \Phi_G[2^\o]$ then for all $y\in\oo$ we have \[(\Phi_G(x), y)\in A_{\pi_1(G)}\Leftrightarrow (x, y)\in A_{S_1}\] \[(\Phi_G(x), y)\in A_{\pi_2(G)}\Leftrightarrow (x, y)\in A_{S_2}.\] \end{proposition} \newpage \section{Generalities on finding generics} There are no proofs in this section. The various assertions should not need them. \begin{notation} Let PO be the set of $x\in 2^{\o\times\o}$ such that $\leq_x$ defined by \[n\leq_x m\] if and only if \[x(n,m)=1\] provides a partial order on $\o$. For $y\in 2^{\o\times \o}$ and $n\in\o$ let \[D_{y,n}=\{m| y(n, m)=1\}.\] Then let $DPO$ be the set of $(x,y)\in $ PO$\times 2^{\o\times\o}$ such that for all $n$ we have $D_{y,n}$ dense in the partially ordered set \[(\o; \leq_x).\] \end{notation} \begin{lemma} \label{A} {\rm DPO} is a $\Ubf{\Pi}^0_2$ subset of $2^{\o\times\o}\times 2^{\o\times\o}$. \end{lemma} \begin{lemma} \label{B} There is a continuous function \[\gamma_\o: {\rm DPO}\rightarrow 2^\o\] such that for all $(x, y)\in {\rm DPO}$ the set \[\{n\in\o| (\gamma(x,y))(n)=1\}\] provides a filter on $(\o;\leq_x)$ meeting each $A_{y,n}$. \end{lemma} \def\s{{\mathcal S}} \def\t{{\mathcal T}} \def\f{{\mathcal F}} \begin{notation} Let $\s(\p_\h)$ be the set of $y\in 2^{2^{<\o}\times (\o\times\o)^{<\o}}$ such that the set \[S(y)=_{\rm df}\{(u,s)| y(u,s)=1\}\] is closed downwards. Let $\f(\p_\h)$ be the set of $z\in 2^{\p_\h}$ such that \[G(z)=\{(T,p)| z(T,p)=1\}\] provides a filter on $\p_\h$. We view $2^{\p_\h}$ as having the product topology, under which it is homeomorphic to the Cantor space $2^\o$. \end{notation} $\s(\p_\h)$ can be viewed as a closed subset of the space \[(\{0,1\})^{2^{<\o}\times (\o\times\o)^{<\o}}.\] $\f(\p_\h)$ is a $\Ubf{\Pi}^0_2$ subset of $2^{\p_\h}$. Hence both these subspaces are Polish in their own right. To each $y_1, y_2\in\s(\p_\h)$ we can continuously associate a partial order on $\o$ isomorphic to $\p_\h\otimes_{S(y_1), S(y_2)}\p_\h$, and thus by lemma \ref{B}: \begin{lemma} \label{C} Let $(\co_i)_{i\in\o}$ be a sequence of dense open subsets of $\p_\h$. Then we may find a continuous function \[\gamma_{\p_\h\times\p_\h}: \s(\p_\h)\times\s(\p_\h)\rightarrow \f(\p_\h)\times\f(\p_\h)\] such that for all $(y_1, y_2)\in\s(\p_\h)\times\s(\p_\h)$, if \[(z_1, z_2)=\gamma_{\p_\h\times\p_\h}(y_1, y_2)\] then \leftskip 0.4in \noindent (1) $G(z_1)\cap \co_i\neq 0$ all $i\in\o$; \noindent (2) $G(z_2)\cap \co_i\neq 0$ all $i\in\o$; \noindent (3) there is a corresponding filter $G_{y_1, y_2} \subset \p_\h\otimes_{S(y_1), S(y_2)}\p_\h$ meeting all the dense open sets of section \ref{dense} with \[\pi_1(G_{y_1, y_2})=G(z_1)\] \[\pi_2(G_{y_1,y_2})=G(z_2).\] \end{lemma} Observe that we can reorganize $\gamma_{\p_\h\times\p_\h}$ into its coordinate functions and find a pair \[\gamma_1: \s(\p_\h)\times\s(\p_\h)\rightarrow \f(\p_\h),\] \[\gamma_2: \s(\p_\h)\times\s(\p_\h)\rightarrow \f(\p_\h),\] such that if \[(z_1, z_2)=\gamma_{\p_\h\times\p_\h}(y_1, y_2)\] then for $i\in\{1, 2\}$ we have $z_i=\gamma_i(y_1, y_2)$. We implicitly use this reorganization in the next section. \newpage \section{Finishing up} \label{finishing} I understand the next lemma to be folklore. \begin{lemma} Equality of $\Ubf{\Pi}^1_n$ sets is $\Ubf{\Pi}^1_{n+1}$ complete in the codes. \end{lemma} \begin{proof} For notational simplicity we assume $n=1$. Then given any $\Ubf{\Pi}^1_2$ set $P\subset 2^\omega$ we can appeal to the tree representation for $\Ubf{\Sigma}^1_1$ sets and continuously assign \[x \mapsto T_x\] to each point in $2^\o$ a tree $T_x\subset (\o\times\o)^{<\o}$ such that $x\in P$ if and only if \[\forall y\in\o^\o\exists f\in \o^\o\forall n ((y|_n, f|_n)\in T_x).\] Thus if we assign to each $x$ the $\Ubf{\Pi}^1_1$ set \[A_x=\{y\in\o^\o: \forall f\in \o^\o\exists n ((y|_n, f|_n)\notin T_x)\}\] then we have \[x\in P\] if and only if \[A_x=\emptyset.\] Thus we have reduced membership in $P$ to equality of a corresponding $\Ubf{\Pi}^1_1$ set with the empty set. It is easily checked that the assignment \[x \mapsto A_x\] is continuous in the codes. \end{proof} \begin{theorem} Assume {\rm AD}$^{L(\R)}$. Then there is no injection in $L(\R)$ from $\Ubf{\Pi}^1_{n+1}$ into $\Ubf{\Pi}^1_n$. \end{theorem} \begin{proof} Suppose instead we have \[{\Theta}: \Ubf{\Pi}^1_{n+1}\hookrightarrow \Ubf{\Pi}^1_n\] inside $L(\R)$. For the sake of concreteness let us assume $n=1$. Then by the basis theorem for $\Ubf{\Sigma}^2_1$ we may assume that $\Theta$ is itself $\Ubf{\Sigma}^2_1$, and hence by the uniformization theorem that there is a function in $L(\R)$ \[\theta: \f(\p_\h)\rightarrow 2^{2^{<\o}\times \lo}\] such that for all $z_1, z_2\in \f(\p_\h)$ we have \[\{x\in 2^\o: \forall y((x, y)\in A_{G(z_1)})\}=\{x\in 2^\o: \forall y((x, y)\in A_{G(z_2)})\}\] if and only if \[\{x\in 2^\o|\forall y\in\oo\exists n ((x|_n, y|_n)\notin \theta(z_1))\} =\{x\in 2^\o|\forall y\in\oo\exists n ((x|_n, y|_n)\notin \theta(z_2))\}.\] Since AD implies that all functions on Polish spaces are Baire measurable, we may find a comeager set on which $\theta$ is continuous. This means that there is a countable collection $(\co_i)_{i\in\o}$ of open dense subsets of $\p_\h$ such that $\theta$ is continuous on the $\Ubf{\Pi}^0_2$ subset $D$ of $\f(\p_\h)$ consisting of $\{z\in \f(\p_\h)\}$ such that \[\forall i(G(z)\cap \co_i\neq 0).\] But now applying \ref{C} we may find {\it continuous} functions \[\Gamma_1, \Gamma_2: \s(\p_\h)\times \s(\p_\h)\rightarrow D\] such that for all $(y_1, y_2)\in \s(\p_\h)\times \s(\p_\h)$ we have that if $\Gamma_i(y_1, y_2)=z_i$ ($i=1, 2$) then there is $G_{y_1, y_2}\subset \amalg$ meeting all the dense sets of $\S$\ref{dense} with $\pi_1(G_{y_1, y_2})=G(z_1)$ and $\pi_2(G_{y_1, y_2})=G(z_2)$ (where $\pi_1$, $\pi_2$ are defined as at the start of section \ref{things}). \smallskip \noindent {\bf Claim:} If $\Gamma_1(y_1, y_2)=z_1$, $\Gamma_2(y_1, y_2)=z_2$, then \[\{x\in \o^\o: \forall r((x, r)\in A_{G(z_1)})\} =\{x\in \o^\o: \forall r((x, r)\in A_{G(z_2)})\}\] if and only if \[\{x\in 2^\o: \forall r((x, r)\in A_{S(y_1)})\}= \{x\in 2^\o: \forall r((x, r)\in A_{S(y_2)})\}.\] \smallskip \noindent {\bf Proof of claim:} We will use \ref{finally} several times in this proof. For this we need to keep in mind that \[A_{\pi_1(G_{y_1, y_2})}=A_{G(z_1)},\] \[A_{\pi_2(G_{y_1, y_2})}=A_{G(z_2)}.\] Suppose first that \[\{x\in \o^\o: \forall r((x, r)\in A_{G(z_1)})\} \neq\{x\in \o^\o: \forall r((x, r)\in A_{G(z_2)})\}.\] Without loss we may assume there is some $x_0, r_0$ with $x_0\in \{x\in \o^\o: \forall r((x, r)\in A_{G(z_1)})\}$ but \[(x, r_0)\notin A_{G(z_2)}.\] Then by the statement of \ref{finally}(1) we must have some $\hat{x}$ with \[\Phi_{G_{y_1, y_2}}(\hat{x})=x_0.\] By \ref{finally}(2) we have for all $r\in\o^\o$ \[(x_0, r)\in A_{G(z_1)}\Leftrightarrow (\hat{x}, r)\in A_{S(y_1)}\] \[(x_0, r)\in A_{G(z_2)}\Leftrightarrow (\hat{x}, r)\in A_{S(y_2)}\] and thus \[(\hat{x}, r_0)\notin A_{S(y_2)}\] while \[\forall r((\hat{x}, r)\in A_{S(y_1)}).\] Thus \[\{x\in 2^\o: \forall r((x, r)\in A_{S(y_1)})\} \neq\{x\in 2^\o: \forall r((x, r)\in A_{S(y_2)})\}.\] So now for the other direction. Let us assume $x_0$, $r_0$ have been chosen so that $\forall r(({x}_0, r)\in A_{S(y_1)})$ but $(({x}_0, r_0)\notin A_{S(y_2)})$; the other case, with $y_1$ and $y_2$ interchanged, is essentially identical. Let $\hat{x}=\Phi_{G(y_1, y_2)}(x_0)$. Then by 7.5(2) we have for all $r$ that \[(\hat{x}, r)\in A_{G(z_1)}\] but \[(\hat{x}, r_0)\notin A_{G(z_2)}.\] \hfill (Claim$\Box$) \smallskip But then the composition \[(y_1, y_2)\mapsto (\theta(\Gamma_1(y_1, y_2)), \theta(\Gamma_2(y_1, y_2)))\] gives a continuous reduction of the equivalence relation of coding the same $\Ubf{\Pi}^1_2$ set to the equivalence relation of coding the same $\Ubf{\Pi}^1_1$ set. Since the former is $\Ubf{\Pi}^1_3$ complete while the later is only $\Ubf{\Pi}^1_2$, we have our desired contradiction. \end{proof} \newpage \begin{thebibliography}{99} \bibitem{andretta} A. Andretta, {\bf Notes on descriptive set theory}, unpublished manuscript, University of Turino, 2000. \bibitem{dichotomy} G. Hjorth, {\it A dichotomy for the definable universe,} {\bf Journal of Symbolic Logic,} vol. 60(1995), pp. 1199-1207. \bibitem{hjorth} G. Hjorth, {\it An absoluteness principle for Borel sets,} {\bf Journal of Symbolic Logic,} vol. 63(1998), pp. 663--693. \bibitem{classification} G. Hjorth, {\bf Classification and Orbit Equivalence Relations,} American Mathematical Society Mathematical Surveys and Monographs Series, Rhode Island, 2000. \bibitem{mamost} D.A. Martin, Y.N. Moschovakis, J.R. Steel, {\it The extent of definable scales,} {\bf Bulletin of the American Mathematical Society,} vol. 6(1982), pp. 435--440. \bibitem{martinsteel} D.A. Martin, J.R. Steel, {\it The extent of scales in $L(\R)$,} {\bf Cabal Seminar 79-81,} (eds. A.S. Kechris, D.A. Martin, J.R. Steel), vol. 1019, pp.86--96. \bibitem{moschovakis} Y.N. Moschovakis, {\bf Descriptive Set Theory,} North-Holland, Amsterdam, 1980. \end{thebibliography} \leftskip 0.5in greg@math.ucla.edu \bigskip MSB 6363 UCLA CA 90095-1555 \leftskip 0in \end{document}