Forcing Arguments in Infinite RamseyTheory

Abstract

This is a contribution to combinatorial set theory, specifically to infinite Ramsey Theory, which deals with partitions of infinite sets. The basic pigeon hole principle states that for every partition of the set of all natural numbers in finitely many classes there is an infinite set of natural numbers that is included in some one class. Ramsey’s Theorem, which can be seen as a generalization of this simple result, is about partitions of the set [N]k of all k-element sets of natural numbers. It states that for every k ≥ 1 and every partition of [N]k into finitely many classes, there is an infinite subset M of N such that all k-element subsets of M belong to some same class. Such a set is said to be homogeneous for the partition. In Ramsey’s own formulation (Ramsey, [8], p.264), the theorem reads as follows.

Theorem (Ramsey). Let Γ be an infinite class, and μ and r positive numbers; and let all those sub-classes of Γ which have exactly r numbers, or, as we may say, let all r−combinations of the members of Γ be divided in any manner into μ mutually exclusive classes Ci (i = 1, 2, . . . , μ), so that every r−combination is a member of one and only one Ci; then assuming the axiom of selections, Γ must contain an infinite sub-class △ such that all the r−combinations of the members of △ belong to the same Ci.

In [5], Neil Hindman proved a Ramsey-like result that was conjectured by Graham and Rotschild in [3]. Hindman’s Theorem asserts that if the set of all natural numbers is divided into two classes, one of the classes contains an infinite set such that all finite sums of distinct members of the set remain in the same class. Hindman’s original proof was greatly simplified, though the same basic ideas were used, by James Baumgartner in [1].

We will give new proofs of these two theorems which rely on forcing arguments. After this, we will be concerned with the particular partial orders used in each case, with the aim of studying its basic properties and its relations to other similar forcing notions. The partial order used to get Ramsey’s Theorem will be seen to be equivalent to Mathias forcing. The analysis of the partial order arising in the proof of Hindmans Theorem, which we denote by PFIN, will be object of the last chapter of the thesis.

A summary of our work follows.

In the first chapter we give some basic definitions and state several known theorems that we will need. We explain the set theoretic notation used and we describe some forcing notions that will be useful in the sequel. Our notation is generally standard, and when it is not it will be sufficiently explained. This work is meant to be self-contained. Thus, although most of the theorems recorded in this first, preliminary chapter, will be stated without proof, it will be duly indicated where a proof can be found.

Chapter 2 is devoted to a proof of Ramsey’s Theorem in which forcing is used to produce a homogeneous set for the relevant partition. The partial order involved is isomorphic to Mathias forcing.

In Chapter 3 we modify Baumgartner’s proof of Hindman’s Theorem to define a partial order, denoted by PC , from which we get by a forcing argument a suitable homogeneous set. Here C is an infinite set of finite subsets of N, and PC adds an infinite block sequence of finite subsets of natural numbers with the property that all finite unions of its elements belong to C. Our proof follows closely Baumgartner’s.

The partial order PC is similar both to the one due to Matet in [6] and to Mathias forcing. This prompts the question whether it is equivalent to one of them or to none, which can only be solved by studying PC , which we do in chapter 4.

In chapter 4 we first show that the forcing notion PC is equivalent to a more manageable partial order, which we denote by PFIN. From a PFIN- generic filter an infinite block sequence can be defined, from which, in turn, the generic filter can be reconstructed, roughly as a Mathias generic filter can be reconstructed from a Mathias real.

In section 4.1 we prove that PFIN is not equivalent to Matet forcing. This we do by showing that PFIN adds a dominating real, thus also a splitting real (see [4]). But Blass proved that Matet forcing preserves p-point ultrafilters in [2], from which follows that Matet forcing does not add splitting reals. Still in section 4.1 we prove that PFIN adds a Mathias real by using Mathias characterization of a Mathias real in [7] according to which x ⊆ ω is a Mathias real over V iff x diagonalizes every maximal almost disjoint family in V . In fact, we prove that if D = (Di)i∈ω is the generic block sequence of finite sets of natural numbers added by forcing with PFIN, then both {minDi : i ∈ ω} and {maxDi : i ∈ ω} are Mathias reals. In section 4.2 we prove that PFIN is equivalent to a two-step iteration of a σ-closed and a σ-centered forcing notions.

In section 4.3 we prove that PFIN satisfies Axiom A and in section 4.4 that, as Mathias forcing, it has the pure decision property. In section 4.5 we prove that PFIN does not add Cohen reals. So far, all the properties we have found of PFIN are also shared by Mathias forcing. The question remains, then, whether PFIN is equivalent to Mathias forcing. This we solve by first showing in section 5.1 that PFIN adds a Matet real and then, in section 5.2, that Mathias forcing does not add a Matet real, thus concluding that PFIN and Mathias forcing are not equivalent forcing notions.

In the last, 5.3, section we explore another forcing notion, denoted by M2, which was introduced by Shelah in [9]. It is a kind of “product” of two copies of Mathias forcing, which we relate to denoted by M2.

Bibliography [1] J.E. Baumgartner. A short proof of Hindmanʼs theorem. Journal of Combinatorial Theory, 17:384–386, 1974. [2] A. Blass. Applications of superperfect forcing and its relatives. In Set theory and its applications. Lecture notes in Mathematics. Springer, Berlin., 1989. [3] R.L. Graham and B. L. Rothschild. Ramseyʼs theorem for n-parameter sets. Transaction American Mathematical Society, 159:257–292, 1971. [4] L. Halbeisen. A playful approach to Silver and Mathias forcing. Studies in Logic (London), 11:123142, 2007. [5] N. Hindman. Finite sums from sequences within cells of partition of N. Journal of Combinatorial Theory (A), 17:1–11, 1974. [6] P. Matet. Some filters of partitions. The Journal of Symbolic Logic, 53:540– 553, 1988. [7] A.R.D. Mathias. Happy families. Annals of Mathematical logic, 12:59– 111, 1977. [8] F.P. Ramsey. On a problem of formal logic. London Mathematical Society, 30:264–286, 1930. [9] S. Shelah and O. Spinas. The distributivity numbers of finite products of P(ω)/fin. Fundamenta Mathematicae, 158:81–93, 1998.

