Definable Combinatorics of Graphs and Equivalence Relations Citation Meehan, Connor George Walmsley (2018) Definable Combinatorics of Graphs and Equivalence Relations. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/45E4-MC27. https://resolver.caltech.edu/CaltechTHESIS:06012018-160828760 Abstract Let D = ( X , D ) be a Borel directed graph on a standard Borel space X and let χ B ( D ) be its Borel chromatic number. If F 0 , …, F n -1 : X → X are Borel functions, let D F 0 , …, F n -1 be the directed graph that they generate. It is an open problem if χ B ( D F 0 , …, F n -1 ) ∈ {1, …, 2 n + 1, ℵ 0 }. Palamourdas verified the foregoing for commuting functions with no fixed points. We show here that for commuting functions with the property that there is a path from each x ∈ X to a fixed point of some F j , there exists an increasing filtration X = ⋃ m < ω X m such that χ B ( D F 0 , …, F n -1 ↾ X m ) ≤ 2 n for each m . We also prove that if n = 2 in the previous case, then χ B ( D F 0 , F 1 ) ≤ 4. It follows that the approximate measure chromatic number χ ap M ( D ) ≤ 2 n + 1 when the functions commute. If X is a set, E is an equivalence relation on X , and n ∈ ω , then define [ X ] n E = {( x 0 , ..., x n - 1 ) ∈ n X : (∀ i , j )( i ≠ j → ¬( x i E x j ))}. For n ∈ ω , a set X has the n -Jónsson property if and only if for every function f : [ X ] n = → X , there exists some Y ⊆ X with X and Y in bijection so that f [[ Y ] n = ] ≠ X . A set X has the Jónsson property if and only for every function f : (⋃ n ∈ ω [ X ] n = ) → X , there exists some Y ⊆ X with X and Y in bijection so that f [⋃ n ∈ ω [ Y ] n = ] ≠ X . Let n ∈ ω , X be a Polish space, and E be an equivalence relation on X . E has the n -Mycielski property if and only if for all comeager C ⊆ n X , there is some Borel A ⊆ X so that E ≤ B E ↾ A and [ A ] n E ⊆ C . The following equivalence relations will be considered: E 0 is defined on ω 2 by x E 0 y if and only if (∃ n )(∀ k > n )( x ( k ) = y ( k )). E 1 is defined on ω ( ω 2) by x E 1 y if and only if (∃ n )(∀ k > n )( x ( k ) = y ( k )). E 2 is defined on ω 2 by x E 2 y if and only if ∑{ 1 ⁄ ( n + 1) : x ( n ) ≠ y ( n )} < ∞. E 3 is defined on ω ( ω 2) by x E 3 y if and only if (∀ n )( x ( n ) E 0 y ( n )). Holshouser and Jackson have shown that ℝ is Jónsson under AD. The present research will show that E 0 does not have the 3-Mycielski property and that E 1 , E 2 , and E 3 do not have the 2-Mycielski property. Under ZF + AD, ω 2/ E 0 does not have the 3-Jónsson property. Let G = ( X , G ) be a graph and define for b ≥ 1 its b -fold chromatic number χ ( b ) ( G ) as the minimum size of Y such that there is a function c from X into b -sets of Y with c ( x ) ∩ c ( y ) = ∅ if x G y . Then its fractional chromatic number is χ f ( G ) = inf b χ ( b ) ( G ) ⁄ b if the quotients are finite. If X is Polish and G is a Borel graph, we can also define its fractional Borel chromatic number χ f B ( G ) by restricting to only Borel functions. We similarly define this for Baire measurable and μ -measurable functions for a Borel measure μ . We show that for each countable graph G , one may construct an acyclic Borel graph G ' on a Polish space such that χ f BM ( G ') = χ f ( G ) and χ BM ( G ') = χ ( G ), and similarly for χ f μ and χ μ . We also prove that the implication χ f ( G ) = 2 ⇒ χ ( G ) = 2 is false in the Borel setting. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: Descriptive set theory; graph theory; combinatorics; equivalence relations Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Awards: Apostol Award for Excellence in Teaching in Mathematics, 2014. Thesis Availability: Public (worldwide access) Research Advisor(s): Kechris, Alexander S. Thesis Committee: Kechris, Alexander S. (chair) Tamuz, Omer Graber, Thomas B. Lupini, Martino Defense Date: 22 May 2018 Funders: Funding Agency Grant Number Natural Sciences and Engineering Research Council of Canada (NSERC) Postgraduate Scholarship-Doctoral Program (PGS D) NSF DMS-1464475 Record Number: CaltechTHESIS:06012018-160828760 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:06012018-160828760 DOI: 10.7907/45E4-MC27 Related URLs: URL URL Type Description https://arxiv.org/abs/1709.04567 arXiv Article adapted for Chapter 3 ORCID: Author ORCID Meehan, Connor George Walmsley 0000-0002-7596-2437 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 11006 Collection: CaltechTHESIS Deposited By: Connor Meehan Deposited On: 04 Jun 2018 20:22 Last Modified: 04 Oct 2019 00:22 Thesis Files Preview PDF (Complete thesis) - Final Version See Usage Policy. 791kB Repository Staff Only: item control page

Definable Combinatorics of Graphs and Equivalence Relations Thesis by Connor Meehan In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy CALIFORNIA INSTITUTE OF TECHNOLOGY Pasadena, California 2018 Defended May 22, 2018 © 2018 Connor Meehan ORCID: 0000-0002-7596-2437 All rights reserved ii ACKNOWLEDGEMENTS iii I would like to firstly thank my advisor, Alexander Kechris, for his patience, encouragement, and mentorship throughout my time as a graduate student. I would like to thank the department of mathematics at the California Institute of Technology for its surprisingly effective efforts at fostering a sense of community. I would like to thank Ronnie Chen for his constant companionship, our countless discussions (mathematical or otherwise), and his astute perspectives shared within. I owe great thanks to William Chan for profoundly increasing the enjoyment of my graduate studies, for supplying an outlet for my frustrations, and most of all, for his friendship. I would also like to thank Duncan Palamourdas for our brief and inspiring correspondence. I would like to thank my parents, Deborah and Stephen Meehan, for their support for me while I pursued my dreams. I would like to thank Cassandra Chan for showing that she cared. Lastly, I would like to thank both the Natural Sciences and Engineering Research Council of Canada and the National Science Foundation. This research is partially supported by NSERC PGS D and by NSF grant DMS-1464475. ABSTRACT iv Let D = (X, D) be a Borel directed graph on a standard Borel space X and let χB (D) be its Borel chromatic number. If F0, . . . , Fn−1 : X → X are Borel functions, let DF0,...,Fn−1 be the directed graph
that they generate. It is an open problem if χB DF0,...,Fn−1 ∈ {1, . . . , 2n + 1, ℵ0 }. Palamourdas [25] verified the foregoing for commuting functions with no fixed points. We show here that for commuting functions with the property that there is a path from each x ∈ X to a fixed point of
Ð some Fj , there exists an increasing filtration X = m<ω Xm such that χB DF0,...,Fn−1  Xm ≤ 2n
for each m. We also prove that if n = 2 in the previous case, then χB DF0,F1 ≤ 4. It follows that ap the approximate measure chromatic number χM (D) ≤ 2n + 1 when the functions commute. If X is a set, E is an equivalence relation on X, and n ∈ ω, then define [X]nE = {(x0, ..., xn−1 ) ∈ n X : (∀i, j)(i , j → ¬(xi E x j ))}. For n ∈ ω, a set X has the n-Jónsson property if and only if for every function f : [X]=n → X, there exists some Y ⊆ X with X and Y in bijection so that f [[Y ]=n ] , X. Ð A set X has the Jónsson property if and only for every function f : ( n∈ω [X]=n ) → X, there exists Ð some Y ⊆ X with X and Y in bijection so that f [ n∈ω [Y ]=n ] , X. Let n ∈ ω, X be a Polish space, and E be an equivalence relation on X. E has the n-Mycielski property if and only if for all comeager C ⊆ n X, there is some Borel A ⊆ X so that E ≤B E  A and [A]nE ⊆ C. The following equivalence relations will be considered: E0 is defined on ω 2 by x E0 y if and only if (∃n)(∀k > n)(x(k) = y(k)). E1 is defined on ω (ω 2) by x E1 y if and only if (∃n)(∀k > n)(x(k) = y(k)). E2 is defined on ω 2 by Í 1 : x(n) , y(n)} < ∞. E3 is defined on ω (ω 2) by x E3 y if and only if x E2 y if and only if { n+1 (∀n)(x(n) E0 y(n)). Holshouser and Jackson have shown that R is Jónsson under AD. The present research will show that E0 does not have the 3-Mycielski property and that E1 , E2 , and E3 do not have the 2-Mycielski property. Under ZF + AD, ω 2/E0 does not have the 3-Jónsson property. Let G = (X, G) be a graph and define for b ≥ 1 its b-fold chromatic number χ(b) (G) as the minimum size of Y such that there is a function c from X into b-sets of Y with c(x) ∩ c(y) = ∅ if x G y. Then (b) its fractional chromatic number is χ f (G) = inf b χ b(G) if the quotients are finite. If X is Polish and f G is a Borel graph, we can also define its fractional Borel chromatic number χB (G) by restricting to only Borel functions. We similarly define this for Baire measurable and µ-measurable functions for a Borel measure µ. We show that for each countable graph G, one may construct an acyclic f Borel graph G0 on a Polish space such that χBM (G0) = χ f (G) and χBM (G0) = χ(G), and similarly f for χµ and χµ . We also prove that the implication χ f (G) = 2 ⇒ χ(G) = 2 is false in the Borel setting. PUBLISHED CONTENT AND CONTRIBUTIONS v [3] William Chan and Connor Meehan. “Definable Combinatorics of Some Borel Equivalence Relations” In: ArXiv e-prints (Sep. 2017). arXiv: 1709.04567 [math.LO]. Connor Meehan participated in producing the results and writing the paper. Each author contributed equally to this work. TABLE OF CONTENTS Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Published Content and Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter I: Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter II: Borel Chromatic Numbers of Graphs of Commuting Functions . . . . . . . . . . 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Commuting Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Two Commuting Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter III: Definable Combinatorics of Some Borel Equivalence Relations . . . . . . . . . 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Basic Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 ω 2 Has the Jónsson Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 ω-Jónsson Function for ω 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 The Structure of E0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 ω 2/E0 Has the 2-Jónsson Property . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Partition Properties of ω 2/E0 in Dimension 2 . . . . . . . . . . . . . . . . . . . . . 3.8 E0 Does Not Have the 3-Mycielski Property . . . . . . . . . . . . . . . . . . . . . 3.9 Surjectivity and Continuity Aspects of E0 . . . . . . . . . . . . . . . . . . . . . . . 3.10 ω 2/E0 Does Not Have the 3-Jónsson Property . . . . . . . . . . . . . . . . . . . . 3.11 Failure of Partition Properties of ω 2/E0 in Dimension Higher Than 2 . . . . . . . . 3.12 b P3E0 Is Proper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 E1 Does Not Have the 2-Mycielski Property . . . . . . . . . . . . . . . . . . . . . 3.14 The Structure of E2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.15 E2 Does Not Have the 2-Mycielski Property . . . . . . . . . . . . . . . . . . . . . 3.16 Surjectivity and Continuity Aspects of E2 . . . . . . . . . . . . . . . . . . . . . . . 3.17 The Structure of E3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.18 E3 Does Not Have the 2-Mycielski Property . . . . . . . . . . . . . . . . . . . . . 3.19 Completeness of Ultrafilters on Quotients . . . . . . . . . . . . . . . . . . . . . . . 3.20 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter IV: Fractional Borel Chromatic Numbers and Definable Combinatorics . . . . . . . 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Elementary Facts about the Fractional Chromatic Number . . . . . . . . . . . . . . 4.3 The Baire Measurable Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 The µ-Measurable Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Combining All Quantities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi iii iv v vi 1 4 4 6 7 16 20 20 25 30 34 36 41 45 46 48 51 54 55 57 58 66 68 73 75 76 78 79 79 81 83 85 86 f 4.6 The χB (G) = 2 Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 vii Chapter 1 1 INTRODUCTION Descriptive set theory is a branch of set theory that focuses on sets of a particular structure definable via some constructive rules, as opposed to sets whose existence is guaranteed by some consequence of the axiom of choice. A Polish space is a topological space that is separable and completely metrizable. The prototypical example of a definable set is a Borel set: one that belongs to the smallest family of sets containing all open sets and closed under complements and countable unions. To repeat the first sentence more concretely, descriptive set theory concerns the study of definable sets in Polish spaces. Descriptive set theory is a major research area of set theory and can both be approached from and have results that relate to many other fields of mathematics, such as mathematical logic, topology, and ergodic theory. In this thesis, we focus chiefly on descriptive combinatorics. In particular, we study problems related to graphs and equivalence relations from the viewpoint of descriptive set theory, asking when certain definable objects will satisfy certain definable properties. For example, every acyclic graph can be 2-coloured, but it is possible for the minimum size of the range of a Borel colouring of an acyclic graph to be 2ℵ0 . This thesis consists of three separate papers: Borel Chromatic Numbers of Graphs of Commuting Functions (with Konstantinos Palamourdas), Definable Combinatorics of Some Borel Equivalence Relations (with William Chan), and Fractional Borel Chromatic Numbers and Definable Combinatorics. The first two papers have been submitted for publication. For a more detailed introduction to each paper, see the introduction section of each chapter. In Chapter 2, we study a Borel graph colouring problem; namely, what is the smallest size of a finite set (if one even exists) that can be used for a Borel colouring of a directed graph generated by n Borel functions on a standard Borel space? Palamourdas [25] has previously shown that for such a digraph DF0,...,Fn−1 , its Borel chromatic number χB (DF0,...,Fn−1 ) is in the set  1, . . . , 12 (n + 1)(n + 2), ℵ0 and that if the functions Fj commute and have no fixed points, then this can be improved to {1, . . . , 2n + 1, ℵ0 }. In Chapter 2, we provide a recursive structure for breaking down subdividing a Borel graph of this structure. We show that in the commuting case, if χB (DF0,...,Fn−1 ) < ℵ0 and each point has a forward path to a fixed point, then very large portions of Ð the graph can be coloured with only 2n colours: there exists an increasing filtration X = m<ω Xm 
such that χB DF0,...,Fn−1  Xm ≤ 2n for each m. It is a standard result of graph theory that any digraph D with maximum out-degree bounded by n can be (2n + 1)-coloured. Though the case χB (DF0,...,Fn−1 ) = ℵ0 is possible, Kechris, Solecki, and Todorčević [15] have asked whether the Borel analog of this fact is that χB (DF0,...,Fn−1 ) = {1, . . . , 2n + 1, ℵ0 } for arbitrary Borel functions Fj . The results in Chapter 2 give further evidence that this may be true in the case that the functions commute. In Chapter 3, we study some well-known equivalence relations defined on Polish spaces and whether they satisfy a combinatorial notion known as the n-Mycielski property (so-called due to a theorem of Mycielski showing that = has this property). We show that, though E0 satisfies the 2-Mycielski property, the relations E1, E2 , and E3 do not, and moreover E0 fails to have the 3-Mycielski property. These equivalence relations occupy special positions in the poset of Borel equivalence relations under Borel reducibility, and theorems regarding the structure of Borel sets A for which Ei ≤∆1 Ei  A are important in our proofs about the Mycielski property. 1 One reason that the Mycielski property is interesting is that it aids in the study of another combinatorial notion: the Jónsson property. This is a notion that has been studied by set theorists under various axiom systems; for example, the existence of cardinals with the Jónsson property implies that 0] exists. Holshouser and Jackson [11] used the Mycielski property of = to show that the set ω 2 has the Jónsson property under the axiom system ZF + AD. We show using the fact that E0 does not have the 3-Mycielski property that the quotient ω 2/E0 does not have the Jónsson property in this axiom system. The exact relation between an equivalence relation possessing the Mycielski property and its quotient having the Jónsson property is still unknown. We ask whether the quotients for the equivalence relations E1, E2 , and E3 also fail to have the Jónsson property under the axiom of determinacy. In Chapter 4, we study a classical combinatorial notion in the definable setting; that of the fractional f chromatic number χ f . We show that the fractional Borel number χB behaves much like that of its f classical counterpart. In particular, the quantities χ, χ f , χB can all be made distinct for the same Borel graph (and indeed any values that satisfy some obvious conditions). We construct Borel graphs to prove this idea. These Borel graphs are acyclic but otherwise behave (for the sake of Borel colourings) much like a fixed countable graph. We also show that even though χ f (G) = 2 f forces χ(G) = 2, this is not true for Borel colourings: there exists a graph G for which χB (G) = 2 but χB (G) = 3. 2 f No consensus yet exists for how to compute χB (G) for Borel graphs G with χ(G) < χB (G). Marks showed [22] that the shift graph Gn on the free part of 2Fn satisfies χB (Gn ) = 2n + 1, and we ask f whether it is true that χB (Gn ) = 2. 3 Chapter 2 4 BOREL CHROMATIC NUMBERS OF GRAPHS OF COMMUTING FUNCTIONS (with Konstantinos Palamourdas) 2.1 Introduction Kechris, Solecki, and Todorčević initiated the field of descriptive graph combinatorics in their seminal paper [15]. The broad objective is to study how combinatorial notions of graphs such as matchings and colourings behave under definability constraints. For a comprehensive review of the subject, see [19]. A directed graph, or digraph, is a pair D = (X, D), where X is a set and D is a binary irreflexive relation on X. A path in D is a sequence {xi }i<α in X for some α ∈ {1, 2, . . . , ω} such that xi D xi+1 for all i with i + 1 < α. A subset A ⊆ X is independent if for any x, y ∈ A, ¬x D y. If A ⊆ X, we let D  A = (A, D ∩ (A × A)). For any set Y , a Y -colouring on D is a function c : X → Y such that if x D y, then c(x) , c(y). The chromatic number χ(D) is then the minimum cardinality of Y such that there is a Y -colouring of D. In case X is a standard Borel space, we can consider analogous definable notions of colouring. We define the Borel chromatic number χB (D) to be the minimum cardinality of a standard Borel Y such that there is a Borel Y -colouring of D. If µ is a Borel probability measure on X, we define ap the approximate µ-measurable chromatic number χµ (D) to be the minimum cardinality of a standard Borel Y such that for every ε > 0, there is a Borel set A ⊆ X with µ (X\A) < ε and a µ-measurable Y -colouring of D  A. We then define the approximate measure chromatic ap ap number χM (D) as the supremum of χµ (D), where µ ranges over all Borel probability measures on X. If F ⊆ X X is a family of functions from X to X, we define DF = (X, DF ) by x DF y ⇔ x , y ∧ ∃ f ∈ F ( f (x) = y) . If F = {Fi : i < n}, we also write DF0,...,Fn−1 for DF . It is a standard graph theory result (for a proof, see [15]) that for the case of finitely many functions,
we have χ DF0,...,Fn−1 ≤ 2n + 1 for any digraph of this form. Because the (2n + 1)-clique (i.e., a digraph of size 2n + 1 in which every x, y have either x D y or y D x) can be written in this form, this bound is sharp. In this paper, we will be interested in χB (DF ) in the case when X is a standard Borel space and F is a finite family of Borel functions on X. Such digraphs arise naturally, for example, when studying the action of a finitely generated group on a standard Borel space. Kechris, Solecki, and Todorčević [15] showed that in the case of a single function F, we have χB (DF ) ∈ {1, 2, 3, ℵ0 }. Let X = [ω]ℵ0 , the set of all infinite subsets of ω, and let F : X → X be defined by F(A) = A\ {min A}. Kechris, Solecki, and Todorčević showed in [15] that χB (DF ) = ℵ0 , even though DF is acyclic and therefore χ (DF ) = 2. This is an example of a major departure of the definable version of a combinatorial graph notion from its classical counterpart.
It follows from χB (DF ) ∈ {1, 2, 3, ℵ0 } that χB DF0,...,Fn−1 ∈ {1, . . . , 3n, ℵ0 }. In [15], Kechris,
Solecki, and Todorčević ask whether it is in fact true that χB DF0,...,Fn−1 ∈ {1, . . . , 2n + 1, ℵ0 }. In [25], Palamourdas made improvements and showed that  
1 χB DF0,...,Fn−1 ∈ 1, . . . , (n + 1)(n + 2), ℵ0 2 He also showed that in the case of only 2 or 3 functions,

χB DF0,F1 ∈ {1, . . . , 5, ℵ0 } and χB DF0,F1,F2 ∈ {1, . . . , 8, ℵ0 } .
In the case that the functions {Fi }i<n commute, Palamourdas [25] claimed that χB DF0,...,Fn−1 ∈ {1, . . . , 2n + 1, ℵ0 }. However, Michael Wheeler noted in private correspondence that his proof requires that the functions do not have any fixed points in X. In Section 4.5.1 of this paper, we show that Palamourdas’s argument lends itself to a natural induction result concerning the general bound for χB (DF0,...,Fn−1 ). This insight allows us to obtain a slight improvement of the bound:

Corollary 2.2.4. For n ≥ 3, we either have χB DF0,...,Fn−1 = ℵ0 or χB DF0,...,Fn−1 ≤ 21 (n + 1)(n + 2) − 2. From Section 2.3 onward, we revisit the case in which the functions {Fi }i<n commute, without assuming anything about the existence of fixed points for the functions. We show that such a digraph can be separated into two smaller digraphs, one for which no fixed points exist, and one for which every point has a path to a fixed point (we say the digraph has a fixed ceiling). We then provide some evidence that digraphs of the latter type may actually be easier to colour in a Borel way: 5 
Theorem 2.3.15. If DF0,...,Fn−1 has a fixed ceiling and χB DF0,...,Fn−1 < ℵ0 , there exists an increasing
Ð filtration X = i∈ω Xi such that each χB DF0,...,Fn−1 |Xi ≤ 2n. This particular structuring of X implies a result for measurable colourings of DF0,...,Fn−1 :
Corollary 2.3.22. If DF0,...,Fn−1 has a fixed ceiling and χB DF0,...,Fn−1 < ℵ0 , then we have
ap χM DF0,...,Fn−1 ≤ 2n + 1. In Section 2.4, we more closely study this setting when there are only 2 functions. In this case, we may drop the requirement to approximate X by Xi :

Theorem 2.4.3. If DF0,F1 has a fixed ceiling and χB DF0,F1 < ℵ0 , then χB DF0,F1 ≤ 4. 2.2 The General Case If D = (X, D) is a digraph, we let D(x) = {y ∈ X : x D y}. The members of D(x) are known as successors of x. We first recall two results from [25]. Theorem 2.2.1. [25] Fix n ≥ 0. Suppose that X is standard Borel and F = {Fi }i<n is a

finite family of Borel functions on X such that χB DF0,...,Fn−1 < ℵ0 . Then χB DF0,...,Fn−1 ≤  1 (n + 1)(n + 2). In particular, there exists a Borel colouring c : X → (i, j) ∈ (n + 1)2 : i + j ≤ n 2   of DF0,...,Fn−1 such that if c(x) = (i0, j0 ), then {(i0, j) : j < j0 } ⊆ c DF0,...,Fn−1 (x) and for each   i < i0 , c DF0,...,Fn−1 (x) ∩ {(i, j) : j ≤ n − 1} , ∅. In particular, Theorem 2.2.1 provides a new proof that χB (DF ) ∈ {1, 2, 3, ℵ0 }. The bound provided by this theorem is not optimal in general, however, as the following special improvements show. Theorem 2.2.2. [25] Suppose that X is standard Borel and F0, F1, F2 : X → X are Borel. Then

χB DF0,F1 ∈ {1, 2, 3, 4, 5, ℵ0 } and χB DF0,F1,F2 ∈ {1, . . . , 8, ℵ0 }. The colouring produced by Theorem 2.2.1 divides X into 12 (n + 1)(n + 2) independent subsets in a very organized way. In particular, if we restrict the digraph to A = c−1 [{(i, j) : i > 0}], then each x ∈ A has at most n − 1 successors in A, since one successor always has colour (0, j) for some j < n + 1. By a standard result of descriptive set theory (for a proof, see [17]), we can write a Borel relation D ⊆ A × A with the property that ∀x (|D(x)| ≤ n − 1) as the disjoint union of n − 1 Borel 6 functions {Gi }i<n−1 , where Gi has Borel domain Ai ⊆ A. By extending Gi to be identity on A\Ai , it follows that DF0,...,Fn−1  A = DG0,...,G n−2 . This observation allows for a natural induction argument that is unnecessary for the proof of Theorem 2.2.1. However, it becomes useful when combined with the base case of Theorem 2.2.2.
Define the function u : ω → ω by letting u(n) be the maximum value of χB DF0,...,Fn−1 , for DF0,...,Fn−1 a digraph of the form described in Theorem 2.2.1. Since a (2n + 1)-clique can take this form, u(n) ≥ 2n + 1. In particular, u(1) = 3, u(2) = 5, u(3) ∈ {7, 8} and Theorem 2.2.1 implies that u(n) ≤ 21 (n + 1)(n + 2). Lemma 2.2.3. For all n < ω, we have u(n + 1) ≤ u(n) + n + 1. Proof. Suppose we have a digraph DF0,...,Fn of the form described in Theorem 2.2.1. It suffices to prove that χB (DF0,...,Fn ) ≤ u(n) + n + 1. Let c be the colouring furnished by Theorem 2.2.1. If we define A = c−1 [{(i, j) : i > 0}], then as noted above, there are Borel functions {Gi }i<n on A such that DF0,...,Fn  A = DG0,...,G n−1 .
Since χB (DG0,...,G n−1 ) ≤ χB DF0,...,Fn−1 < ℵ0 , we can let d : A → u(n) be a Borel colouring of à à DF0,...,Fn  A. Then X = i<u(n) d −1 [{i}] t j<n+1 c−1 [{(0, j)}] is a Borel partition of X into u(n) + n + 1 independent subsets.  Corollary 2.2.4. Fix n ≥ 3. Suppose that X is standard Borel and F = {Fi }i<n is a finite family of

Borel functions on X such that χB DF0,...,Fn−1 < ℵ0 . Then χB DF0,...,Fn−1 ≤ 12 (n + 1)(n + 2) − 2. Proof. By Theorem 2.2.2, we have that u(3) ≤ 8. Hence the result follows by applying Lemma 2.2.3 and induction.  2.3 Commuting Functions In this section, we shall examine digraphs generated by commuting functions, which have a number of properties that allow them to be analyzed more easily. For example, Fact 2.3.11 will show that if x satisfies |D(x)| ≤ m, then so do each of its successors. Definition 2.3.1. If n < ω, X is a set, and { fi }i<n is a sequence in X X , we let ◦i<n fi be shorthand for the composition function f0 ◦ · · · ◦ fn−1 . In the case n = 0, ◦i<n fi denotes id X . If F = { fi }i∈I for some finite index set I instead and F commutes, we also define ◦i∈I fi = ◦ j<|I | fi j for any bijection j 7→ i j from |I | to I. 7  If F ⊆ X X is a family of functions, we let CF = ◦i<n fi ∈ X X : n < ω ∧ ∀i < n ( fi ∈ F ) . In particular, {id X } ∪ F ⊆ CF . Note that if F is a commuting family of functions on X, then so is CF . Definition 2.3.2. If X is a set and f ∈ X X , we let Fix f = {x ∈ X : f (x) = x} be the set of all fixed points of f . Given digraphs D0 = (X, D0 ) and D1 = (Y, D1 ) on the standard Borel spaces X and Y , a Borel homomorphism from D0 to D1 is a Borel function f : X → Y such that for every a, b ∈ X, a D0 b ⇒ f (a) D1 f (b). In this case, we write D0 B D1 . By composing f with a colouring of D1 , it follows that χB (D0 ) ≤ χB (D1 ). Note that if X is standard Borel and F ⊆ X X is a commuting family of Borel functions with no fixed points, then any H ∈ CF is a Borel automorphism of DF . Let D be a family of digraphs on standard Borel spaces and n ≥ 1 an integer. Then it is clear that χB (D) ≤ n for every D ∈ D if and only if D B Kn for every D ∈ D, where Kn is the complete digraph on n points. Below, we construct a much more complicated finite digraph that has chromatic number 2n + 1 which admits Borel homomorphisms for the family of digraphs generated by n commuting Borel functions with no fixed points.
Definition 2.3.3. For integers M, n ≥ 0, let D M,n = XM,n, D M,n be the finite digraph with n
o n XM,n = x ∈ (M + 1)[−M,M] : ∀s, t ∈ [−M, M]n s − t = 1 → x(s) , x(t) and x D M,n y ⇔ ∃ j < n∀s s j < M → y (s) = x s + e j

. Note that if x D M,n y, then x(0) , y(0). One can regard the points of the digraph D M,n as n-dimensional cubic grids of side length 2M + 1, each of whose cells contains one of M + 1 different colours. A grid x connects to y if it can be shifted onto y, replacing the missing face in an arbitrary way. As we will see in Theorem 2.3.5, we can think of each cell as a point in a digraph of the form DF0,...,Fn−1 , with the colour of the cell representing the colour assigned by some fixed finite colouring of DF0,...,Fn−1 .
Theorem 2.3.4. For any M, n ≥ 0, χ D M,n ≤ 2n + 1. 8 Proof. For j < n and k ∈ {−1, 1}, let S (k) j : XM,n → XM,n be defined by     x S (k) j (x)(s) =  s + ke j
if ks j < M  x (s) + 1 (mod M + 1) otherwise.  As noted above, c(x) = x(0) is already an (M + 1)-colouring for D M,n . We will define new colourings e0, . . . , e M by recursion. First, set e0 = c. Then let  o n   (k)   min (2n + 1) \ ei S j (x) : j < n, k ∈ {−1, 1}  if x(0) = i + 1 ei+1 (x) =   ei (x) otherwise.  We claim that for each i < M + 1, if x  [−i, i]n = y  [−i, i]n , then ei (x) = ei (y). This is clearly true for i = 0. Assume it holds for i and that x  [−(i + 1), i + 1]n = y  [−(i + 1), i + 1]n . If x(0) = y(0) , i + 1, we are done. Otherwise, note that for all j < n and k ∈ {−1, 1}, S (k) j (x)      (k) (k) n [−i, i]n = S (k) j (y)  [−i, i] , and so ei S j (x) = ei S j (y) . This implies that ei+1 (x) = ei+1 (y). To complete the proof, we verify that e M is a (2n + 1)-colouring of D M,n . Note that for each x, e M (x) = e x(0) (x) < 2n + 1. Suppose that x D M,n y and x(0) < y(0) (the case y(0) < x(0)
(s) = x s + e for all s with s j < M. Then for s ∈ is similar). Choose j < n such that y j h   i n − y(0) − 1 , y(0) − 1 , we have that S (−1) (y)(s) = y(s − e j ) = x(s). It follows from our claim j   that e y(0)−1 S (−1) (y) = e y(0)−1 (x). Therefore, by definition of e y(0) , it follows that j   (y) = e y(0)−1 (x) = e M (x). e M (y) = e y(0) (y) , e y(0)−1 S (−1) j  Theorem 2.3.5. [25] Fix n ≥ 0. Suppose that X is standard Borel and F = {Fi }i<n is a finite
family of commuting Borel functions on X with no fixed points. Then if χB DF0,...,Fn−1 < ℵ0 , we
have χB DF0,...,Fn−1 ≤ 2n + 1. Proof. Choose M ≥ 0 and a Borel colouring c : X → M + 1 of DF0,...,Fn−1 . Define f : X → XM,n by   M+si f (x)(s) = c ◦i<n Fi (x) . Then f is clearly Borel. If s, t ∈ [−M, M]n with s − loss of generality,  t = 1, then without  M+si M+si t = s + e j for some j < n. So f (x)(s) = c ◦i<n Fi (x) , c Fj ◦i<n Fi (x) = f (x)(t), since F commutes and Fj has no fixed points, which verifies that f (x) ∈ XM,n . If xDF0,...,Fn−1 y, choose 9   j < n such that y = Fj (x). Then for any s with s j < M, we have f (y)(s) = c ◦i<n FiM+si (Fj (x)) = f (x)(s + e j ), whence f (x) D M,n f (y). Hence we have DF0,...,Fn−1 B D M,n , and so by Theorem 2.3.4,
 we have χB DF0,...,Fn−1 ≤ 2n + 1. Definition 2.3.6. Let D = (X, D) be a digraph and let r be any function on X. We say that a Y -colouring c of D is restricted by r if for all x ∈ X, c(x) < r(x). We will have the need to produce colourings like the one Theorem 2.3.5 furnishes, but are also restricted by Borel functions of a particular kind. Toward this, we will consider a slightly more complicated version of D M,n below, in which every cell of every grid also has a restriction associated with it.
