Combinatorial Set Theory: Partition Relations for Cardinals : Studies in Logic and the Foundations of Mathematics Series (Studies in Logic and the Foundations of Mathematics)
By Paul Erdos
* Publisher: Elsevier Science Ltd
* Number Of Pages: 348
* Publication Date: 1984-07
* ISBN-10 / ASIN: 0444861572
* ISBN-13 / EAN: 9780444861573
*****
The combinatorial theory of infinite sets constitutes now by itself a branch of mathematics with its own methods and applications to other areas. It includes topics which have arisen as generalizations to the infinite of ideas developed originally for finite sets or structures (such as graphs and partial orders), as well as topics which are inherent to infinite sets.
Among the different aspects of infinitary combinatorics, the study of partition relations has been particularly attractive to set theorists because of its connection to cardinal exponentiation, large cardinals and the axiom of determinacy. Its origin lies in a theorem due to \n F. P. Ramsey\en (1930) which states that for any pair of natural numbers $n$ and $m$, if we partition the $n$-element subsets of an infinite set $A$ into $m$ classes then there is an infinite subset $H$ of $A$ with all its $n$-element subsets lying in the same class. Questions concerning the cardinality of the homogeneous set $H$ come up immediately. For example, if $A$ is an uncountable cardinal, can we guarantee the existence of a homogeneous set of the same cardinality as $A$ for every partition of the $n$-element subsets of $A$? Other interesting questions concern the size of the subsets of $A$ we consider; for example, is there an infinite homogeneous set for every partition of the countable subsets of $A$ into two classes?
It turns out that the answers to questions like this depend on the axioms of set theory one is willing to assume.
In order to be more precise it is convenient to introduce some notation. The expression $\alpha\to(\beta)_\delta^r$ means that for every partition of the set $[A]^r$ of $r$-element subsets of a set $A$ of cardinality $\alpha$ into $\delta$ pieces, there is a set $B$ of cardinality $\beta$ with all its $r$-element subsets in the same piece of the partition.
A cardinal $\kappa$ satisfying $\kappa\to(\kappa)_2^2$ must necessarily be strongly inaccessible, which illustrates the intimate connection between partition relations and large cardinals. Infinite exponent partition relations, i.e. partition relations where $r$ is infinite, contradict the axiom of choice. The axiom of determinacy implies the existence of cardinals satisfying very powerful infinite exponent partition relations.
Erdős and Rado started a partition calculus in their paper ``A partition calculus in set theory'' [Bull. Amer. Math. Soc. 62 (1956), 427--489] introducing several kinds of generalizations to Ramsey's theorem.
Previous steps in the direction of presenting, in an organized way, the theory developed thereafter by many authors in articles scattered in different journals were taken (among others) by \n E. M Kleinberg and N. H. Williams\en. Kleinberg's survey article [Cambridge summer school in mathematical logic (Cambridge, 1971), 361--418, Lecture Notes in Math., 337, Springer, Berlin, 1973] is a delightful introduction to partition relations and their connections to large cardinals and determinacy, including infinite exponent partition relations. Williams' book Combinatorial set theory [North-Holland, Amsterdam, 1977] treats the partition calculus, mostly under the assumption of the generalized continuum hypothesis, along with other topics such as almost disjoint families of sets, delta systems and infinite graphs.
The book under review, as its subtitle indicates, deals almost exclusively with partition relations and constitutes a comprehensive monograph on the subject. Its appearance is welcome and fills a long-standing gap in the contemporary set-theoretical literature.
The authors state in their preface that their aim in writing the book is to present the most important combinatorial ideas in the partition calculus and to give a discussion of the ordinary partition relation for cardinals without the assumption of the generalized continuum hypothesis. The aim is amply satisfied; the authors single out the main types of arguments, fully exploring their power to obtain an immense amount of results.
The axiom of choice is assumed throughout the book, and the authors choose not to bother with ways to avoid using it in cases in which this axiom is not necessary. There is only brief mention of infinite exponent partition relations.
The proofs given in the book are always elegant and nicely presented, although on a few occasions the desire to state results of great generality might cause some pain to the inexperienced reader.
The reader is assumed to be familiar with the basic ideas of set theory. There is an introductory chapter (Chapter 1) containing the main basic set-theoretical concepts and results used in the book. Chapter 2 is also devoted to some preliminaries, including stationary sets and equalities and inequalities for cardinals.
The partition symbols are introduced in Chapter 3. In addition to the ordinary partition properties, the square bracket partitions, the polarized partitions, and other types of partition properties are considered in full generality. Section 8 in this chapter is very useful as a reference; the authors do well in advising the reader to skip this section and use it only to look for definitions of partition symbols used elsewhere in the book. Ramsey's theorem is proved along with its finite version, as well as some other classical results.
Chapters 4 and 6 develop the main tools used to prove partition relations. Chapter 4 contains a general framework for tree arguments and the proof of the ``stepping up lemma''. Chapter 6 deals with ``canonization'' of partitions. Chapter 5 is a vast collection of negative results, including partition relations for finite sets.
Chapter 7 establishes some connections between large cardinals and partition relations. It includes a purely combinatorial proof, together with a metamathematical one, of the result of Hanf and Tarski stating that $\kappa\to(\kappa)_2^2$ fails for many inaccessible cardinals, including the first one. Measurable cardinals are also considered.
Chapters 8 and 9 are the most technical in character. They contain the collection of ``all the results known to the authors'' (i.e. all the results) for ordinary partition relations, systematically organized. The authors announce that ``one might expect little enjoyment from reading these chapters'', a wise warning for the leisurely reader. The importance of these two chapters, the authors explain, lies in providing practical tests to decide whether a partition relation holds and also in locating the most important open problems.
Chapter 10 is devoted to applications of the combinatorial methods to topology, set mappings, cardinal exponentiation and saturated ideals. It is a very enjoyable chapter, a nice reward after the hardships of the previous ones.
The book ends with a survey of results on square bracket partition relations.
http://ifile.it/9h3pqem/0444861572.rar
