. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 5 10 13 16 20 25 31 34 36 37 40 42 49 50 51 56 60 67 68 77 80 81 84 87 90 93 97 101 104 105 109 114 115 118 119

2 7.4 7.5 7.6 7.7 7.8 8 8.1 8.2 8.3 8.4 8.5 8.6 8.7 9 9.1 9.2 9.3 9.4 10

Ramsey theory for trees . . . . . . . . . . . . . . . Hindman’s Finite Sums Theorem . . . . . . . . . . Infinitary partition relations . . . . . . . . . . . . . Structure of trees . . . . . . . . . . . . . . . . . . . Linear and quasi-orders . . . . . . . . . . . . . . . 1980-1990: CODIFICATIONS AND EXTENSIONS Set-theoretic topology . . . . . . . . . . . . . . . . Partition relations . . . . . . . . . . . . . . . . . . Structural partition relations . . . . . . . . . . . . Partial order, not trees . . . . . . . . . . . . . . . Tree results . . . . . . . . . . . . . . . . . . . . . . Linear orders . . . . . . . . . . . . . . . . . . . . . Other combinatorial results . . . . . . . . . . . . . 1990–2000: A SAMPLING . . . . . . . . . . . . . . Partition calculus results . . . . . . . . . . . . . . Linear and partial orders . . . . . . . . . . . . . . Trees . . . . . . . . . . . . . . . . . . . . . . . . . Combinatorial principles . . . . . . . . . . . . . . . POSTSCRIPT . . . . . . . . . . . . . . . . . . . . .

INDEX

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

128 129 132 133 139 144 146 148 153 158 158 164 164 166 167 176 177 179 180 215

CHAPTER 1

INFINITE COMBINATORICS

Jean A. Larson 1

INTRODUCTION

There is a tension in mathematics between generalization and description in concrete terms. Cantor’s extension of number to the transfinite is an example of generalization, and the pull of generalization and the counterbalancing forces are described in the passage that concludes with a famous declaration [Cantor, 1883, 545], “das Wesen der Mathematik liegt gerade in ihrer Freiheit.”1 These principles, I think, do not represent a danger for science as some have suggested: first, the conditions under which new numbers can be generated leave little space for arbitrariness; second, every mathematical construct comes with a natural corrective; if it is impractical or uninspiring it will be dropped due to lack of impact. Conversely, any unnecessary constraint on the mathematical research impetus carries the far greater risk—the more so since there is no scientific justification for it; for the essence of mathematics is its lack of constraints.2 Concrete structure may be sought through classification schemes, in basis problems, in universal structures, and especially in the search for and expectation of local uniformity, regions of simplicity, and inescapable structure. This aspect is 1 The quote has been variously translated, e.g. “the essence of mathematics resides in its freedom.” This version is the one I first encountered as part of a mural by art students at the University of Florida, and is the one I will be using in the postscript. 2 (The above translation of the following paragraph was made by J¨ urg Peters of the University of Florida. When asked why he had translated Freiheit as lack of constraints rather than freedom he said he felt that Cantor’s notion of free was like that of free groups and that lack of constraints better captured that sense.) Es ist, wie ich glaube, nicht n¨ othig in diesen Grunds¨ atzen irgendeine Gefahr f¨ ur die Wissenschaft zu bef¨ urchten, wie dies von Vielen geschieht; einerseits sind die bezeichneten Bedingungen, unter welchen die Freiheit der Zahlenbildung allein ge¨ ubt werden kann, derartige, dass sie der Willk¨ ur einen ¨ aussertst geringen Spielraum lassen; dann aber tr¨ agt auch jeder mathematische Begriff das n¨ othige Correctiv in sich selbst einher; ist er unfruchtbar oder unzweckm¨ assig, so zeigt er es sehr bald durch seine Unbrauchbarkeit und er wird alsdann, wegen mangelnden Erfolgs, fallen gelassen. Dagegen scheint mir aber jede u ¨berfl¨ ussige Einengung des mathematischen Forschungstriebes eine viel gr¨ ossere Gefahr mit sich zu bringen und eine um so gr¨ ossere, als daf¨ ur aus dem Wesen der Wissenschaft wirklich keinerlei Rechtfertigung gezogen werden kann; denn das Wesen der Mathematik liegt gerade in ihrer Freiheit.

3

4 captured by the following quote, most often used in connection with Ramsey theory: “complete disorder is impossible”. This short sentence is embedded in the following quote from Motzkin [1967]:3 The influence on mathematics of its two neighbors, physics and logic, is sometimes opposite or, at least, complementary. Whereas the entropy theorems of probability theory and mathematical physics imply that, in a large universe, disorder is probable, certain combinatorial theorems show that complete disorder is impossible. Already the “pigeon-hole principle” —out of t + 1 objects of t kinds, at least two must be of the same kind—can be interpreted as saying that, while no 2-set (set of two objects) in the given (t + 1)-set needs to be composed of objects of different kind (however probable that may be), at least one 2-set of objects of the same kind must occur. A sophisticated generalization of this principle was initiated in [7] by the mathematical logician Ramsey. The neighbors most relevant to our study are logic and other areas of mathematics. From logic we see that opposite or complementary results may be obtained by extending our basic set-theoretic assumptions in different ways to get consistency results for different aspects of the combinatorial enterprise. Motivated by the Todorcevic paper Basis problems in combinatorial set theory [1998a], we shall be especially interested in what he calls critical members of classes S of interest, of which Todorcevic wrote: “Critical objects are almost always some canonical members of S simple to describe and visualize.” The Pigeonhole Principle,4 which was mentioned in the Motzkin quote, is our first example of an assertion of the lack of disorder. It is a fundamental idea that has been around for a long time, and the principle itself is attributed to Dirichlet in 1834, where he used the name Schubfachprinzip.5 These themes play out in this decade-by-decade review of infinite combinatorics in the 20th Century. The foci are the study of orderings, especially trees, and Ram3 Hans J¨ urgen Pr¨ omel [2005, 3] used the short quote as a theme in the life of Walter Deuber. Theodore S. Motzkin (1908 – 1970) spent the later part of his career at the University of California, Los Angeles. 4 An early use of the English “pigeonhole principle” occurs in Raphael Robinson’ paper [1941] and the first mention found by searching MathSciNet on December 8, 2010 for the word “pigeon” is the Erd˝ os-Rado paper [1956], where “pigeon-hole principle” is offered as a translation of “the box argument” or “the chest of drawers argument” with “Schubfachprinzip” in parenthesis, and attributed (incorrectly) to Dedekind. Those familiar with pigeon hole desks, sometimes used for sorting letters, recognize the image that almost surely inspired this translation, but those unfamiliar with them may think of the pigeon houses of Iran and Egypt, with their many entrances, as is suggested by one Italian translation, principio da casa dos pombos, which appears on Miller’s site (see the next footnote). It would not be surprising if a perusal of British popular articles on mathematics and mathematical puzzles turned up much earlier references. Literary references to the concept go back still further, with an example dating to the 1600s appearing on http://pballew.blogspot.com/2009/06/updating-history-of-pigeon-hole-theorem.html. 5 It is difficult to ascertain the first usage of any idea, symbol or word. The web page for letter P http://jeff560.tripod.com/p.html of Jeff Miller’s site on Earliest Known Uses of Some of the Words of Mathematics, downloaded on December 9, 2010 makes a case for Dirichlet’s priority.