Definition 2.3.7. For integers M, n, m ≥ 0, let D M,n,m = XM,n,m, D M,n,m be the countable digraph with n n XM,n,m = x ∈ ((M + 1) × {S ⊆ ω : |S| ≤ m})[−M,M] :
∀s, t ∈ [−M, M]n s − t = 1 → x0 (s) , x0 (t) , where x = (x0, x1 ) is the notation for the component functions. Let D M,n,m be defined as in Definition 2.3.3. Theorem 2.3.8. For any M, n, m ≥ 0, there is a (2n + m + 1)-colouring c of D M,n,m restricted by  r(x) = x1 0 . Proof. As before, c(x) = x0 (0) is an (M + 1)-colouring of D M,n,m . This time, define e−1 = c and, for i ≤ M, n    o    min (2n + m + 1) \ ei−1 S (k)  if x(0) = i j (x) : j < n, k ∈ {−1, 1} ∪ x1 (0) ei (x) =   ei−1 (x) otherwise.  As in the proof of Theorem 2.3.4, e M is a (2n + m + 1)-colouring of D M,n,m .  The next lemma strengthens Theorem 2.3.5 by showing that we can create a similar style of colouring that is restricted by any function with finite values and that has arbitrarily large invariance under the functions {Fi }i<n . Below, we regard P(ω) as the standard Borel space 2ω via the identification A 7→ χA. 10 Lemma 2.3.9. Fix n, m ≥ 0. Suppose that X is standard Borel and F = {Fi }i<n is a finite family of
commuting Borel functions on X with no fixed points. If χB DF0,...,Fn−1 ≤ M + 1 for some integer M, then for any N ≥ M and Borel function t : X → {S ⊆ ω : |S| ≤ m}, there exists a Borel
function b : X → 2n + m + 1 such that B(x) = b ◦i<n FiN−M (x) is a (2n + m + 1)-colouring of
DF0,...,Fn−1 restricted by T(x) = t ◦i<n FiN (x) . Proof. Fix a Borel colouring c : X → M + 1 of DF0,...,Fn−1 . Define f : X → XM,n,m by      f (x)(s) = c ◦i<n FiM+si (x) , t ◦i<n FiM+si (x) . Then, as in Theorem 2.3.5, f is a Borel homomorphism witnessing that DF0,...,Fn−1 B D M,n,m . Let d be the colouring of D M,n,m furnished by Theorem 2.3.8 and let b = d ◦ f , so that b is Borel.
Then B = b ◦ ◦i<n FiN−M is a colouring of DF0,...,Fn−1 since ◦i<n FiN−M  ∈ CF is an automorphism

 of DF0,...,Fn−1 . For each x ∈ X, we have B(x) < f ◦i<n FiN−M (x) 1 0 = t ◦i<n FiN (x) . We now introduce some definitions useful for analyzing the structure of the digraphs of interest. Definition 2.3.10. Let < F be the transitive closure of DF . If we have a finite set {Fi : i < n} of functions and I ⊆ n, let < I be shorthand for < {Fi : i∈I} . Finally, let < be shorthand for <n . For each relation <ξ , we let ≤ξ denote x ≤ξ y ⇔ x <ξ y ∨ x = y. Note, in particular, that < F is not necessarily irreflexive. Suppose X is a set and F ⊆ X X . We make the obvious but important observation that for x, y ∈ X, x ≤F y ⇔ ∃H ∈ CF (H(x) = y). In particular, if P ⊆ X is Borel, then so is {x ∈ X : ∀y ≥ x (y ∈ P)}. This also yields the following two basic properties: Fact 2.3.11. Suppose X is a set, F ⊆ X X is a family of commuting functions, H ∈ F , and x, y ∈ X with x ≤F y. Then 1. H(x) ≤F H(y) and 2. if x ∈ FixH , then y ∈ FixH . Proof. Let H 0 ∈ CF be such that y = H 0(x). Then H(y) = H(H 0(x)) = H 0(H(x)) proves (1). If x ∈ FixH , then H(y) = H 0(H(x)) = H 0(x) = y proves (2).  11 Definition 2.3.12. Let D = (X, D) be a digraph. We say that a collection {Ai }i∈I of disjoint subsets à of X are separated if for all i , j ∈ I and x ∈ Ai, y ∈ A j , we have ¬x D y. If X = i∈I Ai , we say that {Ai }i∈I is a separation. In particular, if DF0 Ai,...,Fn−1 Ai . à i∈I Ai is a separation for DF0,...,Fn−1 , then for each i ∈ I, DF0,...,Fn−1  Ai = Definition 2.3.13. Let X be a set and F ⊆ X X a family of functions. We say that DF has a fixed ceiling if for every x ∈ X, there exists a y ∈ X with x ≤F y such that y ∈ Fix f for some f ∈ F . Lemma 2.3.14. Fix n ≥ 0. Suppose that X is standard Borel and F = {Fi }i<n is a finite family of commuting Borel functions on X. Then there exists a Borel separation X = A t B such that for each i < n, Fi  A has no fixed points and DF0,...,Fn−1  B has a fixed ceiling. Proof. Define B= Ø Ø   H −1 FixFj and A = X\B. H∈CF j<n Since CF is a countable family of Borel functions, A t B is a Borel partition of X. Note that