Aquesta tesi és una contribució a la teoria combinatria de conjunts, específcament a la teoria de Ramsey, que estudia les particions de conjunts infinits. El principi combinatori bàsic diu que per a tota partició del conjunt dels nombres naturals en un nombre finit de classes hi ha un conjunt infinit de nombres naturals que està inclòs en una de les classes. El teorema de Ramsey [6], que hom pot veure com una generalització d'aquest principi bàsic, tracta de les particions del conjunt [N]k de tots els subconjunts de k elements de nombres naturals.

Afirma que, per a cada k >/=1 i cada partició de [N]k en un nombre finit de classes, existeix un subconjunt infinit de nombres naturals, M, tal que tots els subconjunts de k elements de M pertanyen a una mateixa classe. Els conjunts amb aquesta propietat són homogenis per a la partició.

En [3], Neil Hindman va demostrar un resultat de tipus Ramsey que Graham i Rotschild havien conjecturat en [2]. El teorema de Hindman afirma que si el conjunt de nombres naturals es divideix en dues classes, almenys una d'aquestes classes conté un conjunt infinit tal que totes les sumes finites d'elements distints del conjunt pertanyen a la mateixa classe. La demostració original del Teorema de Hindman va ser simplificada per James Baumgartner en [1].

En aquesta tesi donem noves demostracions d'aquests dos teoremes, basades en la tècnica del forcing. Després, analitzem els ordres parcials corresponents i n'estudiem les propietats i la relació amb altres ordres coneguts semblants. L'ordre parcial emprat en la demostració del teorema de Ramsey és equivalent al forcing de Mathias, definit en [5]. L'ordre parcial que apareix en la prova del teorema de Hindman, que anomenem PFIN, serà l'objecte d'estudi principal de la tesi.

En el primer capítol donem algunes definicions bàsiques i enunciem alguns teoremes coneguts que necessitarem més endavant.

El segon capítol conté la demostració del teorema de Ramsey. Usant la tècnica del forcing, produïm un conjunt homogeni per a una partició donada. L'ordre parcial que utilitzem és equivalent al de Mathias.

En el tercer capítol, modifiquem la demostració de Baumgartner del teorema de Hindman per definir un ordre parcial, que anomenem PC , a partir del qual, mitjançant arguments de forcing, obtenim el conjunt homogeni buscat. Aquí, C es un conjunt infinit de conjunts finits disjunts de nombres naturals, i PC afegeix una successió de conjunts finits de nombres naturals amb la propietat de que totes les unions finites de elements d'aquesta successió pertanyen al conjunt C . A partir d'aquesta successió és fàcil obtenir un conjunt homogeni per a la partició del teorema original de Hindman. L'ordre parcial PC és similar a l'ordre definit per Pierre Matet en [4] i també al forcing de Mathias. Per això, és natural preguntar-nos si aquests ordres són equivalents o no.

En el quart capítol treballem amb un ordre parcial que és equivalent a PC i que anomenem PFIN. Mostrem que PFIN té les propietats següents:

(1) A partir d'un filtre genèric per a PFIN obtenim una successió infinita de conjunts finits de nombres naturals. Com en el cas del real de Mathias, aquesta successi_o ens permet reconstruir tot el filtre genèric.

(2) PFIN afegeix un real de Mathias, que és un "dominating real". Ara bé, si afegim un "dominating real" afegim també un "splitting real". Aquest fet ens permet concloure que PFIN no és equivalent al forcing de Matet, ja que el forcing de Matet no afegeix "splitting reals"

(3) PFIN es pot veure com una iteració de dos ordres parcials, el primer dels quals és "sigma-closed" i el segon és "sigma-centered". (4) PFIN té la "pure decision property". (5) PFIN no afegeix reals de Cohen.

En el cinquè capítol demostrem que PFIN afegeix un real de Matet i, finalment, que el forcing de Mathias no afegeix reals de Matet. Això és com demostrem que el forcing de Mathias i PFIN no són ordres equivalents.

Al final del capítol donem una aplicació de PFIN. Demostrem que un cert ordre definit per Saharon Shelah en [7], que anomenem M2, és una projecció de PFIN. Això implica que si G és un filtre PFIN-genèric sobre V, l'extensió V [G] conté també un filtre genèric per a M2. L'ordre M2 és una mena de producte de dues cópies del forcing de Mathias.

REFERÈNCIES

[1] J.E. Baumgartner. A short proof of Hindman's theorem, Journal of Combinatorial Theory, 17: 384-386, (1974). [2] R.L. Graham and B.L. Rothschild. Ramsey's theorem for m-parameter sets, Transaction American Mathematical Society, 159: 257-292, (1971). [3] N. Hindman. Finite sums from sequences within cells of partitions of N, Journal of Combinatorial Theory (A), 17: 1-11, (1974). [4] P. Matet. Some _lters of partitions, The Journal of Symbolic Logic, 53: 540-553, (1988). [5] A.R.D. Mathias. Happy families, Annals of Mathematical Logic, 12: 59-111, (1977). [6] F.P. Ramsey. On a problem of formal logic, London Mathematical Society, 30:264_D286, 1930. [7] S. Shelah and O. Spinas. The distributivity numbers of finite products of P(!)=fin, Fundamenta Mathematicae, 158:81_D93, 1998.