Dissertations / Theses on the topic 'Forcing theory'

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.

The zero forcing number is a graph parameter first introduced as a tool for solving the minimum rank problem, which is: Given a simple, undirected graph G, and a field F, let S(F,G) denote the set of all symmetric matrices A=[a_{ij}] with entries in F such that a_{ij} doess not equal 0 if and only if ij is an edge in G. Find the minimum possible rank of a matrix in S(F,G). It is known that the zero forcing number Z(G) provides an upper bound for the maximum nullity of a graph. I investigate properties of the zero forcing number, including its behavior under various graph operations.

In geometry we will consider n-dimensional generalizations of the Power of a Point Theorem and of Pascal's Hexagon Theorem. In generalizing the Power of a Point Theorem, we will consider collections of cones determined by the intersections of an (n-1)-sphere and a pair of hyperplanes. We will then use these constructions to produce an n-dimensional generalization of Pascal's Hexagon Theorem, a classical plane geometry result which states that "Given a hexagon inscribed in a conic section, the three pairs of continuations of opposite sides meet on a straight line." Our generalization of this theorem will consider a pair of n-simplices intersecting an (n-1)-sphere, and will conclude with the intersections of corresponding faces lying in a hyperplane. In graph theory we will explore the interaction between zero forcing and cut-sets. The color change rule which lies at the center of zero forcing says "Suppose that each of the vertices of a graph are colored either blue or white. If u is a blue vertex and v is its only white neighbor, then u can force v to change to blue." The concept of zero forcing was introduced by the AIM Minimum Rank - Special Graphs Work Group in 2007 as a way of determining bounds on the minimum rank of graphs. Later, Darren Row established results concerning the zero forcing numbers of graphs with a cut-vertex. We will extend his work by considering graphs with arbitrarily large cut-sets, and the collections of components they yield, to determine results for the zero forcing numbers of these graphs.

The present dissertation is a contribution to the field of Mathematical Logic and, more particularly, to the subfield of Set Theory. Within Set theory, we are mainly concerned with the interactions between the largecardinal axioms and the method of Forcing. This is the line of research with a deeper impact in the subsequent configuration of modern Mathematics. This area has found many central applications in Topology [ST71][Tod89], Algebra [She74][MS94][DG85][Dug85], Analysis [Sol70] or Category Theory [AR94][Bag+15], among others. The dissertation is divided in two thematic blocks: In Block I we analyze the large-cardinal hierarchy between the first supercompact cardinal and Vopenka’s Principle (Part I). In Block II we make a contribution to Singular Cardinal Combinatorics (Part II and Part III). Specifically, in Part I we investigate the Identity Crisis phenomenon in the region comprised between the first supercompact cardinal and Vopenka’s Principle. As a result, we settle all the questions that were left open in [Bag12, §5]. Afterwards, we present a general theory of preservation of C(n)– extendible cardinals under class forcing iterations from which we derive many applications. In Part II and Part III we analyse the relationship between the Singular Cardinal Hypothesis (SCH) and other combinatorial principles, such as the tree property or the reflection of stationary sets. In Part II we generalize the main theorems of [FHS18] and [Sin16] and manage to weaken the largecardinal hypotheses necessary for Magidor-Shelah’s theorem [MS96]. Finally, in Part III we introduce the concept of _-Prikry forcing as a generalization of the classical notion of Prikry-type forcing. Subsequently we devise an abstract iteration scheme for this family of posets and, as an application, we prove the consistency of ZFC + ¬SCH_ + Refl(La present tesi és una contribució a l’estudi de la Lògica Matemàtica i més particularment a la Teoria de Conjunts. Dins de la Teoria de Conjunts, la nostra àrea de recerca s’emmarca dins l’estudi de les interaccions entre els Axiomes de Grans Cardinals i el mètode de Forcing. Aquestes dues eines han tigut un impacte molt profund en la configuració de la matemàtica contemporànea com a conseqüència de la resolució de qüestions centrals en Topologia [ST71][Tod89], Àlgebra [She74][MS94][DG85][Dug85], Anàlisi Matemàtica [Sol70] o Teoria de Categories [AR94][Bag+15], entre d’altres. La tesi s’articula entorn a dos blocs temàtics. Al Bloc I analitzem la jerarquia de Grans Cardinals compresa entre el primer cardinal supercompacte i el Principi de Vopenka (Part I), mentre que al Bloc II estudiem alguns problemes de la Combinatòria Cardinal Singular (Part II i Part III). Més precisament, a la Part I investiguem el fenòmen de Crisi d’Identitat en la regió compresa entre el primer cardinal supercompacte i el Principi de Vopenka. Com a conseqüència d’aquesta anàlisi resolem totes les preguntes obertes de [Bag12, §5]. Posteriorment presentem una teoria general de preservació de cardinals C(n)–extensibles sota iteracions de longitud ORD, de la qual en derivem nombroses aplicacions. A la Part II i Part III analitzem la relació entre la Hipòtesi dels Cardinals Singulars (SCH) i altres principis combinatoris, tals com la Propietat de l’Arbre o la reflexió de conjunts estacionaris. A la Part II obtenim sengles generalitzacions dels teoremes principals de [FHS18] i [Sin16] i afeblim les hipòtesis necessàries perquè el teorema de Magidor-Shelah [MS96] siga cert. Finalment, a la Part III, introduïm el concepte de forcing _-Prikry com a generalització de la noció clàssica de forcing del tipus Prikry. Posteriorment dissenyem un esquema d’iteracions abstracte per aquesta família de forcings i, com a aplicació, derivem la consistència de ZFC + ¬SCH_ + Refl(