1. INTRODUCTION

5

sey theory, especially the partition calculus. Along the way, results about almost disjoint sets, set mappings, transversals, and regressive functions are discussed, and a wide variety of combinatorial tools are mentioned as they come into play. Lists of a variety of results are briefly described to capture the breadth and flavors of different decades. Occasionally conferences and applications to or from infinite combinatorics are described to indicate some of the ways in which the field has benefited by interactions with communities of mathematicians in finite combinatorics, model theory, topology, and other aspects of set theory, including large cardinals and forcing. My goal in writing this chapter was to be inclusive, that is, to acknowledge multiple discoveries, rediscoveries,6 and inventions of ideas. I apologize in advance for the omissions and incorrect statements that surely appear in this wide ranging survey. I have not concerned myself greatly about who had the first seed leading to each discovery, nor with assessing the quality of the variety of contributions. Let me state my criteria for attribution of results: (1) they must be directly stated; (2) they must be proved and published in a reputable journal, or in rare cases vetted by someone other than the author or explicitly ascribed by others, usually when the idea of proof has been generalized. This approach is informed by having listened to Paul Erd˝ os describe how he decided at what point and to whom money should be awarded for the solutions to certain of his problems.

1.1

Overview of the history of orderings

A broad overview of the history of orderings starts with foundational work on cardinal and ordinal numbers, including the Schr¨oder-Bernstein Equivalence theorem, fundamentals of cardinal and ordinal arithmetic, and Zermelo’s Well-Ordering Theorem. An early treatment in English was Huntington’s book on the continuum as a type of order [1905c]. The first systematic study of linear and partial orderings was carried out by Hausdorff, who set the stage at the beginning of century with his first mathematical paper [1901] in which he generalized ordinals. He investigated the family α M of functions from an ordinal number α into a linearly ordered set M under various orderings including the lexicographic ordering and eventual domination. Hausdorff identified critical elements, found bases, generating sets, universal linear orders7 for scattered linear orderings of bounded cardinality, showed every partial order has a maximal well-ordered subset, and set up and studied a classification scheme 6 At

