PARTITION PROPERTIES AND HALPERN-LAUCHLI THEOREM ON THE C„v„ FORCING .- ,a By YUAN-CHYUAN SHEU A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA 2005 ACKNOWLEDGEMENTS I would like to thank my advisor, Jindrich Zapletal, for his patience and almost infinite discussion with me on the problems I was trying to solve. Without him, I simply could not have got this far. I would also like to thank the other members of my supervisory committee: Dr. Jean A. Larson, Dr. William Mitchell, Dr. Rick L. Smith, and Dr. Greg Ray. I have learned a lot from them either through taking classes taught by them, personal conversations, or hearing them speak in seminars and conferences. I am very grateful to the Department of Mathematics for supporting me with a teaching assistantship during my years as a graduate student. I also would like to thank the College of Liberal Arts and Science for supporting me with a Keene Dissertation Fellowship in the spring 2005 term. Finally, I must acknowledge the contribution of my family and all my friends in the Department of Mathematics for their caring and support. u V ^- TABLE OF CONTENTS ACKNOWLEDGEMENTS h ABSTRACT iv CHAPTERS INTRODUCTION 1 1 2 PRELIMINARIES 3 2.1 Basic Definitions 3 2.2 The Property of Baire 5 2.3 The space 2'^ 6 2.4 The C„nn Trees 6 2.5 Determinacy 7 3 BLASS PARTITION THEOREM 8 3.1 Blass Theorem on the Perfect Sets 8 3.2 Partition Theorem on the Cmin Tress 10 CANONICAL PARTITION THEOREM 17 4 4.1 Perfect Tree Case 17 4.2 Cmin Tree Case 18 HALPERN-LAUCHLI THEOREM 24 5 5.1 Introduction 24 5.2 Cmin Tree Case 25 OTHER FORCING NOTIONS 33 6 6.1 The Eo Trees 33 6.2 The Silver Forcing 34 6.3 The Packing Measures 36 REFERENCES 38 BIOGRAPHICAL SKETCH 39 ui J 1 , Abstract of Dissertation Presented to the Graduate School of the University of Florida in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy PARTITION PROPERTIES AND HALPERN-LAUCHLI THEOREM ON THE FORCING .^ . . . C^i„ . ., - ^ By- : Yuan-Chyuan Sheu May 2005 • Chairman: Jindrich Zapletal Major Department: Mathematics In this dissertation, we focus on a special breed of forcing notion called Cmin forcing, which is forcing equivalent to the form H(M) \ / for some C™n-ideal /. We define a special perfect subsets ofthe space 2'^, called Cmin trees. We study the partition properties and Halpern-Lauchli theorems on these trees. We obtained three principal theorems which will be our dicussion Chapters 3,4 and 5 respectively. We also show that the some other forcing notions do not have similarpartition properties. This is in Chapter 6. • IV CHAPTER 1 INTRODUCTION This dissertation is based upon the deep combinatorial theorem of Halpern- Lauchli [6] on the perfect trees which Halpern and Lauchli developed in the 1960's. The Halpern-Lauchli Theorem is obtained as a byproduct of the proof of Con[ZF+ -'AC + BP), where BP is the statement that there exists a prime ideal in every Boolean algebra, a consequence of the Axiom of Choice equivalent to Compactness Theorem for the First-Order Predicate Calculus. It has been noticed since then that the lemma of the proof might be of independent interest. One of the main applications of the Halpern-Lauchli Theorem is the proof of the well known Blass Theorem [1] on perfect trees, which states [S]<u,{n- 1)! Let a Cmin tree [14] be a nonempty binary tree T C 2^'^ such that every node t E T can be extended both into a splitnode of even length and into a splitnode of odd length. The study of the Cmin trees was originated from Geschke et al. [4], where the authors defined the Cmin function (see Chapter 2 for definition). The Cmin (7-ideal / generated by the Cmin homogeneous sets is nontrivial and the subsets of 2^ that contain all the branches of a Cmin tree are the typical /-positive sets. The Cmin trees as a forcing notion ordered by inclusion is proper. We have shown that for the C•m'iminn trees we have a similar but different This is contained in Chapter 3. 1 In 1930 Ramsey [11] proved the famous pigeon-hole principle for finite sets. A new situation arises if partitions into an arbitrary number of classes are considered. For this case, Erdos and Rado proved the so-called canonical version of Ramsey [3] Theorem. Based on the Cmin version of Blass Theorem, we also proved the canonical theorem on Borel equivalence relations on Cmin trees. This means that, fixing a shape and parity pattern, there exists a finite set G of equivalence relations on [2*^]" such that for any Borel equivalence relation / on [2'^]" there is an equivalence relation geG and a Cmin tree T C 2'^ such that / [T]" = g [T]". This is in Chapter 4. \ \ We obtained a Cmin tree version of the Halpern-LauchU Theorem. In a 1984 paper, Richard Laver generalized the existing Halpern-Lauchli Theorem to the [8] infinite product ofperfect trees. From there, equivalent results on Hilbert cubes and selective ultrafilters can be derived. We have developed the Halpern-Lauchli Theorem on the infinite product of Cmin trees and we have the equivalent results on Hilbert cubes and selective ultrafilters as well. This is contained in Chapter 5. We have also shown that the Cmin trees are special by constructing counterex- amples that demonstrate that no such results are possible for a variety ofother kinds offorcing notions such as Eq Forcing, Silver Forcing and the forcing notion associated with the Packing Measure. This is the main content of Chapter 6. CHAPTER 2 PRELIMINARIES 2.1 Basic Definitions A relation is a set R all of whose elements are ordered pairs. / is a function iff / is a relation and Vx e dom(/) 3!y G ran(/) ((x,y) G /). f : A ^ B means / is a function, A — dom(/), and ran(/) Q B. U f : A ^ B and X e R, the set of all real numbers, f{x) is the unique y such that {x,y) G /; liC C A, f \ C = fnC X B isthe restriction of / to C, and f'C = ran(/ \ C) = {fix) -.xeC}. A total ordering is a pair {A, R) such that R totally orders A; that is, yl is a set, Ris a relation, R is transitive on A: Vx, y,z E A [xRy and yRz —> xRz), trichotomy holds: Vx, y € A{x = y or xi?j/ or yRx), and /? is irreflexive: Vx G >1 it is not the case that xRx. As usual, we write xRy for (x, y) G R. We say that J? well-orders A, or (^, /?) is a well-ordering iflF {A, R) is a total ordering and every non-empty subset of A has an /l-least element. Definition 2.1.1. (a) A partial order is a pair (P, <)such that P # and < is a relation on P which is transitive and reflexive (Vp G P(p < p))- p < q is read " p extends q". Elements ofP are called conditions. (b) (P, <) is a partial order in the strict sense iff it in addition satisfies Vp, q{p < q and q < p -^ p — q)- In that case, define p < q iffp < q and p ^ q. X Definition 2.1.2. An equivalence relation on a set is a binary relation ~, which X ~ is reflexive, symmetric, and transitive: For all x,y, z G , we have that x x, ^ ^ ^ ^ X y y X, ifX '^ y and y '^ z then x z. Definition 2.1.3. A tree is a partial order in the strict sense (T, <), such that for each X eT, {y eT : y < x} is well-ordered by <. The set of all finite sequence of O's and I's, 2'^'^ is a tree with any s,t E 2'^'^, s <tiS s Ct. For any T C 2<'^ let [T] be the set of all branches through the tree , T. Any T C 2<'^ is a tree if Vi G T and s = t \n for some n, then s eT. Definition 2.1.4. A skew tree is a tree so that on each level there is at most one branching node. For distinct a, E [T], let d{a,j3) be the level of the highest common node of the paths a and /5 through T. Here we assume for any n-set it is the case that the elements are listed in lexicographic order, and we may assume that the trees are skew. Definition 2.1.5. By the shape of an n-element set {ao, ...,a„_i} C [T], we mean the linear ordering -< o/ {1, ..., n — 1} given by i < j -^^ ^(ai-i, oti) is in a lower level than d{aj-i, aj). Definition 2.1.6. By the parity pattern p, of an n-element set {ao, ..., a„_i} E [T]", we mean p E 2"~^ given by p{i) — iff the i-th (counting from 0) lowest splitnode of the n-set is on the even level. 0T= Definition 2.1.7. Let T = {Ti : i < d) be a seqence of trees. Define (2)i<rf7i to be the set of all n-tuples X from the product of {Ti : i < d} such that \X{i)\ = \X{j)\ for any i,j < d; for A C uj, let (^'^ T be the set of all n-tuples Y from the product of {Ti\ i < d} such that \Y{i)\ - \Y{j)\ G A for any ij < d. Definition 2.1.8. An algebra of sets is a collection S of subsets of a given set S such that (i)SeS, (ii) ifXeSandYeS then X\JY eS, (Hi) ifXeS then S\X eS. ' ''^'^ A a-algebra is additionally closed under countable unions: (iv) IfXneS for all n, then U~ o^n e 5. For any collection X of subsets ofS there is a smallest a-algebra S such that S D X; namely the intersection of all a-algebras S of subsets of S for which X CS. Definition 2.1.9. A set of reals B is Borel if it belongs to the smallest a-algebra B ofsets of reals that contains all open sets. 2.2 The Property of Baire Let us call a set yl C 2'^ nowhere dense if the complement of A contains a dense open set. Note that A is nowhere dense just in case that for every non empty open set G, there is a nonempty open set H C G such that yl n i/ = 0. A set ^ is nowhere dense if and only if its closure A is nowhere dense. A set A C 2'^ is meager if A is the union of countably many nowhere dense sets. -. , Definition 2.2.1. A set A has the Baire property if there exists an open set G such that AAG = {A\G)\J{G\A) is meager. G Clearly, every meager set has the Baire property. Note that if is open, then G\G is nowhere dense. Hence if AAG is meager then (2'^ \ A)A{2'^ \G) = AAG is meager, and it follows that the complement of a set with the Baire property also has 6 the Baire property. It is also easy to see that the union of countably many sets with the Baire property has the Baire property and we have: Lemma 2.2.2. The sets having the Baire property form a a-algebra; hence every Borel set has the Baire property. 2.3 The space 2'^ Let CO be the set of all natural numbers. The space 2'^ is the set of all infinite sequences of numbers or 1, (a„ : n € w), with the following topology: For every finite sequence s = {uk ' k < n), let 0{s) ^{fe2^:sCf} = {{Ck : k e to) : {Vk < n)ck = aj. The sets 0{s) form a basis for the topology of 2'^. Note that each 0{s) is also closed. The space 2'^ is separable and is metrizable: consider the metric where n is the least number such that /(n) y^ g{n). The countable set ofall eventually constant sequences is dense in 2'^. This separable metric space is complete, as every Cauchy sequence converges. 2.4 The Crr,ir. Trees Definition 2.4.1. Let Cmin [2'^]^ -) 2 6e the mapping defined by Cmin{x,y) = A(x,y) mod 2, where A{x,y) is the least number n such that x{n) ^ y(n), and let I, the Cmin-ideal be the a-ideal a-generated by the Cmin homogeneous sets. The above definition can be found in Geschke et al. [4]. It is not diflficult to A verify that Cmin homogeneous sets must be meager. It is so because if is Cmin- homogeneous, say \/x,y e A Cmin{x, y) - 0, then all the split nodes of A are on even levels.