x ∈ B ⇔ ∃H ∈ CF ∃ j < n Fj (H(x)) = H(x) ⇔ ∃y ≥ x ∃ j < n Fj (y) = y . Therefore, Ð we may conclude DF0,...,Fn−1  B has a fixed ceiling if we show that j<n Fj [B] ⊆ B. Since   Ð Ð −1 ) (id ⊆ B, no Fi  A has a fixed point. Fix Fix = F X F j<n j<n j j It remains only to show that A t B is a separation; consider any x ∈ A and y ∈ B. If x DF0,...,Fn−1 y, then there is a fixed point z such that x < y ≤ z. This implies that x ∈ B, a contradiction. If y DF0,...,Fn−1 x, then choose j < n such that Fj (y) = x. Let z ≥ y be a fixed point; by Fact 2.3.11, Fj (z) ≥ Fj (y) = x is a fixed point too, again implying x ∈ B.  Lemma 2.3.14 shows us that it is enough to consider digraphs with fixed ceilings, since Theorem 2.3.5 will allow to find a Borel colouring for DF0,...,Fn−1  A. Theorem 2.3.15. Fix n ≥ 0. Suppose that X is standard Borel and F = {Fi }i<n is a finite family
of commuting Borel functions on X. If χB DF0,...,Fn−1 < ℵ0 and DF0,...,Fn−1 has a fixed ceiling, then
Ð there exists an increasing filtration X = i∈ω Xi such that for each i ∈ ω, χB DF0,...,Fn−1 |Xi ≤ 2n. We will prove this theorem after detailing a useful way to decompose the space X of such a digraph. In what follows, we work with a fixed digraph DF0,...,Fn−1 with the above properties. 12 We will define Borel subsets Q m ⊆ X for each m < ω by recursion. Let  I = (I0, I1 ) ∈ P(n)2 : n = I0 t I1 ∧ I1 , ∅ . For each (I0, I1 ) ∈ I, define Q0(I0,I1 ) = {x ∈ X : ∀y ≥ x∀i (i ∈ I0 ↔ Fi (y) , y)} , and define Q0 = Ð (I0,I1 ) . (I0,I1 )∈I Q 0 Lemma 2.3.16. For every x ∈ X, there exists y ≥ x with y ∈ Q0 . Proof. Fix any x ∈ X. Let I1 = {i < n : ∃y ≥ x (Fi (y) = y)} and I0 = n\I1 . Since DF0,...,Fn−1 has a fixed ceiling, I1 , ∅, so that (I0, I1 ) ∈ I. For each i ∈ I1 and j < n, let k (i) j ≥ 0 be such that n o (i) k ◦ j<n Fj j (x) is a fixed point of Fi . Then if we let k j = max k (i) j : i ∈ I1 for each j < n, it follows that y = ◦ j<n Fj j (x) ∈ Q0(I0,I1 ) . k   Let I 0 = (I0, I1 ) ∈ P(n)2 : n ) I0 t I1 and J = ({0} × I) ∪ (ω\ {0} × I 0). For (I0, I1 ) ∈ I 0, let I2 = n\ (I0 t I1 ). Suppose that for every i ≤ m and I0, I1 ⊆ n with (i, I0, I1 ) ∈ J , we have defined Qi(I0,I1 ) . For any (I0, I1 ) ∈ I 0, we define ( ! Ø Ø 0,I1 ) Q(I Qi : ∀i ∈ I0 ∀y ≥ I0 x Fi (y) , y ∧ Fi (y) < Qi m+1 = x ∈ X\ i≤m i≤m ∧∀i ∈ I1 ∀y ≥ I0 x (Fi (y) = y) ∧ ∀i ∈ I2 ∃ j ≤ m∀y ≥ I0 x Fi (y) ∈ Q j
. Ð 0,I1 ) and we define Q m+1 = (I0,I1 )∈I 0 Q(I m+1 . It is immediate from these definitions that if x ∈ Q m and x ≤ y, then y ∈ Q m 0 for some m0 ≤ m. Lemma 2.3.17. X = Ð m<ω Q m . Ð Proof. For ease of notation, let Q = m<ω Q m ⊆ X. Suppose for sake of contradiction that x ∈ X\Q. Define x0 = x and I00 = n. Suppose that xm ≥ x and Im0 ⊆ n have been defined with 0 xm < Q and Fj (xm ) ∈ Q for all j ∈ n\Im0 . If there exists y > Im0 x with y ∈ Q, define xm+1 and Im+1 as follows: for this y, choose xm+1 such that xm ≤ Im0 xm+1 < Im0 y and j ∈ Im0 such that xm+1 < Q but 0 Fj (xm+1 ) ∈ Q. Let Im+1 = Im0 \ { j}. Note that since Fj (xm+1 ) ≥ Fj (xm ), we have that Fj (xm+1 ) ∈ Q 0 for all j < Im+1 . Continue this process until we reach some N ≤ n such that xN < Q but ∀y > I N0 x, y < Q. 13 ki By Lemma 2.3.16, there are ki for i < n such that N > 0, n y = ◦i<n Fi (x) ∈ Q0 . In particular, o
and so IN ( n. For j ∈ n\IN0 , let m j = min m < ω : ∃y0 ≥ I N0 x Fj (y0) ∈ Q m . For j ∈ k ( j) (j) n\IN0 and i ∈ IN0 , let ki be such that if y = ◦i∈I N0 Fi i (xN ), then Fj (y) ∈ Q m j . Let I1 = n o ( j) 0 0 i ∈ IN : ∃y ≥ I N x (Fi (y) = y) and I0 = IN0 \I1 . Next, for j ∈ I1 and i ∈ IN0 , let k̃i be such that n o n o (j) k̃ ( j) ( j) ◦i∈I N0 Fi i (xN ) ∈ FixFi . Then let ki = max ki : j ∈ n\IN0 ∪ k̃i : j ∈ I1 for each i ∈ IN0 . If we set y = ◦i∈I N0 Fiki (xN ), then one can check that y ∈ Q(I0,I1 ) max j ∈n\I 0 (m j +1) , even though y < Q. N  (I 0,I 0 ) 0,I1 ) and j < I0 ∪ I1 . Then Fj (x) ∈ Q m00 1 for some m0 < m Lemma 2.3.18. Suppose that x ∈ Q(I m with I0 ∪ I1 ⊆ I00 ∪ I10 . Proof. We need only check that the inclusion I0 ∪ I1 ⊆ I00 ∪ I10 holds. Suppose that ` ∈ I20 \I2 . Then
F` Fj (x) ∈ Q m 00 for some m00 < m0, but Fj (F` (x)) ∈ Q m 0 , a contradiction.  Given m > 0, (I0, I1 ) ∈ I 0, and a function a : I2 → n m0, I00 , I10  o ∈ J : m0 < m , we define n  o I00,I10 (I0,I1 ) 0 0 0
0,I1 ) Q(I (a) = x ∈ Q : ∀ j ∈ I ∀y ≥ x a( j) = m , I , I → F (y) ∈ Q . 2 I0 j m m 0 1 m0 Let a = (a0, a1, a2 ) be the component functions for such an a. We now show that for every m > 0, we can separate Q m into rather homogeneous subsets. Lemma 2.3.19. Both Q0 = separations. Ã (I0,I1 ) and (for any m > 0) Q m (I0,I1 )∈I Q 0 = Ã (I0,I1 ) (a) are I0,I1,a Q m Proof. It is clear by the definitions that each is a partition. We will handle the m > 0 case. Choose 0 0 0,I1 ) 0 ∈ Q (I0,I1 ) (a0), and j < n such that F (x) = x 0 and x , x 0. Since x , x 0, we must x ∈ Q(I (a), x j m m 0,I1 ) have j ∈ I0 , which in particular implies that x ≤ I0 x 0. By the definition of Q(I (a), it follows m 0 0 0 0 0 immediately that a = a . Also, i ∈ I1 ⇔ Fi (x ) = x ⇔ i ∈ I1 , so that I1 = I1 , and similarly, I0 = I00 . The proof of the m = 0 case is analogous.  Fix an integer M ≥ 0 and a colouring c : X → M + 1 of DF0,...,Fn−1 . Lemma 2.3.20. For every integer N ≥ 0, there exists a Borel function b : Q0 → 2n − 1 such that
the function B(x) = b ◦i<n FiN (x) is a (2n − 1)-colouring of DF0,...,Fn−1  Q0 . 14 Ã Proof. Since Q0 = (I0,I1 )∈I Q0I0,I1 is a finite Borel separation, it suffices to find such a (2n − 1)colouring for each Q0I0,I1 . To do this, note that DF0,...,Fn−1  Q0I0,I1 = D{Fi : i∈I0 }  Q0I0,I1 and that Fi for i ∈ I0 has no fixed points in Q0I0,I1 . Therefore, we can apply Lemma 2.3.9 (with

m = 0) to obtain a Borel b : Q0I0,I1 → 2 |I0 | + 1 such that B(x) = b ◦i∈I0 FiN (x) = b ◦i<n FiN (x) is a colouring on Q0I0,I1 . Since 2 |I0 | + 1 ≤ 2n − 1, we are done.  1) for some (m, I, I1 ) ∈ J . For x ∈ X, let I0 (x) = I if and only if x ∈ Q(I,I m Lemma 2.3.21. Let m ≥ 0 be an integer. Suppose that N ≥ M and there is a Borel function
Ð b : j≤m Q j → 2n such that the function B(x) = b ◦i∈I0 (x) FiN (x) is a colouring. Then there is a
Ð Borel b0 : j≤m+1 Q j → 2n such that the function B0(x) = b0 ◦i∈I0 (x) FiN−M (x) is a colouring of Ð 0 j≤m+1 Q j and B extends B. Ð  j≤m Q j j≤m Q j = B. (I0,I1 ) Since Q m+1 = I0,I1,a Q m+1 (a) is a finite Borel separation, it suffices to extend b0 to generate a Ð 0,I1 ) 2n-colouring on each Q(I j≤m Q j . To do this, note as in Lemma 2.3.20 that DF0,...,Fn−1  m+1 (a) ∪ (I0,I1 ) Q m+1 (a) is generated by {Fi : i ∈ I0 }, which have no fixed points, so we can apply Lemma 2.3.9. 0,I1 ) |I | |I | This time, we obtain a b0 : Q(I m+1 (a) → 2 0 + 2 + 1 by using the restriction Ð Proof. First of all, define b0 on by b0(x) = b ◦i∈I0 (x) FiM (x) , so that B0 
à  o n  T(x) = {B0 (Fi (x)) : i ∈ I2 } = b ◦`∈a0 (i) F`M (Fi (x)) : i ∈ I2 n   o n    o M M M = b ◦`∈a0 (i)∪a1 (i) F` (Fi (x)) : i ∈ I2 = b ◦`∈a0 (i)∪a1 (i)\I0 F` ◦ Fi ◦`∈I0 F` (x) : i ∈ I2   = t ◦i∈I0 FiM (x) , n   o where t = b ◦`∈a0 (i)\I0 F`M ◦ Fi (x) : i ∈ I2 is Borel. Letting B0 be as defined in the statement, Ð (I0,I1 ) 0,I1 ) then B0 is a colouring separately on Q(I (a) and j≤m Q j . If x DF0,...,Fn−1 y and x ∈ Q m+1 (a), m+1 Ð y ∈ j≤m Q j , then y = Fi (x) for some i ∈ I2 , and hence the restriction T ensures B0(x) , B0(y). Since 2 |I0 | + |I2 | + 1 ≤ 2n, we are done.  We now have enough information to complete the proof of Theorem 2.3.15. Ð Proof of Theorem 2.3.15. Let Xm = i≤m Qi . Beginning with Lemma 2.3.20 with N = mM, we can Ð argue by Lemma 2.3.21 and induction that for every j ≤ m, there is a Borel function b j : i≤ j Qi 15   Ð N− j M such that the Borel function B j (x) = b j ◦i∈I0 (x) Fi (x) is a 2n-colouring of i≤ j Qi . Hence
Bm shows that χB DF0,...,Fn−1  Xm ≤ 2n.  In the case of measurable colourings, this countable filtration of X is enough to provide a bound for the approximate measure chromatic number. Corollary 2.3.22. Fix n ≥ 0. Suppose that X is standard Borel and F = {Fi }i<n is a finite family
of commuting Borel functions on X. Suppose in addition that χB DF0,...,Fn−1 < ℵ0 . Then we have
ap χM DF0,...,Fn−1 ≤ 2n + 1. Ð Proof. By Lemma 2.3.14 and Theorems 2.3.5 and 2.3.15, we can write X = A t i<ω Xi ,
Ð where {Xi }i<ω is increasing, A is separated from i<ω Xi , and χB DF0,...,Fn−1  A ≤ 2n + 1 and
χB DF0,...,Fn−1  Xi ≤ 2n for all i < ω. So for any probability measure µ and ε > 0, there exists

an n such that µ (X\ (A t Xn )) < ε, and χµ DF0,...,Fn−1  (A t Xn ) ≤ χB DF0,...,Fn−1  (A t Xn ) ≤ 2n + 1.  2.4 Two Commuting Functions We first recall a result from [25] that concerns digraphs with no infinite paths. Definition 2.4.1. Suppose X is a set, and F = {Fi }i<n is a finite family of functions on X. We say that A ⊆ X is bounded if DF0,...,Fn−1 is cowellfounded on A. Lemma 2.4.2. [25] Fix n ≥ 0. Suppose that X is standard Borel and F = {Fi }i<n is a finite family of Borel functions on X. Suppose A ⊆ X is bounded such that for all x ∈ X\A and y ∈ A, ¬x DF0,...,Fn−1 y. If for some integer M, c : X\A → M is a Borel colouring of DF0,...,Fn−1  (X\A), then there is a Borel colouring c0 : X → max {n + 1, M } of DF0,...,Fn−1 extending c. Given a digraph DF0,...,Fn−1 as in Lemma 2.4.2, let n    o B(X) = x ∈ X : ∃M ∀i ∈ n M+1 ∃k < M Fik ◦ j<k Fi j (x) = ◦ j<k Fi j (x) . So B(X) is the set of x ∈ X for which there is an M for which there are no paths of length M beginning at x. Therefore, B(X) is bounded and clearly Borel from its definition. Theorem 2.4.3. Suppose that X is standard Borel and F0, F1 : X → X are commuting Borel

functions. If χB DF0,F1 < ℵ0 and DF0,F1 has a fixed ceiling, then χB DF0,F1 ≤ 4. 16 To prove this theorem, we will introduce a decomposition of X different from the Qi sets considered in Section 2.3. In what follows, we work with a fixed digraph DF0,F1 satisfying the conditions of Theorem 2.4.3. Fix an integer M ≥ 0 and a colouring c : X → M + 1 of DF0,F1 . Define r : X → ω by n r(x) = min k 0 + k 1 : F0k0 ◦ F1k1 (x) ∈ FixF0 ∪ FixF1 o . Hence r(x) is the minimum length of a path from x to a fixed point. Since DF0,F1 has a fixed ceiling, r is finite on all of X. Define Ri = {x ∈ X : r(x) = i}. In particular, R0 = FixF0 ∪ FixF1 . Clearly, r and hence each Ri is Borel. Proposition 2.4.4. Suppose x ∈ X. Then 1. for each i < 2, r (Fi (x)) ∈ {r(x), r(x) − 1}; 2. if r(x) > 0, then r (Fi (x)) = r(x) − 1 for at least one i < 2; and     k0 k1 k 3. if r F0 (x) = r(x) for all k < ω, then r F0 ◦ F1 (x) = max {r(x) − k 1, 0}. Proof. If H ∈ C{F0,F1 } and H(x) ∈ R0 , then by Fact 2.3.11, H (Fi (x)) ∈ R0 for each i < 2, showing that that r (Fi (x)) ≤ r(x). Additionally, F0k0 ◦ F1k1 (F0 (x)) = F0k0 +1 ◦ F1k1 (x) shows that r(x) ≤ r (F0 (x)) + 1, proving (1). Let k 0 + k1 be minimal such that F0k0 ◦ F1k1 (x) ∈ R0 . If r(x) > 0 then some ki > 0; if i = 1, then F0k0 ◦ F1k1 −1 (F1 (x)) = F0k0 ◦ F1k1 (x) shows that r (F1 (x)) = r(x) − 1, proving (2).   (3) is immediate for k 1 = 0. If k 1 + 1 ≤ r(x), then since r F0k0 ◦ F1k1 (x) = r(x) − k 1 for any   k0 k1 +1 k 0 < ω, it follows from (2) that r F0 ◦ F1 (x) = r(x) − (k 1 + 1). If k 1 + 1 > r(x), then     r F0k0 ◦ F1k1 +1 (x) ≤ r F0k0 ◦ F1k1 (x) = 0.  Lemma 2.4.5. Suppose F0 has no fixed points and that for every x ∈ X, r(F0 (x)) = r(x). Then
χB DF0,F1 ≤ 3. Proof. Let f : X → XM,1 be the Borel function defined by   f (x)(s) = c F0M+r(x)+s ◦ F1r(x) (x) . Since F0 has no fixed points, f(x) ∈ XM,1 . If y = F0 (x),  then r(x) = r(y), and so for any s ∈ M+r(y)+s r(y) [−M, M), we have f (y)(s) = c F0 ◦ F1 (F0 (x)) = f (x)(s + 1), whence f (x) D M,1 f (y). 17   M+r(y)+s r(y) If y = F1 (x) and x , y, then r(y) = r(x) − 1, and so f (y)(s) = c F0 ◦ F1 (F1 (x)) =   M+r(x)−1+s r(x)−1+1 (x) = f (x)(s − 1) for s ∈ (−M, M]. Therefore, DF0,F1 B D M,1 , and so c F0 ◦ F1 the result follows by Theorem 2.3.4.  Lemma 2.4.6. Suppose that F0 is the same as in Lemma 2.4.5. For every Borel function t : R0 → {S ⊆ ω :  |S| ≤ m}, there exists a Borel colouring b : X → m + 3 of X restricted by T(x) = t F0M (x) for x ∈ R0 . Proof. This time, define the Borel function f : X → XM,1,m by      r(x) M+r(x)+s r(x) M+r(x)+s ◦ F1 (x) . ◦ F1 (x) , t F0 f (x)(s) = c F0 As in Lemma 2.4.5, f witnesses that DF0,F1 B D M,1,m . If we let b = d ◦ f , where d is the colouring from Theorem 2.3.8, then b is a Borel colouring and for each x ∈ R0 , we have b(x) <   M+r(x) r(x) t F0 ◦ F1 (x) = T(x).  Proof of Theorem 2.4.3: For each i < 2, define Bi = {x ∈ X : ∀y ≥ x (Fi (y) , y ∧ r(Fi (y)) = r(y))} . We claim that B(X) t B0 nt B1 are o separated; in fact, that each of the three sets is closed under j successors. If x ∈ Bi , then Fi (x) is an infinite path beginning at x, showing that B(X)∩Bi = ∅. j<ω Since DF0,F1 has a fixed ceiling, there exists y ≥ x with y ∈ FixF1−i , showing that B0 ∩ B1 = ∅. If x DF0,F1 y and there are no paths of length M beginning at x, then there are no such paths beginning at y, showing that B(X) is closed under successors. It is also immediate from the definition that each Bi is too, proving the claim. Each Bi is clearly Borel. By applying Lemma 2.4.2 to B(X) and Lemma 2.4.5 to each Bi , we obtain a Borel 3-colouring c of DF0,F1  (B(X) t B0 t B1 ). Consider any x ∈ R0 and assume without loss j j+1 of generality that x ∈ FixF1 . Then either there exists j < ω with F0 (x) = F0 (x), in which case there are no paths of length j + 1 beginning at x, or F0i (x) , F0i+1 (x) for all i < ω, in which case x ∈ B0 . This shows that R0 ⊆ B(X) t B0 t B1 . Let B0 = X\ (B(X) t B0 t B1 ) and for each i < 2, define n  o  r(x) r(x) Bi0 = x ∈ B0 : ∀y ≥ x (r(Fi (y)) = r(y)) ∧ Fi F1−i (x) = F1−i (x) If x ∈ B00 , then r(x) > 0 and so by Proposition 2.4.4, it follows that r(F1 (x)) = r(x) − 1, so that n o j B00 ∩ B10 = ∅. If x ∈ Bi0, r(y) > 0, and x DF0,F1 y, then Fi (y) is an infinite path beginning at y, j<ω 18  r F (x)

r (Fj (x)) ( j ) so that y < B(X). Using Proposition 2.4.4, it is clear that Fi F1−i Fj (x) = F1−i Fj (x) for each j < 2, and so y < Bi . Hence y ∈ B0 and so y ∈ Bi0. In particular, this shows that B00 and B10 are separated and that if x ∈ Bi0, then Fj (x) ∈ Bi0 unless j = 1 − i and r(x) = 1, in which case it belongs to B(X) t B0 t B1 . If we define F10 : B0 → B0 by   if r(x) > 1 x  if r(x) = 1,  F1 (x)  F10(x) =  then it is easy to check that F0  B0 commutes with F10 and DF0,F1  B0 = DF0 B0,F10 . Hence,   letting s(x) = {c (F1 (x))}, we can apply Lemma 2.4.6 with the restriction t(x) = s F0M (x) = n   o n  o c F1 F0M (x) = c F0M (F1 (x)) = {c (F1 (x))}. The same argument applies to B10 , and we obtain a 4-colouring c0 on B(X) t B0 t B1 t B00 t B10 that extends c.   Finally, B00 = B0\ B00 t B10 is bounded. If not, let {xi }i<ω be an infinite path in B00. By Proposition 2.4.4 r (xi ) is monotonically decreasing in i, and so we may assume that every xi ∈ Rk for some  fixed k > 0. Without loss of generality, assume r (F1 (x0 )) = k − 1. Then r F0` (F1 (x0 )) ≤ k − 1   k0 k1 i for every ` < ω, and so xi = F0 (x0 ). By Proposition 2.4.4, r F0 ◦ F1 (x0 ) = max {k − k1, 0}. So since x0 < B0 , it must be that F(y) = y for some y ≥ x. Letting y = F0k0 ◦ F1k1 (x), it follows that x k0 = F0k0 (x) is in B10 , a contradiction. Hence we may apply Lemma 2.4.2 to extend c0 to a Borel 4-colouring of all of DF0,F1 , completing the proof.  There are straightforward ways to generalize Proposition 2.4.4 and Lemmas 2.4.5 and 2.4.6 for digraphs of the form DF0,...,Fn−1 for n > 2. However, it seems difficult to adapt the proof of Theorem 2.4.3, since the additional functions mean there are much fewer bounded subsets of the digraph. 19 Chapter 3 20 DEFINABLE COMBINATORICS OF SOME BOREL EQUIVALENCE RELATIONS (with William Chan) 3.1 Introduction Set theorists have studied the Jónsson property and other combinatorial partition properties of well-ordered sets under the axiom of choice, large cardinal axioms, and the axiom of determinacy. Holshouser and Jackson began the study of the Jónsson property using definability techniques for sets which generally cannot be well-ordered in a definable manner. Let X be a set and E an equivalence relation on X. For each n ∈ ω, let [X]nE be the collection of Ð n tuples (x0, ..., xn−1 ) ∈ n X so that for all i , j, ¬(xi E x j ). Let [X]<ω n∈ω [X]E . For each n ∈ ω, E = X has the n-Jónsson property if and only if for every function f : [X]=n → X, there is some Y ⊆ X with Y in bijection with X and f [[Y ]=n ] , X. X has the Jónsson property if and only if for every function f : [X]=<ω → X, there is some Y ⊆ X with Y in bijection with X, and f [[Y ]=<ω ] , X. Holshouser and Jackson showed that ω 2 has the Jónsson property under the axiom of determinacy, <ω → ω 2. For each n ∈ ω, let f : [X]n → X be f  [X]n . Their proof has two AD. Let f : [ω 2]= n = = notable tasks: (1) Holshouser and Jackson first (assuming all sets have the Baire property) choose comeager sets Cn ⊆ n (ω 2) so that fn  Cn is continuous. Then a single perfect set P ⊆ ω 2 is found so that for each n, fn  [P]=n is continuous. To obtain this perfect set P, they use a classical theorem of Mycielski which states: If Cn is a sequence of comeager subsets of n (ω 2), then there is some perfect set P ⊆ ω 2 so that [P]=n ⊆ Cn for all n. (2) Since each fn is continuous on [P]=n , they use a fusion argument to simultaneously prune P to a smaller perfect set Q ⊆ P so that there exists some real that is missed by each fn on [Q]=n . Holshouser and Jackson ask whether other sets which may not be well-ordered in some choiceless setting like AD could also have the Jónsson property. They observed that under ZF + AD + V = L(R), every set X ∈ LΘ (R) has a surjective function f : R → X. Define an equivalence relation on R by x E y if and only if f (x) = f (y). Then X is in bijection with R/E. The study of the Jónsson property for sets in LΘ (R) is equivalent to studying the Jónsson property for quotients of R by equivalence relations on R. Note that R is in bijection with R/=. Through dichotomy results of Harrington, Hjorth, Kechris, Louveau, and others, the equivalence relations =, E0 , E1 , E2 , and E3 occupy special positions in the structure of ∆11 equivalence relations under ∆11 reducibilities. = is the identity equivalence relation on ω 2. E0 is defined on ω 2 by x E0 y if and only if (∃n)(∀k > n)(x(k) = y(k)). E1 is defined on ω (ω 2) by x E1 y if and only if Í 1 : n ∈ x 4 y} < ∞, (∃n)(∀k > n)(x(k) = y(k)). E2 is defined on ω 2 by x E2 y if and only if { n+1 where 4 denotes the symmetric difference. E3 is defined on ω (ω 2) by x E3 y if and only if (∀n)(x(n) E0 y(n)). Holshouser and Jackson asked whether the methods applicable for showing R/= has the Jónsson property could be used to show the quotients of these other ∆11 equivalence relations could be Jónsson. An important aspect of their proof for R was the theorem of Mycielski. They defined the Mycielski property for arbitrary equivalence relations as follows: Let E be an equivalence relation on a Polish space X. For each n ∈ ω, E has the n-Mycielski property if and only if for every comeager C ⊆ n X, there exists some ∆11 A ⊆ X so that E ≤∆1 E  A and [A]nE ⊆ C. 1 They asked whether any of the ∆11 equivalence relations mentioned above have the n-Mycielski property for various n ∈ ω and whether the Mycielski property could be used to prove the Jónsson property for the quotient of any of these equivalence relations. Holshouser and Jackson began this study by showing that E0 has the 2-Mycielski property and this can be used to show ω 2/E0 has the 2-Jónsson property. This paper will show that the Mycielski property fails in most cases: Theorem 3.8.1. The equivalence relation E0 does not have the 3-Mycielski property. Theorem 3.13.4. The equivalence relation E1 does not have the 2-Mycielski property. Theorem 3.15.1. The equivalence relation E2 does not have the 2-Mycielski property. Theorem 3.18.2. The equivalence relation E3 does not have the 2-Mycielski property. These results require understanding the structure of ∆11 subsets of ω 2 or ω (ω 2) so that E0 ≤∆1 E0  A 1 (or E1 ≤∆1 E1  A, etc.) that come from the proofs of the dichotomy results. Kanovei, Sabok, 1 and Zapletal in [13], [14], [29], and [30] have studied the forcing of such ∆11 sets for each of these equivalence relations. 21 Given that the Mycielski property fails in general, a reflection on Holshouser and Jackson’s proof of the Jónsson property for ω 2 shows that it is only used to find some perfect set P so that fn  [P]=n is nicely behaved (i.e., continuous). This paper will give a forcing style proof of Holshouser and Jackson results that ω 2 is Jónsson and ω 2/E0 is 2-Jónsson assuming all functions satisfy a certain definability condition expressed in Lemma 3.3.3. This definability condition follows from the Mycielski property for the equivalence relation and the assumption that all sets have the Baire property. All ∆11 functions have this definability condition and under the axiom of choice and large cardinal assumptions, projective and even more complex sets also satisfy this condition. Following part (2) of Holshouser and Jackson’s template for ω 2, suppose one could find some ∆11 set B ⊆ ω 2 with E0 ≤∆1 E0  B and f  [B]3E0 is continuous for some function f . Could one then 1 somehow prune B to some C ⊆ B so that E0 ≤∆1 E0  C and f [[C]3E0 ] , ω 2, or even better, miss an 1 E0 -class? This paper will have some discussion on how these continuity and surjectivity properties for E0 and E2 can fail. This line of reasoning shows both part (1) and part (2) of the proof of Holshouser and Jackson establishing ω 2 is Jónsson fail for E0 and several other ∆11 equivalence relations. Moreover, for E0 , it will in fact be shown that ω 2/E0 is not Jónsson under determinacy: Theorem 3.10.4. (ZF + AD) ω 2/E0 does not have the 3-Jónsson property and hence is not Jónsson. Here are some historical remarks about the Jónsson property: Under the axiom of choice, mathematicians usually study the Jónsson property on cardinals. Cardinals possessing the Jónsson property are called Jónsson cardinals. For n ∈ ω, let P n (X) denote the collection of all n-element subsets of X. Since there is a well-ordering, the Jónsson property is usually defined using P n (X) rather than [X]=n . This paper will use the term “classical Jónsson property” when discussing the Jónsson property using P n (X). Under the axiom of choice, Jónsson cardinals also have model-theoretic characterizations. The existence of Jónsson cardinals imply V , L. Moreover, it has large cardinal consistency strength: for instance, it implies 0] exists. Erdős and Hajnal ([5] and [4]) showed that if 2κ = κ + , then κ + is not a Jónsson cardinal. Hence under CH, 2ℵ0 is not a Jónsson cardinal. Every real valued measurable cardinal is Jónsson (see [4] Corollary 11.1). Solovay showed the consistency of a measurable cardinal implies the consistency of 2ℵ0 being real valued measurable. Hence it is consistent relative to a measurable cardinal that 2ℵ0 is a Jónsson cardinal. The sets ω 2, ω 2/E0 , ω (ω 2)/E1 , ω 2/E2 , ω (ω 2)/E are all in bijection with each other using the axiom of choice. Hence if CH holds, these 3 22 quotients do not have the Jónsson property and if 2ℵ0 is real valued measurable, then all these quotients do have the Jónsson property. Studies of the Jónsson property and other combinatorial partition properties of cardinals under AD date back to the 1960s and 1970s. Assuming AD, for each n ∈ ω, ℵn is a Jónsson cardinal ([21]). More recently Woodin had shown that under ZF + AD+ , every cardinal κ < Θ has the Jónsson property. Also [12] showed that in ZF + AD + V = L(R), every cardinal κ < Θ is Jónsson. [12] asked whether ω 2, which cannot be well-ordered, has the Jónsson property. In analogy, they asked if every set in LΘ (R) has the Jónsson property. Holshouser and Jackson’s answer to this question for ω 2 begins the work that is carried out in this paper. Throughout, results attributed to Holshouser and Jackson can be found in [11] and [10]. We will frequently identify R with ω 2 and use ∆11 as an abbreviation for “Borel”. This paper is organized as follows: Section 3.2 contains definitions of the main concepts and some basic facts about determinacy. Section 3.3 will give a proof of the result of Holshouser and Jackson which shows ω 2 has the Jónsson property if all sets have the Baire property. The proof uses forcing arguments and fusion. This section will have some discussions about how absoluteness available under AD+ can help prove said result without using the Mycielski property. However, throughout the paper, a flexible fusion argument is necessary for handling the combinatorics. It is unclear what the relation is between properness, fusion, and the Jónsson property for the five equivalence relations considered. Upon considering the Jónsson property for ω 2, a natural question is whether there is a function f : P ω (ω 2) → ω 2 so that for all A ⊆ ω 2 with A ≈ ω 2, f [P ω (A)] = ω 2. Such a function is called an ω-Jónsson function for ω 2. Under the axiom of choice, [5] showed that every set has an ω-Jónsson function. Section 3.4 gives an example under ZF + ACRω (choice for countable sets of nonempty subsets of ω 2) of a ∆11 ω-Jónsson function for ω 2. From the effective proof of the E0 -dichotomy, every Σ11 set A ⊆ ω 2 so that E0 ≤∆1 E0  A contains 1 the body of a perfect tree with certain symmetry restrictions, known as an E0 -tree. Section 3.5 will modify the proof of the E0 -dichotomy using Gandy-Harrington methods to prove a structure theorem for Σ11 sets with the same E0 -saturation on which the restriction of E0 is not smooth: For example, if A and B are two Σ11 sets with E0 ≤∆1 E0  A, E0 ≤∆1 E0  B, and [A]E0 = [B]E0 , then 1 1 there are E0 trees p and q with [p] ⊆ A, [q] ⊆ B, and p and q are the same except possibly at the stem. This consideration reveals the failure of the weak 3-Mycielski property (see Definition 23 3.2.24) for E0 . Section 3.6 will introduce the forcing b P2E0 . We will use this forcing to prove the result of Holshouser and Jackson stating that ω 2/E0 has the 2-Jónsson property. Let X and Y be sets. Let n ∈ ω. Define X → (X)Yn to mean that for any function f : P n (X) → Y , there is some Z ⊆ X with Z ≈ X and | f [P n (Z)]| = 1. Define X 7→ (X)Yn to mean that for any function f : [X]=n → Y , there is some Z ⊆ X with Z ≈ X and | f [[Z]=n ]| = 1. Section 3.7 will show that ω 2/E0 7→ (ω 2/E0 )2n holds for all n ∈ ω. Section 3.8 will show that E0 does not have the 3-Mycielski property or weak 3-Mycielski property. Section 3.9 will produce a continuous function Q : [ω 2]3E0 → ω 2 so that for every Σ11 A ⊆ ω 2 with E0 ≤∆1 E0  A, Q[[A]3E0 ] = ω 2. A modification of this function yields a ∆11 function 1 K : 3 (ω 2) → ω 2 so that on any such set A, K  [A]3E0 is not continuous. Section 3.10 will use the function produced in the previous section to show that ω 2/E0 does not have the 3-Jónsson property or the classical 3-Jónsson property under ZF + AD. (In particular, ω 2/E is not Jónsson under AD.) 0 Section 3.11 will use the classical 3-Jónsson map for ω 2/E0 to show the failure of ω 2/E0 → (ω 2/ E0 )32 . The fusion argument related to the proper forcing b P2E0 established many of the combinatorial properties of E0 in dimension two. Given the failure of these properties in dimension three, a natural question would be whether the three dimensional analog b P3E0 is proper and possesses a reasonable fusion. Section 3.12 will show that b P3E0 is proper by having some type of fusion argument. However, there is far less control of this fusion. Section 3.13 will show that E1 does not have the 2-Mycielski property. Section 3.14 will modify the proof of the E2 -dichotomy result using Gandy-Harrington methods to give structural result about E2 -big Σ11 sets with the same E2 -saturation: For example, if A and B are two Σ11 sets with E2 ≤∆1 E2  A, E2 ≤∆1 E2  B, and [A]E2 = [B]E2 , then there are two E2 -trees 1 1 (perfect trees with certain properties) p and q so that [p] ⊆ A, [q] ⊆ B, [[p]]E2 = [[q]]E2 , and p and q resemble each other in specific ways. Section 3.15 will use results of the previous section to show E2 does not have the 2-Mycielski property and the weak 2-Mycielski property. Section 3.16 will produce a continuous function Q : [ω 2]3E2 → ω 2 so that on any Σ11 set A with 24 E2 ≤∆1 E2  A, Q[[A]3E2 ] = ω 2. There is also a ∆11 function P0 : 3 (ω 2) → ω 2 so that for any such 1 set A, P0  A is not continuous. Section 3.17 contains no new results but just gives the rather lengthy characterization of Σ11 sets A ⊆ ω (ω 2) so that E3 ≤∆1 E3  A that comes from the E3 -dichotomy result. This structure result is 1 applied in Section 3.18 to show that E3 does not have the 2-Mycielski property. Section 3.19 will study the completeness of non-principal ultrafilters on quotients of Polish spaces by equivalence relations. The authors would like to thank Jared Holshouser and Stephen Jackson whose talks and subsequent discussions motivated the work that appears here. The authors would also like to thank Alexander Kechris for comments and discussions about this paper. 3.2 Basic Information Definition 3.2.1. Let σ ∈ <ω 2. Suppose |σ| = k. Then σ̃ ∈ ω 2 is defined by σ̃(n) = σ( j) where 0 ≤ j < k and j ≡ n mod k. For example, 0̃, 1̃, f 01, etc. will appear frequently. Definition 3.2.2. Let σ ∈ <ω 2. Let Nσ = {x ∈ ω 2 : x ⊇ σ}. {Nσ : σ ∈ <ω 2} is a basis for the topology on ω 2. Let σ, τ ∈ <ω 2. Let Nσ,τ = {(x, y) ∈ 2 (ω 2) : x ∈ Nσ ∧ y ∈ Nτ }. {Nσ,τ : σ, τ ∈ <ω 2} is a basis for the topology on 2 (ω 2). Nσ,τ,ρ is defined similarly for 3 (ω 2). Definition 3.2.3. Let n ∈ ω and σ : n → <ω 2. Let Nσ = {x ∈ ω (ω 2) : (∀k < n)(σ(k) ⊆ x(k))}. {Nσ : σ ∈ <ω (<ω 2)} is a basis for the topology on ω (ω 2). Let σ, τ : n → <ω 2. Let Nσ,τ = {(x, y) ∈ 2 (ω (ω 2)) : x ∈ Nσ ∧ y ∈ Nτ }. {Nσ,τ : σ, τ ∈ <ω (<ω 2) ∧ |σ| = |τ|} is a basis for the topology on 2 (ω (ω 2)). Definition 3.2.4. Let A and B be two sets. A ≈ B denotes that there is a bijection between A and B. Often this paper will consider settings where the full axiom of choice may fail. In such contexts, not all sets have a cardinal, i.e. is in bijection with an ordinal. Similarity of size is more appropriately 25 given by the existence of bijections. Recall the following method of producing bijections between sets which is provable in ZF: Fact 3.2.5. (Cantor-Schröder-Bernstein) (ZF) Let X and Y be two sets. Suppose there are injections Φ : X → Y and Ψ : Y → X. Then there is a bijection Λ : X → Y . Definition 3.2.6. Let X and Y be sets. X Y is the set of functions from X to Y . P(X) is the power set of X. Let n ∈ ω. Define P n (X) = {F ∈ P(X) : F ≈ n} Ø P <ω (X) = P n (X) n∈ω Let E be an equivalence relation on a set X. Let n ∈ ω. Define [X]nE = {(x0, ..., xn−1 ) ∈ n X : (∀i, j < n)(i , j ⇒ ¬(xi E x j ))} Ø [X]nE [X]<ω = E n∈ω Definition 3.2.7. Let X be a set and n ∈ ω. A set X has the n-Jónsson property if and only for all functions f : [X]=n → X, there is some Y ⊆ X so that Y ≈ X and f [[Y ]=n ] , X. X has the Jónsson property if and only if for all f : [X]=<ω → X, there is some Y ⊆ X so that Y ≈ X and f [[Y ]=<ω ] , X. A set X has the classical n-Jónsson property (or classical Jónsson property) if and only the above holds with [X]=n (or [X]=<ω ) replaced with P n (X) (or P <ω (X), respectively). If X is a wellordered set, one can identify a finite set F ⊆ X with the increasing enumeration of its elements. Such a presentation is helpful for defining useful functions on P n (X). In the absence of choice, it is easier to define functions when one considers order tuples from [X]=n . For this reason, the paper mostly concerns the Jónsson property as defined above rather than the classical Jónsson property, although the classical version will be discussed in Section 3.10. ω Definition 3.2.8. Let X be a set. [X]ω = and P (X) are defined as above (with ω in place of n ∈ ω). Let N ∈ ω ∪ {ω}. A N-Jónsson function for X is a function Φ : [X]=N → X so that for any Y ⊆ X with Y ≈ X, Φ[[Y ]=N ] = X. A classical N-Jónsson function for X is defined in the same way as the above with P N (X) instead of [X]=N . 26 With the axiom of choice, [5] showed that every set has an ω-Jónsson map. The existence of ω-Jónsson maps for certain cardinals is where Kunen’s original proof of the Kunen inconsistency used the axiom of choice. Note that for N ∈ ω ∪ {ω}, a counterexample to the N-Jónsson property for some set is equivalent to the existence of an n-Jónsson function for that set. Definition 3.2.9. Let X and Y be Polish spaces. Let E and F be equivalence relations on X and Y , respectively. A ∆11 reduction between X and Y is a ∆11 function Φ : X → Y such that for all a, b ∈ X, a E b if and only if Φ(a) F Φ(b). This situation is denoted by E ≤∆1 F. Define E ≡∆1 F if and only if E ≤∆1 F and F ≤∆1 E. 1 1 1 1 Definition 3.2.10. Let E be an equivalence relation on a set X. If x ∈ X, then [x]E = {y ∈ X : y E x} is the E-class of x. Let A ⊆ X. [A]E = {y ∈ X : (∃x ∈ A)(x E y)} is the E-saturation of A. Definition 3.2.11. Let X be a Polish space and E be an equivalence relation on X. Let n ∈ ω. X has the n-Mycielski property if and only if for every C ⊆ n X which is comeager in n X, there is a ∆11 set A ⊆ X so that E ≡∆1 E  A and [A]nE ⊆ C. 1 E has the Mycielski property if and only if for all sequences (Cn : n ∈ ω) such that for all n ∈ ω, Cn ⊆ n X is comeager in n X, there is a some set A ⊆ X so that E ≡∆1 E  A and for all n ∈ ω, 1 [A]nE ⊆ Cn . The Mycielski property of equivalence relations comes from the following eponymous result: Fact 3.2.12. (Mycielski) Let (Cn : n ∈ ω) be a sequence such that for each n ∈ ω, Cn ⊆ n (ω 2) is a comeager subset of n (ω 2). Then there is a perfect set P ⊆ ω 2 so that for all n ∈ ω, [P]=n ⊆ Cn . Definition 3.2.13. Let E be an equivalence relation on a Polish space X. Let n ∈ ω. E has the n-continuity property if and only if for every function f : n X → X, there is some ∆11 A ⊆ X so that E ≡∆1 E  A and f  [A]nE is continuous. 1 Fact 3.2.14. Let E be an equivalence relation on a Polish X which has the n-Mycielski property. Then for every function f : n X → X with the property of Baire (i.e. f −1 [U] has the Baire property for every open set U), there is some ∆11 A ⊆ X with E ≡∆1 E  A so that f  [A]nE is continuous. 1 Hence if every set has the Baire property, then E has the n-continuity property. Proof. Let f : n X → X. Since f is Baire measurable, there is some C ⊆ n X so that f  C is continuous. By the n-Mycielski property, there is some A ⊆ X with E ≡∆1 E  A so that [A]nE ⊆ C. 1 f  [A]nE is continuous.  27 In place of the axiom of choice, the paper will often use the axiom of determinacy. The following is a quick description of determinacy: Definition 3.2.15. Let X be a set. Let A ⊆ ω X. The game G A is defined as follows: Player 1 plays ai ∈ X, and player 2 plays bi ∈ X for each i ∈ ω. At turn 2i, player 1 plays ai , and at turn 2i + 1, player 2 plays bi . Let f ∈ ω X be defined by f (2i) = ai and f (2i + 1) = bi . Player 1 wins this play of G A if and only if f ∈ A. Player 2 wins otherwise. A winning strategy for player 1 is a function τ : <ω X → X so that for any (bi : i ∈ ω) if (ai : i ∈ ω) is defined recursive by a0 = τ(∅) and an+1 = τ(a0 ...an bn ), then player 1 wins the resulting play of G A. One may define a winning strategy for player 2 similarly. The Axiom of Determinacy for X, denoted AD X , is the statement that for all A ⊆ ω X, G A has a winning strategy for some player. AD refers to AD2 or equivalently ADω . ADR will also be used. Note that ADR often will refer to ADω 2 or ADω ω . AD implies classical regularity properties for sets of reals: Every set of reals has the Baire property and is Lebesgue measurable. Every uncountable set of reals has a perfect subset. Every function on the reals is continuous on a comeager set. Uniformization, however, is more subtle: Definition 3.2.16. Let R ⊆ ω 2 × ω 2. Let R x = {y : (x, y) ∈ R}. Suppose for all x ∈ ω 2, R x , ∅. R is uniformizable if and only if there is some function f : ω 2 → ω 2 so that for all x ∈ ω 2, (x, f (x)) ∈ R. Such a function f is called a uniformization of R. Fact 3.2.17. (ZF + ADR ) Every relation is uniformizable. Proof. Suppose R ⊆ ω 2 × ω 2 with the property that for all x, R x , ∅. Consider the two-step game where player 1 plays a ∈ ω 2 and player 2 responds with b ∈ ω 2. Player 2 wins if and only if (a, b) ∈ R. Clearly player 1 cannot have a winning strategy. Any winning strategy for player 2 yields a uniformization of R.  Woodin has shown that if there is a measurable cardinal with infinitely many Woodin cardinals below it, then L(R) |= AD. Solovay showed in [27] Lemma 2.2 and Corollary 2.4 that the relation R(x, y) if and only y is not ordinal definable from x is not uniformizable in L(R). Hence ADR is stronger than than AD. AD is not capable of proving full uniformization. 28 Definition 3.2.18. Let E be an equivalence relation on ω 2 and n ∈ ω. Let f : (ω 2/E)n → ω 2/ E. A lift of f is a function F : n (ω 2) → ω 2 with the property that for all (x0, ..., xn ) ∈ n (ω 2), [F(x0, ..., xn−1 )]E = f ([x0 ]E , ..., [xn−1 ]E ). Fact 3.2.19. Let E be an equivalence relation on ω 2 and n ∈ ω. Let f : n (ω 2/E) → ω 2/E. Define R f (x0, ..., xn−1, y) ⇔ y ∈ f ([x0 ]E , ..., [xn−1 ]E ). If F is a uniformization of R f (with respect to the last variable), then F is a lift of f . Under ADR , every such function has a lift. Many natural models of AD such as L(R) are not models of ADR . However, functions on quotients of equivalence relations with all classes countable are still uniformizable: AD+ is a strengthening of AD which holds in all known models of AD (in particular L(R)). See [28] Definition 9.6 for the definition of AD+ . It is open whether AD and AD+ are equivalent. Also ADR + DC implies AD+ , and it is open whether this holds without DC. Fact 3.2.20. (Countable Section Uniformization) (Woodin) (AD+ ) Let R ⊆ ω 2× ω 2 have the property that for all x ∈ ω 2, R x is countable. Then R is uniformizable. Proof. See [20] Theorem 3.2 for a proof.  Fact 3.2.21. (AD+ ) Let E be an equivalence relation on ω 2 with all classes countable. Let n ∈ ω and f : n (ω 2/E) → ω 2/E. Then f has a lift. For the results of this paper, we replace all results that require lifts by lifts on some comeager set. The benefit is that such lifts follows from comeager uniformization which is provable in just ZF + AD. Fact 3.2.22. (Comeager Unformization) (ZF + AD) Let R ⊆ ω 2 × ω 2 be a relation such that (∀x)(∃y)R(x, y), then there is a comeager C ⊆ ω 2 and some function f : C → ω 2 so that (∀x ∈ C)R(x, f (x)). By shrinking to an appropriate comeager set, one can assume that the uniformizing function is also continuous. Often, in order to use the techniques of forcing over countable elementary structures, we will need to augment the axiom of determinacy by dependent choice (DC). Kechris [16] proved that AD and 29 AD + DC have the same consistency strength by showing if L(R) |= AD, then L(R) |= DC. However, Solovay [27] showed that ADR + DC has strictly stronger consistency strength than ADR . If one is ultimately interested in functions F : n (ω 2) → ω 2 which are lifts of some function f : n (ω 2/E) → ω 2/E only in order to infer information about f , then the demand in the Mycielski property that one considers tuples coming from a single set A ⊆ ω 2 such that E ≡∆1 E  A seems 1 restrictive. If one ultimately will collapse back to the quotient, two sets A and B with the same E-saturation should work equally well. These parameters motivate the following concepts: Definition 3.2.23. Let n ∈ ω and E be an equivalence relation on some Polish space X. Let (Ai : i < n) be a sequence of subsets of X. Define E Ö Ai = {(x0, ..., xn−1 ) : (∀i)(xi ∈ Ai ) ∧ (∀i , j)(¬(xi E x j ))}. i<n This set will sometimes be denoted A0 ×E ... ×E An−1 . Definition 3.2.24. Let E be an equivalence relation on a Polish space X. Let n ∈ ω. E has the n-weak-Mycielski property if and only if for any C ⊆ n X which is comeager in n X, there are ∆11 ÎE Ai ⊆ C. sets (Ai : i < n) with the property that for each i < n, E ≡∆1 E  Ai and i<n 1 3.3 ω 2 Has the Jónsson Property This section will give a forcing style proof of Holshouser and Jackson’s result that ω 2 has the Jónsson property under some determinacy assumptions. The Jónsson property for ω 2 will follow from a flexible fusion argument for Sacks forcing and the fact that under determinacy assumptions, every function is definable (on some perfect set) with certain absoluteness properties between countable structures and the real universe. Continuous functions will satisfy this property. Thus, the Baire property and the Mycielski property for = suffice to show that every function has such a definition on some perfect set. Absoluteness phenomena that occur under AD+ can also induce this definability. Later, we will see that the Mycielski property fails for all the other simple equivalence relations considered; the hope is that such a definability and absoluteness approach could establish Jónsson type properties without the Mycielski property. In the following, the fusion argument is essential for the combinatorics of the forcing argument. It is unclear what the relation is between fusion (or properness), the Mycielski property, and the Jónsson property. Definition 3.3.1. A tree p on 2 is a subset of <ω 2 so that if s ∈ p and t ⊆ s, then t ∈ p. p is a perfect tree if and only if for all s ∈ p, there is a t ⊇ s so that tˆ0, tˆ1 ∈ p. 30 Let S denote the collection of all perfect trees on 2, ≤S =⊆, and 1S = <ω 2. (S, ≤S, 1S ) is Sacks forcing, denoted by just S. Let p ∈ S. s ∈ p is a split node if and only if sˆ0, sˆ1 ∈ p. s ∈ p is a split of p if and only if s  (|s| − 1) is a split node of p. For n ∈ ω, s is a n-split of p if and only if s is a ⊆-minimal element of p with exactly n-many proper initial segments which are split nodes of p. Let splitn (p) denote the set of n-splits of p. Note that |splitn (p)| = 2n and split0 (p) = {∅}. If p, q ∈ S, define p ≤Sn q if and only if p ≤S q and splitn (p) = splitn (q). If p ∈ S and s ∈ p, then define ps = {t ∈ p : t ⊆ s ∨ s ⊆ t}. Let p ∈ S. Let Λ be defined as follows: (i) Λ(p, ∅) = ∅. (ii) Suppose Λ(p, s) has been defined for all s ∈ n 2. Fix an s ∈ n 2 and i ∈ 2. Let t ⊇ Λ(p, s) be the minimal split node of p extending Λ(p, s). Let Λ(p, sˆi) = tˆi. Let Ξ(p, s) = pΛ(p,s) . For n ∈ ω, let Sn denote the n-fold product of S. If p ∈ S, then let pn ∈ Sn be defined so that for all i < n, pn (n) = p. n,m Let n ∈ ω and m < n. There is an Sn -name xgen which names the mth Sacks-generic real coming from an Sn -generic filter. Fact 3.3.2. A fusion sequence is a sequence hpn : n ∈ ωi in S so that for all n ∈ ω, pn+1 ≤Sn pn . Ñ The fusion of this sequence is pω = n∈ω pn . pω is a condition in S. Lemma 3.3.3. Let f : [ω 2]=<ω → ω 2. Let fn = f  [ω 2]=n . Suppose there is a countable model M of some sufficiently large fragment of ZF, p ∈ S ∩ M, and a Sn -name τn ∈ M so that pn τn ∈ ω 2 n,0 n,n−1 and whenever Gn ⊆ Sn is Sn -generic over M with pn ∈ Gn , τn [Gn ] = fn (xgen [Gn ], ..., xgen [Gn ]). Then there exists a q ∈ S so that f [[[q]]=<ω ] , ω 2. n : m ∈ ω) be a sequence of dense open subsets of Sn in M so that Proof. For each n ∈ ω, let (Dm n n and if D is a dense open subset of Sn in M, then there is some m so that for all m, Dm+1 ⊆ Dm n ⊆ D. Dm Let z ∈ ω 2 \ (ω 2) M . 31 A fusion sequence hpn : n ∈ ωi with p0 = p will be constructed with the following properties: For all n > 0, m ≤ n, and (σ0, ..., σm−1 ) ∈ m (n 2) so that σi , σj if i , j: (i) (Ξ(pn, σ0 ), ..., Ξ(pn, σm−1 )) ∈ Dnm . (ii) There are some k ∈ ω and i ∈ 2 so that z(k) , i and (Ξ(pn, σ0 ), ..., Ξ(pn, σm−1 )) M ˇ Sm τm ( ǩ) = i. Suppose this fusion sequence hpn : n ∈ ωi could be constructed. Let q be its fusion. Fix m > 0. m Suppose (x0, ..., xm−1 ) ∈ [[q]]=m . Let G(x = {(p0, ..., pm−1 ) ∈ Sm ∩ M : (∀i < m)(xi ∈ [pi ])}. 0,...,xm−1 ) m Note that G(x is a Sm generic filter over M: There is some L so that for all k ≥ L, there are 0,...,xm−1 ) σik ∈ k 2 with the property that for all i < m, xi ∈ Ξ(p k , σik ) and for all i , j, σik , σjk . Then for k )) ∈ G m . (i) asserts that this element belongs to Dm all k ≥ L, (Ξ(p k , σ0k ), ..., Ξ(p k , σm−1 k. (x0,...,xm−1 ) m Hence G(x is Sm -generic over M. 0,...,xm−1 ) m By (ii), τm [G(x ] , z. Also 0,...,xm−1 ) m m,0 m m,m−1 m τm [G(x ] = fm (xgen [G(x ], ..., xgen [G(x ]) = fm (x0, ..., xm−1 ). 0,...,xm−1 ) 0,...,xm−1 ) 0,...,xm−1 ) Hence z < fm [[[q]]=m ]. Thus f [[[q]]=<ω ] , ω 2. The construction of the fusion sequence remains: Let p0 = p. Suppose pn has been constructed with the above properties. For some J ∈ ω, let (σ̄k : k < J) enumerate all tuples of strings (σ0, ..., σm−1 ) where m ≤ n + 1, σi ∈ n+1 2, and if i , j, σi , σj . Next, one constructs a sequence r−1, ..., r J−1 as follows: Let r−1 = pn . Suppose we have constructed rk for k < J − 1 and σ̄k+1 = (σ0, ..., σm−1 ). (Case I) There is some (u0, ..., um−1 ) ≤Sm (Ξ(rk , σ0 ), ..., Ξ(rk , σm−1 )) and c ∈ (ω 2) M so that (u0, ..., um−1 ) M Sm τm = č. m Also as Dn+1 is dense open in Sm , one may choose (u0, ..., um−1 ) satisfying the above and m . Note that since z < M and c ∈ M, there must be some j ∈ ω and (u0, ..., um−1 ) ∈ Dn+1 i ∈ 2 so that c( j) , i and z( j) = i. Now let rk+1 ∈ S be so that for all σ ∈ n+1 2 Ξ(rk+1, σ) =    ui  (∃i)(0 ≤ i ≤ m − 1)(σ = σi )   Ξ(rk , σ)  otherwise (Case II) For all (u0, ..., um−1 ) ≤Sm (Ξ(rk , σ0 ), ..., Ξ(rk , σm−1 )), (u0, ..., um−1 ) 32 M Sm τm < M. . Hence there are (u0, ..., um−1 ) ≤Sm (Ξ(rk , σ0 ), ..., Ξ(rk , σm−1 )), (v0, ..., vm−1 ) ≤Sm (Ξ(rk , σ0 ), ..., Ξ(rk , σm−1 )), and j ∈ ω so that ˇ = 0̌ (u0, ..., um−1 ) Mm τm ( j) S (v0, ..., vm−1 ) m ˇ Sm τm ( j) = 1̌ m is dense open, one may Without loss of generality, suppose that z( j) = 1. Moreover since Dn+1 m . Define r assume that (u0, ..., um−1 ) ∈ Dn+1 k+1 in the same way as in Case I. Finally, let pn+1 = r J−1 . pn+1 ≤Sn pn and condition (i) and (ii) are satisfied. This completes the construction.  Fact 3.3.4. (ZF + DC) Let p ∈ S and n ∈ ω. If fn : [[p]]=n → ω 2 is continuous, then there is a countable elementary M ≺ VΞ (for Ξ some sufficiently large cardinal) and a name τn so that M, τn , and p satisfy the conditions of Lemma 3.3.3. Proof. If fn is continuous, then fn has Σ11 and Π11 formulas with parameters from ω 2 defining it. Let M ≺ VΞ be a countable elementary substructure containing p and all the parameters used to define fn . (This requires DC.) Using Mostowski’s absoluteness, fn (as defined by this formula) continues to define a function in the forcing extension M[G], where G ⊆ Sn is Sn -generic over M. So there is n,0 n,n−1 some Sn -name τn ∈ M so that pn SMn τn = fn (xgen , ..., xgen ). Suppose Gn ⊆ Sn is Sn -generic over n,0 n,n−1 M and contains pn . Then M[Gn ] |= τn [Gn ] = fn (xgen [Gn ], ..., xgen [Gn ]). Let π : M[Gn ] → N be the Mostowski collapse of M[Gn ]. Since reals are not moved by the Mostowski collapse map π, π( fn ) is still defined by the same formula. So n,0 n,n−1 n,0 n,n−1 N |= π(τn [Gn ]) = τn [Gn ] = π( fn (xgen [Gn ], ..., xgen [Gn ])) = fn (xgen [Gn ], ..., xgen [Gn ]). n,0 n,n−1 Then applying Mostowski absoluteness, τn [Gn ] = fn (xgen [Gn ], ..., xgen [Gn ]).  Theorem 3.3.5. (Holshouser-Jackson) Assume ZF + DC and all sets of reals have the Baire property. Then ω 2 has the Jónsson property. Proof. Let f : [ω 2]=<ω → ω 2. Let fn : [R]=n → R be defined by fn = f  [ω 2]=n . Since all sets of reals have the Baire property, there are comeager subsets Cn ⊆ n (ω 2) so that fn  Cn is continuous. By the theorem of Mycielski (i.e. = has the Mycielski property), there is a perfect tree p so that [[p]]=n ⊆ Cn for all n ∈ ω. Hence for all n ∈ ω, fn  [[p]]=n is a continuous function. Then Fact 3.3.4 and Lemma 3.3.3 imply that ω 2 has the Jónsson property.  33 Remark 3.3.6. As a consequence of phrasing this argument using forcing, one needed to introduce countable elementary substructures. DC is necessary in general to obtain useful countable elementary substructures. One can use a more direct topological argument to avoid DC. 3.4 ω-Jónsson Function for ω 2 Let ACRω be the axiom of countable choice for ω 2: If E is a countable set of nonempty subsets of ω 2, then E has a choice function. Note that ZF + AD implies ACRω . Using the axiom of choice, every set has an ω-Jónsson function. However, just ZF + ACRω implies there is a ∆11 classical ω-Jónsson function for ω 2. In fact, a slightly stronger statement holds: Theorem 3.4.1. (ZF + ACRω ) There is a ∆11 function Φ : P ω (ω 2) → ω 2 so that if B ⊆ ω 2 is uncountable, then Φ[P ω (B)] = ω 2. There is a ∆11 classical ω-Jónsson function for ω 2. Proof. Let A be a countable subset of ω 2. Let a∅A be the longest element of <ω 2 which is an initial segment of every element of A. A is undefined for i ∈ 2. If a A is defined, let a A be the longest element If aσA is undefined, then aσˆi σ σˆi A is of <ω 2 which is an initial segment of every element of A ∩ NaσA ˆi , if it exists. Otherwise aσˆi undefined. (Note this happens if and only if A ∩ Naσ ˆi is a singleton.) For A ∈ P ω (ω 2), let Ψ(A) be the collection of σ ∈ <ω 2 so that aσA is defined. Ψ(A) is an infinite tree on 2 with possibly dead nodes and is not perfect. Ψ is a ∆11 function. Using some recursive coding, let X be the collection of reals coding infinite binary trees (which may have dead branches). X is an uncountable Π10 set. Let T ∈ X. Let T̂ = {σˆ0̃, σˆ1ˆ0̃ : σ ∈ T }. T̂ ∈ P ω (ω 2). One seeks to show that Ψ(T̂) = T. To see this, the following claim is helpful: If σ ∈ T, then aT̂σ = σ and if σ < T, then aT̂σ is undefined. This claim is proved by induction: ∅ ∈ T so 0̃, 1ˆ0̃ ∈ T̂. aT̂∅ = ∅. Suppose this holds for σ. Suppose σˆi ∈ T. Then σˆiˆ0ˆ0̃ and σˆiˆ1ˆ0̃ are both in T̂. By induction, aT̂σ = σ. The longest string which is an initial segment of every element of T̂ ∩ NaT̂ ˆi = T̂ ∩ Nσˆi is σˆi. This shows aT̂σˆi = σˆi. Suppose σ σˆi < T. Either aT̂σ is undefined or aT̂σ is defined. If aT̂σ is undefined, then aT̂σˆi is undefined. Suppose aT̂σ is defined. By induction, aT̂σ = σ. σ ∈ T implies that σˆ0ˆ0̃ and σˆ1ˆ0̃ are both in T̂. Since σˆi < T, Nσˆi ∩ T̂ = NaT̂ ˆi ∩ T̂ = {σˆiˆ0̃}. aT̂σˆi is undefined. This completes the proof of the claim. σ 34 This shows Φ(T̂) = T. Hence Ψ[P ω (ω 2)] = X. Let Γ : X → ω 2 be a ∆11 bijection. Let Φ = Γ ◦ Ψ. Let B be an uncountable subset of ω 2. Then there is an uncountable C ⊆ B which has no isolated points. One way to see this is to note that using a countable basis, the Cantor-Bendixson process must stop at a countable ordinal. The fixed point starting from B would be an uncountable set with no isolated points. Fix such a set C. Let E = {Nσ ∩ C : σ ∈ <ω 2 ∧ Nσ ∩ C , ∅}. E is a countable set. Using ACRω , let Λ be a choice function for E. Let T be any infinite binary tree on 2. The following objects will be constructed: (I) cs ∈ C for each s ∈ <ω 2. (II) A strictly increasing sequence (ki : i ∈ {−1} ∪ ω) of integers. For each n ∈ ω, let An = {cs : s ∈ n 2}. The objects above will satisfy the following properties: A (i) If s ∈ T, then as |s |+1 is defined and has length less than k |s| . If s < T, then A|s|+1 ∩ Ncs k |s | = {cs }. A (ii) If s ∈ T, then csˆi ⊇ as |s |+1 ˆi for each i ∈ 2. (iii) For all m, if n > m, then {x  k m : x ∈ Am } = {x  k m : x ∈ An }. Let c∅ be any element of C. Let k −1 = 0. Let A0 = {c∅ }. Suppose for m ∈ ω, cs ∈ C for all s ∈ m 2 and k m−1 have been defined. Suppose properties (i) to (iii) hold for t ∈ <ω 2 with |t| < m. Let s ∈ T ∩ m 2. Since cs ∈ C and C has no isolated points, there is some ms > k m−1 so that N(cs ms )ˆ(1−cs (ms )) ∩ C , ∅. Let csˆcs (ms ) = cs and let csˆ(1−cs (ms )) = Λ(N(cs ms )ˆ(1−cs (ms )) ). If s < T, then let csˆi = cs for each i ∈ 2. Let k m = sup{ms + 1 : s ∈ m 2 ∩ T }. Since for each s ∈ T ∩ m 2, ms > k m−1 , (i) to (iii) still hold for t with |t| < m. Let s ∈ T. Using the Am induction hypothesis for (ii) on s  m − 1, one has that cs ⊇ asm−1 ˆs(m − 1). csˆ0 and csˆ1 extend Am+1 Am+1 Am asm−1ˆs(m − 1). This shows that as is defined. In fact, as = cs  ms . If s < T, (i) is clear m from the construction. Properties (i) to (iii) hold for s ∈ 2. Ð Let A = n∈ω An . Note that A is countably infinite and A ⊆ C ⊆ B. From the above properties, A if s ∈ T, then asA is defined and in fact equal to as |s |+1 . Suppose s < T. Let t ⊆ s be maximal A with t ∈ T. The above properties imply that A ∩ NatAˆs(|t|) = {ctˆs(|t|) } = {cs }. Hence atˆs(|t|) is not defined and hence asA is not defined. Thus T = Ψ(A). This shows that Φ[P ω (B)] = ω 2. Φ is an ω-Jónsson function for ω 2.  35 Question 3.4.2. Under ZF + ¬ACRω , can there be a classical ω-Jónsson function for ω 2? The first statement of Theorem 3.4.1 may not be true without ACRω : Let Cω denote the finite support product of Cohen forcing C. Let G ⊆ Cω be Cω -generic over L. For each n ∈ ω, let cn be the nth -Cohen generic real naturally added by G. Let A = {cn : n ∈ ω}. Let H = (HOD(A ∪ {A})) L[G] . H is called the Cohen-Halpern-Lévy model. In H, A has no countably infinite subsets. Hence the first statement of Theorem 3.4.1 cannot hold. However A is not in bijection with ω 2. This suggest the following natural question: In H, is there a classical ω-Jónsson function for ω 2? 3.5 The Structure of E0 Definition 3.5.1. E0 is the equivalence relation defined on ω 2 by x E0 y if and only if (∃n)(∀k > n)(x(k) = y(k)). Definition 3.5.2. Let {s, vni : i ∈ 2 ∧ n ∈ ω} ⊆ <ω 2 have the property that for all n ∈ ω and i ∈ 2, hii ⊆ vni and |vn0 | = |vn1 |. σ(|σ|−1) Let ϕ(∅) = s. If σ ∈ <ω 2 and |σ| > 0, then let ϕ(σ) = sˆv0σ(0)ˆ...ˆv|σ|−1 . A perfect tree p is an E0 -tree if and only if there is a sequence {s, vni : i ∈ 2 ∧ n ∈ ω} with the above properties so that p is the ⊆-downward closure of {ϕ(σ) : σ ∈ <ω 2}. Let PE0 be the collection of all perfect E0 trees. If p, q ∈ PE0 , then p ≤PE0 q if and only if p ⊆ q. Let 1PE0 = <ω 2. (PE0, ≤PE0 , 1PE0 ) is forcing with perfect E0 -trees. i,p If p ∈ PE0 , then the notation s p and vn will be used to denote the strings witnessing p is a perfect E0 -tree. Ð Let Φ : ω 2 → [p] be defined by Φ(x) = n∈ω ϕ(x  n), where ϕ is associated with the E0 -tree p as above. Φ is the canonical homeomorphism of ω 2 onto [p], and Φ is a reduction witnessing E0 ≤∆1 E0  [p]. 1 Fact 3.5.3. Suppose B is a Σ11 set so that E0 ≤∆1 E0  B. Then there is an E0 -tree p so that [p] ⊆ B. 1 Proof. This is implicit in [7]. See [29] Lemma 2.3.29 and [13] Theorem 10.8.3.  The weak Mycielski property for E0 considers E0 -products of ∆11 sets A0, ..., An−1 so that E0 ≡∆1 1 E0  Ai and [Ai ]E0 = [A j ]E0 . Showing the failure of the weak Mycielski property requires finding some structure shared by all of the sets A0, ..., An−1 . For instance, are there perfect E0 -trees pi so that [pi ] ⊆ Ai and [[pi ]]E0 = [[p j ]]E0 ? How similar can pi and p j be chosen to be? 36 We will first consider a simpler solution using the σ-additivity of the E0 -ideal, which follows Fact 3.5.3. A stronger result giving more information using effective methods will follow. Fact 3.5.4. For each n ∈ ω, suppose An ⊆ ω 2 is Σ11 and there is no E0 -tree p so that [p] ⊆ An . Ð Then there is no E0 tree p so that [p] ⊆ n∈ω An . Ð Proof. Suppose there is some E0 -tree p so that [p] ⊆ n∈ω An . Let Φ : ω 2 → [p] be the canonical injective reduction witnessing E0 ≤∆1 E0  [p]. For each n ∈ ω, Φ−1 [An ] is a Σ11 set, and 1 −1 −1 ω2 = Ð n∈ω Φ [An ]. There is some m ∈ ω so that Φ [Am ] is nonmeager. Therefore, there is some continuous injective function Ψ : ω 2 → Φ−1 [Am ] which witnesses E0 ≤∆1 E0  Φ−1 [Am ]. 1 Φ ◦ Ψ witnesses E0 ≤∆1 E0  Am . This implies there is some E0 -tree q so that [q] ⊆ Am . 1 Contradiction.  Definition 3.5.5. If x ∈ ω 2 and n ∈ ω, let x≥n ∈ ω 2 be defined by x≥n (k) = x(n + k). If A ⊆ ω 2, then let (A)≥n = {z : (∃x ∈ A)(z = x≥n )}. Definition 3.5.6. Let s ∈ <ω 2. Define switchs : ω 2 → ω 2 by switchs (x)(n) =    s(n)  n < |s|   x(n)  otherwise . Also if σ ∈ <ω 2, switchs (σ) ∈ |σ| 2 is defined as above just for n < |σ|. Theorem 3.5.7. Let n ∈ ω. For k < n, let Ak ⊆ ω 2 be Σ11 so that E0 ≤∆1 E0  Ak and for all 1 k < n − 1, [Ak ]E0 ⊆ [Ak+1 ]E0 . Then there exists E0 -trees p k so that [p k ] ⊆ Ak and for all a, b < n, i,p i,p |s pa | = |s pb |, and vm a = vm b for all m ∈ ω and i ∈ 2. Proof. For each c ∈ ω, let ( Ec = (x0, ..., xn−1 ) ∈ ) Ö Ak : (∀i, j < n)((xi )≥c = (x j )≥c ) . k<n For each c ∈ ω, Ec is a Σ11 set. For k < n, let π k : n (ω 2) → ω 2 be the projection map onto the Ð k th coordinate. π0 [Ec ] is Σ11 for each c ∈ ω. Since [Ai ]E0 ⊆ [Ai+1 ]E0 , c∈ω π0 [Ec ] = A0 . By Fact 3.5.4, there is some m ∈ ω so that π0 [Em ] contains the body of an E0 -tree q0 . By choosing an appropriate subtree, one may assume that |s q0 | > m. Let s0 = s q0  m. 37 Fix k < n − 1. Suppose the E0 -tree qk and s k ∈ m 2 have been constructed so that s k ⊆ s qk and [qk ] ⊆ π k [Em ]. Then " # Ø switchs [[qk ]] ∩ π k+1 [Em ] = [[qk ]]E0 . s∈ m 2 E0 By Fact 3.5.4, there is some s k+1 sk+1 [[qk ]] ∩ π k+1 [Em ] contains an E0 -tree. Let qk+1 be such an E0 -tree. Note that switchsk [qk+1 ] is an E0 -subtree of qk . ∈ m 2 so that switch For i < n, let pi = switchsi [qn−1 ]. Note that [pi ] ⊆ πi [Em ] ⊆ Ai .  The rest of this section will prove a result that implies Theorem 3.5.7 using an effective definability condition. We will use the methods from [13] Theorem 10.8.3 to simultaneously produce E0 -trees, which are very similar to each other, through several sets. Definition 3.5.8. Let z ∈ ω 2. Let Pz be the forcing of nonempty Σ11 (z) sets ordered by inclusion with largest element Pz = ω 2. Pz is z-Gandy-Harrington forcing. Fact 3.5.9. There is a z-recursive (in a suitable sense) collection D = {Dn : n ∈ ω} of dense open Ñ subsets of Pz so that if G ⊆ Pz is generic for D, then G , ∅. Proof. See [13] Theorem 2.10.4.  Fact 3.5.10. Let z ∈ ω 2. There is a Π11 (z) set D ⊆ ω, Σ11 (z) set P ⊆ ω × ω 2, and Π11 (z) set Q ⊆ ω × ω 2 with the following properties: (i) For all e ∈ D, P e = Q e , where if X ⊆ ω × ω 2, then X e = {x ∈ ω 2 : (e, x) ∈ X }. (ii) If X ⊆ ω 2 is ∆11 (z), then there is some e ∈ D so that X = P e = Q e . Definition 3.5.11. Let z ∈ ω 2. Let Sz be the union of all ∆11 (z) sets C so that for all x, y ∈ C, ¬(x E0 y). Let Hz = ω 2 \ Sz . Fact 3.5.12. Let z ∈ ω 2. Sz is Π11 (z). Hz is Σ11 (z). If X ∩ Hz , ∅ and X is Σ11 (z), then there exists x, y ∈ X with x , y and x E0 y. Hz is E0 -saturated. Proof. Let D, P, and Q be the sets from Fact 3.5.10. Note that x ∈ Sz ⇔ (∃e)(e ∈ D ∧ x ∈ Q e ∧ (∀ f , g)(( f , g ∧ f , g ∈ P e ) ⇒ ¬( f E0 g))). Sz is Π11 (z). Hence Hz is Σ11 (z). 38 Let A be the collection of all Σ11 (z) subsets of ω 2 whose elements are pairwise E0 -inequivalent. Let U ⊆ ω × ω 2 be a universal Σ11 (z) set. {e : U e ∈ A} = {e : (∀ f , g)(( f , g ∈ U e ∧ f , g) ⇒ ¬( f E0 g))} The above is a Π11 (z) set. So A is a collection of Σ11 (z) sets which is Π11 (z) in the codes. By Σ11 (z)-reflection (see [13], Theorem 2.7.1), every Σ11 (z) set X whose elements are E0 -inequivalent has a ∆11 (z) set C whose elements are E0 -inequivalent and X ⊆ C. Suppose X is Σ11 (z), X ∩ Hz , ∅, and the elements of X are pairwise E0 -inequivalent. By the previous paragraph, there is some ∆11 (z) set C which also E0 -inequivalent and X ⊆ C. Then X ⊆ Sz . Contradiction. Suppose x ∈ Hz , y < Hz , and x E0 y. Let n ∈ ω be so that x≥n = y≥n . y ∈ Sz implies that there is some ∆11 (z) E0 -inequivalent set X so that y ∈ X. switch xn [X] is a ∆11 (z) E0 -inequivalent set containing x. This contradicts x ∈ Hz . This shows Hz is E0 -saturated.  Lemma 3.5.13. Let z ∈ ω 2 and n, ` ∈ ω. Suppose ( B̂i : i < n) is a collection of nonempty Σ11 (z) sets. Suppose for all i, j < n, ( B̂i )≥` = ( B̂ j )≥` . Let D ⊆ Pz be a dense open subset of the forcing Pz . Then there is a collection (Bi : i < n) of nonempty Σ11 (z) sets so that for all i, j < n, Bi ∈ D, Bi ⊆ B̂i , and (Bi )≥` = (B j )≥` . Proof. For k < n, Σ11 (z) sets {Bik : −1 ≤ k < n ∧ 0 ≤ i < n} will be constructed with the properties that (i) For all i < n, Bii ∈ D. (ii) If −1 ≤ k < n − 1 and 0 ≤ i < n, then Bik+1 ⊆ Bik . (iii) For all −1 ≤ k < n and 0 ≤ i, j ≤ n, (Bik )≥` = (B kj )≥` . Note that this implies that if k ≥ i, then Bik ∈ D. Let Bi−1 = B̂i . (iii) is satisfied. Suppose for −1 ≤ k < n − 1 and 0 ≤ i < n, Bik has been constructed with the desired properties. k+1 , so that B k+1 ⊆ B k Since D is dense open, there is some nonempty Σ11 (z) set, denoted Bk+1 k+1 k+1 and k+1 k+1 k k+1 Bk+1 ∈ D. For 0 ≤ i < n, let Bi = {x ∈ Bi : (∃z)(z ∈ Bk+1 ∧ x≥` = z≥` )}. All the conditions are satisfied. Finally, let Bi = Bin−1 .  39 Theorem 3.5.14. Let z ∈ ω 2 and n ∈ ω. Let (Aa : a < n) be a collection of Σ11 (z) sets so that Ñ a<n [Aa ∩ Hz ]E0 , ∅. Then there are E0 -trees (pa : a ∈ n) so that for all a, b < n, k ∈ ω and i < 2, i,p i,p (i) |s pa | = |s pb | and vk a = vk b (ii) [pa ] ⊆ Aa . Proof. We will construct the following objects: For each a < n, k ∈ ω, i ∈ 2, and t ∈ <ω 2, (a) wta, s a, vki ∈ <ω 2 (b) `k ∈ ω and for all k ∈ ω, `k ≤ mk < `k+1 (c) Σ11 (z) nonempty sets Xta with the following properties (i) For all a < n and t ∈ <ω 2, |wta | = `|t| . For all a < n and k ∈ ω, |s a | = |s b | and |vk0 | = |vk1 |. For all k ∈ ω and i ∈ 2, hii ⊆ vik . For all a < n and t ∈ <ω 2, if |t| = 1, then s a ⊆ wta and if t > 1, then t(|t|−2) s aˆv0t(0)ˆ...ˆv|t|−2 ⊆ wta . (ii) If a ∈ n, t ∈ <ω 2, u ∈ <ω 2, and t ⊆ u, then Xua ⊆ Xta , Xta ⊆ Nwta , and X∅a ⊆ Aa ∩ Hz . (iii) Let D = (Dn : n ∈ ω) be the collection of dense open subset of Pz from Fact 3.5.9. For all t ∈ <ω 2, Xta ∈ D|t| . (iv) For all k < ω, `k < `k+1 . For all k < ω, t, u ∈ k 2, and a, b ∈ n, (Xta )≥`k = (Xub )≥`k . Suppose we can construct the objects with these properties. For a < n, let pa be the E0 -tree given i,p by s pa = s a and vk a = vki . Let Φa : ω 2 → [pa ] be the canonical map associated with the E0 -tree a : k ∈ ω}. pa . For each x ∈ ω 2, let G ax be the Pz -filter generated by the upward closure of {Xxk Ñ a ∈ D . G a is a filter generic for D. By Fact 3.5.9, G ax ∩ D k , ∅ since Xak G ax , ∅. By (i) and k x Ñ (ii), G ax = {Φa (x)}. Thus Φa (x) ∈ X∅a ⊆ Aa ∩ Hz . Therefore, [pa ] ⊆ Aa . Ñ Next, we will describe the construction. Since a<n [Aa ∩ Hz ]E0 , ∅, let (xa : a < n) be elements of ω 2 so that for all a, b < n, xa ∈ Aa ∩ Hz and xa E0 xb . Choose `0 ∈ ω so that for all a, b < n, Ó (xa )≥`0 = (xb )≥`0 . Let w∅a = xa  `0 . Let Z = {r ∈ ω 2 : (∃y0, ..., yn−1 )( a<n ya ∈ Aa ∩ Hz ∧ w∅aˆr = ya )}. Z is a nonempty Σ11 (z) set. Let Ba = {x ∈ Aa ∩ Hz : (∃r)(r ∈ Z ∧ x ⊇ w∅a ∧ x≥`0 = r)}. For each a < n, Ba is a nonempty Σ11 (z) set. Note that for all a, b < n, (Ba )≥`0 = (Bb )≥`0 . Applying Lemma 3.5.13, find sets (X∅a : a ∈ ω) so that X∅a ⊆ Ba and X∅a ∈ D0 . Suppose Xta has been constructed for a < n and t ∈ k 2. X00k ⊆ Hz is nonempty and Σ11 (z). By Fact 3.5.12, there are x, y ∈ X00k so that x , y and x E0 y. By (i) and (ii), x  `k = y  `k . Therefore, 40 there is some `k+1 > `k so that x≥`k+1 = y≥`k+1 . Let mk be smallest m so that `k ≤ m < `k+1 and x(m) , y(m). Without loss of generality, suppose that x(mk ) = 0 and y(mk ) = 1. For i ∈ 2, let a = switch a w 0 . w00k ˆ0 = x  `k+1 and w00k ˆ1 = y  `k+1 . For a ∈ n and t ∈ <ω 2, let wtˆi wt 0k ˆi Í 0 i a  m . If k > 0, then let L = |s 0 | + If k = 0, then let s a = wh0i 0 k 0≤ j≤k−1 |v j |. Let v k be the string of length mk − L k defined by vki ( j) = w00k ˆi (L k + j). Let Z = {z ∈ ω 2 : (∃x, y)(x, y ∈ X00n ∧ w0k ˆ0 ⊆ x ∧ w0k ˆ1 ⊆ y ∧ z = x≥`k+1 = y≥`k+1 )}. Z is a nonempty Σ11 (z). For t ∈ k+1 2 and a < n, let Bta = {x ∈ Xtk : (∃z)(z ∈ Z ∧ x = wtaˆz)}. Bta is a nonempty Σ11 (z) set and (Bta )≥`k+1 = (Bub )≥`k+1 for all a, b ∈ n and t, u ∈ k+1 2. Apply Lemma 3.5.13 to get Xta ⊆ Bta so that Xta ∈ D k+1 and (Xta )≥`k+1 = (Xub )≥`k+1 . This completes the construction.  3.6 ω 2/E Has the 2-Jónsson Property 0 Theorem 3.6.1. (Holshouser-Jackson) E0 has the 2-Mycielski property. One can prove this by producing an E0 -tree p using an E0 -tree fusion argument to ensure that [[p]]2E0 meets a fixed countable sequence of dense (topologically) open subsets of 2 (ω 2). The fusion argument is quite similar to the fusion argument used in the forcing style proof of the 2-Jónsson property for ω 2/E0 in this section. By Theorem 3.5.7, if (Aa : a < n) is a sequence of Σ11 sets so that [Aa ]E0 = [Ab ]E0 for all a, b < n, then there is a sequence of E0 -trees (pa : a ∈ n) so that for all a, b < n and i < 2, |s pa | = |s pb | and p p vi a = vi b . This motivates the definition of the following forcings: Definition 3.6.2. Let n > 0, let b PnE0 be the collection of n-tuples of E0 -trees (p0, ..., pn−1 ) so that p p for all a, b < n and i < 2, |s pa | = |s pb | and vi a = vi b . Let ≤bPn be coordinatewise ≤PE0 . Let E0 PnE0, ≤bPn , 1bPn ) is forcing with n E0 -trees with the same E0 -saturation. 1bPn = (1PE0 , ..., 1PE0 ). (b E0 E0 E0 0 and x 1 be the b Let xgen P2E0 names for the left and right generic real added by a generic filter for gen b P2E0 . Definition 3.6.3. If p, q ∈ PE0 , then let p ≤PnE q be defined in the same way as p ≤Sn q, when p and 0 q are considered as conditions in Sacks forcing S. Let ≤bn2 be the coordinate-wise ordering using ≤PnE . PE 0 0 A sequence hpn : n ∈ ωi of conditions of PE0 is a fusion sequence if and only if pn+1 ≤PnE pn for 0 all n ∈ ω. Similarly, a sequence h(pn, qn ) : n ∈ ωi of conditions in b P2 is a fusion sequence if and E0 only if (pn+1, qn+1 ) ≤bn2 (pn, qn ) for all n ∈ ω. PE 0 41 Suppose p ∈ PE0 . Let n ∈ ω with n > 0. Let u, v ∈ n 2 with u(n−1) , v(n−1). Suppose (p0, q0) ∈ b P2E0 with the property that p0 ≤PE0 Ξ(p, u) and q0 ≤PE0 Ξ(p, v). Let A = {s ∈ n 2 : s(n − 1) = u(n − 1)} (u,v) and B = {s ∈ n 2 : s(n − 1) = v(n − 1)}. Then define prune(p 0,q 0 ) (p) ∈ P E0 by Ø (u,v) prune(p0,q 0) (p) = switchsΞ(p,t) (p0) ∪ t∈A Ø switchsΞ(p,t) (q0) t∈B Suppose (p, q) ∈ b P2E0 . Let n ∈ ω, n > 0, and u, v ∈ n 2 so that u(n − 1) , v(n − 1). Let (u,v) (p0, q0) ≤bPn (p, q) so that p0 ≤PE0 Ξ(p, u) and q0 ≤PE0 Ξ(q, v). Define 2prune(p 0,q 0 ) (p, q) by E0 (u,v) 2prune(p0,q 0) (p, q) =  (u,v) (u,v) prune(p0,switch p (q 0)) (p), prune(switch q (p0),q 0) (q) s s  Perhaps more concretely: Let A = {s ∈ n 2 : s(n − 1) = u(n − 1)} and B = {s ∈ n 2 : s(n − 1) = v(n − 1)}. Ø  Ø Ø Ø (u,v) 2prune(p0,q 0) (p, q) = switchsΞ(p,t) (p0)∪ switchsΞ(p,t) (q0), switchsΞ(q,t) (p0)∪ switchsΞ(q,t) (q0) t∈A t∈B t∈A t∈B (u,v) Fact 3.6.4. Suppose (p, q), (p0, q0), n, u, and v are as in Definition 3.6.3. Then 2prune(p 0,q 0 ) (p, q) ∈ x p y q b P2 and if 2prune(u,v) 0 0 (p, q) = (x, y), then s = s and s = s . (p ,q ) E0 If |u| = n, then 2prune(u,v) (p, q) ≤bn2 (p, q). (p 0,q 0 ) PE 0 If hpn : n ∈ ωi is a fusion sequence of conditions in PE0 , then pω = and is called the fusion of the fusion sequence. Ñ n∈ω pn is a condition in PE0 Similarly, if h(pn, qn ) : n ∈ ωi is a fusion sequence of conditions in b P2E0 , then (pω, qω ) = Ñ Ñ ( n∈ω pn, n∈ω qn ) is a condition in b P2E0 and is called the fusion of the fusion sequence. Fact 3.6.5. ([14] Proposition 7.6) b P2E0 is a proper forcing. In fact, for any countable model M and (p, q) ∈ (b P2E0 ) M , there is a (p0, q0) ≤bP2 (p, q) which is a (M, b P2E0 )-master condition and [p0] ×E0 [q0] E0 consists of pairs of reals which are b P2E0 -generic over M. Moreover, if τ is a b P2E0 -name in M such that (p, q) M b P2E τ ∈ ω 2, then one can even find (p0, q0) with 0 the above properties and so that either (i) there is some z ∈ ω 2 ∩ M with z E0 0̃ so that (p0, q0) b P2E 0 or (ii) (p0, q0) b P2E ¬(τ E0 0̃). 0 42 τ = ž Proof. Let (Dn : n ∈ ω) be a decreasing sequence of dense open subsets of b P2E0 in M with the property that if D is a dense open subset of b P2E0 in M, then there is some k ∈ ω so that D k ⊆ D. There are two cases: (Note that 0̃ can be replaced by any real in M in the following argument and hence as well in the statement of the fact.) (Case I) There is some (p0, q0) ≤bP2 (p, q) so that (p0, q0) z ∈ (ω 2) M and (p00, q00) so that (p00, q00) M b P2E E0 (p00, q00) ∈ D0 . Let (p0, q0 ) = (p00, q00). M b P2E (Case II) (p, q) (p0, q0 ) = (p0, q0). M b P2E τ E0 0̃. Then there is some 0 τ = ž. Since D0 is dense open in b P2E0 , one may assume 0 ¬(τ E0 0̃). Let (p0, q0) be any condition below (p, q) so that (p0, q0) ∈ D0 . Let 0 In either case, we will construct a fusion sequence ((pn, qn ) : n ∈ ω) of conditions in (b P2E0 ) M with the following property: (i) For all n ∈ ω, (u, v) ∈ n 2 × n 2 so that u(n − 1) , v(n − 1), (Ξ(pn, u), Ξ(qn, v)) ∈ Dn . Suppose this can be done to produce a fusion sequence h(pn, qn ) : n ∈ ωi. Let (p0, q0) be the fusion of this fusion sequence. First, it will be shown that (i) implies that (p0, q0) is a (M, b P2E0 )-master condition with the property that [p0] ×E0 [q0] consists entirely of pairs of reals which are b P2E0 -generic over M. Let D be a dense open subset of b P2E0 with D ∈ M. By the choice of (Dn : n ∈ ω), there is some k ∈ ω so that D k ⊆ D. Let G ⊆ b P2E0 be b P2E0 -generic over M containing (p0, q0). Let K = |Λ(p k , 0 k )|. Let EK be the collection of (p, q) ∈ b P2E0 so that |s p | > K and there is some j with K < j < |s p | so that s p ( j) , s q ( j). EK is dense open. Since G is generic, G ∩ EK , ∅. As G is generic and (p0, q0) ∈ G, one may assume that there is some (p00, q00) ≤bP2 (p0, q0) E0 with (p00, q00) ∈ G ∩ Ek . So there is some J > k and u, v ∈ J 2 with u(J − 1) , v(J − 1) so that (p00, q00) ≤bP2 (Ξ(p0, u), Ξ(q0, v)) ≤bP2 (Ξ(p J, u), Ξ(qJ, v)). Since (p00, q00) ∈ G and G is E0 E0 a filter, (Ξ(p J, u), Ξ(qJ, v)) ∈ G. However (Ξ(p J, u), Ξ(qJ, v)) ∈ D J ⊆ D k by (i). Note that (Ξ(p J, u), Ξ(qJ, v)) ∈ M. Since G was an arbitrary generic containing (p0, q0), it has been shown that (p0, q0) bV2 GÛ ∩ M̌ ∩ Ď , ∅. (p0, q0) is a (M, b P2E0 )-master condition. b P2E0 is proper. PE 0 Now suppose (a, b) ∈ [p0] ×E0 [q0]. Let G(a,b) = {(p, q) ∈ b P2E0 ∩ M : (a, b) ∈ [p] × [q]}. Let D be a dense open set. There is some k so that D k ⊆ D. Since ¬(a E0 b), there is some j > k and some u, v ∈ j 2 with u( j − 1) , v( j − 1) so that Λ(p0, u) ⊆ a and Λ(q0, v) ⊆ b. Then 43 (a, b) ∈ [Ξ(p j , u)] ×E0 [Ξ(q j , v)]. Therefore (Ξ(p j , u), Ξ(q j , v)) ∈ G(a,b) ∩ D k ⊆ G(a,b) ∩ D. G(a,b) is b P2E0 -generic over M. (a, b) is a b P2E0 -generic pair of reals over M. It is clear using the forcing theorems that if Case I holds, then statement (i) of the fact holds and if Case II holds, then statement (ii) of the fact holds. Now it remains to construct the fusion sequence: (p0, q0 ) is already given depending on the case. The rest of the construction is the same for both cases. Suppose (pn, qn ) have been constructed with the desired properties. For some J ∈ ω, let (u0, v0 ), ..., (u J−1, v J−1 ) enumerate all (u, v) ∈ n 2 × n 2 with u(n − 1) , v(n − 1). We will construct sequence of conditions in b P2E0 , (x−1, y−1 ), ..., (x J−1, y J−1 ): Let (x−1, y−1 ) = (pn, qn ). Suppose one has (x k , y k ) for k < J − 1. Since Dn+1 is dense open, find some (p0, q0) ≤bP2 (Ξ(x k , u k ), Ξ(y k , vk )) so that (p0, q0) ∈ Dn+1 . Let k ,vk ) (x k+1, y k+1 ) = 2prune(u (x , y ). (p 0,q 0 ) k k E0  Lemma 3.6.6. Let f : [ω 2]2E0 → ω 2. Suppose there is a countable model M of some sufficiently b P2 large fragment of ZF, (p, q) ∈ b P2E0 ∩ M, and τ ∈ M E0 so that (p, q) M b P2E τ ∈ ω 2 and whenever 0 0 [G], x 1 [G]). Then there is a G⊆b P2E0 is b P2E0 -generic over M with (p, q) ∈ G, then τ[G] = f (xgen gen 0 0 0 0 ω (p , q ) ≤bP2 (p, q) so that [ f [[p ] ×E0 [q ]]]E0 , 2. E0 Proof. Let (p0, q0) ∈ b P2E0 be given by Fact 3.6.5. Then exactly one of the two happens: (i) For all G ⊆ b P2E0 which are generic over M, M[G] |= τ[G] E0 0̃. By absoluteness, τ[G] E0 0̃. (ii) For all G ⊆ b P2E0 which are generic over M, M[G] |= ¬(τ[G] E0 0̃). By absoluteness, ¬(τ[G] E0 0̃). 0 [G Let (a, b) ∈ [p0]×E0 [q0]. By Fact 3.6.5, there is some b P2E0 -generic filter G(a,b) so that xgen (a,b) ] = a 1 and xgen [G(a,b) ] = b. 0 [G 1 If (i) holds, then f (a, b) = f (xgen (a,b) ], xgen [G (a,b) ]) = τ[G (a,b) ] which is E0 related to 0̃. So [ f [[p0] ×E0 [q0]]]E0 = [0̃]E0 , ω 2. 0 [G 1 If (ii) holds, then f (a, b) = f (xgen (a,b) ], xgen [G (a,b) ]) = τ[G (a,b) ], but ¬(τ[G (a,b) ] E0 0̃). So 0̃ < [ f [[p0] ×E0 [q0]]]E0 .  44 Theorem 3.6.7. (Holshouser-Jackson) (ZF + DC + AD) ω 2/E0 has the 2-Jónsson property. Proof. Let F : [ω 2/E0 ]2= → ω 2/E0 . Define the relation R ⊆ ω 2 × ω 2 × ω 2 by R(x, y, z) ⇔ z ∈ F([x]E0, [y]E0 ) AD can prove comeager uniformization (Fact 3.2.22): There is a comeager set C ⊆ [ω 2]2E and 0 a continuous function f : C → ω 2 which uniformizes R on C. Since E0 has the 2-Mycielski property, let p be an E0 -tree so that [[p]]2E0 ⊆ C. So f  [[p]]2E0 is a continuous function. By a similar argument as in Fact 3.3.4, one can find a name τ satisfying Lemma 3.6.6 using the condition (p, p) ∈ b P2E0 . Then Lemma 3.6.6 gives some (p0, q0) ≤bP2 (p, p) so that [ f [[p0] ×E0 [q0]]]E0 is either E0 [0̃]E0 or does not contain 0̃. Since (p0, q0) ∈ b P2E0 , [p0] and [q0] have the same E0 -saturation. Let A = [[p0]]E0 = [[q0]]E0 . Note that E0 ≡∆1 E0  A. Let B = A/E0 . There is a bijection between B 1 and ω 2/E0 . Moreover, F[[B]2= ] is either the singleton {[0̃]E0 } or is missing the element [0̃]E0 . In either case, F[[B]2= ] , ω 2/E0 .  3.7 Partition Properties of ω 2/E0 in Dimension 2 Definition 3.7.1. Let X and Y be sets. Let n ∈ ω. Denote X → (X)Yn to mean that for any function f : P n (X) → Y , there is some Z ⊆ X with Z ≈ X and | f [P n (Z)]| = 1. Denote X 7→ (X)Yn to mean that for any function f : [X]=n → Y , there is some Z ⊆ X with Z ≈ X and | f [[Z]=n ]| = 1. Fact 3.7.2. (Galvin) Assuming ZF and all sets of reals have the Baire property, ω 2 → (ω 2)2n for all n ∈ ω. Note that ω 2 7→ (ω 2)22 is not true: If x, y ∈ ω 2 and x , y, then define d(x, y) = min{n : x(n) , y(n)}. Define f : [ω 2]2= → 2 by f (x, y) = x(d(x, y)). Note that f (x, y) , f (y, x). It is impossible to find a homogeneous set for this coloring of [ω 2]2= . However, under AD, ω 2/E0 7→ (ω 2/E0 )2n does hold: Lemma 3.7.3. Let n > 1. Let F : [ω 2]2E0 → n be a function. Suppose there is a countable model M of some sufficiently large fragment of ZF, (p, q) ∈ b P2E0 ∩ M, and τ is a b P2E0 -name in M so that (p, q) bM2 τ ∈ ň and whenever G ⊆ b P2E0 is b P2E0 -generic over M with (p, q) ∈ G, PE 0 0 1 [G]). Then there is a (p0, q0) ≤ τ[G] = F(xgen [G], xgen b P2 E0 45 (p, q) so that |F[[p0] ×E0 [q0]]| = 1. Proof. Since (p, q) M b P2E 0 τ ∈ n̂, there is some (r, s) ≤bP2 (p, q) and some k ∈ n so that (r, s) E0 M b P2E τ= 0 ǩ. Using Fact 3.6.5, let (p0, q0) ≤bP2 (r, s) be a (M, b P2E0 )-master condition so that [p0]×E0 [q0] consists E0 of pairs of reals which are b P2E0 -generic over M. (p0, q0) works. Using the forcing theorem and the assumptions,  Theorem 3.7.4. (ZF + DC + AD) ω 2/E0 7→ (ω 2/E0 )2n for all n ∈ ω. Proof. Let f : [ω 2/E0 ]2= → n. Define a relation R ⊆ ω 2 × ω 2 × n by R(x, y, k) ⇔ k = f ([x]E0, [y]E0 ). AD can prove comeager uniformization (Fact 3.2.22) so there is some comeager C ⊆ [ω 2]2E and a 0 continuous function F : C → n which uniformizes R on C. Since E0 has the 2-Mycielski property, let p be an E0 -tree so that [[p]]2E0 ⊆ C. F  [[p]]2E0 is a continuous function. As before, one can find a b P2E0 -name τ satisfying Lemma 3.7.3 using the the condition (p, p). Then using Lemma 3.7.3, there is a (r, s) ≤bP2 (p, p) so that |F[[r] ×E0 [s]]| = 1. Let k be the unique element in this set. E0 Let A = [r]E0 = [s]E0 . A/E0 ≈ ω 2/E0 . Suppose x, y ∈ A/E0 and x , y. There is some a, b ∈ A with a ∈ [r], b ∈ [s], a ∈ x, and b ∈ y. F(a, b) = k. Therefore, R(a, b, k). By definition, f (x, y) = k. So | f [[A]2= ]| = 1.  Remark 3.7.5. Before, we mentioned that ω 2 7→ (ω 2)22 is not true. Using the notation from the above proof: Observe that the function F produced in the above proof is E0 -invariant in the sense that if x E0 x 0 and y E0 y0 then F(x, y) = F(x 0, y0). Also since (r, s) ∈ b P2E0 , if a ∈ A, then there is some a0 ∈ [r] and a00 ∈ [s] with a E0 a0 E0 a00. These two facts are essential in proving ω 2/E 7→ (ω 2/E )2 . 0 0 n Later it will be shown that the partition relation for ω 2/E0 will fail in higher dimension. The counterexample is closely connected to the failure of the 3-Jónsson property. 3.8 E0 Does Not Have the 3-Mycielski Property An earlier section mentioned that Holshouser and Jackson proved E0 has the 2-Mycielski property and ω 2/E0 has the 2-Jónsson property. The next few sections will show that dimension 2 is the best possible for these combinatorial properties. This section will show the failure of the 3-Mycielski property and the weak 3-Mycielski property for E0 . Theorem 3.8.1. Let D ⊆ 3 (ω 2) be defined by D = {(x, y, z) ∈ 3 (ω 2) : (∃n)(x(n) , y(n) ∧ x(n) , z(n) ∧ y(n + 1) , z(n + 1))}. 46 D is dense open in 3 (ω 2). If p is an E0 -tree with associated objects {s, vni : i ∈ 2 ∧ n ∈ ω}, ϕ, and Φ as in Definition 3.5.2, then g Φ(110), g Φ(1̃)) < D. (Φ(010), E0 does not have the 3-Mycielski property. Proof. Suppose (x, y, z) ∈ D. Then there is an n ∈ ω so that x(n) , y(n), x(n) , z(n), and y(n + 1) , z(n + 1). Let σ = x  (n + 2), τ = y  (n + 2), and ρ = z  (n + 2). Then Nσ,τ,ρ ⊆ D. D is open. Suppose σ, τ, ρ ∈ <ω 2 and |σ| = |τ| = | ρ| = k. Let σ0 = σˆ00, τ0 = τˆ10, and ρ0 = ρˆ11. Then Nσ 0,τ 0,ρ0 ⊆ Nσ,τ,ρ and Nσ 0,τ 0,ρ0 ⊆ D. D is dense open. Í Let L−1 = |s|. For n ∈ ω, let Ln = |s| + k ≤n |vk0 |. Note that if x(n) = y(n), then for all Ln−1 ≤ k < Ln , Φ(x)(k) = Φ(y)(k). If x(n) , y(n), then Φ(x)(Ln−1 ) , Φ(y)(Ln−1 ), and there may be other Ln−1 ≤ k < Ln so that Φ(x)(k) , Φ(y)(k). g g g Suppose Φ(010)(n) , Φ(110)(n) and Φ(010)(n) , Φ(1̃)(n). Then there exists some k so that L3k−1 ≤ g g + 1) = Φ(1̃)(n + 1). n < L3k . If n , L3k − 1, then n + 1 < L3k . Since 110(3k) = 1 = 1̃(3k), Φ(110)(n g Φ(110), g Φ(1̃)) ∈ D. Suppose Hence if n , L3k − 1, then n cannot be used to witness that (Φ(101), g g g 3k ) = n = L3k − 1. Since 110(3k + 1) = 1 = 1̃(3k + 1), one has that Φ(110)(n + 1) = Φ(110)(L Φ(1̃)(L3k ) = Φ(1̃)(n + 1). If n = L3k − 1, then n does not witness membership in D. Hence g Φ(110), g Φ(1̃)) < D. (Φ(010), g E0 110), g ¬(010 g E0 1̃), and ¬(110 g E0 1̃), (Φ(010), g Φ(110), g Φ(1̃)) ∈ [[p]]3 . Hence Since ¬(010 E0 3 [[p]]E0 * D. Suppose B is ∆11 so that E0  B ≡∆1 E0 . By Fact 3.5.3, there is some E0 -tree p so that [p] ⊆ B. By 1 the above, [B]3E0 * D. E0 does not have the 3-Mycielski property.  The 3-Mycielski property asks for a single ∆11 set A with E0 ≤∆1 E0  A so that [A]3E0 = A×E0 A×E0 A 1 is contained inside a comeager set. If one is interested in combinatorial properties of the quotient ω 2/E , such as the Jónsson property, then one is only concerned with three sets A, B, and C with 0 the same E0 -saturation. With this consideration, the 3-Mycielski property seems unnecessarily restrictive. The weak 3-Mycielski property was defined to remove this demand. One other curiosity of the 3-Mycielski property is that Theorem 3.8.1 allows a (topologically) dense open subset of 3 (ω 2) to be a counterexample to the 3-Mycielski property. Let D ⊆ 3 (ω 2) be any 47 dense open set. There are three strings σ, τ, and γ of the same length so that Nσ,γ,τ ⊆ D. Let p, q, r be any three perfect E0 -trees so that s p = σ, s q = τ, sr = γ, and for all n ∈ ω and i ∈ 2, i,q i,p vn = vn = vni,r . Then [p] ×E0 [q] ×E0 [r] ⊆ D. Also [[p]]E0 = [[q]]E0 = [[r]]E0 . So no dense open set can be a counterexample to the weak 3-Mycielski property. Using the more informative structure theorem for E0 proved above and the argument in Theorem 3.8.1, a comeager subset of 3 (ω 2) is used to show E0 does not have the weak 3-Mycielski property. Theorem 3.8.2. For each k ∈ ω, let D k = {(x, y, z) ∈ 3 (ω 2) : (∃n ≥ k)(x(n) , y(n) ∧ x(n) , z(n) ∧ y(n + 1) , z(n + 1))}. Each D k is dense open. Ñ Let C = n∈ω Dn . C is comeager. For any ∆11 sets A0 , A1 , and A2 such that (I) E0 ≤∆1 E0  A0 , E0 ≤∆1 E0  A1 , E0 ≤∆1 E0  A2 1 1 1 (II) [A0 ]E0 = [A1 ]E0 = [A2 ]E0 , A0 ×E0 A1 ×E0 A2 * C. C does not have the weak 3-Mycielski property. Proof. Let A0, A1, A2 be any three ∆11 sets so that E0 ≤∆1 E0  Ai and have the same E0 -saturation. 1 By Theorem 3.5.7, there are E0 -trees, p, q, and r so that (i) |s p | = |s q | = |sr | = k i,p i,q (ii) vn = vn = vni,r for all n ∈ ω and i ∈ 2 (iii) [p] ⊆ A0 , [q] ⊆ A1 , and [r] ⊆ A2 . Note that the only differences among the three E0 -trees occurs in the stems. Hence by the same argument as in Theorem 3.8.1, [p] ×E0 [q] ×E0 [r] * D k . Hence A0 ×E0 A1 ×E0 A2 * D k . So A0 ×E0 A1 ×E0 A2 * C.  3.9 Surjectivity and Continuity Aspects of E0 As we have seen, based on Holshouser and Jackson’s proof of the Jónsson property for ω 2, the Mycielski property primarily shows that an arbitrary function f on n (ω 2) could be continuous on 48 [[p]]=n for some perfect tree p. Using the continuity of f  [[p]]=n , they show that there is some perfect subtree q ⊆ p so that f [[[q]]=n ] , ω 2. As the previous section shows that E0 does not have the 3-Mycielski property, it is natural to ask if by some other means it is possible to find for any f : 3 (ω 2) → ω 2, some ∆11 set A so that E0 ≤∆1 E0  A and f  [A]3E0 is continuous. Also if the function f  [A]3E0 is continuous, is 1 it possible to find some ∆11 B ⊆ A with E0 ≤∆1 E0  B so that f [[B]3E0 ] does not meet all E0 1 equivalence classes? This section will provide an example to show both of these properties can fail. This example will also be modified in the next section to show the failure of the 3-Jónsson property for E0 . Fact 3.9.1. Let A = {x ∈ ω 3 : (∀n)(x(n) , x(n + 1))}. There is a continuous function P : [ω 2]3E0 → A so that for any E0 -tree p, P[[[p]]3E0 ] = A. Moreover, if p, q, and r are E0 -trees so that i,q i,p |s p | = |s q | = |sr | and for all i ∈ 2 and n ∈ ω, vn = vn = vni,r , then P[[[p]] ×E0 [[q]] ×E0 [[r]]] meets all E0 -classes of A, where the latter E0 is defined on ω 3. Proof. Let (x, y, z) ∈ [ω 2]3E0 . Let L0 be the largest N ∈ ω so that x  N = y  N = z  N. Define    0     a0 = 1     2  x(L0 ) = y(L0 ) x(L0 ) = z(L0 ) . y(L0 ) = z(L0 ) Suppose one has defined Ln and an . Let Ln+1 be the smallest N > Ln so that x(N) , y(N) if an = 0, x(N) , z(N) if an = 1, and y(N) , z(N) if an = 2. Define    0 x(Ln+1 ) = y(Ln+1 )     an+1 = 1 x(Ln+1 ) = z(Ln+1 ) .     2 y(Ln+1 ) = z(Ln+1 )  Define P(x, y, z) ∈ A by P(x, y, z)(n) = an . P is continuous. Now let p be an E0 tree. Let s and vni , for n ∈ ω and i ∈ 2, be associated with the E0 -tree p. Let Φ : ω 2 → [p] be the canonical homeomorphism. Let v ∈ A. Let    (0, 1)     (ai, bi ) = (1, 0)      (1, 1)  49 v(i) = 0 v(i) = 1 . v(i) = 2 Let a, b ∈ ω 2 be defined by a(n) = an and b(n) = bn . Then (Φ(0̃), Φ(a), Φ(b)) ∈ [[p]]3E0 and P((Φ(0̃), Φ(a), Φ(b))) = v. Hence P[[[p]]3E0 ] = A. A similar procedure proves the second statement after noting the three E0 -trees are the same after their stems.  Theorem 3.9.2. There is a continuous Q : [ω 2]3E0 → ω 2 so that for any E0 -tree p, Q[[[p]]3E0 ] = ω 2. Proof. Let t0 = 00, t1 = 01, and t2 = 10. Let Q0 : ω 3 → ω 2 be defined by Q0(x) = t x(0)ˆt x(1)ˆ.... Q0 is a continuous injection. Q0[A] is a perfect subset of ω 2. Q0[A] = [T] for some perfect tree T. Let Q00 : Q0[A] → ω 2 be the continuous bijection naturally induced by T. Let Q = Q00 ◦ Q0 ◦ P. Q has the desired property.  Corollary 3.9.3. There is a ∆11 function K : 3 (ω 2) → ω 2 so that on any Σ11 set A so that E0 ≤∆1 E0  1 A, K[[A]3E0 ] = ω 2. Moreover, for any Σ11 sets A0 , A1 , and A2 so that for all i < 3, E0 ≤∆1 E0  Ai 1 ÎE0 and [A0 ]E0 = [A1 ]E0 = [A2 ]E0 , [K[ i<3 Ai ]]E0 = ω 2. Fact 3.9.4. There is a ∆11 function P0 : 3 (ω 2) → A so that for all E0 -tree p, P0  [[p]]3E0 is not continuous. Proof. Let P be the function from Fact 3.9.1. Define P0 by   f  01     P0(x, y, z) = P(x, y, z)     f 01  (x, y, z) < [ω 2]3E0 (∀k)(∃n > k)(P(x, y, z)(n) = 2) . (∃k)(∀n > k)(P(x, y, z)(n) < 2) Suppose P0 is continuous on some [[p]]3E0 . Let s ∈ <ω 2 be so that for all n < |s| − 1, s(n) , s(n + 1) and there exists some n < |s| so that s(n) = 2. By continuity, (P0)−1 [Ns ] ∩ [[p]]3E0 is open in [[p]]3E0 . There is some u, v, w ∈ <ω 2 so that |u| = |v| = |w| and Nϕ(u),ϕ(v),ϕ(w) ∩[[p]]3E0 ⊆ (P0)−1 [Ns ]∩[[p]]3E0 . Let x = uˆ0̃, y = vˆf 01, and z = wˆf 10. Then (Φ(x), Φ(y), Φ(z)) ∈ (P0)−1 [Ns ] ∩ [[p]]3E0 . However, there is a k so that for all n > k, P(Φ(x), Φ(y), Φ(z))(n) < 2. Therefore, P0(Φ(x), Φ(y), Φ(z)) = f 01. f However, 01 < Ns since there is some n so that s(n) = 2.  Theorem 3.9.5. There is a ∆11 function K : 3 (ω 2) → ω 2 so that for all Σ11 sets A so that E0 ≤∆1 1 E0  A, K  [A]3E0 is not continuous. 50 Proof. Let Q0 be the function from the proof of Theorem 3.9.2. Let P0 be the function from Fact 3.9.4. K = Q0 ◦ P0 works.  As a consequence, one has another proof of the failure of the 3-Mycielski property for E0 . Corollary 3.9.6. E0 does not have the 3-Mycielski property. Proof. Let C ⊆ 3 (ω 2) be any comeager set so that K  C is a continuous function, where K is from Fact 3.9.5. Then C witnesses the failure of the 3-Mycielski property for E0 .  ω 2/E Does Not Have the 3-Jónsson Property 0 n be the equivalence relation defined on ω n by x E n y if and Definition 3.10.1. For n ∈ ω, let Etail tail 3.10 only if (∃r)(∃s)(∀a)(x(r + a) = y(s + a)). 3 invariant, which means for Fact 3.10.2. The function P : [ω 2]3= → A from Fact 3.9.1 is E0 to Etail 3 P(x 0, y 0, z0). all (x, y, z), (x 0, y0, z0) ∈ [ω 2]3E0 such that x E0 x 0, y E0 y0, and z E0 z0, P(x, y, z) Etail Proof. Using the notation from Fact 3.9.1, let (L k : k ∈ ω) and (a k : k ∈ ω) be the L and a sequences for (x, y, z) and let (Jk : k ∈ ω) and (b k : k ∈ ω) be the L and a sequences for (x 0, y0, z0). 0 , y 0 0 Let M ∈ ω be so that x≥M = x≥M ≥M = y≥M , and z≥M = z≥M . Let r ∈ ω be largest so that Lr < M, and let s ∈ ω be largest so that Js < M. (Case I) Suppose Lr+1 = Js+1 . Then ar+1 = bs+1 . Since for all n ≥ 1, Lr+n, Js+n ≥ M, Lr+n = Js+n 3 P(x 0, y 0, z0). and ar+n = bs+n . Hence P(x, y, z) Etail (Case II) Suppose ar = bs . Then one must have for all n ∈ ω, Lr+n = Js+n and ar+n = bs+n . Hence 3 P(x 0, y 0, z0). P(x, y, z) Etail (Case III) Suppose ar , bs and Lr+1 , Js+1 . Without loss of generality, Lr+1 < Js+1 , ar = 0, and bs = 2. This implies that for all M ≤ k < Lr+1 , x(k) = x 0(k) = y(k) = y0(k) = z(k) = z0(k). However, x(Lr+1 ) , y(Lr+1 ) and y(Lr+1 ) = y0(Lr+1 ) = z0(Lr+1 ) = z(Lr+1 ) because Lr+1 < Js+1 . Hence ar+1 = 2. For any k so that Lr+1 ≤ k < Js+1 , y(k) = y0(k) = z(k) = z0(k). However, y0(Js+1 ) , z0(Js+1 ) hence y(Js+1 ) , z(Js+1 ) and Js+1 is the smallest N > Lr+1 for which this happens. Hence Lr+2 = Js+1 . Also ar+2 = bs+1 . Hence for all n ∈ ω, a(r+2)+n = b(s+1)+n . This 3 P(x 0, y 0, z0). implies P(x, y, z) Etail  2 ≤ 3 3 Fact 3.10.3. Etail ∆1 Etail  A. Hence E0 ≡∆1 Etail  A. 1 1 51 Proof. Let Φ : ω 2 → A be defined by Φ(x) = x ⊕ 2̃, where (x ⊕ y)(n) =    x(k)  n = 2k   y(k)  n = 2k + 1 2 y. Then there are some a, b ∈ ω so that for all n, x(a + n) = y(b + n). For all n ∈ ω, Suppose x Etail Φ(x)(2a + n) = Φ(y)(2b + n). 2 y). Let a, b ∈ ω. Suppose a is even and b is odd. Then Φ(x)(a + 0) ∈ 2 but Suppose ¬(x Etail Φ(y)(b + 0) = 2. The same argument works if a is odd and b is even. Suppose a and b are both 2 y), there is some k so that x(a0 + k) , y(b0 + k). Then even. Let a = 2a0 and b = 2b0. Since ¬(x Etail Φ(x)(a + 2k) = x(a0 + k) , y(b0 + k) = Φ(y)(b + 2k). Suppose a and b are both odd. a = 2a0 + 1 2 y), there is some k so that x((a0 + 1) + k) , y((b0 + 1) + k). Hence and b = 2b0 + 1. Since ¬(x Etail 3 Φ(y)). Φ(x)(a + (1 + 2k)) , Φ(y)(b + (1 + 2k)). This shows ¬(Φ(x) Etail 3 2 ≡ 3 3 Since Etail ∆1 E0 and Etail  A ≤∆1 Etail ≡∆1 E0 , one has E0 ≡∆1 Etail  A. 1 1 1 1  Theorem 3.10.4. (ZF + AD) ω 2/E0 does not have the 3-Jónsson property. 3 be defined by Proof. Let P be the function from Fact 3.10.2. Let P̄ : [ω 2/E0 ]3= → A/Etail P̄(a, b, c) = d if and only if (∀x, y, z)((x ∈ a ∧ y ∈ b ∧ z ∈ c) ⇒ P(x, y, z) ∈ d). 3  A by Fact 3.10.3, let U : A/ By Fact 3.10.2, P̄ is a well defined function. Since E0 ≡∆1 Etail 1 3 → ω 2/E be a bijection (given by Fact 3.2.5). Etail 0 Let F : [ω 2/E0 ]3= → ω 2/E0 be defined by U ◦ P̄. Let X ⊆ ω 2/E0 be such that there is a bijection B : ω 2/E0 → X. By Fact 3.2.22, AD implies B has a Ð lift B0 : D → X, where D ⊆ ω 2 is some comeager set. Since B was a bijection, B0 is a reduction Ð Ð of E0  D to E0  X. Using AD, there is a comeager set C ⊆ D so that B0  C : C → X Ð is a continuous reduction of E0  C to E0  X. There is a continuous function witnessing E0 ≤∆1 E0  C. By composition, there is a continuous reduction witnessing E0 ≤∆1 E0  B0[C]. 1 1 Ð There is an E0 -tree p so that [p] ⊆ B0[C] ⊆ X. By Fact 3.9.1, P[[[p]]3E0 ] = A. This implies that 3 . Since U is a bijection, U[ P̄[[X]3 ]] = F[[X]3 ] = ω 2/E . F witnesses ω 2/E P̄[[X]3= ] = A/Etail 0 0 = = does not have the 3-Jónsson property.  52 As an earlier section mentions, since this paper is often concerned with sets without well-orderings, we defined the Jónsson property using sets of tuples [A]=n . The usual definition of the Jónsson property (of cardinals) involve the n-elements subsets of A, P n (A). This paper calls this the classical n-Jónsson property. With a slight modification, one can also obtain the failure of the classical 3-Jónsson property for ω 2/E0 . Definition 3.10.5. Let S3 be the permutation group on 3 = {0, 1, 2}. S3 acts on ω 3 in the natural way: if p ∈ S3 and x ∈ ω 3, then (p · x)(n) = p(x(n)). 3 y). Let F be an equivalence relation on ω 3 defined by x F y if and only if (∃p ∈ S3 )(p · x Etail Fact 3.10.6. Let A = {x ∈ ω 3 : (∀n)(x(n) , x(n + 1))}. F  A ≡∆1 E0 . 1 3  A is hyperfinite by Fact 3.10.3. Note that E 3  A ⊆ F  A and each F  A Proof. Note that Etail tail 3 equivalence class is a union of at most six Etail  A equivalence classes. By a result of Jackson, F  A is hyperfinite. Hence, F  A ≤∆1 E0 . 1 2 ≤ Next a reduction Φ : ω 2 → A will be produced witnessing Etail ∆11 F  A: Φ(x) = x(0)ˆ2012102ˆx(1)ˆ2012102ˆx(2)... 2 y, then Φ(x) F Φ(y). If x Etail 3 Φ(y). Consider what Suppose Φ(x) F Φ(y). This means there is some g ∈ S3 so that g · Φ(x) Etail happens for each g ∈ S3 : g will be presented in cycle notation. 3 Φ(y) implies that x E 2 y. g = id: It is clear that g · Φ(x) Etail tail g = (0, 1): Then a portion of g · Φ(x) looks like ...ˆg(x(i))ˆ2102012ˆg(x(i + 1))ˆ2102012ˆg(x(i + 2))ˆ... g = (0, 2): ...ˆg(x(i))ˆ0210120ˆg(x(i + 1))ˆ0210120ˆg(x(i + 2))ˆ... g = (0, 1, 2): ...ˆg(x(i))ˆ0120210ˆg(x(i + 1))ˆ0120210ˆg(x(i + 2))ˆ... g = (0, 2, 1): ...ˆg(x(i))ˆ1201021ˆg(x(i + 1))ˆ1201021ˆg(x(i + 2))ˆ... 53 In all these cases, Φ(y) will contain a block of 2012102, but g · Φ(x) cannot possibly contain such 3 Φ(y). a block. So it is impossible that g · Φ(x) Etail g = (1, 2): ...ˆg(x(i))ˆ1021201ˆg(x(i + 1))ˆ1021201ˆg(x(i + 2))ˆ... 2 1̃. This however The only way that some tail of g · Φ(x) contains blocks of 2012102 is if x Etail 3 Φ(1̃). This implies that both x E 2 1̃ and y E 2 1̃. x E 2 y. forces g · Φ(x) Etail tail tail tail 2 into F  A. This shows that Φ is a reduction of Etail This completes the proof that E0 ≡∆1 F  A.  1 Theorem 3.10.7. (ZF + AD) ω 2/E0 does not have the classical 3-Jónsson property. 3 Proof. Let P : [ω 2]3E0 → A be the function from Fact 3.9.1. Fact 3.10.2 shows that P is E0 to Etail invariant. Note that if (x0, x1, x2 ) ∈ [ω 2]3E0 and g ∈ S3 , then there is some other h ∈ S3 so that P(xg(0), xg(1), xg(2) ) = h · P(x0, x1, x2 ). Define a function Ψ : P 3 (ω 2/E0 ) → A/F as follows: Let D ∈ P 3 (ω 2/E0 ). Choose any (x0, x1, x2 ) ∈ [ω 2]3E0 so that D = {[x0 ]E0, [x1 ]E0, [x2 ]E0 }. Let Ψ(A) = [P(x0, x1, x2 )]F . By the above observations, Ψ is a well-defined surjection onto A/F. By Fact 3.10.6, there is a bijection Γ : A/F → ω 2/E0 . Let Φ = Γ ◦ Ψ. By an argument similar to Theorem 3.10.4, Φ witnesses ω 2/E0 does not have the classical 3-Jónsson property.  3.11 Failure of Partition Properties of ω 2/E0 in Dimension Higher Than 2 This section will use the failure of the classical 3-Jónsson property to show that the classical partition property in dimension three fails for R/E0 . Note that for any Y , the failure of ω 2/E0 → (ω 2/E0 )Y3 implies the failure of ω 2/E0 7→ (ω 2/E0 )Y3 . Theorem 3.11.1. (ZF + AD) For any set Y with at least two elements, ω 2/E0 → (ω 2/E0 )Y3 fails. In fact, if Y is a set so that there is a partition of ω 2/E0 by nonempty sets indexed by elements of Y , then there is map f : P 3 (ω 2 /E0 ) → Y with the property that for all C ⊆ ω 2/E0 with C ≈ ω 2/E0 , f [P 3 (C)] ≈ Y . Proof. Let a, b ∈ Y . Partition ω 2/E0 into two nonempty disjoint sets A and B. Let Λ : ω 2/E0 → Y be defined by   a  x∈A Λ(x) =  b x∈B  54 Let Φ be the classical 3-Jónsson function from the proof of Theorem 3.10.7. Define f : P 3 (ω 2/E0 ) → Y by f = Λ ◦ Φ. Suppose C ⊆ ω 2/E0 and C ≈ ω 2/E0 . Suppose a0 ∈ A and b0 ∈ B. Since Φ is a classical 3-Jónsson map, there are some R, S ∈ P 3 (C) so that Φ(R) = a0 and Φ(S) = b0 . Since f (R) = a and f (S) = b. | f [P 3 (C)]| = 2. For the second statement, suppose (Ay : y ∈ Y ) is a partition of ω 2/E0 into nonempty sets. Define Λ : ω 2/E0 → Y by Λ(x) = y if and only if x ∈ Ay . Let f = Λ ◦ Φ. This maps works by an argument like above.  Given a set X and n ∈ ω, one can define d X (n) to be the smallest element of ω, if it exists, such that for every k and every function f : P n (X) → k, there is some S ⊆ k with |S| ≤ d X (n) and A ⊆ X with A ≈ X so that f [P n (A)] ⊆ S. Say that d X (n) is infinite if no such integer exists. [1] showed that assuming the appropriate sets have the Baire property, for every n, k ∈ ω and function f : P n (ω 2) → k, there is an S ⊆ k with |S| ≤ (n − 1)! and a set A ⊆ ω 2 with A ≈ ω 2 so that f [P n (A)] ⊆ S. Hence for n > 0, dω 2 (n) ≤ (n − 1)! assuming AD. Under AD+ , dω 2/E0 (2) is finite and equal to 1, but for n ≥ 3, dω 2/E0 (n) is infinite. 3.12 b P3E0 Is Proper Fact 3.6.5 shows that b P2E0 is proper by having a very flexible fusion argument. Moreover, below any condition (p, q) ∈ b P2E0 and countable elementary submodels M, one can find a (M, b P2E0 )-master condition (p0, q0) so that every element of [p0] ×E0 [q0] is a b P2E0 -generic real over M. This fusion argument for b P2E0 is also used to prove numerous combinatorial properties in dimension 2. The analog of most of these properties in dimension 3 fails. No fusion with the type of property that b P2E0 has can exist for b P3E0 . The natural question to ask would be whether b P3E0 is proper at all. This section will show that b P3E0 is proper via a fusion argument. However, one loses control of when exactly conditions meet dense sets. Definition 3.12.1. Suppose (p, q, r) ∈ b P3E0 . Let (u, v, z) be a triple of strings in <ω 2 of the same length n+1 so that {0, 1} = {u(n), v(n), z(n)}. Suppose (p0, q0, r 0) ≤bP3 (Ξ(p, u), Ξ(q, v), Ξ(r, z)). Let E0 (u,v,z) 3prune(p0,q 0,r 0) (p, q, r) be the unique condition (a, b, c) ≤bn+1 (p, q, r) so that Ξ(a, u) = p0, Ξ(b, v) = q0 3 PE 0 and Ξ(c, z) = r 0. 55 (u,v,z) In the above, we defined the relation ≤bn3 as coordinate-wise ≤PnE . 3prune(p 0,q 0,r 0 ) (p, q, r) has an PE 0 0 explicit definition that is obtained by copying p0, q0 and r 0 below the appropriate part of (p, q, r) like in Definition 3.6.3. Fact 3.12.2. (With Zapletal) b P3E0 is a proper forcing. Proof. Let (p, q, r) ∈ b P3E0 . Let Ξ be some large regular cardinal. Let M ≺ VΞ be a countable elementary substructure containing (p, q, r). Let (Dn : n ∈ ω) enumerate all the dense open subsets of b P3E0 that belong to M. One may assume that Dn+1 ⊆ Dn for all n ∈ ω. If there exists some condition (p0, q0, r 0) ≤b03 (p, q, r) with (p0, q0, r 0) ∈ D0 , then by elementarity PE 0 there is such a condition in M. Let (p0, q0, r0 ) be such a condition in M. Otherwise, let (p0, q0, r0 ) = (p, q, r). Suppose one has defined (pn, qn, rn ). Let {(ui, vi, zi ) : i < K } enumerate all the strings in <ω 2 with length n + 1 so that {u(n), v(n), z(n)} = {0, 1}. Let (a−1, b−1, c−1 ) = (pn, qn, rn ). For i with −1 ≤ i < K − 1, suppose one has defined (ai, bi, ci ). j j j −1 , b−1 , c−1 ) = (a , b , c ). Suppose for j with −1 ≤ j < n+1, one has defined (a , b , c ). Let (ai+1 i i i i+1 i+1 i+1 i+1 i+1 j j j If there exists some condition below (Ξ(ai+1, ui+1 ), Ξ(bi+1, vi+1 ), Ξ(ci+1, zi+1 )) that belongs to D j+1 , j+1 j+1 j+1 then choose, by elementarity, such a condition (a0, b0, c0) ∈ M ∩ D j+1 . Let (ai+1 , bi+1 , ci+1 ) = j j j+1 j+1 j+1 j j j (u ,vi+1,zi+1 ) j 3prune(ai+1 (ai+1, bi+1, ci+1 ). If no such condition exists, then let (ai+1 , bi+1 , ci+1 ) = (ai+1, bi+1, ci+1 ). 0,b0,c 0 ) n+1, bn+1, c n+1 ). Let (p Let (ai+1, bi+1, ci+1 ) = (ai+1 n+1, qn+1, rn+1 ) = (aK−1, bK−1, cK−1 ). Note that i+1 i+1 n+1 (pn+1, qn+1, rn+1 ) ≤b3 (pn, qn, rn ). PE 0 h(pn, qn, rn ) : n ∈ ωi forms a fusion sequence in b P3E0 . Let (pω, qω, rω ) be the fusion of this fusion sequence. The claim is that this is a (M, b P3E0 )-master condition below (p, q, r). It is necessary to show for each n that (pω, qω, rω ) Û b3 b P3E M̌ ∩ Ďn ∩ G , ∅. Let G be any PE0 -generic 0 over M containing (pω, qω, rω ). There is some (p0, q0, r 0) ∈ G ∩ Dn . Since G is a filter, there is some (p00, q00, r 00) ≤bP3 (pω, qω, rω ) so that (p00, q00, r 00) ∈ G ∩ Dn . By genericity, one may assume E0 there is some m > n and some (u, v, z) ∈ m 2 so that (p00, q00, r 00) ≤bP3 (Ξ(pω, u), Ξ(qω, v), Ξ(rω, z)). E0 During the construction while producing (pm, qm, rm ), the strings (u, v, z) = (ui, vi, zi ) for some i in the chosen enumeration of strings. Note that (p00, q00, r 00) ≤bP3 (Ξ(ain−1, ui ), Ξ(bin−1, vi ), Ξ(cin−1, zi )) E0 and (p00, q00, r 00) ∈ Dn . At this stage, one would have chosen some (a0, b0, c0) ∈ M ∩ Dn below i ,vi ,zi ) (Ξ(ain−1, ui ), Ξ(bin−1, vi ), Ξ(cin−1, zi )) and set (ain, bin, cin ) = 3prune(u (an−1, bin−1, cin−1 ). Note that (a 0,b0,c 0 ) i 56 (p00, q00, r 00) ≤bP3 (Ξ(pω, u), Ξ(qω, v), Ξ(rω, z)) ≤bP3 (a0, b0, c0). Since G is a filter and (p00, q00, r 00) ∈ E0 E0 G, (a0, b0, c0) ∈ G ∩ M ∩ Dn . This shows that b P3E0 is a proper forcing.  In the proof, one extends a portion of the three trees to get into a dense set D only if it was possible and otherwise ignored D. Because of this, one cannot prove that [pω ] ×E0 ×[qω ] ×E0 [rω ] consists entirely of reals which are b P3E0 -generic over M. 3.13 E1 Does Not Have the 2-Mycielski Property This section will give an example to show E1 does not have the 2-Mycielski property. The notation of Definition 3.2.3 will be used in the following. As in earlier sections, an understanding of the structure theorem of E1 -big Σ11 sets is essential: Definition 3.13.1. E1 is the equivalence relation on ω (ω 2) defined by x E1 y if and only if there exists a k so that for all n ≥ k, x(n) = y(n). Definition 3.13.2. [14] Let s be an infinite subset of ω. Let πs : ω → s be the unique increasing enumeration of s. A homeomorphism Φ : ω (ω 2) → ω (ω 2) is an s-keeping homeomorphism if and only if the following hold: 1. For all n ∈ ω, if x(n) , y(n), then Φ(x)(πs (m)) , Φ(y)(πs (m)) for all m ≤ n. 2. For all n ∈ ω, if for all m > n, x(m) = y(m), then for all k > πs (n), Φ(x)(k) = Φ(y)(k). Fact 3.13.3. Let B ⊆ ω (ω 2) be Σ11 . E1  B ≡∆1 E1 if and only if there is some infinite s ⊆ ω and 1 s-keeping homeomorphism Φ so that Φ[ω (ω 2)] ⊆ B. Proof. This result is implicit in [18]. See [14], Section 7.2.1.  Theorem 3.13.4. Let D = {(x, y) ∈ 2 (ω (ω 2)) : (∃n)(x(n)(0) , y(n)(0))}. D is dense open and for all ∆11 B such that E1  B ≡∆1 E1 , [B]2E1 * D. 1 E1 does not have the 2-Mycielski property. Proof. Suppose (x, y) ∈ D. There is some n ∈ ω so that x(n)(0) , y(n)(0). Let σ, τ : (n + 1) → 1 2 be defined by σ(k) = x(k)  1 and τ(k) = y(k)  1. Then (x, y) ∈ Nσ,τ ⊆ D. D is open. Let σ, τ : m → <ω 2. Define σ0, τ0 : (m + 1) → <ω 2 by σ0(k) =    σ(k)  k<m   h0i  k=m and 57 τ0(k) =    τ(k)  k<m   h1i  k=m . Nσ 0,τ 0 ⊆ Nσ,τ and Nσ 0,τ 0 ⊆ D. D is dense open. Let s ⊆ ω be infinite. Let πs : ω → s be the unique increasing enumeration of s. Let Φ : ω (ω 2) → ω (ω 2) be an s-keeping homeomorphism. Let δn : (πs (n) + 1) → 1 2 be defined by δn (k) = Φ(0̄)(k)  1. A strictly increasing sequence hmn : n ∈ ωi of natural numbers and functions σn : mn → mn 2 satisfying the following for all n ∈ ω will be defined: 1. σn (k) ⊆ σn+1 (k) for each k < mn . 2. Φ[Nσn ] ⊆ Nδn . 3. There exists a j < mn such that σn (n)( j) = 1 and for all k > n and i < mn , σn (k)(i) = 0. Let m−1 = 0 and σ−1 = δ−1 = ∅. Suppose mn and σn have been defined and satisfy conditions 2 and 3 if n ≥ 0. Define y ∈ Nσn by y(i)( j) = 0 if (i, j) < mn × mn . Then Φ(y) ∈ Nδn . Since y(k) = 0̄(k) for all k > n and Φ is an s-keeping homeomorphism, Φ(y)(k) = Φ(0̄)(k) for all k > πs (n). Thus Φ(y) ∈ Nδn+1 . By continuity of Φ, there is some M ≥ mn so that if τ : M → M 2 is defined by τ(i) = y(i)  M, then Φ(Nτ ) ⊆ Nδn+1 . Let mn+1 = M + 1 and define σn+1 (i)( j) =   1  i =n+1∧ j = M   y(i)( j)  otherwise . mn+1 and σn+1 satisfy conditions 1, 2, and 3. Ñ Let x ∈ ω (ω 2) be so that {x} = n∈ω Nσn . ¬(0̄ E1 x) since for all n, there exists a j so that x(n)( j) = 1 by condition 3. However since Φ(x) ∈ Nδn for all n, (Φ(0̄), Φ(x)) < D. From Definition 3.13.2, Φ is a E1 reduction so ¬(Φ(0̄) E1 Φ(x)). Hence [Φ(ω (ω 2))]2E1 * D. So it has been shown that for all infinite s ⊆ ω and s-keeping homeomorphisms Φ, [Φ[ω (ω 2)]]2E1 * D. By Fact 3.13.3, every ∆11 set B so that E1  B ≡∆1 E1 contains Φ[ω (ω 2)] for some s and 1 some s-keeping homeomorphism Φ. Therefore, [B]2E1 * D for all such B. E1 does not have the 2-Mycielski property.  3.14 The Structure of E2 This section will give a proof of a result about the structure of E2 -big sets necessary for analyzing the weak-Mycielski property for E2 . The proof is similar to but a bit a more technical than the argument of [13] Theorem 15.4.1. Some of the notation and terminology come from [13]. 58 Definition 3.14.1. Suppose x, y ∈ ω 2. Define δ(x, y) = 1 . k +1 k∈x4y Õ Suppose m < n ≤ ω. Suppose x, y ∈ N 2 where n ≤ N ≤ ω. Define  Õ 1 n δm (x, y) = : (m ≤ k < n) ∧ (k ∈ x4y) . k +1 Let A, B ⊆ ω 2. Let m < n ≤ ω. Let  > 0. Define δmn (A, B) <  if and only if for all x ∈ A, there is some y ∈ B so that δmn (x, y) <  and for all y ∈ B, there exists some x ∈ A so that δmn (x, y) < . Definition 3.14.2. E2 is the equivalence relation on ω 2 defined x E2 y if and only if δ(x, y) < ∞. Lemma 3.14.3. Let m < n ≤ ω. Fix N so that n ≤ N ≤ ω. If n < ω, then δmn is a pseudo-metric on N 2. If n = ω, then δmn is a pseudo-metric on any E2 equivalence class. Lemma 3.14.4. Let m, p ∈ ω. Let q ∈ Q+ . Let ( X̂i : i < p) be a sequence of Σ11 (z) subsets of ω 2. Let (xi : i < p) be a sequence in ω 2 with the property that xi ∈ X̂i and δmω (x0, xi ) < q. Then there exists a sequence (Xi : i < p) of Σ11 (z) sets with xi ∈ Xi and δmω (X0, Xi ) < q. Proof. Let        ©Û ª ω X0 = x ∈ X̂0 : (∃z1, ..., z p−1 ) ­ zi ∈ X̂i ∧ δm (x, zi ) < q® .     «1≤i<p ¬  For 1 ≤ i < p, define  Xi = x ∈ X̂i : (∃z)(x ∈ X0 ∧ δmω (x, z) < q) .  Lemma 3.14.5. Let m, p ∈ ω. Let q ∈ Q+ . Let ( X̂i : i < p) be a sequence of Σ11 (z) sets with δmω ( X̂0, X̂i ) < q for all i < p. Let j < p. Suppose A ⊆ X̂ j is a Σ11 (z) set. Then there exists a sequence (Xi : i < p) of Σ11 (z) sets with the property that for all i < p, Xi ⊆ X̂i , X j = A, and δmω (X0, Xi ) < q. Proof. Let X0 = {x ∈ X̂0 : (∃z)(z ∈ A ∧ δmω (x, z) < q)}. For all i < p and i , j, let Xi = {x ∈ X̂i : (∃z)(z ∈ X0 ∧ δmω (x, z) < q)} Let X j = A.  59 Lemma 3.14.6. Let m, p ∈ ω. Let q ∈ Q+ . Let ( X̂i : i < p) be a sequence of Σ11 (z) sets with δmω ( X̂0, X̂i ) < q for all i < p. Let D be a dense open subset of Pz . Then there exists a sequence (Xi : i < p) of Σ11 (z) sets with Xi ⊆ X̂i , Xi ∈ D, and δmω (X0, Xi ) < q for all i < p. Proof. Let Yi−1 = X̂i . j One seeks to define Σ11 (z) sets Yi for all −1 ≤ j < p with the property that if −1 ≤ j < p − 1, then j+1 j j j j Yi ⊆ Yi , and for any −1 ≤ j < p and 0 ≤ i < p, Yj ∈ D and δmω (Y0 , Yi ) < q. j Suppose one has defined Yi with the desired properties for j < p − 1 and all i < p. Since D is j j dense open in Pz , pick some A ⊆ Yj+1 so that A ∈ D. Use Lemma 3.14.5 with {Yi : i < p} and j A ⊆ Yi to obtain {Yi Let Xi = Yi p−1 j+1 : i < p} with the desired properties. .  In the previous three lemmas, the first set was distinguished. In the following argument, we index the sets by strings and so in applications of the three lemmas, one will need to indicate what this distinguished set is. Lemma 3.14.7. Let z ∈ ω 2. Let k, m, p ∈ ω. Let r, v ∈ Q+ . Let (Bsi : s ∈ k 2 ∧ i < p) be a sequence of Σ11 (z) sets. Let (bis : s ∈ k 2 ∧ i < p) be a sequence in ω 2 with bis ∈ Bsi . Suppose for all i < p, δmω (b00k , bi0k ) < r. Suppose for each i < p and for all s ∈ k 2, δmω (bi0k , bis ) < v. Let D be a dense open subset of Pz . Then there is a sequence (Csi : s ∈ k 2 ∧ i < p} of Σ11 (z) sets so that for all i < p and s ∈ k 2, δmω (C00k , C0i k ) < r, δmω (C0i k , Csi ) < v, and Csi ∈ D. Proof. For each i < p, apply Lemma 3.14.4 to {Bsi : s ∈ k 2} and {bis : s ∈ k 2} using 0 k as the distinguished index to obtain a sequence of Σ11 (z) sets {Esi : s ∈ k 2} with the property that Esi ⊆ Bsi , bis ∈ Esi , and δmω (E0i k , Esi ) < v. Now apply Lemma 3.14.4 to {E0i k : i < p} and {bi0k : i < p} with 0 as the distinguished index to obtain Σ11 (z) sets Ai ⊆ E0i k so that δmω (A0, Ai ) < r. For each i < p, apply Lemma 3.14.5 to {Esi : s ∈ k 2} with 0 k as the distinguished index and Ai ⊆ E0i k to obtain Σ11 (z) sets Gi,−1 with the properties that Gi,−1 = Ai and δmω (Gi,−1 , Gi,−1 s s ) < v. 0k 0k Note that since Gi,−1 = Ai , the sequence {Gi,−1 : i < p ∧ s ∈ k 2} has the property that for all i < p, s 0k δmω (G0,−1 , Gi,−1 ) < r and for each i < p and s ∈ k 2, δmω (Gi,−1 , Gi,−1 s ) < v. 0k 0k 0k 60 i, j One wants to create G s for −1 ≤ j < p, i < p, and s ∈ k 2 so that i, j (i) For each i ∈ ω, s ∈ k 2, and −1 ≤ l ≤ j < p, G s ⊆ Gi,l s . (ii) For all i < p, δmω (G0k , G0k ) < r. 0, j i, j (iii) For each i < p and s ∈ k 2, δmω (G0k , G s ) < v. i, j i, j l, j (iv) If j ≥ 1 and 0 ≤ l ≤ j, then G s ∈ D. This already holds for j = −1. Suppose the construction worked up to stage j < p − 1 producing j+1, j j+1, j+1 objects with the above properties. Apply Lemma 3.14.6 to {G s : s ∈ k 2} to get sets {G s : j+1, j+1 j+1, j+1 s ∈ k 2} each in D and δmω (G0k , Gs ) < v. i, j j+1, j+1 j+1, j Next apply Lemma 3.14.5 to {G0k : i < p} with 0 as the distinguished index and G0k ⊆ G 0k i, j+1 i, j 0, j+1 i, j+1 to obtain sets G0k ⊆ G0k with δmω (G0k , G0k ) < r. (Note it is acceptable to use the notation j+1, j+1 G 0k since it is the same set as before by the statement of Lemma 3.14.5.) i, j For each i , j + 1, apply Lemma 3.14.5 on {G s : s ∈ k 2} with 0 k as the distinguished index and i, j+1 i, j+1 i, j+1 i, j i, j+1 : s ∈ k 2} with the property that δmω (G0k , G s ) < v. This G0k ⊆ G0k to obtain sets {G s completes the construction at stage j + 1. i,p−1 Let Csi = G s .  Definition 3.14.8. ([13] Definition 15.2.2) Let q > 0 be a rational number. Let A ⊆ ω 2. Let a ∈ A. q The q-galaxy of a in A, denoted Gal A(a), is the set of all b ∈ A so that there exists a0, ..., al ∈ A with a = a0 , b = al , and δ(ai, ai+1 ) < q for all 0 ≤ i < l − 1. A ⊆ ω 2 is q-grainy if and only if for all a ∈ A and b ∈ Gal A(a), δ(a, b) < 1. A is grainy if and only if A is q-grainy for some positive rational number q. q Fact 3.14.9. Let z ∈ ω 2 and rational q > 0. If A is a Σ11 (z) q-grainy set, then there is some B ⊇ A which is ∆11 (z) q-grainy. Proof. (See [13], Claim 15.2.4 for a more constructive proof.) Let U ⊆ ω× ω 2 be a universal Σ11 (z) set. The relation in variables e, a, and b expressing b ∈ GalU e (a) is Σ11 (z). q Let A be the collection of all Σ11 (z) q-grainy subsets of ω 2. q {e : U e ∈ A} = {e : (∀a)(∀b)(b ∈ GalU e (a) ⇒ δ(a, b) < 1)} 61 This shows that A is a collection of Σ11 (z) sets which is Π11 (z) in the code. By Σ11 (z) reflection, every Σ11 (z) q-grainy set is contained inside of a ∆11 (z) q-grainy set.  Definition 3.14.10. Let z ∈ ω 2. Let Sz be the union of all ∆11 (z) grainy sets. Let Hz = ω 2 \ Sz . Fact 3.14.11. Let z ∈ ω 2. Sz is Π11 (z). Hence Hz is Σ11 (z). Every nonempty Σ11 (z) subset of Hz is not grainy. Proof. Similar to Fact 3.5.12.  Theorem 3.14.12. Let z ∈ ω 2. Let p ∈ ω. Suppose (Xi : i < p) is a collection of Σ11 (z) subsets Ñ of ω 2 with the property that i<p [Xi ∩ Hz ]E2 , ∅. Then there is a strictly increasing sequence (mk : k ∈ ω) and functions gi : <ω 2 → <ω 2 for each i < p with the following properties: 1. If |s| = k, then for all i < p, gi (s) ∈ mk 2. 2. If s ⊆ t, then for all i < p, gi (s) ⊆ gi (t). k 3. If |s| = |t| = k > 0 and s(k − 1) = t(k − 1), then δmmk−1 (gi (s), gi (t)) < 2−(k+1) , k 4. If |s| = |t| = k > 0 and s(k − 1) , t(k − 1), then |δmmk−1 (gi (s), gi (t)) − 1k | < 2−(k+1) . k 5. For i, j < p and s ∈ k 2 with k > 0, δmmk−1 (gi (s), g j (s)) < 2−(k+1) . Ð 6. Define Φi (x) = n∈ω gi (x  n). Φi : ω 2 → Xi ∩Hz is a reduction witnessing E2 ≤∆1 E2  Xi ∩Hz . 1 Moreover, for i, j < p, [Φi [ω 2]] E2 = [Φ j [ω 2]] E2 . Proof. During the construction, one will seek to create (i) a strictly increasing sequence (mk : k ∈ ω), (ii) for each i < p and s ∈ <ω 2, Σ11 (z) sets Ais , (iii) and for each i < p, gi (s) ∈ <ω 2. These objects will satisfy the following properties: (I) If |s| = k, then |gi (s)| = mk . s ⊆ t implies gi (s) ⊆ gi (t). (II) ∅ , Ais ⊆ X i ∩ Hz ∩ Ngi (s) . s ⊆ t implies Ait ⊆ Ais . (III) If k > 0, |s| = k, then δmωk (Ai0k , Ais ) ≤ 2−(k+4) , where 0 k : k → 2 is the constant 0 function. k (IV) If k > 0, |s| = |t| = k, and s(k − 1) = t(k − 1), then δmmk−1 (gi (s), gi (t)) ≤ 2−(k+1) . 62 k (V) If k > 0, |s| = |t| = k, s(k − 1) , t(k − 1), then |δmmk−1 (gi (s), gi (t)) − 1k | < 2−(k+1) . (VI) If |s| = k and i < p, δmωk (A0s , Ais ) < 2−(k+6) . k (VII) If |s| = k and k > 0, then δmmk−1 (gi (s), g j (s)) < 2−(k+1) . (VIII) Let D = (Dn : n ∈ ω) be the countable collection of dense open subsets of Pz from Fact 3.5.9. For all s ∈ <ω 2 and i < p, Ais ∈ D|s| . Suppose it is possible to construct these objects having the above properties. It only remains to Ñ verify 6: {Φi (x)} = k∈ω Axk by (II) and (VIII). Hence Φi maps into Xi ∩ Hz by (II). Note that δ(Φi (x), Φ j (y)) = lim k→∞ δ0mk (gi (x  k), g j (y  k)). Also using (IV) and (V), for any k Õ |δ0mk (gi (x  k), gi (y  k)) − δ0k (x  k, y  k)| < 2−( j+1) < 1 j<k Hence Φi (x) E2 Φi (y) ⇔ δ(Φi (x), Φi (y)) < ∞ ⇔ δ(x, y) < ∞ ⇔ x E2 y. This shows each Φi witnesses E2 ≤∆1 E2  Xi ∩ Hz . Using (VII), for each i, j < p and x ∈ ω 2, 1 δmm0k (gi (x  k), g j (x  j)) < Õ 2−( j+1) < 1 j<k Hence Φi (x) E2 Φ j (x). Hence [Φi [ω 2]]E2 = [Φ j [ω 2]]E2 . Ñ Next the construction: Since i<p [Xi ∩ Hz ]E2 , ∅, let (bi∅ : i < p) be such that for all i, j < p, j bi∅ E2 b∅ and bi∅ ∈ Xi ∩ Hz . Therefore, choose m0 ∈ ω so that for all i < p, δmω0 (b0∅, bi∅ ) < 2−6 . For each i < p, let gi (∅) = bi∅  m0 . Let B∅i = Xi ∩ Hz ∩ Ngi (∅) . Apply Lemma 3.14.7 to {B∅i : i ∈ p}, {bi∅ : i < p}, and the dense open (in Pz ) set D0 (where r = 2−6 and v = 1) to obtain sets Ai∅ with the desired properties. Suppose the objects from stage k have been constructed with the desired properties. As A00k ⊆ Hz , Fact 3.14.11 implies that A00k is not 2−(k+5) -grainy. Hence there is a sequence a0, ..., a M of points in A00k so that for each 0 ≤ j < M − 1, δ(a j , a j+1 ) < 2−(k+5) but δ(a0, a M ) > 1. 1 1 and δ(a0, a I ) − k+1 < 2−(k+5) . Hence there is some I so that δ(a0, a I ) > k+1 Let b00k ˆ0 = a0 and b00k ˆ1 = a I . Since δmωk (A0s , Ais ) < 2−(k+6) by (VI), find bi0k+1, bi0k ˆ1 ∈ Ai0k so that δ(b00k+1, bi0k+1 ) < 2−(k+6) and δ(b00k ˆ1, bi0k ˆ1 ) < 2−(k+6) . 1 The claim is that for all i < p, |δmωk (bi0k+1, bi0k ˆ1 ) − k+1 | < 2−(k+4) : To see this, |δmωk (bi0k+1, bi0k ˆ1 ) − 63 1 | k +1 ≤ |δmωk (bi0k+1, bi0k ˆ1 ) − δmωk (b00k+1, b00k ˆ1 )| + |δmωk (b00k+1, b00k ˆ1 ) − 1 | k +1 < |δmωk (bi0k+1, bi0k ˆ1 ) − δmωk (b00k+1, bi0k ˆ1 )| + |δmωk (b00k+1, bi0k ˆ1 ) − δmωk (b00k+1, b00k ˆ1 )| + 2−(k+5) ≤ δmωk (bi0k+1, b00k+1 ) + δmωk (bi0k ˆ1, b00k ˆ1 ) + 2−(k+5) ≤ 2−(k+6) + 2−(k+6) + 2−(k+5) = 2−(k+4) This proves the claim. Now fix a i < p. By (III), δmωk (Ai0k , Ait ) < 2−(k+4) for each t ∈ k 2. For each s ∈ k+1 2, let bis ∈ Aisk be such that δmωk (bi0k ˆs(k), bis ) < 2−(k+4) . Suppose s ∈ k+1 2 and s(k) = 1. |δmωk (bi0k+1, bis ) − 1 | k +1 ≤ |δmωk (bi0k+1, bis ) − δmωk (bi0k+1, bi0k ˆ1 )| + |δmωk (bi0k+1, bi0k ˆ1 ) − 1 | k +1 < δ(bis, bi0k ˆ1 ) + 2−(k+4) ≤ 2−(k+4) + 2−(k+4) = 2−(k+3) By (I), (II), and the fact that bi0k+1, bi0k ˆ1 ∈ Ai0k , there exists some mk+1 > mk so that 1 | < 2−(k+3) for all s ∈ k+1 2 with s(k) = 1. (i) |δmmkk+1 (bi0k+1, bis ) − k+1 (ii) δmωk+1 (b00k+1, bi0k+1 ) < 2−(k+7) for all i < p. (iii) δmωk+1 (bi0k+1, bis ) < 2−(k+5) for all s ∈ k+1 2. Let gi (s) = bis  mk+1 . Suppose s(k) = t(k). Without loss of generality, suppose s(k) = t(k) = 1. Then δmmkk+1 (gi (s), gi (t)) ≤ δmmkk+1 (bis, bi0k ˆ1 ) + δmmkk+1 (bi0k ˆ1, bit ) ≤ 2−(k+4) + 2−(k+4) = 2−(k+3) < 2−(k+2) This establishes (IV). Suppose s(k) , t(k). Without loss of generality, suppose s(k) = 1. Hence t(k) = 0. |δmmkk+1 (gi (s), gi (t)) − 1 | k +1 ≤ |δmmkk+1 (bis, bit ) − δmmkk+1 (bis, bi0k+1 )| + |δmmkk+1 (bis, bi0k+1 ) − 1 | k +1 < δmmkk+1 (bit, bi0k+1 ) + 2−(k+3) < 2−(k+4) + 2−(k+3) < 2−(k+2) This establishes (V). 64 Let s ∈ k+1 2. Without loss of generality suppose s(k) = 0. Suppose i, j < p. Observe: δmmkk+1 (gi (s), g j (s)) ≤ δmωk (bis, bs ) ≤ δmωk (bis, bi0k+1 ) + δmωk (bi0k+1, bs ) j j ≤ δmωk (bis, bi0k+1 ) + δmωk (bi0k+1, b0k+1 ) + δmωk (b0k+1, bs ) j j j ≤ δmωk (bis, bi0k+1 ) + δmωk (bi0k+1, b00k+1 ) + δmωk (b00k+1, b0k+1 ) + δmωk (b0k+1, bs ) j j j ≤ 2−(k+4) + 2−(k+6) + 2−(k+6) + 2−(k+4) ≤ 2−(k+3) + 2−(k+5) < 2−(k+2) This establishes (VII). For s ∈ k+1 2, let Bsi = Aisk ∩ Ngi (s) . Apply Lemma 3.14.7 on {Bsi : i < p ∧ s ∈ k+1 2}, {bis : i < p ∧ s ∈ k+1 2}, r = 2−(k+7) , v = 2−(k+5) , and D k+1 to obtain the desired objects (Ais : i < p ∧ s ∈ k+1 2) which satisfy the remaining conditions. This completes the proof.  By relativizing to the appropriate parameter, one can obtain the following result. Corollary 3.14.13. Let p ∈ ω. Suppose (Xi : i < p) is a collection of Σ11 subsets of ω 2 with the property that for all i < p, E2 ≤∆1 E2  Xi and for all i, j < p, [Xi ]E2 = [X j ]E2 . Then there 1 exists a sequence of strictly increasing integers (mk : k ∈ ω) and maps gi : <ω 2 → <ω 2 satisfying conditions 1 - 5 of Theorem 3.14.12. Fact 3.14.14. Let B ⊆ ω 2 be a Σ11 so that E2 ≤∆1 E2  B. There there exists a strictly increasing 1 sequence (mk : k ∈ ω) with m0 = 0 and function g : <ω 2 → <ω 2 with the following properties: 1. If |s| = k, then |g(s)| = mk . 2. If s ⊆ t, then g(s) ⊆ g(t). k 3. If |s| = |t| = k > 0 and s(k − 1) = t(k − 1), then δmmk−1 (g(s), g(t)) < 2−(k+1) . k (g(s), g(t)) − 1k | < 2−(k+1) . 4. If |s| = |t| = k > 0 and s(k − 1) , t(k − 1), then |δmmk−1 Ð 5. Let Φ : ω 2 → ω 2 be defined by Φ(x) = n∈ω g(x  n). Then Φ is a ∆11 function such that Φ[ω 2] ⊆ B and Φ witnesses E2 ≤∆1 E2  B. 1 Proof. This is implicit in [8]. Also see [13] Theorem 15.4.1 and [14] Theorem 7.43. The proof is quite similar to Theorem 3.14.12.  65 3.15 E2 Does Not Have the 2-Mycielski Property Theorem 3.15.1. Let D ⊆ 2 (ω 2) be defined by D = {(x, y) ∈ 2 (ω 2) : (∃i < j)(δi (x, y) > 2 ∧ (∀n)(i ≤ n < j ⇒ x(n) , y(n)))} j D is dense open. Let (mk : k ∈ ω), g, and Φ be as in Fact 3.14.14. (Φ(0̃), Φ(f 01)) < D. For any ∆11 set B so that E2  B ≡∆1 E2 , [B]2E2 * D. 1 E2 does not have the 2-Mycielski property. Proof. Let (x, y) ∈ D. There is some i < j so that for all n with i ≤ n < j, x(n) , y(n) and j δi (x, y) > 2. Let σ = x  ( j + 1) and let τ = y  ( j + 1). Then (x, y) ∈ Nσ,τ ⊆ D. D is open. Í 1 > 2. Let σ0, τ0 ∈ j+1 2 Let σ, τ ∈ <ω 2 with |σ| = |τ|. Let i = |σ|. Find a j > i so that i≤n< j n+1 be defined by σ (k) = 0    σ(k)  k <i  0  otherwise and τ (k) = 0    τ(k)  k <i  1  otherwise . Nσ 0,τ 0 ⊆ Nσ,τ and Nσ 0,τ 0 ⊆ D. D is dense open. Note that one must have 1 ≥ 2−k−1 m + 1 ≤m<m Õ mk−1 k because 1k − 2−k−1 ≥ 2−k − 2−k−1 = 2−k−1 and so otherwise, condition 4 could not hold for any s, t ∈ k 2 with s(k − 1) , t(k − 1). This implies that for any s and t so that s(k −1) = t(k −1), there must be some m with mk−1 ≤ m < mk so that g(s)(m) = g(t)(m). Note that for all s, t ∈ k+1 2. k+1 k (g(s), g(t)) = δmmk−1 (g(s), g(t)) + δmmkk+1 (g(s), g(t)) ≤ δmmk−1 1 1 + 2−k−1 + + 2−k−2 < 2. k k +1 j Hence for any s, t, if there exists i < j so that δi (g(s), g(t)) > 2, then there is some k ≥ 1 so that i ≤ mk−1 < mk < mk+1 ≤ j. j Now suppose that there is some i < j so that δi (Φ(0̃), Φ(f 01)) > 2. There is some k ≥ 1 so that i ≤ mk−1 < mk < mk+1 ≤ j. Without loss of generality, suppose k is even. 0̃(k) = 0 = f 01(k). 66 By the above, there is some l with mk ≤ l < mk+1 so that Φ(0̃)(l) = Φ(f 01)(l). This shows (Φ(0̃), Φ(f 01)) < D. ¬(0̃ E2 f 01) so ¬(Φ(0̃) E2 Φ(f 01)). Hence [Φ[ω 2]]2E2 * D. It has been shown that for all (mk : k ∈ ω), g, and associated Φ, [Φ[ω 2]]2E2 * D. If B ⊆ ω 2 is ∆11 with the property that E2  B ≡∆1 E2 , then Fact 3.14.14 implies that there is some (mk : k ∈ ω) and 1 g so that Φ[ω 2] ⊆ B. This shows that for all such B, [B]2E2 * D. E2 does not have the 2-Mycielski property.  Theorem 3.15.2. For each n ∈ ω, let Dn = {(x, y) ∈ 2 (ω 2) : (∃i < j)(n ≤ i < j ∧ δi (x, y) > 3 ∧ (∀m)(i ≤ m < j ⇒ x(m) , y(m)))}. j Each Dn is a dense open subset of 2 (ω 2). Hence C = Ñ n∈ω Dn is a comeager subset of 2 (ω 2). Suppose (mk : k ∈ ω), g 0 , g 1 , Φ0 , and Φ1 have properties 1 - 6 from Theorem 3.14.12. Then (Φ0 (0̃), Φ1 (f 01)) < C. For any ∆11 sets B0 and B1 with E2 ≤∆1 E2  B0 , E2 ≤∆1 E2  B1 , and [B0 ]E2 = [B1 ]E2 , 1 1 B0 ×E2 B1 * C. E2 does not have the weak 2-Mycielski property. k (g 0 (s), g 1 (t))− Proof. Using Theorem 3.14.12, if |s| = |t| = k > 0 and s(k −1) , t(k −1), then |δmmk−1 1 −k k | < 2 . To see this: 1 k |δmmk−1 (g 0 (s), g 1 (t)) − | k 1 k k k ≤ |δmmk−1 (g 0 (s), g 1 (t)) − δmmk−1 (g 1 (s), g 1 (t))| + |δmmk−1 (g 1 (s), g 1 (t)) − | k mk 0 1 −(k+1) −(k+1) −(k+1) −k ≤ δmk−1 (g (s), g (s)) + 2 ≤2 +2 =2 k Also if |s| = |t| = k > 0 and s(k − 1) = t(k − 1), then δmmk−1 (g 0 (s), g 1 (t)) < 2−k . To see this: k k k δmmk−1 (g 0 (s), g 1 (t)) ≤ δmmk−1 (g 0 (s), g 1 (s)) + δmmk−1 (g 1 (s), g 1 (t)) = 2−(k+1) + 2−(k+1) = 2−k Dn is dense open by the same argument as in Theorem 3.15.2. Note that if k > 0, then 1 ≥ 2−k m + 1 ≤m<m Õ mk−1 k k because 1k − 2−k ≥ 2−(k−1) − 2−k = 2−k and so otherwise |δmmk−1 (g 0 (s), g 1 (s)) − 1k | < 2−k could not hold. 67 Therefore if |s| = |t| > 0, and s(k − 1) = t(k − 1), then there must be some m with mk−1 ≤ m < mk so that g 0 (s)(m) = g 1 (t)(m). Note that for all s, t ∈ k+1 2 with k > 0, k+1 k δmmk−1 (g(s), g(t)) = δmmk−1 (g(s), g(t)) + δmmkk+1 (g(s), g(t)) ≤ 1 1 + 2−k + + 2−(k+1) < 3. k k +1 j Hence for any s, t, if there exists i < j so that δi (g 0 (s), g 1 (t)) > 3, then there is some k ≥ 1 so that i ≤ mk−1 < mk < mk+1 ≤ j. Now by essentially the same argument as in Theorem 3.15.1, (Φ0 (0̃), Φ1 (f 01)) < Dm0 . Hence 0 1 (Φ (0̃), Φ (f 01)) < C. Now suppose that B0 and B1 are some ∆11 sets so that E2 ≤∆1 E2  B0 , E2 ≤∆1 E2  B1 , and 1 1 [B0 ]E2 = [B1 ]E2 . By Corollary 3.14.13, there is a sequence (mk : k ∈ ω), g 0 , g 1 , Φ0 and Φ1 as above so that Φi [ω 2] ⊆ Bi . By the earlier argument, B0 ×E2 B1 * C. Hence E2 does not have the weak 2-Mycielski property.  3.16 Surjectivity and Continuity Aspects of E2 Fact 3.14.14 states that every Σ11 set B ⊆ ω 2 so that E2 ≤∆1 E2  B has a closed set C ⊆ B so that 1 E2 ≡∆1 E2  C. Fact 3.14.14 even asserts that C is the body of a tree on 2 with a specific structure: 1 Definition 3.16.1. A tree p ⊆ <ω 2 is an E2 -tree if and only if there is some sequence (mk : k ∈ ω) and map g : <ω 2 → <ω 2 satisfying the conditions of Fact 3.14.14 so that p is the downward closure of g[<ω 2]. Note that if Φ is the map associated with (mk : k ∈ ω) and g, then [p] = Φ[ω 2]. The following notation is used to avoid some very tedious superscripts and subscripts in the following results: Definition 3.16.2. If x, y ∈ ω 2 and m, n ∈ ω with m ≤ n, then let ς(m, n, x, y) = δmn (x, y). Fact 3.16.3. There is a continuous function P : [ω 2]3E2 → ω 3 so that for any E2 -tree p, P[[[p]]3E2 ] = ω 3. Proof. For (x, y) ∈ [ω 2]2E2 and any n, m ∈ ω, define Sn,m (x, y) = min{k ∈ ω : δnk (x, y) > 3m+2 } Each Sn,m is continuous on [ω 2]3E2 . 68 If (x, y, z) ∈ [ω 2]3E2 , then define a strictly increasing sequence of integers (Ln : n ∈ ω) by recursion as follows: Let L0 = 0. Given Ln , let Ln+1 = min{SLn,n (x, y), SLn,n (x, z), SLn,n (y, z)} (It is implicit that Ln depends on the triple (x, y, z).) By induction, it can be shown that each Ln as a function of (x, y, z) is continuous on [ω 2]3E2 . Define    0     P(x, y, z)(n) = 1     2  ω 3 P is continuous on [ 2]E2 . SLn,n (x, y) ≤ SLn,n (x, z) and SLn,n (x, y) ≤ SLn,n (y, z) SLn,n (x, z) < SLn,n (x, y) and SLn,n (x, z) ≤ SLn,n (y, z) SLn,n (y, z) < SLn,n (x, y) and SLn,n (y, z) < SLn,n (x, z) Also define the sequence of integers (Nn : n ∈ ω) by recursion as follows: Let N0 = 0 and if Nn has been defined, then let ( )  Õ  1 − 2−(i+2) > 3n+2 Nn+1 = min k ∈ ω : i + 1 N ≤i<k i Note that Nn+1 > Nn + 2 for each n ∈ ω. By the definition of Nn+1 , one has that   Õ 1 −i−2 −2 ≤ 3n+2 . i + 1 N ≤i<N −1 n n+1 These two facts imply Õ Nn ≤i<Nn+1 Õ 1 1 ≤ 3n+2 + + i+1 Nn+1 N ≤i<N 2−i−2 < 3n+2 + 1 (3.1) n+1 −1 n Let k n = Nn+1 − Nn . Fix a v ∈ ω 3. Define σn, τn ∈ k n 2 by σn =    1̃  k n  v(n) = 0  f 01  k n  otherwise τn =    1̃  k n  v(n) = 1  f 10  k n  otherwise Let x = 0̃, y = σ0ˆσ1ˆσ2ˆ..., and z = τ0ˆτ1ˆτ2 .... Note (x, y, z) ∈ [ω 2]3E2 . Fix an E2 -tree p. Let (mk : k ∈ ω), g : <ω 2 → <ω 2, and Φ : ω 2 → ω 2 be the associated objects of p coming from the definition of an E2 -tree. 69 Suppose v(n) = 0, then ς(mNn, mNn+1, Φ(x), Φ(y)) = Õ ς(mi, mi+1, Φ(x), Φ(y)) > Nn ≤i<Nn+1  Õ Nn ≤i<nn+1  1 −i−2 −2 > 3n+2 i+1 (3.2) using the definition of Nn+1 . Also ς(mNn, mNn+1, Φ(x), Φ(y)) < Õ Nn ≤i<Nn+1   Õ 1 −n−2 n+2 +2 < 3 +1+ i+1 N ≤i<N n 3 2 (3.3) 2−i−2 < 3n+2 + n+1 using equation (3.1) for the second inequality. Note also ς(mNn, mNn+1, Φ(x), Φ(z)) = ς(mNn, mNn +1, Φ(x), Φ(y)) + Õ ς(mi, mi+1, Φ(x), Φ(z)) Nn <i<Nn+1 Õ 1 1 Õ 1 + 2−Nn −2 + + 2−i−2 Nn + 1 2 N <i<N i + 1 N <i<N n n n+1 n+1   Õ Õ 1 1 1 3 1 1 = + + 2−i−2 < (3n+2 ) + 2 N ≤i<N i + 1 2 Nn + 1 2 2 N ≤i<N < n n n+1 n+1 using equation (3.1). In summary, 1 3 ς(mNn, mNn+1, Φ(x), Φ(z)) < (3n+2 ) + 2 2 (3.4) Similarly, ς(mNn, mNn+1, Φ(y), Φ(z)) < 12 (3n+2 ) + 23 . The case for v(n) = 1 and v(n) = 2 are similar. It remains to show that P(Φ(x), Φ(y), Φ(z)) = v. In the following, let (Ln : n ∈ ω) be the sequence defined as above using (Φ(x), Φ(y), Φ(z)). The following statements will be proved by induction on n: (I) mNn < Ln+1 ≤ mNn+1 . (II) P(Φ(x), Φ(y), Φ(z))(n) = v(n). (III) The following holds: 1 3 max{ς(Ln+1, mNn+1, Φ(x), Φ(y)), ς(Ln+1, mNn+1, Φ(x), Φ(z)), ς(Ln+1, mNn+1, Φ(y), Φ(z))} < (3n+2 )+ . 2 2 Suppose properties (I), (II), and (III) holds for all k < n. Suppose v(n) = 0. (The other cases are similar.) 70 Ln ≤ mNn by definition if n = 0 and by the induction hypothesis otherwise. Therefore, ς(Ln, mNn+1, Φ(x), Φ(y)) ≥ ς(mNn, mNn+1, Φ(x), Φ(y)) > 3n+2 using equation (3.2). This shows Ln+1 ≤ SLn,n (Φ(x), Φ(y)) ≤ mNn+1 . Using the induction hypothesis or the definition when n = 0,  3 1 max ς(Ln, mNn, Φ(x), Φ(y)), ς(Ln, mNn, Φ(x), Φ(z)), ς(Ln, mNn, Φ(y), Φ(z)) < (3n+1 )+ < 3n+2 . 2 2 Hence Ln+1 ≤ mNn is impossible. This proves (I). Observe that ς(Ln, mNn+1, Φ(x), Φ(z)) = ς(Ln, mNn, Φ(x), Φ(z)) + ς(mNn, mNn+1, Φ(x), Φ(z)) 3 1 3 1 < (3n+1 ) + + (3n+2 ) + ≤ 3n+2 2 2 2 2 using the induction hypothesis and equation (3.4). This shows SLn,n (Φ(x), Φ(z)) > mNn+1 . Similarly, SLn,n (Φ(y), Φ(z)) > mNn+1 . SLn,n (Φ(x), Φ(y)) ≤ mNn+1 has already been shown above. Thus P(Φ(x), Φ(y), Φ(z))(n) = 0 = v(n). This shows (II). Note that 3 1 ς(Ln+1, mNn+1, Φ(x), Φ(z)) ≤ ς(mNn, mNn+1, Φ(x), Φ(z)) < (3n+2 ) + 2 2 using equation (3.4). Similarly, 1 3 ς(Ln+1, mNn+1, Φ(y), Φ(z)) < (3n+2 ) + . 2 2 Finally, ς(Ln, mNn+1, Φ(x), Φ(y)) = ς(mNn, mNn+1, Φ(x), Φ(y))− ς(Ln, Ln+1, Φ(x), Φ(y))−ς(Ln, mNn, Φ(x), Φ(y)) 1 3 1 3 3 − 3n+2 + (3n+1 ) + < (3n+2 ) + 2 2 2 2 2 using equation (3.3), the definition of the sequence (Ln : n ∈ ω), and the induction hypothesis. This proves (III).  < 3n+2 + Theorem 3.16.4. There is a continuous function Q : [ω 2]3E2 → ω 2 so that for any E2 -tree p, Q[[[p]]3E2 ] = ω 2. There is a ∆11 function K : 3 (ω 2) → ω 2 so that on any Σ11 set A with E2 ≤∆1 E2  A, K[[A]3E2 ] = ω 2 1 (and in particular the image meets each E2 -equivalence class). 71
Proof. One can obtain Q by composing the function from Fact 3.16.3 with a homeomorphism from ω 3 → ω 2. One can obtain K by mapping elements of 3 (ω 2) \ [ω 2]3E2 to 0̃ and mapping elements in [ω 2]3E2 according to Q. Note that by Fact 3.14.14, every such set A contains an E2 -tree.  Lemma 3.16.5. Let X and Y be topological spaces. Let B ⊆ P(X) be a nonempty family of subsets of X. Let A ⊆ Y be Borel. Suppose f : X → Y is a Borel function with the property that for all B ∈ B and open U ⊆ X with U ∩ B , ∅, there exists an x ∈ B with f (x) < A and an x 0 ∈ U ∩ B with f (x 0) ∈ A. Then there is a Borel function g : X → Y such that g  B is not continuous for all B ∈ B. Proof. The assumption above implies that A is Borel but not equal to either ∅ or Y . The topology of Y is not {∅, Y }. There exists some y1, y2 ∈ Y and open set V ⊆ Y with y1 ∈ V and y2 < V. Define g(x) =    y1  f (x) < A   y2  f (x) ∈ A . Suppose there was some B ∈ B so that g  B is a continuous function. By the assumptions, there is a x ∈ B so that f (x) < A. So g(x) = y1 . By continuity, g −1 [V] ∩ B is a nonempty open set containing x ∈ B. There is some U ⊆ X open so that g −1 [V] ∩ B = U ∩ B. By the assumptions, there some x 0 ∈ U ∩ B so that f (x 0) ∈ A. Hence g(x 0) = y2 < V. Contradiction.  Fact 3.16.6. There is a ∆11 function P0 : [ω 2]3E2 → ω 3 so that on any E2 -tree p, P0  [[p]]3E2 is not continuous. Proof. Apply Lemma 3.16.5 to X = [ω 2]3E2 , Y = ω 3, B = {[[p]]3E2 : p is an E2 -tree}, f the function P from Fact 3.16.3, and A = {z ∈ ω 3 : (∃k)(∀n > k)(z(n) = 0)}. It remains to show that these objects satisfy the required properties of Lemma 3.16.5. Fix an E2 -tree p. Let (mk : k ∈ ω), g : <ω 2 → <ω 2, and Φ be the objects associated with p from the definition of an E2 -tree. Fact 3.16.3 implies P[[[p]]3E2 ] = ω 3. Hence there is some (x, y, z) ∈ [[p]]3E2 so that P(x, y, z) < A. Let U ⊆ [ω 2]3E2 be open so that U ∩ [[p]]3E2 , ∅. There are some s, t, u ∈ <ω 2 so that ∅ , Ns,t,u ∩ [[p]]3E2 ⊆ U ∩ [[p]]3E2 . Let x 0 = sˆ0̃, y0 = tˆ1̃, and z0 = uˆf 01. Using the computation from the proof of Fact 3.16.3, if k is chosen so that L k ≥ m|s| , then for all n > k, P(Φ(x 0), Φ(y0), Φ(z0))(n) = 0. Hence (Φ(x 0), Φ(y0), Φ(z0)) ∈ U ∩ [[p]]3E2 and P(Φ(x 0), Φ(y0), Φ(z0)) ∈ A.  72 Theorem 3.16.7. There is a ∆11 function K : 3 (ω 2) → ω 2 so that for any Σ11 set A with E2 ≤∆1 E2  A, 1 K  A is not continuous. Proof. Use the usual arguments to adjust the domain and range of the function from Fact 3.16.6. Then apply Fact 3.14.14.  Corollary 3.16.8. E2 does not have the 3-Mycielski property. Proof. Let C ⊆ 3 (ω 2) be any comeager set so that K  C is continuous. Then C witnesses the failure of the 3-Mycielski property for E2 .  3.17 The Structure of E3 This section will give the characterization of E3 -big Σ11 sets coming from its dichotomy result. See the references mentioned below for the details. Definition 3.17.1. E3 is the equivalence relation on ω (ω 2) defined by x E3 y if and only if (∀n)(x(n) E0 y(n)). Definition 3.17.2. Let h·, ·i : 2 ω → ω be some recursive pairing function. Let π1, π2 : 2 ω → ω be projections onto the first and second coordinate, respectively. Let A ⊆ ω. Define dom(A) = {(i, j) : hi, ji ∈ A}. If A ⊆ ω is finite, let L(A) = sup π1 [dom(A)]. If s ∈ n 2, let grid(s) : dom(n) → 2 be defined by grid(s)(i, j) = s(hi, ji). Definition 3.17.3. Z2 is the group (2, +Z2, 0) where +Z2 is modulo 2 addition and 0 denotes the identity element. ω ω Let ω Z2 = (ω 2, + Z2, 0̃) where + Z2 is the coordinate-wise addition of +Z2 and 0̃ is the constant 0 function. ω ω ω ω ω Let ω (ω Z2 ) = (ω (ω 2), + ( Z2 ), 0̄) where + ( Z2 ) is the coordinate-wise addition of + Z2 and 0̄ ∈ ω (ω 2) is defined by 0̄(k)( j) = 0 for all k, j ∈ ω. Let Z ⊆ ω 2 be defined by Z = {x ∈ ω 2 : (∃k)(∀ j > k)(x( j) = 0)}. É ωZ 2 , 0̃) is the ω-direct product of Z . 2 n∈ω Z2 = (Z, + É É ω (ω Z ) ω( ω 2 , 0̄) is the ω-product of n∈ω Z2 ) = ( Z, + n∈ω Z2 . 73 É If g ∈ ω ( n∈ω Z2 ), define supp (g) = {n ∈ ω : g(n) , 0̃}. É ω( ω ω ω ω ω ω n∈ω Z2 ) acts on ( 2) by left addition when ( 2) is considered as ( Z2 ). That is, g · x = ω (ω Z ) 2 g+ x. É Fact 3.17.4. x E3 y if and only if there is a g ∈ ω ( n∈ω Z2 ) so that x = g · y. É Definition 3.17.5. A grid system is a sequence (gs,t : s, t ∈ <ω 2 ∧ |s| = |t|}) in ω ( n∈ω Z2 ) with the following properties: ω (I) If s, t, u ∈ n 2 for some n ∈ ω, then gs,u = gt,u + ( É n∈ω Z2 ) gs,t . (II) For all m ≤ n, s, t ∈ n 2, u, v ∈ m 2 and l ∈ π1 [dom(n)] with u ⊆ s, and v ⊆ t, if grid(s)  dom(n \ m) ∩ ((l + 1) × ω) = grid(t)  dom(n \ m) ∩ ((l + 1) × ω) then for all i ≤ l, gs,t (i) = gu,v (i). Fact 3.17.6. Let B ⊆ ω (ω 2) be Σ11 so that E3  B ≡∆1 E3 . Then there is a continuous injective map 1 Φ : ω (ω 2) → ω (ω 2), a grid system (gs,t : s, t ∈ <ω 2 ∧ |s| = |t|), and sequences (ki : i ∈ ω) and (pm,i : m, i ∈ ω) in ω with the following properties: (i) Φ[ω (ω 2)] ⊆ B. (ii) If s, t ∈ n 2, then supp (gs,t ) ⊆ (k L(n) + 1). (iii) For each m ∈ ω, (ki : i ∈ ω) and (pm,i : i ∈ ω) are strictly increasing sequences. (iv) For all x, y ∈ ω (ω 2) and m, j ∈ ω, if x(m)( j) = 0 and y(m)( j) = 1, then Φ(x)(k m )(pm, j ) = 0 and Φ(y)(k m )(pm, j ) = 1. (v) Let x, y ∈ ω (ω 2) and l ∈ ω. Suppose    ∀(i, j) ∈ ((l + 1) × ω) \ dom(n) x(i)( j) = y(i)( j) . Let s, t ∈ n 2 be such that for all (i, j) ∈ dom(n), grid(s)(i, j) = x(i)( j) and grid(t)(i, j) = y(i)( j). Then (gs,t · Φ(x))(l) = Φ(y)(l). Proof. This is implicit in [9]. See the presentation in [13] Chapter 14, especially Section 14.5 and 14.6.  Note that Φ as above is an E3 reduction. 74 3.18 E3 Does Not Have the 2-Mycielski Property Definition 3.18.1. For each s ∈ <ω 2, let Ngrid(s) = {x ∈ ω (ω 2) : (∀(i, j) ∈ dom(|s|))(x(i)( j) = s(hi, ji))}. Each Ngrid(s) is an open neighborhood of ω (ω 2) and also the collection {Ngrid(s) : s ∈ <ω 2} forms a basis for the topology of ω (ω 2). When σ : m → <ω 2, then Nσ will refer to the usual basic open neighborhood of ω (ω 2). Both types of open sets will be used in the proof of the following result. Theorem 3.18.2. Let D = {(x, y) ∈ 2 (ω (ω 2)) : x(0) , y(0)}. D is dense open. For all Σ11 sets B ⊆ ω (ω 2) with E3  B ≡∆1 E3 , [B]2E3 * D. 1 E3 does not have the 2-Mycielski property. Proof. Suppose (x, y) ∈ D. There is some n so that x(0)(n) , y(0)(n). Define σ, τ : 1 → <ω 2 by σ(0) = x(0)  (n + 1) and τ(0) = y(0)  (n + 1). Then (x, y) ∈ Nσ,τ ⊆ D. D is open. Suppose σ, τ : m → <ω 2 have the property that for all k < m, |σ(k)| = |τ(k)|. Define σ0, τ0 : m → <ω 2 by      σ(k)   τ(k)  k,0 k,0 0 0 σ (k) = and τ (k) =    σ(k)ˆ0  τ(k)ˆ1 k=0 k=0   Nσ 0,τ 0 ⊆ Nσ,τ and Nσ 0,τ 0 ⊆ D. D is dense open. Fix Φ and the other objects specified by Fact 3.17.6. Note that for any s ∈ <ω 2, gs,s = 0̄. In particular, g∅,∅ = 0̄. Let ρn : 1 → <ω 2 be defined by ρn (0) = Φ(0̄)(0)  n. If s ∈ <ω 2, then define xs ∈ ω (ω 2) by xs (i)( j) =    s(hi, ji)  (i, j) ∈ dom(|s|)  0  otherwise . Let s0 = ∅. Suppose one has defined sn ∈ <ω 2 so that xsn (0) = 0̃ and Φ(xsn )(0) = Φ(0̄)(0). By continuity, find some u ∈ <ω 2 with sn ⊆ u and xsn ∈ Ngrid(u) so that Ngrid(u) ⊆ Φ−1 [Nρn+1 ]. Now find the least 75 k > |u| so that k = h1, qi for some q ∈ ω. Define sn+1 ⊇ u of length k + 1 by j < |u|    u( j)     sn+1 ( j) = 1     0  j=k . otherwise Note that since xsn+1 (0) = 0̃ = 0̄(0), (g∅,∅ · Φ(xsn+1 ))(0) = Φ(0̄)(0) by condition (v) of Definition 3.17.6. This implies that Φ(xsn+1 )(0) = Φ(0̄)(0). Now define x ∈ ω (ω 2) by ! x(i)( j) = Ø grid(sn ) (i, j). n∈ω Since Ngrid(sn ) ⊆ Φ−1 [Nρn ] for all n ∈ ω, Φ(x)(0) = Φ(0̄)(0). Hence (Φ(x), Φ(0̄)) < D. However, there are infinitely many q ∈ ω so that x(1)(q) = 1. Since Φ is an E3 reduction, ¬(Φ(x) E3 Φ(0̄)). We have shown that for any map Φ as in Fact 3.17.6, [Φ[ω (ω 2)]]2E3 * D. Since any Σ11 set B ⊆ ω (ω 2) with the property that E3  B ≡∆1 E3 has some such map Φ so that Φ[ω (ω 2)] ⊆ B, no such B can 1 have the property that [B]2E3 ⊆ D. E3 does not have the 2-Mycielski property.  3.19 Completeness of Ultrafilters on Quotients Without the axiom of choice, one needs to define the notion of completeness of ultrafilters with care. Definition 3.19.1. Let X be a set. Let U be an ultrafilter on X. Let I be a set. U is I-complete if and only if for any set J which inject into I but is not in bijection with I, and any injective function Ñ f : J → U, j∈J f ( j) ∈ U. U is I + -complete if and only if for all J which inject into I and all injective functions f : J → U, Ñ j∈J f ( j) ∈ U. ℵ1 -complete is often called countably complete. A well-known result is that there are no countably complete ultrafilters on ω 2. There are countably complete ultrafilters on quotients of Polish spaces by equivalence relations. Fact 3.19.2. Let C ⊆ P(ω 2/E0 ) be defined by A ∈ C if and only if filter on ω 2. C is a countably complete ultrafilter on ω 2/E0 . 76 Ð A belongs to the comeager Proof. C is an ultrafilter follows from the generic ergodicity of E0 . Countable completeness is clear; in fact under AD, every ultrafilter is countably complete.  A natural question is whether this ultrafilter or any ultrafilter on ω 2/E0 could be more than just countably complete. R injects into ω 2/E0 . Is C R+ -complete? Note the function f in Definition 3.19.1 is required to be injective. Otherwise this notion becomes clearly trivial using the function f : R → C defined by x 7→ (ω 2/E0 ) \ {[x]E0 }. The next fact will show using a modification of the above function that there are no nonprincipal R+ -complete ultrafilters on quotients of Polish spaces. Fact 3.19.3. (ZF + AD) Suppose E is an equivalence relation on a Polish space X so that =≤ E (where ≤ denotes the existence of a reduction). Then no nonprincipal ultrafilter on X/E is R+ complete. Proof. Let U be a nonprincipal (R)+ -complete ultrafilter on X/E. Let Ψ : ω 2 → X be a reduction witnessing =≤ E. Let Φ : ω 2 → X/E be defined by Φ(x) = [Ψ(x)]E . Φ is an injective function. Ñ Let L̃ = (X/E) \ Φ[ω 2] = x∈ω 2 (X/E) \ {Φ(x)}. L̃ ∈ U since U is both nonprincipal and R+ -complete. Ð Let L = L̃. L must be uncountable. Hence L is in bijection with ω 2. Define f : L → (X/E) by f (x) = (X/E) \ {[x]E , Φ(x)} To show f is injective, it suffices to show that the map on L defined by x 7→ {[x]E , Φ(x)} is injective: Suppose x , y and {[x]E , [Ψ(x)]E } = {[y]E , [Ψ(y)]E }. Since Ψ is a reduction, ¬(Ψ(x) E Ψ(y)). Therefore, one must have that x E Ψ(y). This is impossible since [x]E ∈ (X/E) \ Φ[ω 2]. This shows f is injective. Ñ Ñ Since for all x ∈ L, [x]E < f (x), L̃ ∩ x∈L f (x) = ∅. Since L̃ ∈ U, x∈L f (x) < U. U is not R+ -complete. Contradiction.  Fact 3.19.4. (ZF + ADR or ZF + AD+ + V = L(P(R)) Let X be a Polish space and E be an equivalence relation on ω 2. If ω 2/E is not well-ordered, then there is no R+ -complete nonprincipal ultrafilter on X/E. Proof. Under ZF + ADR , results of Woodin and Martin show that every set of reals is κ-Suslin for some κ < Θ. So the complement of E is κ-Suslin for some κ < Θ. In ZF + AD, [6] showed that 77 if the complement of E is κ-Suslin, then either the identity reduces into E or ω 2/E is in bijection with a cardinal less than or equal to κ (and hence can be well-ordered). Under ZF + AD+ + V = L(P(R), [2] Theorem 1.4 (along with [2] Corollary 3.2) states that for any set X, either X is wellordered or R injects into X. In either case, the result now follows from 3.19.3. 3.20  Conclusion This section includes some questions. Question 3.20.1. Under ZF + ¬ACRω , can there be ω-Jónsson functions for ω 2? In particular, is there an ω-Jónsson function for ω 2 in the Cohen-Halpern-Lévy model H (see Question 3.4.2)? Question 3.20.2. It was shown that E2 does not have the 2-Mycielski property. An interesting question would be: what is the relation between the n-Mycielski property, n-Jónsson property, and the surjectivity properties in dimension n for E2 ? In particular, does the 2-dimensional version of the results in Section 3.16 hold? Does ω 2/E2 have the 2-Jónsson property, 3-Jónsson property, or full Jónsson property? Question 3.20.3. For E1 and E3 , this paper only considers the Mycielski property. One can ask about some of the other properties of E1 or E3 which had been studied for E0 and E2 . For example: Does ω (ω 2)/E1 or ω (ω 2)/E3 have the Jónsson property? Question 3.20.4. Assuming determinacy, if R/E0 injects into a set X, can X have the Jónsson property? More specifically, if E is a ∆11 equivalence relation on R so that E0 ≤∆1 E, can R/E 1 have the Jónsson property? 78 Chapter 4 79 FRACTIONAL BOREL CHROMATIC NUMBERS AND DEFINABLE COMBINATORICS 4.1 Introduction A graph is an ordered pair G = (X, G), where X is a set and G ⊆ X × X is symmetric and irreflexive. For any set Y , a Y -colouring on G is a function c : X → Y such that if x G y, then c(x) , c(y). The chromatic number χ(G) is then the minimum cardinality of Y such that there is a Y -colouring of G. A slight generalization of this is as follows: if b ≥ 1 is an integer and Y is a set of colours, a b-fold colouring of a graph G = (X, G) is an assignment C : X → [Y ]b (the subsets of Y of size b) such that if x G y, then C(x) ∩ C(y) = ∅. If |Y | = a ∈ N, then C is an a : b-colouring. The b-fold chromatic number χ(b) (G) is then defined exactly as the regular chromatic number. Since χ(b) (G) = χ(G) whenever χ(G) is infinite, the notion is only interesting when χ(G) is finite. In  this case, the sequence χ(b) (G) b≥1 is subadditive [26]. The fractional chromatic number of such a graph G is χ f (G) = limb→∞ χ b(G) = inf b χ b(G) . (b) (b) As with many combinatorial notions, the field of descriptive set theory is interested in how the study changes when one restricts the focus to only definable objects. The subfield known as descriptive graph combinatorics began in the paper of Kechris, Solecki, and Todorčević [15] and is comprehensively reviewed in [19]. In case X is a standard Borel space, we can consider analogous definable notions of colouring. If α is a class of functions between standard Borel (or Polish) spaces (such as Borel functions), we define the α-chromatic number χα (G) to be the minimum cardinality of a standard Borel Y such that there is a Y -colouring of G in the class α. In this paper, we will be interested in the cases α = B, the Borel functions, α = BM, the Baire measurable functions, and α = µ, the µ-measurable functions for µ a Borel probability measure on X. It will occasionally be helpful to also denote the classical chromatic number χ as χc to fit with this convention. In case χα (G) is finite, we can f analogously define χα(b) (G) for every b ≥ 1, in addition to χα (G). Given graphs G0 = (X, G0 ) and G1 = (Y, G1 ), a homomorphism from G0 to G1 is a function f : X → Y such that for every a, b ∈ X, a G0 b implies that f (a) G1 f (b). In this case, we write G0  G1 , and we write G0 B G1 if X, Y are standard Borel and f is Borel. It is easy to see that G0 B G1 implies that χB (G0 ) ≤ χB (G1 ). The classical chromatic number is a celebrated invariant of graph theory. The fractional chromatic number uncovers some answers to related combinatorial problems. Scheinerman and Ullman [26] give the following example: suppose we have a set of committees who require hour-long meetings with graph relation G determining that two committees cannot meet at the same time. If G = C5 , the cycle on 5 vertices, then since χ(C5 ) = 3, all meetings can take place within 3 hours. However, since there is a 5 : 2-colouring of C5 , they may take place in 2.5 hours if the hour-long meetings can be split into 2 parts. The fractional chromatic number χ f satisfies χ f ≤ χ by its definition. It also can take any value in {0} ∪ {1} ∪ [2, ∞). Lastly, if χ f (G) = 2, it follows that χ(G) = 2 since both are equivalent to the characterization that G has no odd cycles. In descriptive graph combinatorics, it is common to examine which theorems of classical combinatorics remain true in the definable setting and to determine what the analog is for those that do not. In this paper, we begin what appears to be the first examination of the fractional Borel chromatic number. In section 4.2, we review basic facts about the fractional chromatic number that we will require in the paper. In particular, we show that for any values 2 < χ f ≤ χ, there is a countable graph attaining these values. In sections 4.3 and 4.4, we prove that an analog of this is true for both the Baire measurable and the µ-measurable chromatic number. In fact, this is due to a more general phenomenon. Given a countable graph, one may recreate it as a graph on a Polish space that is acyclic but such that any Baire measurable colouring must essentially follow the rules of classical colouring on the original graph. The exact statements are: Theorem 4.3.1. Let G = (Y, G) be a countable graph. There exists a Borel graph G0 = ω 2 × Y, G0 such that
1. if y0 G y1 , then for all nonmeager B0, B1 ⊆ ω 2, there exist x0 ∈ B0 and x1 ∈ B1 with (x0, y0 ) G0 (x1, y1 ); and 2. if ¬y0 G y1 , then for all x0, x1 ∈ ω 2, we have ¬(x0, y0 ) G0 (x1, y1 ). Theorem 4.4.1. Let G = (Y, G) be a countable graph and let µ be Lebesgue measure on [0, 1]. There exists a Borel graph G0 = ([0, 1] × Y, G0) such that 80 1. if y0 G y1 , then for all non µ-null B0, B1 ⊆ [0, 1], there exist x0 ∈ B0 and x1 ∈ B1 with (x0, y0 ) G0 (x1, y1 ); and 2. if ¬y0 G y1 , then for all x0, x1 ∈ [0, 1], we have ¬(x0, y0 ) G0 (x1, y1 ). These theorems essentially allow one to strip away the original combinatorics of the graph at a classical scale (by making it acyclic and hence bipartite) while leaving the original combinatorics intact at a definable scale. In section 4.5, we then show that these two theorems can be freely combined: Theorem 4.5.1. For any possible way of assigning values from the set [2, ∞) to χ, χµ , χBM , χB , and their fractional counterparts that is consistent with the obvious (classical) conditions, there is a Borel graph G on a Polish space X with a probability measure µ realizing these eight values. Lastly, in Section 4.6, we show perhaps the most interesting fact: the rule that χ f (G) = 2 implies that χ(G) = 2 does not transfer over to the definable case. f Theorem 4.6.1. There exists a Borel graph on a Polish space X with χB (G) = 2, but χB (G) = 3. In light of this fact, we theorize that one should be able to replace 3 in the above theorem with n for any n ≥ 4. 4.2 Elementary Facts about the Fractional Chromatic Number First, we will observe that one can make the gap between χ f and χ arbitrarily large with finite graphs. Definition 4.2.1. Given positive integers a, b with a ≥ 2b, define Ka:b ⊆ [a]b × [a]b by s Ka:b t ⇔ s∩t = ∅   and let Ka:b = [a]b , Ka:b . Graphs of the form Ka:b are known as Kneser graphs. It is known (see Section 3.2 of [26]) that χ f (Ka:b ) = ab and χ (Ka:b ) = a − 2b + 2. Lemma 4.2.2. Given any integers n ≥ 1 and m ≥ 3, there is a finite graph G with χ f (G) = 2 + 1n and χ(G) = m. Proof. Let G = K(m−2)(2n+1):(m−2)n .  81 If Cm is the cycle graph on m vertices, then χ f (C2m+1 ) = 2 + m1 [26]. Hence, for an arbitrary graph G, χ f (G) = 2 implies the lack of odd cycles and hence χ f (G) = 2 ⇒ χ(G) = 2. It will be useful to define a special graph. Let X = [0, 1) regarded as the circle, i.e. equipped with the metric d(x, y) = min {|x − y| , 1 − |x − y|} . Definition 4.2.3. Given any real number r ≥ 2, define Gr ⊆ X 2 by x Gr y ⇔ d(x, y) ≥ 1 . r Let Gr = (X, Gr ). Clearly, Gr is closed and hence Borel. Lemma 4.2.4. Given any real r ≥ 2 and positive integers c, d such that r ≤ dc , there exists a Borel f c : d-colouring of Gr . In particular, χB (Gr ) ≤ r and χB (Gr ) ≤ dre.  i i+1  Proof. Define the map f : [0, d) → c by f (x) = i ⇔ x ∈ r , r . Since rc ≥ d, f indeed maps into c. Then define g : X → [c]d by g(x) = { f (x), f (x + 1), . . . , f (x + d − 1)} . Clearly, g is a Borel map. It is straightforward to check by a case analysis that g is a c : d-colouring of Gr .  Definition 4.2.5. Given positive integers a, b with a ≥ 2b, let i G a,b j ⇔ j ∈ {i + b, i + b + 1, . . . , i + a − b} (mod a)
for i, j < a and let Ga,b = a, G a,b .
It is known [26] that χ f Ga,b = ab . In fact, we can slightly improve this statement. Proposition 4.2.6. For all positive integers a, b with a ≥ 2b, Ga,b  G ba . In particular, if c, d are positive integers with ab ≤ dc , then there is a c : d-colouring of Ga,b . Proof. Define φ : a → X by φ(i) = ai . It is straightforward to check that φ is an embedding of Ga,b into G ba .  The reason that Proposition 4.2.6 is useful is that we can find relatively nice d-fold colourings for a countable disjoint union of graphs of the form Ga,b . This yields the following result: 82 Lemma 4.2.7. Given any real α > 2 and any integer m ≥ α, there exists a countable graph G with χ f (G) = α and χ(G) = m. Proof. Choose sequences pi, qi of positive integers such that 2 ≤ qpii ≤ α and qpii → α. Let
à G1 = i<ω G pi,qi . Then χ f (G1 ) ≥ χ f G pi,qi = qpii , so χ f (G1 ) ≥ α. Given dc ≥ α, since dc ≥ qpii , we can find a c : d-colouring of each G pi,qi and hence a c : d-colouring of G by joining these together, showing χ f (G1 ) = α. It follows that χ(G1 ) = dαe by using the above argument with c = dαe and d = 1. Then choose m ≥ 1 so that 2 + 1n ≤ α and let G2 be a finite graph with χ f (G2 ) = 2 + 1n and χ(G2 ) = m, as furnished by Lemma 4.2.2.  4.3 The Baire Measurable Case We first handle the Baire measurable case, showing that we can construct an acyclic graph that f sets χBM and χBM to any possible values we wish them to be. Our construction follows that of Miller [23], who showed that the equivalence relation E0 on ω 2 can be treed by a graph relation  G such that χBM (G) = κ for any κ ∈ 2, 3, . . . , ℵ0, 2ℵ0 . In effect, for finite n, Miller divided the space ω 2 into n subspaces such that every Baire measurable colouring could not assign the same colour to nonmeager subsets of different subspaces. We generalize this below; as Miller’s graph was to Kn , so ours is to an arbitrary countable graph G. Theorem 4.3.1. Let G = (Y, G) be a countable graph. There exists a Borel graph G0 = ω 2 × Y, G0 such that
1. if y0 G y1 , then for all nonmeager B0, B1 ⊆ ω 2, there exist x0 ∈ B0 and x1 ∈ B1 with (x0, y0 ) G0 (x1, y1 ); and 2. if ¬y0 G y1 , then for all x0, x1 ∈ ω 2, we have ¬(x0, y0 ) G0 (x1, y1 ). f In particular, we have that χ (G0) = χ f (G0) = 2, χBM (G0) = χB (G0) = χ (G), and χBM (G0) = f χB (G0) = χ f (G). Proof. As mentioned above, most of our construction works due to Miller’s argument in [23]. Enumerate Y as {yi }i<|Y | . Because <ω 2 is countable, we can pick sequences {un }, {vn } in <ω 2 such that for each n, un, vn are of length n + 1, un (n) , vn (n), there exist i , j such that 0i_ 1 ⊆ un and 0 j_ 1 ⊆ vn , and for any such pair u, v ∈ <ω 2, there exists n ∈ N with u ⊆ un and v ⊆ vn . We then define G0 by 83 (x0, yi )G0(x1, y j ) ⇔  i_ _ yi Gy j ∧ ∃n un ⊆ 0 1 x0 ∧ vn ⊆ 0 j_ _ 1 x1 ∧ ∀m ≥ n + 1  i_ _   0 1 x (m) = 0 j_ _  1 y (m)  . By our choice of sequences {un }, {vn }, G0 is acyclic. Property (2) is also immediately clear from the definition of the graph. To prove property (1), suppose that yi G y j . Choose u, v ∈ <ω 2 such that B0 is comeager in Nu and B1 is comeager in Nv . Then by our choice of {un }, {vn }, there exists an n with 0i_ 1_ u ⊆ un and 0 j_ 1_ v ⊆ vn . Define u0, v 0 so that 0i_ 1_ u0 = un and 0 j_ 1_ v 0 = vn . If we choose x ∈ ω 2 such
that u0_ x ∈ B0 and v 0_ x ∈ B1 , then we have (u0_ x, yi ) G0 v 0_ x, y j . f Colouring G0 according to the colouring of G shows that χB (G0) ≤ χ (G) and χB (G0) ≤ χ f (G). If c is a Baire measurable k-fold colouring of G0, then define an induced function c0 on Y by setting c0(y) to be some k-set whose preimage under c is nonmeager in ω 2 × {y}. Then property (1) shows (k) (G0) ≥ χ(k) (G) for every k ∈ N. This shows that c0 must be a k-fold colouring of G. Hence χBM f  that χBM (G0) ≥ χ (G) and χBM (G0) ≥ χ f (G). One can view the graph from Theorem 4.3.1 in the following way: each vertex from the original countable graph Y has been enlarged from a single point to become the Polish space ω 2. Then “almost all” of the points in a pair of these “enlarged vertices” are connected in the graph G0 if and only if they were connected in G. The connections are in a definable way such that the resulting graph is acyclic. So from a classical viewpoint, the graph is bipartite and hence has lost its original structure. But from a definable view, the combinatorics of the graph have been preserved. f Corollary 4.3.2. For nany assignment χ, χ f , χBM , χBM ∈ [2, ∞) that obeys the o nof the quantities o f f f conditions χ f ≤ min χ, χBM , max χ, χBM ≤ χBM , χ, χBM ∈ N, and χα = 2 ⇒ χα = 2 for α ∈ {c, BM }, there exists a Borel graph G on a Polish space X whose chromatic numbers satisfy this assignment. Proof. Let G0, G1 be countable graphs with chromatic numbers χBM and χ and fractional chromatic f number χBM and χ f , respectively. Then let G0 be the Borel graph obtained from G0 as in Theorem 4.3.1 and let G be the disjoint union of G0 and G1 .  84 4.4 The µ-Measurable Case We wish to repeat Section 4.3 for µ-measurable colourings, and so we require a new construction. This time, we modify a graph constructed by Laczkovich as noted in the appendix of [15]. Laczkovich divides the interval [0, 1] into n subspaces in such a way that any Lebesgue measurable colouring must restrict each colour almost everywhere to a particular subspace. This was an early example of a graph for which χ(G) = 2 but χB (G) = n for any n. Again, we modify the graph to do the same to any countable graph as the original one did to Kn . Theorem 4.4.1. Let G = (Y, G) be a countable graph and let µ be Lebesgue measure on [0, 1]. There exists a Borel graph G0 = ([0, 1] × Y, G0) such that 1. if y0 G y1 , then for all non µ-null B0, B1 ⊆ [0, 1], there exist x0 ∈ B0 and x1 ∈ B1 with (x0, y0 ) G0 (x1, y1 ); and 2. if ¬y0 G y1 , then for all x0, x1 ∈ [0, 1], we have ¬(x0, y0 ) G0 (x1, y1 ). In particular, if we let µ0 be a product measure on we have that χ (G0) = χ f (G0) = 2, χµ (G0) = f f χB (G0) = χ (G), and χµ (G0) = χB (G0) = χ f (G). Proof. We will instead construct our Borel graph on a Borel subset X ⊆ [0, 1] and argue that  it is isomorphic to a graph with the properties above. Let U = (a, b, c, d) ∈ R4 : ad − bc , 0 . Then U is open and hence we may find a sequence {(a k , b k , ck , dk )} that is dense in U and such that {a k , b k , ck , dk : k ∈ N} is algebraically independent over the rationals. Define fk on R by x+bk . By a theorem of J. von Neumann [24], the linear fractional transformations fk fk (x) = ackk x+d k generate a free group H under composition. Let X ⊆ [0, 1) be the cocountable set of all real numbers that are not fixed points of any non-identity member of H. Enumerate Y as {yi }i<|Y | . Define G0 on X × X by ! G0 = Ø Ø © ª graph ( fk ) ∩ ­­ [1 − 2−i, 1 − 2−(i+1) ) × [1 − 2− j , 1 − 2−( j+1) )®® . k∈N «(i, j)∈ {(i, j):i, j<|Y |∧yi G y j } ¬ We can convert G0 to be of the form required in the theorem statement by fixing a measurepreserving Borel isomorphism of X ∩ [1 − 2−i, 1 − 2−(i+1) ) with [0, 1] × {yi }. Hence we prove the associated statements for the graph G0 = (X, G0). 85 Property (2) is again immediately clear from the definition of the graph. If we have two subsets Bi ⊆ X ∩ [1 − 2−i, 1 − 2−(i+1) ) and B j ⊆ X ∩ [1 − 2− j , 1 − 2−( j+1) ) with yi G y j that have positive Lebesgue measure, then we can find points ti ∈ Bi and t j ∈ B j that are Lebesgue points of density. Choose ε > 0 such that if k ∈ {i, j} and 0 < h < ε, then [t k , t k + h) ⊆ [1 − 2−k , 1 − 2−(k+1) ) 1 9 h. Then for any C 1 function f on [0, 1] such that | f 0 − 1| < 10 ε and and µ (Bk ∩ [t k , t k + h)) > 10 1 ε, it follows that f (Bi ) ∩ B j , ∅. For (a, b, c, d) sufficiently close to (1, t j − ti, 0, 1), f (ti ) − t j < 10 ax+b these conditions hold for the associated linear fractional transformation cx+d . Hence by density there is some k such that fk (Bi ) ∩ B j , ∅. Choosing x0 ∈ Bi with x1 = f (x0 ) ∈ B j , we prove the analog of property (1). If we colour each point in X ∩ [1 − 2−i, 1 − 2−(i+1) ) according to the colour of yi , we obtain that f χµ (G0) ≤ χ (G) and χµ (G0) ≤ χ f (G). If c is a µ-measurable k-fold colouring of G0, then define an induced function c0 on Y by setting c0(y) to be some k-set whose preimage under c is not µ-null in X ∩ [1 − 2−i, 1 − 2−(i+1) ). Then property (1) shows that c0 must be a k-fold colouring of G. Hence f χµ(k) (G0) ≥ χ(k) (G) for every k ∈ N. This shows that χµ (G0) ≥ χ (G) and χµ (G0) ≥ χ f (G).  As before, we have the following immediate corollary, which is proved exactly as Corollary 4.3.2 was. f Corollary 4.4.2. For ofo the quantities χ, χ f , χµ, χµ ∈ [2, ∞) that obeys the conn anyo assignment n f f f ditions χ f ≤ min χ, χµ , max χ, χµ ≤ χµ , χ, χµ ∈ N, and χα = 2 ⇒ χα = 2 for α ∈ {c, µ}, there exists a Borel graph G on a standard Borel space X and a probability measure µ on X whose chromatic numbers satisfy this assignment. 4.5 Combining All Quantities We can combine Theorems 4.3.1 and 4.4.1 to create a Borel graph that handles all quantities considered in this paper at the same time. Theorem 4.5.1. For any possible way of assigning values from the set [2, ∞) to χ, χµ , χBM , χB , and their fractional counterparts that is consistent with the conditions   1. χ ≤ min χµ, χBM and max χµ, χBM ≤ χB , and similarly for the fractional counterparts; f 2. χα ≤ χα for every α ∈ {c, µ, BM, B}; 3. χ, χµ , χBM , χB ∈ N; and f 4. χα = 2 ⇒ χα = 2 for every α ∈ {c, µ, BM, B}; 86 there is a Borel graph G on a Polish space X with a probability measure µ realizing these eight values. If χ = 2, the graph can be chosen to be acyclic. Proof. Let Gc = (Xc, G c ) be a countable graph with χ and χ f as desired (in particular, take Gc to be acyclic if χ = 2). For each α ∈ {µ, BM, B}, use Corollaries 4.3.2 and 4.4.2 to create a f graph Gα = (Xα, G α ) on a Polish space satisfying the specified values of χα and χα . Then define G = Gc t GBM t G µ t GB , where Xc, Xµ , and XB are considered meager, and Xc, XBM , and XB are considered µ-null. Because Gα is acyclic for α ∈ {µ, BM, B}, it follows that χ (G) = χ (Gc ) = χ and χ f (G) = χ f . Because G µ and GB have Baire measurable 2-colourings (when considered f f subgraphs of G), χBM (G) and χBM (G) are as desired. Similarly, χµ (G) and χµ (G) are as desired f because χBM and χB have µ-measurable 2-colourings. Finally, χB (G) and χB (G) are as desired because these are the largest quantities.  4.6 f The χB (G) = 2 Case We noted in Section 4.1 that if χ f (G) = 2 for a graph G, this implies that χ(G) = 2 as well, since both conditions are equivalent to the lack of odd cycles. This classical reasoning has no obvious counterpart when moved to the definable setting. In fact, as the next example shows, there exist f Borel graphs G for which χB (G) = 2 but χB (G) > 2. f f Theorem 4.6.1. There exists a Borel graph on a Polish space X with χBM (G) = χB (G) = 2 (and so χ f (G) = χ(G) = 2), but χBM = χB (G) = 3.
Proof. Let Z act on the Polish space 2Z by the shift action: (n ∗ p) (k) = p(k − n) and let Free 2Z =  p ∈ 2Z : ∀n , 0 (n ∗ p , p) . Letting S(p) = 1 ∗ p, consider the graph G = (X, graph(S)). Then G is acyclic (in fact each connected component is isomorphic to Z), and so χ (G) = 2. Kechris, Solecki, and Todorčević [15] show that χB (G) = 3 and that for each m ≥ 1, there exists a Borel subset Am ⊆ X such that for every x ∈ X, there exist i ≥ 0 and j > 0 such that Si (x), S − j (x) ∈ Am , and for the minimal such i and j, i − j ∈ {2m, 2m + 1}. It follows that for every m ≥ 1 G1 B Hm , where Hm consists of a copy of C2m and C2m+1 intersecting at exactly one point. Since χ f (Hm ) = 2 + m1 , f it follows that χB (G) = 2.  This is the first example of a major departure in the definable theory from the classical theory with f regard to this branch of combinatorics. Since it is false that χB = 2 ⇒ χB = 2, it is natural to f wonder if χB can be made arbitrarily large (but finite) while keeping χB fixed at 2. This seems likely, but no other examples are currently known. 87 f Question 4.6.2. Does there exist a Borel graph on a standard Borel space X satisfying χB (G) = 2 but χB (G) = m for m ≥ 4? Is Theorem 4.5.1 true but with condition 4 relaxed to only hold for α = c? One natural way to generalize the graph in Theorem 4.6.1 is to consider the (acyclic) shift graph
Gn on Free 2Fn . Marks [22] has shown that χB (Gn ) = 2n + 1. f Question 4.6.3. Is χB (Gn ) = 2 for each n ≥ 1? Theorem 4.6.1 shows the answer is affirmative in the case n = 1. Unfortunately, the proof of Theorem 4.6.1 seems to be too dependent on the group Z having a single generator to generalize. 88 BIBLIOGRAPHY 89 [1] Andreas Blass. A partition theorem for perfect sets. Proc. Amer. Math. Soc., 82(2):271–277, 1981. ISSN 0002-9939. doi: 10.2307/2043323. URL http://dx.doi.org/10.2307/ 2043323. [2] Andrés Eduardo Caicedo and Richard Ketchersid. A trichotomy theorem in natural models of AD+ . In Set theory and its applications, volume 533 of Contemp. Math., pages 227– 258. Amer. Math. Soc., Providence, RI, 2011. doi: 10.1090/conm/533/10510. URL http: //dx.doi.org/10.1090/conm/533/10510. [3] William Chan and Connor Meehan. Definable combinatorics of some borel equivalence relations. arXiv preprint arXiv:1709.04567, 2017. [4] Keith J. Devlin. Some weak versions of large cardinal axioms. Ann. Math. Logic, 5:291–325, 1972–1973. ISSN 0168-0072. [5] P. Erdős and A. Hajnal. On a problem of B. Jónsson. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 14:19–23, 1966. ISSN 0001-4117. [6] L. Harrington and R. Sami. Equivalence relations, projective and beyond. In Logic Colloquium ’78 (Mons, 1978), volume 97 of Stud. Logic Foundations Math., pages 247–264. NorthHolland, Amsterdam-New York, 1979. [7] L. A. Harrington, A. S. Kechris, and A. Louveau. A Glimm-Effros dichotomy for Borel equivalence relations. J. Amer. Math. Soc., 3(4):903–928, 1990. ISSN 0894-0347. doi: 10.2307/1990906. URL http://dx.doi.org/10.2307/1990906. [8] G. Hjorth. Actions by the classical Banach spaces. J. Symbolic Logic, 65(1):392–420, 2000. ISSN 0022-4812. doi: 10.2307/2586545. URL http://dx.doi.org/10.2307/2586545. [9] Greg Hjorth and Alexander S. Kechris. Recent developments in the theory of Borel reducibility. Fund. Math., 170(1-2):21–52, 2001. ISSN 0016-2736. doi: 10.4064/fm170-1-2. URL http://dx.doi.org/10.4064/fm170-1-2. Dedicated to the memory of Jerzy Łoś. [10] Jared Holshouser. Partition Properties for Non-Ordinal Sets. PhD thesis, University of North Texas, 2017. [11] Jared Holshouser and Stephen Jackson. Partition properties for hyperfinite quotients. To appear. [12] S. Jackson, R. Ketchersid, F. Schlutzenberg, and W. H. Woodin. Determinacy and Jónsson cardinals in L(R). J. Symb. Log., 79(4):1184–1198, 2014. ISSN 0022-4812. doi: 10.1017/ jsl.2014.49. URL http://dx.doi.org/10.1017/jsl.2014.49. [13] Vladimir Kanovei. Borel equivalence relations, volume 44 of University Lecture Series. American Mathematical Society, Providence, RI, 2008. ISBN 978-0-8218-4453-3. doi: 10.1090/ulect/044. URL http://dx.doi.org/10.1090/ulect/044. Structure and classification. [14] Vladimir Kanovei, Marcin Sabok, and Jindřich Zapletal. Canonical Ramsey theory on Polish spaces, volume 202 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2013. ISBN 978-1-107-02685-8. doi: 10.1017/CBO9781139208666. URL http://dx.doi.org/10.1017/CBO9781139208666. [15] A. S. Kechris, S. Solecki, and S. Todorcevic. Borel chromatic numbers. Adv. Math., 141(1): 1–44, 1999. ISSN 0001-8708. doi: 10.1006/aima.1998.1771. URL http://dx.doi.org/ 10.1006/aima.1998.1771. [16] Alexander S. Kechris. The axiom of determinacy implies dependent choices in L(R). J. Symbolic Logic, 49(1):161–173, 1984. ISSN 0022-4812. doi: 10.2307/2274099. URL http://dx.doi.org/10.2307/2274099. [17] Alexander S. Kechris. Classical descriptive set theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. ISBN 0-387-94374-9. doi: 10.1007/978-14612-4190-4. URL http://dx.doi.org/10.1007/978-1-4612-4190-4. [18] Alexander S. Kechris and Alain Louveau. The classification of hypersmooth Borel equivalence relations. J. Amer. Math. Soc., 10(1):215–242, 1997. ISSN 0894-0347. doi: 10.1090/S08940347-97-00221-X. URL http://dx.doi.org/10.1090/S0894-0347-97-00221-X. [19] Alexander S. Kechris and Andrew S. Marks. Descriptive graph combinatorics. http: //www.math.caltech.edu/~kechris/papers/combinatorics16.pdf. [20] Richard Ketchersid, Paul Larson, and Jindřich Zapletal. Ramsey ultrafilters and countableto-one uniformization. Topology Appl., 213:190–198, 2016. ISSN 0166-8641. doi: 10.1016/ j.topol.2016.08.018. URL http://dx.doi.org/10.1016/j.topol.2016.08.018. [21] Eugene M. Kleinberg. Infinitary combinatorics and the axiom of determinateness. Lecture Notes in Mathematics, Vol. 612. Springer-Verlag, Berlin-New York, 1977. ISBN 3-54008440-1. [22] Andrew Marks. A determinacy approach to borel combinatorics. arXiv:1304.3830, 2013. arXiv preprint [23] Benjamin D Miller. Measurable chromatic numbers. The Journal of Symbolic Logic, 73(4): 1139–1157, 2008. [24] J von Neumann. Zur allgemeinen theorie des masses. Fundamenta Mathematicae, 13(1): 73–116, 1929. [25] K. Palamourdas. 1, 2, 3, . . . , 2n + 1, ∞!. PhD thesis, UCLA, 2012. 90 [26] Edward R Scheinerman and Daniel H Ullman. Fractional graph theory: a rational approach to the theory of graphs. Courier Corporation, 2011. [27] Robert M. Solovay. The independence of DC from AD. In Cabal Seminar 76–77 (Proc. Caltech-UCLA Logic Sem., 1976–77), volume 689 of Lecture Notes in Math., pages 171–183. Springer, Berlin, 1978. [28] W. Hugh Woodin. The axiom of determinacy, forcing axioms, and the nonstationary ideal, volume 1 of De Gruyter Series in Logic and its Applications. Walter de Gruyter GmbH & Co. KG, Berlin, revised edition, 2010. ISBN 978-3-11-019702-0. doi: 10.1515/9783110213171. URL http://dx.doi.org/10.1515/9783110213171. [29] Jindřich Zapletal. Descriptive set theory and definable forcing. Mem. Amer. Math. Soc., 167 (793):viii+141, 2004. ISSN 0065-9266. doi: 10.1090/memo/0793. URL http://dx.doi. org/10.1090/memo/0793. [30] Jindřich Zapletal. Forcing idealized, volume 174 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2008. ISBN 978-0-521-87426-7. doi: 10.1017/ CBO9780511542732. URL http://dx.doi.org/10.1017/CBO9780511542732. 91