the Scottish Book conference held in Denton, Texas in 1979, Paul Erd˝ os [1981, 36] shared his perspective on rediscovery: “Ulam and I settled many of these questions long ago, but we never got around to publishing our results. These results were rediscovered and published by the Indian mathematician B. V. Rao; when Rao sent me a preprint I urged him to publish. Naturally, I did not tell him that Ulam and I had already done the work. Eventually he found out, however, and asked me why I hadn’t said anything about it. I replied that this was the one respect in which I did not want to imitate Gauss, who had a nasty habit of ‘putting down’ younger mathematicians by telling them he had long ago obtained their supposedly new results.” 7 A linear order (P, 2 many cells to at most µ − 1 cells, by combining the last two cells together to get a new partition and applying the induction hypothesis to it to get an infinite set ∆ and a specified cell containing all r-combinations from it. If the specified cell is not the new cell obtained by joining two old ones, ∆ is the desired set, and otherwise he applies the theorem again with µ = 2 to get the required infinite ∆0 ⊆ ∆. We will call a sequence {z1 , z2 , . . . } where the combination of any element zi with any ρ − 1 later elements lands in the same cell Ci begin-homogeneous.85 With this language, Ramsey’s basic induction step argument starts with an to attempt to construct a sequence begin-homogeneous for which all the ρ-combinations end in the first cell, and if it does not work, repeat starting from the point of failure to get a sequence begin-homogeneous and verify that all the ρ-combinations end in the second cell. Corresponding to the theorem discussed above, sometimes also called the Infinite Ramsey’s Theorem, Ramsey proved a finite version quoted below [1930]. Finite Ramsey’s Theorem: Given any r, n and µ we can find an m0 such that, if m ≥ m0 and the r-combinations of any Γm are divided in any manner into µ mutually exclusive classes Ci (i = 1, 2, . . . , µ), then Γm must contain a sub-class ∆n such that all the r-combinations of the members of ∆n belong to the same Ci .86 Ramsey followed the statement of the theorem with the following remarks: 85 The use of begin-homogeneous here is designed to parallel end-homogeneous used in later constructions. 86 Here Γ m denotes a class with m members.

34 “This is the theorem which we require in our logical investigations, and we should at the same time like to have information as to how large m0 must be taken for any given r, n, and µ. This problem I do not know how to solve, and I have little doubt that the values for m0 obtained below are far larger than is necessary.” The study of this question and its generalizations is the core of finite Ramsey theory. 3

1930-1940: EARLY RAMIFICATIONS

In the 1930’s Erd˝ os and Rado, two pioneers in the partition calculus, forged their initial results; Sierpi´ nski constructed a key example which shows that there is no direct uncountable analog of Ramsey’s Theorem; Jones proved his metrization theorem and constructed a special Aronszajn tree87 but did not publish the work until later; and Kurepa made the first systematic study of uncountable trees, giving an equivalent formulation of Suslin’s Problem in terms of trees. Partial orders were shown to be extendible to linear orders, and a denumerable partial order universal for countable partial orders was constructed. The Regressive Function Theorem was generalized and large families of almost disjoint sets were constructed. Equivalence relations became part of the tool kit for analysts;88 graph theory became a subject in its own right89 with the publication of Theorie der endlichen und unendlichen Graphen [K˝onig, 1936], [1990], the first book to present graph theory as a subject. There were ups and downs in mathematical publishing. Zentralblatt f¨ ur Mathematik was founded in 1931 by Springer Verlag in cooperation with the Prussian Academy of Science.90 The Journal of Symbolic Logic was founded in 1936 (cf. [Ducasse and Curry, 1962]), and Alonzo Church included a bibliography of symbolic logic in the first issue. However, on September 1, 1939 Germany invaded Poland and volume 33 of Fundamenta Mathematicae was not published.91 Hausdorff published the third edition of his set theory text; Moore [1932] published his monograph Foundations of Point Set Theory with the revised version of his axioms that he had been working toward in the 1920’s.92 Sierpi´ nski published a monograph [1934] on the Continuum Hypothesis. It naturally included his own work, and also included that of Lusin, Tarski, Kuratowski and others of the Polish school. It started with equivalences of the statement and 87 Recall that a special Aronszajn tree is a tree of height ω all of whose levels are countable 1 and which is the union of countably many antichains. 88 Equivalence relations were one of the topics in [Bourbaki, 1939], a 51-page overview of set theory designed to prepare individuals for the study of analysis. 89 See the AMS Math Review by Robin Wilson [1991]. 90 See the History of Zentralblatt page whose url follows: http://www.zentralblatt-math.org/zmath/en/about/history/ downloaded September 7, 2010. 91 See [Kuzawa, 1970, 489–490] for an overview of the loss of life and property of the mathematical community of Poland during the war period 1939–1945. 92 Jones [1997, 97], in his article The beginning of topology in the United States and the Moore school, assessed this work of Moore and Topology by Solomon Lefschetz [1930] as follows: “While definitely limited, these books were of considerable help in formulating the knowledge and tools necessary for research.”

3. 1930-1940: EARLY RAMIFICATIONS

35

continued with discussions, all the while assuming CH, of Lusin sets, the duality between sets of measure zero and sets of first category, the proof that there is no measure on all subsets of the real numbers which is (1) not identically zero; (2) zero on singletons; (3) countably additive. The founders of the Moscow school, Egorov and Lusin, fell on hard times in the 1930’s. In September 1930 Egorov was arrested for his religious beliefs, Name Worshipping, and exiled to a camp near Kazan on the Volga River, and he died after a hunger strike initiated because the prison guards would not let him practice his religious beliefs.93 The Moscow Mathematical Society had elected Kolman, a loyal Bolshevik, as president. Lusin was alarmed by what happened to Egorov, so he left Moscow University for the Steklov Institute of the Central Aero-Hydrodynamics Institute in Leningrad, but kept his position as the head of the mathematical group of the Russian Academy of Sciences. Kolman’s denunciation of Lusin in print prevented Lusin from attending the International Congress of 1932. The Russian Academy of Sciences and the Steklov Institute were moved to Moscow in 1934. In July 1936, articles in Pravda appeared accusing Lusin, in particular, of claiming results of his students as his own and of publishing his best papers in the West. These articles led to a series of meetings of the Moscow Mathematical Society which drafted a resolution against Lusin that led to the loss of his university position and loss of good will from some of his colleagues, but not his position as an academician. Lusin made a statement in response to the resolution promising, in part, to publish primarily in the Soviet Union. What became known as the Lusin Affair had a chilling effect: mathematicians in the Soviet Union basically stopped publishing their results abroad.94 The study of transversal theory was launched when Philip Hall [1935] proved his celebrated theorem on matching:

Hall’s Marriage Theorem: Given n boys, if, for each positive k ≤ n, any k of the boys between them know at least k girls, then it is possible to marry each boy to a girl that he knows.

The result can also be formulated as an existence theorem for a system of distinct representatives: For each boy b, there is a set Gb of girls he knows, and a selection of distinct girls from each of these sets yields the desired outcome. D. K˝onig [1931] had an equivalent but initially lesser known result published in Hungarian. Transversals are regarded in a variety of ways: as injective choice functions for a sequence of sets; as sets whose intersection with every set in a family is a singleton; as systems of unique representatives. 93 See

[Graham and Kantor, 2007] for details. [Demidov and Levshin, 1999] and the Math Review MR1790419 (2001k:01066) by F. Smithies of it for more information. 94 See

36

3.1

Extensions

This section includes extensions of results from earlier decades for linear and partial orderings, almost disjoint families and regressive functions. Also included is the following result which discusses an extension of a different kind. Edward Marczewski95 [1930] proved a theorem that is known in the literature by his birth name: Szpilrajn’s Theorem: (linear) order.

Every partial order has an extension to a total

For Marczewski, a linear order was a transitive, irreflexive, trichotomous binary relation. Marczewski first proved a lemma than any partial order with an incomparable pair can be extended to a partial order in which the pair has a specified order. He next observed that the union of an increasing well-ordered chain of partial orders under extension is a partial order. He concluded that there must be a maximal extension, hence one which is a linear order, citing [Kuratowski, 1922] and [Hausdorff, 1914]. In his paper, he remarks that the theorem is already known, citing the third edition of Sierpi´ nski’s book, Zarys teorji mnogo´sci, but that the proofs of Banach, Kuratowski and Tarski had not yet been published. Andrzej Mostowski96 [1938] constructed a denumerable partial order universal for denumerable partial orders,97 extending the Bernstein result for countable linear orders which Hausdorff had extended under CH to larger size linear orders. Hausdorff [1936] revisited ordered sets and constructed an (ω1 , ω1∗ )-gap inside the “dyadic number sequences.” He commented on its relationship to his earlier work in a footnote [Hausdorff, 1936, 244, footnote 1]: F¨ ur Folgen reeler order rationaler Zahlen habe ich dies bereits 1909 gemacht (Graduierung nach dem Endverlauf, Abh. S¨achs. Ges. d. Wiss. 31). Da dieser Arbeit whol wenig bekannt is und die Konstruktion f¨ ur dyadische Folgen, die zum vollen Beweis des Satzes I er95 Marczewski had the surname Szpilrajn until 1940. Kuratowski directed his thesis at the University of Lw´ ow. Other influential colleagues there included Mazurkiewicz and Sierpi´ nski. 96 Andrzej Mostowski (November 1, 1913 – August 22, 1975) wrote up his doctoral thesis, On the Independence of the Definition of Finiteness in the System of Logic in 1938 and defended it at Warsaw University in February 1939 (recall that Poland was invaded in September 1939). Kuratowski was the official supervisor, but Mostowski counted himself a student of Tarski. Lindenbaum had suggested that he work on the method of independence proofs sketched by Fraenkel (cf. [Crossley, 1975, 44]). This conversation was the starting point of the main content of Mostowski’s dissertation, namely, what came to be known as Fraenkel-Mostowski permutation models. In conversation with Crossley [1975], Mostowski shared some memories of his three escapes during World War II, and his decision to take some bread instead of his “nice, very big, wonderful notebook with all these discoveries” which subsequently was burned. For more on his life and his interactions with mathematicians inside and outside of Poland, see [Ehrenfeucht et al., 2008]. 97 Recall a partial order (P, 2ℵ0 .” He then stated what has come to be known as the Normal Moore Space Conjecture: “Is every normal Moore space M metric?” Jerry Vaughan [1980] asked Jones why he thought that 2ℵ0 < 2ℵ1 was true, and here is the response Vaughan recorded from their October 12-13, 1979 conversation [1980, 40]: “Think of a countable sequence, say ω, as being an initial segment of an uncountable set, say ω1 . Well, it is perfectly obvious to even the most stupid person, and I guess maybe it helps to be a little stupid, if you take all the sequences which run through the first infinity of ordinals, which gives a set of cardinality 2ℵ0 , look how many more you can get by running the rest of the way through ω1 with uncountable sequences. It is clear that there ought to be a whole lot more of them. I thought surely that I could prove that overnight, maybe even in an hour, but I could not get anywhere on it. I remember one week I worked on that problem pretty hard and could not see it. I happened to run into Moore walking across campus and told him that I was losing my mind: I could not prove 2ℵ0 < 2ℵ1 even though it ought to be true. Well, he just laughed and said ‘Neither could Sierpinski.’ It had not occurred to me to look in Sierpinski’s book; so I looked in there and found some things equivalent to this. He did not do much with it, but he did enough to convince me that I was wasting my time.” Peter Nyikos [1980a, 28] completes the story: “The real cause of the delay, as Jones has informed us, is that he was hoping to settle the entire normal Moore space problem · · · .” Jones [1980]112 shared reactions of his thesis advisor Moore to this work: When I was a student at Texas, Moore apparently didn’t consider work in abstract spaces very highly. · · · I think he just felt there was more substance and beauty in other less abstract kinds of problems - continua, decompositions, etc. So when I proved that if 2ℵ0 < 2ℵ1 then every separable, normal Moore space was metrizable [1], I wasn’t asked to present the proof in class but rather to the Mathematics Club (as it was called). And when I wanted to use it together with other things for a thesis, Moore didn’t like the idea at all but chose instead 111 Peter Nyikos [1980a] pointed out that Jones and Moore used completely separable for second countable, i.e. there is a countable family of open sets such that every open set can be represented as a union of some of them. 112 The paper [Jones, 1980] appeared in a volume dedicated to his mathematical work and influence and containing some of the papers presented at a conference held in Greensboro, North Carolina, in October, 1979.

42 a couple of embedding theorems I had gotten. With hindsight he was certainly right. Since I thought that one ought to be able to prove 2ℵ0 < 2ℵ1 , I might still be there! Jones made a presentation entitled A false proposition of logic to the Mathematics Club of the University of Texas in the spring of 1933 (see footnote 6 of [1953]) in which he presented the construction/example of an Aronszajn tree as he much later recounted for the American Mathematical Society on December 29, 1952 [1953].113 A modern description of his example follows [1953, 32–33]: Jones’ Example 1: There exists a well-ordered family F of collections H1 , H2 , . . . , Hz , . . . (z < ω1 ) such that (1) for each ordinal x, x < ω1 , Hx is a countable collection of mutually exclusive sets, (2) if x < y < ω1 , each set of Hy is a proper subset of Hx , (3) if x < y < ω1 , and hx is an element of Hx , there exists a sequence hx , hx+1 , hx+2 , . . . , hy such that hx ⊃ hx+1 ⊃ hx+2 ⊃ · · · ⊃ hy , and for each z, x ≤ z ≤ y, Hz contains exactly one of the sets hx , hx+1 , hx+2 , . . . , hy , but (4) there exists no sequence h1 , h2 , h3 , . . . such that h1 ⊃ h2 ⊃ h2 ⊃ . . . and for each x, x < ω1 , Hx contains exactly one of the sets h1 , h2 , h3 , . . . . Jones used his example to construct a non-metrizable Moore space [1954, 31–33]. He compared his example with the one in Kurepa’s thesis, and described it as follows [1954, 34]: “Aronszajn’s example is similar to the one I have constructed. It yields Example 1 but is not as suitable for the application to Moore spaces.”

3.4

Kurepa

114 made a systematic study of uncountable partial orders, especially ¯Duro Kurepa trees in the wider framework of ramified sets, starting in his thesis, Ensembles et 113 While

Jones’ example was published two decades after its construction (the paper included suitable references to related work that had been published in the meantime), it is included here because of its influence on students in the Texas school of topology, who heard him talk about it and the related road spaces constructed from it. 114 Duro Kurepa (August 16, 1907 – November 2, 1993) was a proud, tall, energetic individual ¯ from a region known for tall people. He spent a substantial portion of his career at the University of Zagreb, an ethnic Serb in Croatia. Specifically, he got his diploma there in 1931 and became an assistant in mathematics there. He spent 1932-1935 in Paris at the Facult´ e des Sciences and the Coll` ege de France. He obtained his doctoral degree at the Sorbonne in 1935 where the president of his committee was Paul Montel, his supervisor (we would say advisor) was Maurice Fr´ echet, and whose third member was Denjoy. Knaster was one of the reviewers of his thesis (cf. Kurepa’s Math Review MR0423284 (54 #11264)). He spent some postdoctoral time in Paris and Warsaw. Then he returned to the University of Zagreb, where he became an assistant professor in 1937, ˇ c, was promoted to associate professor 1938, and full professor in 1948. According to Hrovje Siki´ a Professor at the University of Zagreb and currently editor-in-chief of Glasnik Matematiˇ cki, Kurepa was interested not only in mathematics, but also in languages, and would sometimes include in his lectures comments about idiosyncrasies in Serbian and Croatian word formation. ˇ c recalled was the words for curve, which is krivulja in Croatian and kriva in An example Siki´ Serbian. They came up a semi-popular seminar, about which Kurepa said neither should be used since they failed to follow the rule of names ending in “un”, and he recommended that krivun be used instead to great laughter in his audience. Kurepa moved to the University of

3. 1930-1940: EARLY RAMIFICATIONS

43

Tableaux Ramifi´ees. This section starts with a detailed review of his thesis which includes the definition of a Suslin tree;115 the equivalence of Suslin’s Problem with the non-existence of a Suslin tree; the construction of an Aronszajn tree as a subtree of the tree of all non-empty bounded well-ordered sequences of rationals under end-extension; and the definition of the key parameters for the structural analysis of uncountable trees: height, supremum of the sizes of the levels, and cardinality of the set of branches whose length is the height of the tree. The review of his thesis is followed by an overview of results from the 1930’s beyond the thesis: his construction of a special Aronszajn tree; his initial results on Qembeddable and R-embeddable116 Aronszajn trees; his Fundamental Relation bounding the size of a partial order in terms of the sizes of its well-ordered and conversely well-ordered subsets and the sizes of its antichains; and his use of a super-position of two linear orders to define a witness to the sharpness of the bound in his Fundamental Relation. In the opening paragraph of the published version of his thesis, Kurepa [1935, 1] listed two logical problems that the theory of ordered sets had run up against: (1) the existence of a well-ordering of an arbitrary set,117 and (2) the existence of a cardinal number between any cardinal κ and its power 2κ .118 They shaped much of the research in set theory in the 20th Century, and provided a context for Suslin’s problem [1920], the motivating force in Kurepa’s thesis. While working on his thesis, Kurepa shared his progress in a series of four announcements in Comptes Rendus: [1934a], [1934b], [1934d], [1934c].119 Kurepa [1934a] announced a positive solution to Suslin’s Problem in February with a theorem asserting the equivalence of seven statements about a linearly ordered set E, the first of which posits that E is a continuum isomorphic to each of its intervals and not the product of two sub-continua and the last of which asserts that the set E is dense, it has neither a first nor a last element, is metrizable and is complete. This note introduced the notion of the development or atomization of a linearly ordered set. In modern language this is the process of repeatedly partitioning into subintervals to end up with a family of intervals which are pairwise either disjoint or have one a subset of the other, and so that the family forms a tree under the subset relation. Kurepa discussed developments in §12 of his thesis, and Belgrade in 1965 and remained there until his retirement in 1977. Kurepa was instrumental in the introduction in 1966 of Glasnik Matematiˇ cki Series 3 as the mathematical successor to Glasnik matematicˇ cko-fiziˇ cki i astronomski Series 2. He died tragically in the time of Miloˇsevi´ c and rampant inflation after being beaten by thugs and hidden from view under stairs. 115 Recall that a Suslin tree is a tree of height ω in which every branch and every antichain is 1 countable. 116 A partially ordered set is Q-embeddable, respectively R-embeddable, if it has a strictly increasing map into Q, R respectively. 117 This problem was addressed by Zermelo and Fraenkel as discussed in Kanamori’s first chapter. 118 On this problem, Kurepa wrote [1935, 1, footnote 2], [1996, 11, footnote 2] “La r´ esponse pr´ esum´ ee negative ` a cette probl` eme est appel´ ee l’Hypoth` ese de Cantor.” 119 Carlos Alvarez [1999] has written on the history Suslin’s Problem, and his discussion of these announcements is particularly interesting and detailed.

44 the development of a Suslin line led to the equivalence of the existence of a Suslin line and the existence of a Suslin tree. The second announcement, [1934b] in March, also claimed a positive solution to Suslin’s problem, and as a step toward the proof introduced the two cardinals: • p1 E = inf{|F | : F ⊆ E is a dense subset of E}, and • p2 E = inf{|F| : F is a family of disjoint and non-empty open intervals of E}. Now p1 E is written d(E) and called the density, and p2 E is written c(E) and called the cellularity. These cardinals represent the beginning of Kurepa’s generalization of the Suslin problem to a wider context, and they figure in Kurepa’s Fundamental Relation discussed at the end of this section. In §7 [1996, 58–64] of his thesis, Kurepa defined and investigated p1 E and p2 E for a linearly ordered set E. He focused on the relationship between these cardinals and proved in Lemma 10 that to prove p1 E = p2 E it sufficed to prove it for linearly ordered continua. He also explored when the supremum of p2 E is attained, and proved in Lemma 100 that if the supremum p2 E is attained for every linearly ordered continua, then it is attained for every linearly ordered set. In §12.C.3, Theorem 2, Kurepa proved that + p2 E ≤ (p1 E) .120 In §12.C.4, Lemma 5, he proved that if the density p1 E is singular, then the cellularity p2 E = p1 E is attained. Todorcevic (cf. [Kurepa, 1996, 299]) combined Lemma 4 of §12.C.3, Lemma 5 of §12.C.4 and Theorem 3 of §11.4 [Kurepa, 1935, 110], [Kurepa, 1996, 100] to point out that Kurepa showed that if the cellularity c(E) = p2 E is singular then it is attained. In footnote 11 [1935, 131]121 (the degree of) cellularity is extended to abstract spaces as the supremum of the sizes of disjoint families of open sets. Now we turn to Kurepa’s systematic study of set-theoretic trees122 (ramified tables) within the context of ramified sets and ramified tables. Since the definition of a ramified table essentially filled six pages of the published version of the thesis as printed in [1996], we look at an important family of examples. Suppose that (P, is defined from it in the usual way. Let k be defined on P by a k b if and only a 6< b, b 6< a and a 6= b. Let ≡ be the relation of identity. Then ∗ = (≡, , k) is a ramification relation if for all points a, b, c ∈ P , if a < c and b < c, then a and b are comparable, i.e. the set of predecessors of any point forms a chain.123 Since all pairs are related 120 Todorcevic [1996, 299] called this the first important result on the relationship between density d(E) = p1 E and cellularity c(E) = p2 E. 121 Unfortunately, the supplementary material in pages 127–135 of [Kurepa, 1935] entitled Compl´ ement des r´ esultats pr´ ec´ edents were omitted from the version of Kurepa’s thesis in [Kurepa, 1996]. 122 Arthur Cayley studied finite trees, especially rooted finite trees, coming up with the generating function to list the number of rooted trees with n nodes in [1857], made connections with isomers in chemistry in [1875], and counted the number of distinct rooted trees with n nodes in [1881]. 123 The notation and splitting of all pairs recalls the formal splitting by Hausdorff [1909, 300], [2005, 273] of real-valued functions with a common ordered domain by final rank ordering into f < g, f = g, f > g, f k g.

3. 1930-1940: EARLY RAMIFICATIONS

45

by one of ≡, and k, the set P is a ramified set with respect to this ramification relation. Kurepa gave, as his first example of a ramified set, a genealogical tree [1996, 67], and his first example of a ramified table was the genealogical tree again [1996, 70], so it is clear that he intended to generalize the notion of tree. For Kurepa, a ramified table was the result of the process of ramification applied to a partial order P , i.e. the stratification of the elements of the partial order into levels, by identifying a first level, removing the first level, letting the second level be the first level of the reduced set, and continuing in this fashion. Some partial orders fail to be suitable for ramification. A set E ⊆ P has a first level [premi`ere rang´ee] if for every point a ∈ E, the set of predecessors of a in E has a least element; in such a case, the first level of E is the set of the least elements of the sets of predecessors of elements of E. Kurepa attributed this version of the definition to Fr´echet; his original definition of first level was that it was the unique set F , if it existed, such that every element of E \ F was preceded by one and only one element of F . A ramified set is a ramified table if each of its non-empty subsets has a first level. In the lemma immediately following the definition, he showed that it is equivalent to require that each linearly ordered subset be well-ordered and commented in footnote 10 (see [1996, 70]) that Fr´echet used this statement as the definition and that part of the proof of the lemma of equivalence of these definitions is due to Fr´echet. Thus in the example we are considering, the definition is equivalent to and, in the alternate form, remarkably close to, the current standard definition of a set-theoretic tree as a partially ordered set in which the predecessors of each point are well-ordered. Immediately after the discussion of the definition of ramified table T , Kurepa recursively defined the αth level [rang´ee], which he denoted Rα T , and used the levels to define the height [rang] as the order type of the set of α for which Rα T is non-empty, the length [longeur] as the cardinality of the height, the cofinality [longeur r´eduite] (the cofinality of the height), and the width [largeur] as the upper bound of the cardinalities of the Rα T s. The name ramified table suggests that Kurepa envisioned a distribution of the elements of T into levels, with boxes to contain the elements at each level and immediate successor boxes all stacked above the box that is their common immediate successor, as might be drawn to illustrate the atomization of a linear order by intervals into a tree. Indeed, in the opening paragraph of the second chapter of his thesis Kurepa cites the idea of subdivision as motivation for his generalization of the relation of order to the relation of ramification. He used this approach to the construction of ramified tables and thus was able to show that if all ramified tables of cardinality ω1 have either a chain or an antichain of cardinality ω1 , then there is no Suslin line. Many graduate students have been challenged by their dissertation advisors to give examples that show their theoretical approaches are substantive, and Kurepa was not the only one who received help from a fellow graduate student in producing

46 a desired example. Nachman Aronszajn,124 also a student of Maurice Fr´echet, constructed the first tree of uncountable height with all levels countable. The Aronszajn construction was announced in an abstract of Kurepa [1934c] and is briefly described in a footnote to Theorem 6 of §9 of Kurepa’s thesis [1935, 96], [1996, 88]. Essentially, he built a suitable subtree of the set of one-to-one sequences of countable ordinal length of rationals in Q ∩ (0, 1) whose sums are finite and partially ordered them by end-extension. Aronszajn may have constructed such a tree prior to Kurepa, but Kurepa came up with his own construction of what is now known as an Aronszajn tree inside the tree σQ of bounded well-ordered subsets of the rationals ordered by end-extension. He started with an initial level consisting of all rational singletons. At successor levels of the construction, he extended every node on the immediately preceding level in all possible ways. At limit levels α, he took any denumerable subset F of the collection of well-ordered subsets of Q all of whose initial segments were in levels already constructed which had the property that it and the tree up to that point were dense in each other. More generally, one can build trees inside the ramified table σE, which consists of the collection of non-empty bounded well-ordered subsets of a ordered set E ordered by end-extension. In §10.1, Kurepa [1935, 98], [1996, 89] introduced the notion of similarity for ramified tables and called the similarity classes types of ramification. He showed that if E and F are similar linearly ordered sets, then so are the ramified tables σE and σF of the well-ordered bounded non-empty subsets of E, respectively F , ordered by end-extension. In §10.2, Kurepa sketched the proof that σQ is homogeneous, i.e. that for every element s ∈ σQ, the set of t ∈ σQ properly extending s is similar to σQ. In §10.3, Kurepa introduced distinguished ramified suites [suites ramifi´ees distingu´ees]. A ramified table T is a ramified suite if for every a ∈ T , the set of t ∈ T for which either t c (the power of the continuum) and we split the complete graph of power b into a countable sum of subgraphs; at least one subgraph contains a non-denumerable complete graph. Theorem I is best possible. As a matter of fact, if b = aa = 2a we can split the complete graph of power b into the sum of a subgraphs, such that no one of them contains a triangle. For the sake of simplicity we show this only in the case b = c = 2ℵ0 . Erd˝ os described the example160 as the complete graph G on points of the interval (0, 1) and for each positive integer k, the edges of Gk are those pairs {x, y}< such that 1 1 ≥ y −x = k. k−1 2 2 Erd˝ os, in his Theorem II, assumed the Generalized Continuum Hypothesis and supposed that the complete graph on m = ℵα+2 many points is the sum G = G1 + G2 , and proved that if G1 does not contain a complete graph of power m, then G2 contains a complete graph of power ℵα+1 . Prior to his proofs of the two theorems, he wrote “Tukey and I have shown by a result of Sierpi´ nski that the complete graph of power ℵ1 can be decomposed into the countable sum of trees. Without assuming the continuum hypothesis we can not decide whether this also holds for the complete graph of power ℵ2 .” (See [1942, 365]; the result that Tukey and Erd˝os used is in [Sierpi´ nski, 1924].) Both proofs used a construction process that used a graph G to build a tree or ramification system, as it was called in his paper [1943] with Tarski; we describe only the proof for Theorem I. If G is a graph on b > aa points and the edges of a G are partitioned into a subgraphs enumerated as hGα : α < |a|i, then the process starts by choosing an arbitrary p, splitting the remaining points into sets Qα where q ∈ Qα if α is the least index such that the pair {p, q} is in Gα . At successor stages ξ = η + 1, this approach is repeated; if s : η → |a| is the index of a non-empty set Qs , then ps is chosen as an arbitrary element of Qs and the remaining points are split into sets Qs_ hαi where q ∈ Qs_ hαi if α is the least index 159 Baumgartner [1997, 71] also used “soon after” to indicate when Erd˝ os proved the results of [1942]. 160 Hajnal [1997, 354] reported that Erd˝ os mentioned that the example was pointed out to him by G¨ odel.

4. 1940-1950: PIONEERING PARTITION RESULTS

63

such that the pair {ps , q} is in Gα . At limit stages, intersections are taken. The construction stops when all the points have taken on the role of being the chosen point. By cardinality considerations, the number of chosen points whose index is a sequence of length less than |a|+ is at most |a| · |a|+ = |a|+ , so there must be a point r not chosen at any level of the construction of ordinal height < |a|+ . Since at the ηth level, every point of G has either been chosen or is in one of the sets with an indexing sequence of that length, it follows that r is in the intersection G of the level sets Qs to which it belongs. For some α∗ there must be |a|+ many sequences s with G ⊆ Qs_ hα∗ i and the set of points ps for which this is true is a complete subgraph of Gα∗ of order type |a|+ . Erd˝os did not point out that r may be added to get a sequence of length |a|+ + 1. Erd˝ os [1942] attributed the result that there is a graph on 2ℵα which does not have a complete subgraph of power ℵα+1 nor an independent161 subset of that power to Sierpi´ nski, who proved it for graphs of size ℵ1 . The last part of Erd˝ os-Tarski [1943], subtitled General remarks on inaccessible numbers, includes a list of six problems, of which problems 5 and 6 were discussed in §4.3. The following is a problem for an inaccessible cardinal n. Problem 4. (The Graph Problem.) Is it true that if a complete graph G of power n is split into two graphs G1 and G2 , at least one of the contains a [complete] subgraph of power n? (A graph is to be defined as an arbitrary set of non-ordered couples (x, y) with x 6= y. By a complete graph of power n we mean the set of all such couples formed from the elements of a set N of power n.) In the footnote (page 328) with information on the Graph Problem, the authors cite Ramsey’s Theorem for n = ℵ0 (where the answer is positive), and a paper by Erd˝ os to appear in Revista de Tucum´ an 162 for uncountable n which are not inaccessible (where the answer is negative). The final paragraph of the footnote lists implications of the form positive solution to problem a implies positive solution to problem b. Of particular note is the fact that a positive solution of the Ramification Problem discussed in §4.3 leads to a positive solution of the Graph Problem. Proofs of these implications were postponed. Some connections between graphs and partial orders were investigated. Marczewski [1945, 307] had shown that every graph can be represented by the disjunction relation163 on some collection of sets. Kazimierz Zarankiewicz [1947] connected Marczewski’s representation of graphs via the disjunction relation to 161 An independent subset of a graph is one in which no pair of points is joined by an edge of the graph. 162 The paper by Erd˝ os mentioned here is his [1942] discussed above. 163 Given a graph represented as G = (V, E), Marczewski observed that the collection D of non-empty sets Dx = {{x, y} ∈ / V | y ∈ V \ {x}} has the property that {a, b} ∈ E if and only if Da ∩ Db = ∅.

64 symmetric relations.164 At some point in the late 1940’s and early 1950’s, Kurepa expanded his focus beyond ramified tables, partial orders and the study of monotone functions of them, to include graphs. Since a disjunction relation was one of the constituent parts of Kurepa’s relation ∗ = (, ≡, k) of ramification,165 as explicated in his thesis [1935], the paper [Marczewski, 1945], cited in the paper of Kurepa discussed below, may have been the one that led Kurepa to think about applying his Fundamental Relation (see the end of §3) to graphs. In May 1950 Kurepa proved the following theorem for a binary symmetric relation166 G = (G; ρ), where kG is the cardinality of the vertex set, kc G is the supremum of the sizes of connected subsets of G,167 and ks G is the supremum of the sizes of disconnected subsets of G.168 We will call this theorem Kurepa’s Graph Relation ([1953], [1996, 399]): Theorem 0.1 For any graph G = (G; ρ) one has (0.4)

kG ≤ (2ks G)kc G .

For any ℵα and any cardinal number n ≤ 2ℵα there is a graph g = g(ℵα , n) such that (0.5)

kc g ≤ ℵα , ks g ≤ ℵα , kg = n;

in particular (for n = 2ℵα ) there is a graph Mα such that (0.6)

kc Mα = ℵα ks Mα , kMα = 2ℵα .

With his orientation toward the study of partial order and the fact that he was updating his proof of the Fundamental Relation from [1939], Kurepa referred to the totally disconnected sets as antichains and the pairwise connected sets as chains. Toward an overview of Kurepa’s proof, for α < (kc G)+ ,Slet Tα = α G be the set of functions (sequences) from α into G. Note that T = α Tα is a tree under end-extension. Let δ(X) denote a maximal disconnected subset of X. Kurepa used δ to define sets Dα ⊆ Tα (see below) by recursion on α such that D = S {Dα : α < (kc G)+ ∧ Dα 6= ∅} is a subtree of T closed under initial segments that has the properties that (1) each element is an enumeration of a chain (complete subgraph) in G, and (2) each element with domain a limit ordinal is the union of 164 Kurepa

cited Zarankiewicz’ paper in [Kurepa, 1959a]. Erd˝ os, in Math Review MR0023047 (9,297c), translated the Zarankeiwicz results for symmetric relations into the language of finite graph theory and noted that the author’s results can be deduced from [Tur´ an, 1941]. 165 Kurepa used k as the incomparability relation; ≡ was an equivalence relation, i.e. equality in the case of trees; and > was the converse of λ, and let f : κ → P(κ) be a set mapping with the property that |f (α)| < λ for every α < κ. Then there is a set X ⊆ S of cardinality κ free with respect to f .174

5.1

The partition calculus

This subsection details chronologically the work of Erd˝os, Hajnal, Kurepa, Rado, and others as they explored a variety of approaches to finding subsets with uniform behavior in graphs, binary symmetric relations, and in distributions, partitions and colorings of r-tuples. A chronological presentation was chosen to place in historical context the May 1950 results of Kurepa [1953] whose mathematical context was discussed in §4.4. The Erd˝ os-Rado paper [1950] has been frequently cited as the beginning of the study of canonical partitions.175 Any decomposition or coloring function f defined on r-tuples of a set A induces the “same color” equivalence relation on the r-tuples of A. This equivalence relation is defined even when the number of colors is infinite. Erd˝ os and Rado proved that for each finite r, there is a finite set Cr of equivalence relations on the r-element subsets of N with the property that for every equivalence relation E on the r-tuples of A there is some infinite B ⊆ N and some F ∈ Cr such that the restrictions of E and F to the r-tuples of B are identical. We 173 Andr´ as Hajnal (May 13, 1931 – ) was awarded his doctorate in 1957 at J´ oszef Attila University in Szeged, Hungary where his advisor was L´ aszl´ o Kalmar, a logician. His thesis was on relative constructibility (see Kanamori’s first chapter for more on Hajnal’s thesis work). The Mathematical Genealogy Project site lists 1956 for the year of his doctorate, but a curriculum vitae accessed September 9, 2010 from Hajnal’s Hungarian website at http://www.renyi.hu/ ahajnal/hajn2006.pdf lists 1957. 174 A set mapping is a function f : S → P(S) so that f (s) ∈ / s for every s ∈ S. A subset X ⊆ S is free with respect to a set mapping f on S if for all x, y ∈ X, x ∈ / f (y). See [Komj´ ath and Shelah, 2000] for the history of problems on set mappings and for some set mapping results about ℵn at the end of the century. The history dates back to the thirties and a question of Paul T´ uran, and includes results by Sophie Piccard and Stanislaw Ruziewicz, one of the founders of the Lw´ ow School. 175 The seminal paper [Ramsey, 1930] has an earlier classification of r-ary relations.

5. 1950-1960: FOUNDATION OF THE PARTITION CALCULUS

69

will call such a collection Cr a canonical basis for the equivalence relations on the r-tuples of A. For concreteness, we note that for pairs, the canonical equivalence relations are s ≡min t iff min(s) = min(t); s ≡max t iff max(s) = max(t) and s ≡= t iff s = t; and the equivalence relation in which all s and t are equivalent. For each finite positive r and each I ⊆ r, let EI be the equivalence relation on the r-element subsets of N defined by {x0 , x1 , . . . , xr−1 }< EI {y0 , y1 , . . . , yr−1 }< ⇐⇒ xi = yi for all i ∈ I. Here is a precise statement of Erd˝os and Rado’s oft-quoted canonical partition relation for r-tuples of natural numbers: Canonical Partitions for N: For every positive r < ω and every equivalence relation E on the r-element subsets of N, there is an infinite set M ⊆ ω and an index set I ⊆ {0, 1, . . . , k − 1} such that the restrictions of E and EI to r-tuples from M are identical. In [Erd˝ os and Rado, 1952a], the authors looked at partitions of order types and proved (cf. Theorem 4, pp. 428-9) that if the set of pairs of rational numbers is partitioned into two pieces, then either there is an infinite monotonic sequence whose pairs are in the first cell or there is a subset dense in an open interval all of whose pairs are in the second cell.176 Rado,177 in his joint work with Erd˝os [1952a], used the Axiom of Choice to define a partition of the collection T of all infinite subsets of an infinite set S into two classes, T = K0 ∪ K1 , so that there is no infinite set all of whose infinite subsets are in the same class as follows. Start with a well-ordering < of T . Let K0 be the set of all A ⊆ T for which there is an A0 < A with A0 ⊆ A. Set K1 = T \ K2 . Observe that if S 0 is in T and A is its