% LaTeX2e % Hechler and Laver Trees % A. Miller Dec 2002 last revised April 2012 \def\lastrevised{April 2012.} \documentclass[12pt]{article} \usepackage{amssymb} \pagestyle{myheadings} \def\header{Hechler and Laver Trees} \markboth\header\header \def\al{\alpha} \def\anal{{\bf\Sigma}^1_1} \def\be{\beta} \def\ff{{\mathcal F}} \def\hhf{{{\mathbb H}_\ff}} \def\ka{\kappa} \def\lam{\lambda} \def\la{\langle} \def\llf{{{\mathbb L}_\ff}} \def\om{\omega} \def\proof{\par\noindent Proof\par\noindent} \def\qed{\par\noindent QED\par} \def\range{{\mbox{ range}}} \def\rank{{\mbox{rank}}} \def\ra{\rangle} \def\res{\upharpoonright} \def\rmand{\mbox{ and }} \def\rmiff{\mbox{ iff }} \def\si{\sigma} \def\sm{{\setminus}} \def\su{\subseteq} \newtheorem{theorem}{Theorem} % [section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{define}[theorem]{Definition} \newtheorem{prop}[theorem]{Proposition} \newtheorem{cor}[theorem]{Corollary} \begin{document} \begin{center} {\large Hechler and Laver Trees} \end{center} \begin{flushright} Arnold W. Miller\footnote{ These results were obtained in December 2002 while visiting the Fields Institute at the University of Toronto. Thanks to its director Juris Steprans and his staff for their hospitality and also for the discussions we had with Steprans at that time. It was presented to the SEALS conference in Gainesville Florida in March 2003, and in a topics course at the University of Wisconsin, Madison in the fall of 2009. Last revised \lastrevised. \par Mathematics Subject Classification 2010: 03E15; 03E05; 03E02 \par Keywords: Analytic sets, trees, constructible sets, Martin's Axiom, games.} \end{flushright} \def\address{\begin{flushleft} Arnold W. Miller \\ miller@math.wisc.edu \\ http://www.math.wisc.edu/$\sim$miller\\ University of Wisconsin-Madison \\ Department of Mathematics, Van Vleck Hall \\ 480 Lincoln Drive \\ Madison, Wisconsin 53706-1388 \\ \end{flushleft}} \begin{center} Abstract \end{center} \begin{quote} A Laver tree is a tree in which each node splits infinitely often. A Hechler tree is a tree in which each node splits cofinitely often. We show that every analytic set is either disjoint from the branches of a Heckler tree or contains the branches of a Laver tree. As a corollary we deduce Silver Theorem that all analytic sets are Ramsey. We show that in Godel's constructible universe that our result is false for co-analytic sets (equivalently it fails for analytic sets if we switch Hechler and Laver). We show that under Martin's axiom that our result holds for $\bf\Sigma_2^1$ sets. Finally we define two games related to this property. \end{quote} \begin{define} A subtree $H\su \om^{<\om}$ is {\em Hechler} iff $\forall s\in H\;\forall^\infty n\;\; sn\in H$. A subtree $L\su \om^{<\om}$ is {\em Laver} iff $\forall s\in L\;\exists^\infty n\;\;\; sn\in L$. \end{define} These definitions are motivated by well-known forcing notions of Laver \cite{laver} and Hechler \cite{hechler}. In the classical Hechler forcing the cofinite sets on the $n^{th}$ level of the tree would all be the same. \begin{define} For any subtree $T\su \om^{<\om}$ define $$[T]=\{x\in\om^\om\;:\; \forall n\;\; x\res n\in T\}$$ \end{define} \begin{theorem}\label{eitheror} For any $\anal$ set $A\su\om^\om$ either there exists a Hechler tree $H$ with $[H]\cap A=\emptyset$ or there exists a Laver tree $L$ with $[L]\su A$. \end{theorem} \proof Since analytic sets are projections of closed sets there exists a tree $T$ on $\om^{<\om}\times\om^{<\om}$ such that $$A=p[T]=^{def}\{x\in\om^\om\;: \;\exists y\in\om^\om\; \forall n\; (x\res n,y\res n)\in T\}.$$ Assume that for every Hechler $H$ that $A$ meets $[H]$ and we will show there is a Laver $L$ with $[L]\su A$. For $s,t\in \om^{<\om}$ define $$A_{s,t}=\{x\in\om^\om\:;\;s\su x \exists y\supseteq t\; (x,y)\in [T]\}.$$ \begin{define} We say that $H$ is Hechler with root $s$ if for all $t\in H$ either $s\su t$ or $t\su s$ and beneath $s$ there is cofinite splitting. \end{define} \begin{lemma}\label{lem1} Suppose for every Hechler $H$ with root $s$ that $A_{s,t}\cap [H]\neq\emptyset$. Then there are infinitely many $n$ such that for every Hechler $H$ with root $sn$ that $A_{sn,t}\cap [H]\neq\emptyset$. \end{lemma} \proof Otherwise for all but finitely many $n$ (say $n>N$) there exists a Hechler $H_n$ with root $sn$ which misses $A_{sn,t}$. But then the Hechler tree: $H=\bigcup_{n>N}H_n$ misses $A_{s,t}$ and has root $s$. \qed \begin{lemma}\label{lem2} Suppose for every Hechler $H$ with root $s$ that $A_{s,t}\cap [H]\neq\emptyset$. Then there exists an infinite well-founded tree $T\su\{r\;:\; s\su r\}$ with root $s$ and terminal nodes $B\su T$ such that (1) The nonterminal nodes of $T$ are $\om$-splitting, i.e., if $r\in T\sm B$, then there are infinitely many $n$ with $rn\in T$, and (2) For every $r\in B$ there exists $n$ such that for every Hechler tree $H$ with root $r$, $A_{r,tn}\cap [H]\neq\emptyset$. \end{lemma} \proof For each ordinal $\al$ define a set $B_\al\su \{r\;:\; s\su r\}$ as follows. (a) $r\in B_0$ iff there exists $n$ such that for every Hechler tree $H$ with root $r$, $A_{r,tn}\cap [H]\neq\emptyset$. (b) $B_{\al+1}=B_\al\cup\{r\;:\;\exists^\infty n \;\; rn\in B_\al\}$ (c) $B_\lam=\bigcup_{\al<\lam}$ for $\lam$ a limit ordinal. Define function $\rank(r)$ on $r\supseteq s$ as follows, $\rank(r)=\al$ if $\al$ is the least ordinal with $r\in B_\al$ and $\rank(r)=\infty$ if there is no such ordinal. \bigskip\noindent {\bf Case 1.} $\rank(s)$ is an ordinal. In this case it is easy to build $T$ and $B$ as required. \bigskip\noindent {\bf Case 2.} $\rank(s)=\infty$. We show that this is impossible. Note that if $\rank(r)=\infty$ then for all but finitely many $n$ we must have that $\rank(rn)=\infty$. Hence we may construct a Hechler tree $H$ with root $s$ such that $\rank(r)=\infty$ for all $r\in H$ below the root. For each $n<\om$ for each $r\in \om^{n+|s|}\cap H$ there exists a Hechler $H_r$ with root $r$ such that $$[H_r]\cap A_{s,tn}=\emptyset.$$ Define $$K_n=\bigcup\{H_r\;:\; r\in\om^{n+|s|}\cap H\}$$ Note that $K_n$ is a Hechler tree with root $s$ whose $n+|s|$ level is the same as $H$. It also true that $K_n\cap A_{s,tn}=\emptyset$. Because they are so wide $K=\bigcap_{n<\om}K_n$ is a Hechler tree with root $s$ such that $[K]\cap \bigcup_{n}A_{s,tn}=\emptyset$. This contradicts the hypothesis of the Lemma since $\bigcup_{n}A_{s,tn}=A_{s,t}$. \bigskip Finally, if $T$ is trivial, i.e., $T=B=\{s\}$ just apply Lemma \ref{lem1} to make $T$ infinite. \qed \bigskip\noindent Proof of Theorem \ref{eitheror}: Suppose for every Hechler tree $H$ with trivial root that $A\cap [H]\neq\emptyset$. Apply Lemma \ref{lem2} to obtain a non-trivial well-found tree $T_0$ with terminal nodes $B_0$ and witnesses of length one. Suppose we are given a well-founded tree $T_n$ with trivial root and terminal nodes $B_n$ such that for all $s\in T_n\sm B_n$ there are infinitely many immediate extensions of $s$ in $T_n$ and for each $s\in B_n$ there is a $t_s$ of length $n+1$ such that for every Hechler tree $H$ with root $s$, $A_{s,t_s}\cap [H]\neq\emptyset$. Apply Lemma \ref{lem2} to each node $(s,t_s)$ with $s\in B_n$. Union all these trees together to get $T_{n+1}$ which end extends $T_n$. It follows that $L$ is a Laver where $$L=\bigcup_{n<\om} T_n$$ Note that although the length of the witnesses grow much slower than the $s$-part, nevertheless, they union up to show that ${L}\su A$. \qed \begin{define} For $\ff$ a filter extending the cofinite filter on $\om$ define $\hhf$ to be the Hechler trees mod $\ff$, i.e., instead of demanding that for each $s\in H$ that $sn\in H$ for cofinitely many $n$, we demand that $$\{n\;:\; sn\in H\}\in\ff.$$ Analogously define $\llf$ the Laver trees mod $\ff$ by for each $s\in L$ $$\{n\;:\; sn\in L\}\in\ff^+$$ where $\ff^+$ are the positive $\ff$ sets, i.e, sets whose complement is not in $\ff$. \end{define} \begin{theorem}\label{easy} For any filter $\ff$ and any $\anal$ set $A\su\om^\om$ either there exists a Hechler tree $H\in\hhf$ with $[H]\cap A=\emptyset$ or there exists a Laver tree $L\in \llf$ with $[L]\su A$. \end{theorem} \proof The proof of this goes over mutatis mutandis, the proof of Theorem \ref{eitheror}. \qed Any Hechler tree $H$ may be pruned so that every node in it is strictly increasing, i.e. , if $\la x_0,x_1,\ldots,x_n\ra\in H$ then $x_0\si(f\res n)$, Let $C\su \om^\om\times 2^\om$ be $\Pi_1^1$ so that $g\in B \rmiff \exists x\; (g,x)\in C$. Given $f\in\om^\om$ define $Q(f)=(g,x)$ where $g\in\om^\om$ and $x\in 2^\om$ are determined by $f=2g+x$. Define the $\Pi^1_1$ set $A$ by $$A=\{f\in\om^\om\;:\; Q(f)\in C\}.$$ Note that for any Hechler $H$ we can find $\si:\om^{<\om}\to\om$ such that $$H_\si=^{def}\{f\in\om\;:\;\forall n\;\; f(n)>\si(f\res n)\;\}\su H$$ It follows from (2) that $A$ meets every $[H]$. On the other hand $A$ cannot contain the branches $[L]$ of a Laver tree. This is because of the scale (1). Take a 3 splitting subtree of $T\su L$, i.e., for every $s\in T$ there are exactly 3 immediate extensions of $s$ in $T$. For each $g\in\om^\om$ define $$C_g=\{f\in\om^\om\;:\;\exists x\in 2^\om\; f=2g+x\}$$ and note that $A\su\bigcup_{g\in B} C_g$. If $[T]\su A$ then by the scale property of $B$ there would have to be a countable set $Q\su B$ with such that $$[T]\su \bigcup_{g\in Q} C_g$$ But the $C_g$ are the branches of a binary splitting tree and since $T$ is 3-splitting, it is easy to construct $f\in [T]$ such that $f\notin C_g$ for every $g\in Q$. \qed \begin{theorem} Assume MA +$\neg$CH. If $A\su\om^\om$ is ${\bf \Sigma^1_2}$, then either there is a Hechler tree $H$ with $[H]\cap A=\emptyset$ or there is a Laver tree $L$ with $[L]\su A$. In fact, this is true for any set $A$ which is the union of $\om_1$ many Borel sets. \end{theorem} \proof Suppose $A=\bigcup_{\al<\om_1}B_\al$ where each $B_\al$ is Borel and the union is increasing. Since no $B_\al$ contains the branches of a Laver tree we have $H_\al$ a Hechler tree with $[H_\al]\cap B_\al=\emptyset$. Without loss we may assume that $$[H_\al]=\{f\in\om^\om\;:\;\forall n \; f(n)>\si_\al(f\res n)\;\}$$ where $\si_\al:\om^{<\om}\to\om$. By Martin's axiom we may find $\si:\om^{<\om}\to\om$ which eventually dominates each $\si_\al$. By a counting argument we can find a single $\si:\om^{<\om}\to\om$ which everywhere dominates $\om_1$ of the $\si_\al$. But this means that $H_\si$ is a Hechler tree disjoint from $A$ since the $B_\al$'s are an increasing union. \qed \bigskip\bigskip \noindent Finally we make some remarks about games. \bigskip\noindent {\bf Game 1.} Given $A\su\om^\om$. Player I and II alternatingly play $$n_0,\; m_0>n_0,\; \;n_1, \;\; m_1>n_1,\;\; \ldots$$ with Player I playing $n_k\in\om$ and Player II responding with $m_k>n_k$. The play of the game is won by Player II iff $(m_i:i<\om)\in A$. \begin{prop} (a) Player II has a winning strategy in Game 1 iff there exists a Laver tree $L$ with $[L]\su A$. (b) Player I has a winning strategy in Game 1 iff there exists a Hechler tree $H$ with $[H]\cap A=\emptyset$. \end{prop} \proof Given the trees it easy to get the strategies. For the other direction: (a) Use player II's winning strategy to construct a Laver tree as required. (b) If $\si:\om^{<\om}\to\om$ is Player I's winning strategy, then for any sequence $(m_i:i<\om)$ such that $m_{i+1}>\si(m_0,\ldots,m_i)$ for every $i$ we have that $(m_i:i<\om)\notin A$. But this gives a Hechler tree $H$ with $[H]$ disjoint from $A$. \qed \bigskip\bigskip\noindent {\bf Game 2.} Given $A\su\om^\om$. Player I and II alternatingly play $$X_0,\;\;m_0\in X_1,\;\;X_1,\;\;m_1\in X_1,\ldots$$ with Player I playing $X_k\in[\om]^\om$ and Player II responding with $m_k\in X_k$. Player II wins the play of the game iff $(m_i:i<\om)\in A$. \begin{prop} (a) Player II has a winning strategy in Game 2 iff there exists a Hechler tree $H$ with $[H]\su A$. (b) Player I has a winning strategy in Game 2 iff there exists a Laver tree $L$ with $[L]\cap A=\emptyset$. \end{prop} \proof From right-to-left in both cases is easy. For the other direction: (a) Let $\si$ be a winning strategy for Player II. Consider $$\{m_0\;:\; \exists X_0\;\; \si(X)=m_0\}$$ This set must be cofinite, since otherwise consider $\si$'s response to its complement. Similarly given any sequence $X_0,X_1,\ldots, X_{n-1}$ the set $$\{m_n\;:\; \exists X_n\;\; \si(X_0,\ldots,X_n)=m_n\}$$ must be cofinite. Construct $X_s$ for $s\in\om^{<\om}$ and get a Hechler tree $H$ all of whose branches are plays of the winning strategy and hence are in $A$. (b) The sequence of $X_s$ played by winning strategy of Player I determine a Laver tree $L$. \qed \bigskip Some of the results in this note follow from Zapletal \cite{zap}. \begin{thebibliography}{99} \bibitem{ellen} Ellentuck, Erik; A new proof that analytic sets are Ramsey. J. Symbolic Logic 39 (1974), 163-165. \bibitem{GP} Galvin, Fred; Prikry, Karel; Borel sets and Ramsey's theorem. J. Symbolic Logic 38 (1973), 193-198. \bibitem{hechler} Hechler, Stephen H.; On the existence of certain cofinal subsets of $^{\omega }\omega $. Axiomatic set theory (Proc. Sympos. Pure Math., Vol. XIII, Part II, Univ. California, Los Angeles, Calif., 1967), pp. 155-173. Amer. Math. Soc., Providence, R.I., 1974. \bibitem{laver} Laver, Richard; On the consistency of Borel's conjecture. Acta Math. 137 (1976), no. 3-4, 151-169. \bibitem{silver} Silver, Jack; Every analytic set is Ramsey. J. Symbolic Logic 35 (1970), 60-64. \bibitem{zap} Zapletal, Jindrich; Isolating cardinal invariants. J. Math. Log. 3 (2003), no. 1, 143-162. \end{thebibliography} \address \end{document}