Paul Erdős’ Set Theory

Abstract

Paul Erdős has published more than one hundred research papers in set theory. It is my rough estimate that these contain more than one thousand theorems, many having an interest in their own right. Although most of his problems and results have a combinatorial flavour, and the subject now known as “combinatorial set theory” is one he helped to create, it is also true to say that his work has had a very important impact upon the direction of research in many parts of present day set theory. Whole theories have developed out of basic questions which he formulated.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 An Apology

Paul Erdős has published more than one hundred research papers in set theory. It is my rough estimate that these contain more than one thousand theorems, many having an interest in their own right. Although most of his problems and results have a combinatorial flavour, and the subject now known as “combinatorial set theory” is one he helped to create, it is also true to say that his work has had a very important impact upon the direction of research in many parts of present day set theory. Whole theories have developed out of basic questions which he formulated.

This (relatively) short note does not, and is not intended to, give a methodical survey of set theory or combinatorial set theory or even of Erdős’ work in set theory. I shall simply write about some of the ideas as I learned them during our cooperation over many years, some of the highlights, and some of the outstanding results. In many cases it will not be possible to give a detailed discussion of the present day status of some of the problems I shall mention. If the reader considers that my own name occurs too frequently in this note, I can only offer the excuse that we have published more than 50 joint papers, mostly in set theory, and I probably know these papers better than the rest of his work.

2 Early Days and Some Philosophy

Paul was a child mathematical prodigy, and he started to discover outstanding original results in number theory as a first year undergraduate. We are familiar with the names of mathematicians who influenced his early work in number theory and analysis, Pál Veress, Fejér, Davenport, Mordell to mention just a few. But this is not true for set theory. Paul told me that he learned the basics of set theory from his father, a well educated high-school teacher, and he soon became fascinated with “Cantor’s paradise”. However, he discovered set theory as a subject for research by himself.

Paul, who has always refrained from seriously formulating any kind of philosophy, was (and still is) the ultimate Platonist. $\aleph _{\omega _{\omega +1}+1}$ existed for him just as surely as 3, the smallest odd prime. He was driven by the same compulsive search for “truth” whether he was thinking about inaccessible cardinals or twin primes. Moreover, he could switch from one subject to the other in an instant. All questions which admit a relevant answer in finite combinatorics should also be asked and answered in set theory, and vice-versa. A large part of his greatness lies in the fact that he really did find the relevant questions. It was this attitude which led him to his first encounter with (actual) infinity.

In 1931, as a first year undergraduate student attending the graph theory course of Dénes König, he proved a generalization of Menger’s theorem for infinite graphs. This only appeared in 1936 at the end of König’s book on graph theory. In 1936 he wrote a paper jointly with Tibor Gallai and Endre Vázsonyi having a similar character; they gave necessary and sufficient conditions for an infinite graph to have an Euler line [1, 2].

The next paper I have to mention [ESz], about finite combinatorics, was written with George Szekeres in 1935. They rediscovered the finite version of Ramsey’s theorem and proved a fundamental Ramsey-type result of finite character: If G is a graph having $\left ({ k+\ell-2 \atop k-1} \right )$ vertices (k,ℓ ≥ 3), then either G contains a complete graph on k vertices or there is an independent set of ℓ vertices. From then on he always had in mind possible generalizations of Ramsey’s theorem, and so became the creator of both finite and infinite Ramsey theory.

3 Infinite Ramsey Theory: Early Papers

The Ramsey theorem is about partitions of (finite) k-element subsets of ω (the set of non-negative integers), and in the mid-1930s Erdős began to speculate about partitioning the countable sets. He corresponded with Richard Rado in Cambridge, England about this problem and Rado proved the first theorem saying that “nothing can be said in this case”. The result appeared only much later, in the early 1950s, in a sequence of joint papers by them [9, 12, 13, 18]. I will return to this later.

Erdős’firstrealset-theoreticresultappearedinapaperofDushnikandMiller [DM].The theorem,nowknownastheErdős;Dushnik,Millertheorem,saysthatforaninfinitecardinal κ, if a graph onκvertices does not contain an infinite complete subgraph, then there is an independent set of vertices of size κ. This was the first “unbalanced” generalization of Ramsey’s theorem. Once the result is formulated, the verification for regular κ is a fairly easy exercise. Erdős proved it for singular κ, and his proof, which required a good technical knowledge of the set theory of those days, is included in the Dushnik-Miller paper.

Soon after, in 1942, he proved in [3] the basic theorems of infinite Ramsey theory. Let [X]^r denote the set of r-element subsets of X, and let f : [X]^r → γ be an r-partition of γ colours on X. A set H ⊆ X is homogeneous for f in the colour ν < γ if f(Y ) = ν for all Y ∈ [H]^r. More than 10 years later in joint work with Paul, [12], Richard Rado introduced the partition symbol

$$\displaystyle{\kappa \rightarrow (\lambda _{\nu })_{\nu <\gamma }^{r}}$$

to denote the following assertion: for any r-partition f : [κ] ^r →γ there are ν < γ and H ⊆κ such that |H| = λ _ν and H is homogeneous for colour ν. The negation of this is denoted by replacing the arrow by a crossed arrow, ↛. If λ _ν  = λ for all ν < γ, the notation $\kappa \rightarrow (\lambda )_{\gamma }^{r}$ is used; this is called the “balanced” partition symbol.

Using this notation, Ramsey’s theorem states

$$\displaystyle{\omega \rightarrow (\omega )_{k}^{r}\mbox{ for }1 \leq r,k < w.}$$

The Erdős; Dushnik, Miller theorem says, for any infinite cardinal κ,

$$\displaystyle{\kappa \rightarrow {(\kappa ,\aleph _{0})}^{2}.}$$

The result of Rado I did not state says, for every κ,

$$\displaystyle{\kappa \nrightarrow (\aleph _{0})_{2}^{\aleph _{0} }.}$$

Using these notations, the results proved by Erdős in the 1942 paper are the following:

• (i) ${({2}^{\lambda })}^{+} \rightarrow {(\lambda }^{+})_{\lambda }^{2}.$

• (ii) ${2}^{\lambda } \nrightarrow (3)_{\lambda }^{2}.$

• (iii) Assuming the generalized continuum hypothesis (GCH in what follows) $\aleph _{\alpha +2} \rightarrow {(\aleph _{\alpha +2},\ \aleph _{\alpha +1})}^{2}.$

• (iv) ${2}^{\lambda } \nrightarrow {(\lambda }^{+})_{2}^{2}.$

He attributes (iv) to Sierpiński, who proved it for $\lambda = \aleph _{0}$. He also mentions that the obvious ↛ relation (ii) was pointed out to him by Gödel in conversation.

Of course, the partition symbol was not used in that early paper. In fact Erdős was always slightly resistant to its use. Later, when forced, he did sometimes write the symbol, but I have never seen him read it. When we were discussing such relations he frequently asked me in a complaining voice to “state it in human language”.

The observant reader would already have noted that (iii) was an attempt to find the right generalization of the Erdős; Dushnik, Miller theorem. We will return to this topic later.

4 His “Remarks”

As yet we are still in 1943, and in that year two more significant papers appeared. First I want to say a few words about [5], “Some remarks on Set Theory”. I quote the first sentence: “This paper contains a few disconnected results on the theory of sets.” The “Remarks” became a series. Eleven of them appeared in all. The fifth and sixth were written jointly with Géza Fodor, the seventh to ninth and eleventh with me, and the tenth with Michael Makkai. Several of these papers contain set-theoretical results about Euclidean spaces, Hamel bases and other objects that are familiar to analysts and combinatorialists. The editors and I have decided that this typical Erdős genre deserves a separate treatment, and this will be given by Péter Komjáth in this volume. However, I cannot resist mentioning the first theorem in the first of these papers, the Erdős-Sierpiński duality principle. This generalization of an earlier result of Sierpiński states: Assuming the continuum hypothesis (CH) there is a surjective map $f : \mathbb{R} \rightarrow \mathbb{R}$ which interchanges sets of Lebesgue measure zero and sets of first category.

Stating this theorem allows me an opportunity to say something about his attitude towards the generalized continuum hypothesis (GCH) and mathematical logic in general. It should be remembered that in 1943 Gödal’s proof of the consistency of GCH was quite new. Erdős always knew and appreciated and applied these results. He was happy to have them as a more-or-less justified tool to prove new theorems, and if he could not solve a set theory problem he always tried to solve it assuming GCH. On the other hand, later on he was always uneasy and disappointed if one of his favourite problems turned out to be independent, and he would remark “independence has raised its ugly head”.

5 Large Cardinals: The Erdős-Tarski Paper

The cardinal κ, has the property P(κ) if there is a field of sets which contains a family of λ pairwise disjoint sets for every λ < κ, but which does not contain such a family of size κ. Much to their surprise, Erdős and Tarski [4] proved that for limit cardinalsκ, P(κ) holds if and only if κ, is an uncountable inaccessible. First of all it was surprising that such a seemingly harmless problem should involve inaccessible cardinals which, in those days, had “hardly been born”. The second surprise was, and this is explicitly mentioned in the paper, that the negation of $P({2}^{\aleph _{0}})$ could not be proved in ZFC since it was generally believed that it would be proved consistent that ${2}^{\aleph _{0}}$ is inaccessible. (Indeed, this was one of the first corollaries of Cohen’s method.)

In their paper, they formulated several properties of inaccessible cardinals and they mentioned quite a few connections between these properties in footnotes (without proofs). For example, they knew that if κ is measurable then it has the tree property and that this implies that $\kappa \rightarrow (\kappa )_{\lambda }^{r}$ holds for all λ < κ and r < ω. Of course, they also knew that the simplest Ramsey-type theorem $\kappa \rightarrow (\kappa )_{2}^{2}$ is false if κ is not strongly inaccessible. Later, in 1960 when Tarski, using a result of Hanf, proved that “small” inaccessibles are not measurable, and the theory of large cardinals was created, it became necessary to publish these classical proofs. A new Erdős-Tarski paper (written by Donald Monk) appeared in 1961.

It is of interest to note that Erdős and Tarski made a historical mistake in [4]. It was vaguely speculated that it may turn out to be at least consistent that all strongly inaccessible cardinals are measurable. This probably postponed the discovery of the true situation for almost 20 years. I cannot say how seriously Tarski believed this (I did try to ask him), but Erdős quite happily accepted this hypothesis in the spirit I described in §2. In our joint work from 1956 to 1960 we investigated every combinatorial property of strongly inaccessible cardinals under the assumption that they are measurable, although we did always mention that this was an assumption. However, as was so often the case for Paul, in the end this turned out to be quite fortunate. I will come back to this in §9 and §10.

6 Set Mappings and Compactness

Erdős visited Hungary in 1948 for the first time after the Second World War. Very likely it was during this visit that he recalled an old problem of Paul Turán. Let f be a set mapping on a set X, i.e. $f : X \rightarrow \mathbb{P}(X)$ (the power set of X) such that x∉f(x). We say that f is of order λ if | f(x) |  < λ for x ∈ X. A subset S ⊂ X is independent for f if for all x, y ∈ S, y∉f(x). For combinatorialists, a set mapping of type λ is just a loop-free digraph having out degrees < λ. Turán was interested in the case when $X = \mathbb{R}$ and f(x) is finite, i.e., f is of order ω, and he asked if there is a free set of power ${2}^{\aleph _{0}}$. A young Hungarian, Dezső Lázár who was killed during the war, proved this and he also proved that if f is of order λ < κ ≥ω then there is a free set of size κ provided κ is a regular cardinal. Ruziewicz conjectured that this is true for any κ ≥ ω.

Erdős proved this conjecture assuming GCH in the second of his “Remarks” in 1950 [10]. It remained an open question for ten more years if GCH is really needed. In 1960, I proved the result in ZFC in [H 1] where more history of the problem can be found.

Typically, even before proving the result he conjectured that if λ is an infinite cardinal and f is a set mapping of order λ on any set X, then X is the union of λ independent sets, i.e. the digraph has chromatic number at most λ. This was proved by Géza Fodor [F]. Erdős investigated the problem for finite λ in a paper with N.G. de Bruijn [11]. A little reflection will convince the reader that if the underlying set is finite then it is the union 2λ − 1 independent sets (and this is best possible). To show that this is true for arbitrary X they proved that for any k < ω if every finite subgraph of a graph G has chromatic number of at most k then G also has chromatic number at most k.

The reader may say that this is a consequence of either Tychonov’s theorem on the product of compact spaces or Gödel’ s compactness theorem, but this is how compactness was introduced to infinite combinatorics. Let me point out that it would be quite difficult to find a proof of the set mapping theorem not using compactness. I do not know of any.

Erdős continued the investigation of set mappings with Géza Fodor in [19] and [21]. I want to mention one of their theorems, which later proved to be useful in applications.

Assume f is a set mapping of order λ < κ ≥ω on κ. Let τ < κ and let X _α (α < τ) be a sequence of subsets of κ each of size κ. There is a set S free for f which meets each X _α in a set of size κ. For singular κ their proof used GCH, but my method yields this in ZFC as well.

7 A Partition Calculus in Set Theory

The partition calculus was developed by Erdős and Rado in the early 1950s. The long paper [18] contains all the results they had proved up until then. Their first discovery was that the partition relation $\kappa \rightarrow (\lambda _{\nu })_{\nu <\gamma }^{r}$ made sense for order types as well as cardinals, or even a mixture of these. This led them to a great variety of new problems, some simple and some difficult, but requiring different methods. Let me mention just a few of these. For what countable ordinals α does α → (α, 3)² hold? For what α < ω ₁ does $\lambda \rightarrow (\alpha )_{k}^{2}$ hold, where k is finite and λ is the order type of the reals? They proved the pleasing result that $\eta \rightarrow {(\aleph _{0},\eta )}^{2}$, where η is the order type of the rationals, but for what other countable types is this true? They also noticed that the proof of the Erdős; Dushnik, Miller theorem in the special case κ = ω ₁ actually gives the slightly stronger fact that $\omega _{1} \rightarrow {(\omega _{1},\omega +1)}^{2}$, and then a natural question is, what about $\omega _{1} \rightarrow {(\omega _{1},\omega +2)}^{2}$?

They proved a great many partial results and isolated the most important problems. We cannot collect all their results and problems here, instead I shall discuss some of the important new discoveries. One of these is the positive stepping up lemma which can be stated as follows: If κ is a cardinal and $\kappa \rightarrow (\lambda _{\nu })_{\nu <\gamma }^{r}$ holds, then ${({2}^{<\kappa })}^{+} \rightarrow (\lambda _{\nu } + 1)_{\nu <\gamma }^{r+1}$. Here μ ⁺ denotes the smallest cardinal greater than μ, and ${2}^{<\kappa } =\sum \{ {2}^{\mu } :\mu <\kappa \mbox{ a cardinal}\}$. Let exp _n (κ) denote the n-times iterated exponentiation (i.e. exp₀(κ) = κ and $\exp _{n+1}(\kappa ) = {2}^{\exp _{n}(\kappa )}.)$ Since ${2}^{{<\kappa }^{+} } = {2}^{\kappa }$, and ${\kappa }^{+} \rightarrow {(\kappa }^{+})_{\kappa }^{1}$ just expresses the fact that κ ⁺ is a regular cardinal, we obtain by induction the

Erdős-Rado Theorem:

$$\displaystyle{{(\exp _{n}(\kappa ))}^{+} \rightarrow {(\kappa }^{+})_{\kappa }^{n+1}.}$$

In particular, we have ${({2}^{\kappa })}^{+} \rightarrow {(\kappa }^{+})_{\kappa }^{2},{({2}^{{2}^{\kappa } })}^{+} \rightarrow {(\kappa }^{+})_{\kappa }^{3}$ etc. Quite often in the literature only the first of these (case n = 2) is referred to as the Erdős-Rado theorem, but we have seen that this was already proved in 1943. There can be very few theorems in set theory which have received so many “simplified” proofs as the Erdős-Rado theorem. But in the early 1950s there was no pressing-down lemma, and elementary substructures and chains had not been introduced into set theory. Erdős and Rado used the so-called ramification method. Let me outline this in a simple case. Let f : [X]² → γ be a 2-partition of X with γ colours. Pick an x ₀ ∈ X. The rest of the points can be split into γ parts according to the colour of f({x ₀, y}). Repeat this in each part and continue transfinitely. We get a tree or ramification system as they called it. At the α stage we will have | γ | ^| α | parts. If X has large enough cardinality, the tree we get will have large height. The points picked along a branch of this tree will form a prehomogeneous set, i.e., the colour of a pair $\{x_{\alpha },x_{\beta }\}$ will depend only upon the point, say x _α , which was chosen first. This method is fairly hard to write down formally, but it is really quite intuitive. It was elaborated in great detail in the Erdős-Rado papers and was used for several years to obtain positive partition relations for the case when the underlying set has regular cardinality. Although most of the important proofs have been streamlined to “linear” ones, there is really no algorithm for this translation , and the intuition behind ramification serves as a good tool to obtain new results.

They also discovered polarized partition relations. The symbol

$$\displaystyle{\left ({ \kappa \atop \lambda } \right ) \rightarrow \left ({ \kappa _{\nu } \atop \lambda _{\nu }} \right )_{\nu <\gamma }^{1,1}}$$

means the following: whenever f : κ ×λ → ν is a colouring with γ colours, then there are ν < γ, $K \in {[\kappa ]}^{\kappa _{\nu }}$ and $L \in {[\lambda ]}^{\lambda _{\nu }}$ such that K ×L is homogeneous for f in the colour ν. For combinatorialists, this is just Ramsey for complete bipartite graphs, and the reader can easily formulate the generalization to s-partite graphs.

However, this is not just formalism. It turned out that quite a few problems about polarized partitions are basic questions in set theory. As an illustration, they proved

$$\displaystyle{\left ({ \aleph _{1} \atop \aleph _{0}} \right ) \rightarrow \bigg {({ \aleph _{1} \atop \aleph _{0}} ,{ \aleph _{0} \atop \aleph _{0}} \bigg)}^{1,1}.}$$

In “human language” this says: if A _α (α < ω ₁ ) are arbitrary subsets of ω, then either the intersection of $\aleph _{1}$ of them is infinite, or the union of $\aleph _{0}$ of them has an infinite complement. They attributed the negative relation

$$\displaystyle{CH \Rightarrow \left ({ \aleph _{1} \atop \aleph _{0}} \right )\not\rightarrow \bigg{({ \aleph _{1} \atop \aleph _{1}} ,{ \aleph _{0} \atop \aleph _{0}} \bigg)}^{1,1}.}$$

to Sierpiński who, of course, proved this in a different context.

There is one more important partition relation I should mention, and this realized Paul’s old wish to have a Ramsey theorem for something more than just k-element sets. They introduced the symbol $\kappa \rightarrow (\lambda )_{\gamma }^{<\omega }$ to denote the following statement: for every sequence $f_{n} : {[\kappa ]}^{n} \rightarrow \gamma$ of n-partitions of κ with γ colours, there is a subset H ⊂κ of cardinality λ which is simultaneously homogeneous for each f _n. They only proved that ${2}^{\aleph _{0}} \nrightarrow (\aleph _{0})_{2}^{<\omega }$ with a clever ad-hoc construction, and they asked if $\kappa \rightarrow (\aleph _{0})_{2}^{<\omega }$ can be true for any cardinal κ? We turn back to the discussion of this important symbol in §9 and §10.

There is one more type of partition theorem which I should have mentioned earlier. In [9] they proved the first canonical Ramsey theorem, and this also led to a long sequence of investigations, improvements and generalizations. Just to give the flavour of what this is all about, I will state just one special case. Let $f : {[\omega ]}^{2} \rightarrow \gamma$ be a 2-partition of ω with any number of colours. Then there is an infinite subset H ⊆ω such that either H is homogeneous for some colour, or all pairs in H have different colours, or H is prehomogeneous (the colour of a pair depends only on the least element), or H is endhomogeneous (the colour of a pair depends only on the largest element).

8 My First Encounter with Paul

Erdős visited Hungary in 1955 for the first time since the country had become a member of the Eastern block. He was an Hungarian citizen traveling on an Hungarian passport, and he could not have returned earlier if he wanted to leave again. But in the “liberalized” atmosphere of 1956 the Academy was allowed to elect him as a member and the government granted him a special diplomatic type of passport which allowed him to come and go whenever he wished. This was a great opportunity for young Hungarian mathematicians who had heard of him only by name (of course, it was impossible for us to travel to the West before 1956).

At that time I was a graduate student of László Kalmár in Szeged (a small town on the south-eastern border of Hungary). Paul travelled around the country in 1956 and came to visit the mathematics department at the University of Szeged. He had already corresponded with Géza Fodor who was then a young assistant professor in the department. I was introduced to him as “a promising young man” studying set theory, and soon we were left alone in Professor Kalmár’s office sitting in two enormous armchairs facing each other over a coffee table. I thought he was very old—he was 43 years old and I was 25. I felt very honoured, and a little embarrassed, to be left alone with this famous man. I did not know then that he had met most of his young collaborators in a similar way. He first asked me what were my interests in set theory. I was then writing my thesis on a subject which later was called relative constructibility, and I was quite proud of it. So I started to explain my results with some enthusiasm. He listened to me very politely, and when I had finished he asked “and are you interested in normal set theory as well?” Of course, we were not on first-name terms then and so the question was phrased in a very polite form of Hungarian that is used for addressing a stranger. But it was clear that it was a genuine inquiry and he meant no harm.

Earlier I had thought of a problem when I heard about all the set-mapping results from Géza, What if we investigate set-mappings of more variables, and I asked if there would be large free subsets in this case too? To tell the truth, as a student of Kalmár, I was trained to think like a logician. So what I had in mind was this: if X is a large set and to every finite subset $V \subseteq X$ we associate a countable F(V ) ⊂ X such that $F(V ) \cap V = \varnothing$, is there a large independent set? I even had the vague idea that if F(V ) is the Skolem hull of V in some structure, then an “independent set” would really deserve its name.

Luckily, Paul liked that one! It started a furious activity and the conversation became more fluent and colloquial. The first thing I learned from him (and this took quite a while) was that he would not start to think about the general case. He first wanted to know what happened for set mappings defined on pairs. He proved several lemmas and some partial results and stated a few conjectures. He then suddenly remembered that there was something else he had to do and he called Géza. Quite close to the mathematics building in Szeged stands a rather ugly cathedral built in the 1930s with two high towers. It turned out that he “must” climb the 300 odd stairs to the top! Géza had earlier agreed to accompany him, and he then gently began to persuade me to come along too. I had by then lived for 2 years in Szeged, and I had never had the slightest difficulty in resisting any pressure to visit the tower, especially since the surrounding countryside is absolutely flat and so there was not very much to see. However, much to my own surprise, I could not resist this invitation. Climbing those stairs more results and conjectures were formulated by him while, at the same time, he was complaining that he felt a little dizzy.

That day ended with dinner at Kalmár’s house where the conversation continued mainly about set mappings, but sometimes interrupted with some of his comments on “Sam and Joe”. When we parted, it was almost as from an old friend—there was a joint-paper half ready, which could be completed by correspondence.

9 Our First Joint Paper

The notation used for discussing set-mapping problems is not standardized as in the case of partition relations. A set-mapping of orderλ and typeμ on κ is a function $f : {[\kappa ]}^{\mu } \rightarrow {[\kappa ]}^{<\lambda }$ such that f(x) ∩ x = ∅ for all x ∈ dom(f), and a set S ⊆ κ is free if f(x) ∩ S = ∅ for all x ∈ [S]^μ. I shall denote by $\mathrm{Free}(\kappa ,\lambda ,\mu ,\nu )$ the following assertion: For every set-mapping of order λ and type μ on κ there is a free set of cardinality ν. Likewise, $\mathrm{Free}(\kappa ,\lambda ,<\mu ,\nu )$ denotes the corresponding assertion when $f : {[\kappa ]}^{<\mu } \rightarrow {[\kappa ]}^{<\lambda }$.

Our very first result was to prove that $\mathrm{Free}(\exp _{n-l}{(\lambda )}^{+},\lambda ,n{,\lambda }^{+})$ holds for every infinite λ. The proof of this uses the Erdős-Rado theorem which I had learned during my first conversation with Paul. I also learned that it was not known if the Erdős-Rado theorem is best possible, for example it was not known then if

$$\displaystyle{{2}^{{2}^{\aleph _{0}} } \nrightarrow (\aleph _{0})_{2}^{3}}$$

holds. Assuming GCH we could prove $\neg \mathrm{Free}(\aleph _{1},2,2,\aleph _{1})$ so that our theorem is best possible for n = 2, but for n > 2 any progress seemed to lie far in the future. I will return to this in the section on the negative stepping-up method we developed with Rado, but let me say now that there are only consistency results to show that the theorem is best possible.

I was therefore surprised when shortly afterwards I received a letter from Paul (who was visiting Israel) claiming that $\mathrm{Free}(\kappa ,\lambda ,n,\kappa )$ holds for n < ω and any uncountable limit cardinal κ > λ. The proof used GCH and I realized that it only worked for singular κ (the real theorem is for κ a singular strong limit cardinal, i.e. 2^τ < κ for τ < κ.) We now know that this is a special case of a general “canonization” theorem proved later with Rado, but which Paul discovered in at least two other interesting contexts before the general theorem was formulated. I wrote to tell him that I could not see how the proof works for regular limit κ. He replied by return of post that I was right, but the theorem was true since we may use the “measure hypothesis” from Erdős-Tarski, and he wrote down a proof that $\mathrm{Free}(\kappa ,\lambda ,n,\kappa )$ holds for finite n and λ < κ, an uncountable measurable cardinal. I have to say that during my studies I had read the Erdős-Tarski paper, but either I skipped the footnotes or I did not recognize the significance of the remarks. However, after reading the letter, I did understand the strength of the hypothesis, and the same day proved that it implies $\mathrm{Free}(\kappa ,\lambda ,<\omega ,\kappa )$. Later, when the paper was actually written, we realized that the proof actually gave the stronger result that

$$\displaystyle{\kappa \rightarrow (\kappa )_{\lambda }^{<\omega }}$$

holds for λ < κ if κ > ω is a measurable. This is perhaps one of our best-known joint theorems, and I will say more about this in the next section.

This brings me to our first joint oversight. Although our joint paper with Rado did not appear until 1965, I already had a weak form of the negative stepping-up lemma in 1957 (in fact it was because of this that we decided to write the triple paper on partition relations even though Erdős and Rado had already obtained a great many new unpublished results.)

I told Paul that the negative stepping-up gives us that

$$\displaystyle{\kappa \nrightarrow (\omega )_{2}^{<\omega } \Rightarrow {2}^{\kappa } \nrightarrow (\omega )_{ 2}^{<\omega }.}$$

He immediately pointed out that it is easy “to go through” singular cardinals, and we put into the paper the remark that $\kappa \nrightarrow (\omega )_{2}^{<\omega }$ holds for all κ, less than the first strongly inaccessible cardinal κ ₀ > ω. We only realized later [35], after we learned the Hanf-Tarski results, that this almost trivially implies that

$$\displaystyle{\kappa _{0} \nrightarrow (\omega +1)_{2}^{<\omega },}$$

and therefore, by our theorem, it follows that κ ₀ is not measurable. Unfortunately, this argument is not very strong, we could never make it work beyond the first fixed point in the sequence of inaccessibles.

10 Erdős Cardinals and the Strength of κ → (λ)₂ ^< ω

The real strength of the statement $\kappa \rightarrow (\lambda )_{2}^{<\omega }$ was discovered by the Berkeley school in the early 1960s. Dana Scott first proved that the existence of a measurable cardinal contradicts Gödel’s axiom of constructibility (V = L). Soon afterwards Gaiffman and Rowbottom proved that it also implies that ω has only countably many constructible sets, and more generally Rowbottom proved that $\kappa \rightarrow (\omega _{1})_{2}^{<\omega }$ implies that ω ₁ is inaccessible in L.

Rowbottom also generalized our theorem with Paul. According to the Kiesler-Tarski paper [KT] it was Dana Scott who introduced the notion of a normal measure (a κ-complete 0-1 measure on κ satisfying the pressing down lemma, i.e. if f is regressive on a subset of measure one, then it is constant on a set of measure one.) It was known that if κ is measurable then it carries a normal measure, and Rowbottom proved that, if there is a normal measure on κ and $f : {[\kappa ]}^{n} \rightarrow \lambda (n < w,\lambda <\kappa )$, then there is a homogeneous set of measure one. Of course, this immediately yields our theorem, and the proof actually becomes easier.

I happened to spend 1964 at Berkeley with Tarski’s group and gave a course of lectures on Erdős-Rado set theory. I could not have been too successful as a lecturer, more than 20 people attended the first lecture, and in the end I was left with an audience of three—two students, Reinhardt and Silver, and a young assistant professor Donald Monk. I told them everything I knew about ordinary partition theorems and the little I knew about $\kappa \rightarrow (\lambda )_{2}^{<\omega }$. Silver apparently got interested and his thesis [Si], which appeared in 1966, contained some fantastic discoveries.

First he realized that the real strength of $\kappa \rightarrow (\lambda )_{2}^{<\omega }$ is that it yields, for any given structure on κ, a set of indiscernibles having order type λ (i.e. a set of ordinals such that any two similarly ordered n-tuples satisfy the same formulas.) Using this he proved that the smallest κ satisfying $\kappa \rightarrow (\omega )_{2}^{<\omega }$ must be very large, for example there must be many weakly compact cardinals less than κ. He showed that, for α < ω ₁, if $\kappa \rightarrow (\alpha )_{2}^{<\omega }$ holds, then it is true in L, and finally he proved that if $\kappa \rightarrow (\omega _{1})_{2}^{<\omega }$ holds, then O ^# exists, which means that L is very small, and this expresses the real strength of $\kappa \rightarrow (\omega _{1})_{2}^{<\omega }$. I am not willing to write down the technicalities of this here.

Let me remind the reader that one of the few consequences of the axiom of constructibility which Gödel himself had noticed was that there is an uncountable analytic complement (the complement of a continuous image of a Borel set) which has no perfect subset. It was Solovay who proved that if $\kappa \rightarrow (\omega _{1})_{2}^{<\omega }$ holds for some κ then such a set cannot exist. This was the first application in descriptive set theory. It is stated in Descriptive Set Theory, the 1978 book of Moschovakis, that all applications of the existence of measurable cardinals in descriptive set theory come from a κ satisfying $\kappa \rightarrow (\omega _{1})_{2}^{<\omega }$. All this shows that such cardinals deserve a special name, and the story I have written down shows that they are quite rightly called Erdős cardinals.

11 The Early Sixties. A Long Chapter

After 1956, Paul came home to visit his mother every year. He usually spent some months in Budapest where I also lived at that time. When he was at home I went to work with him at their apartment two or three times a week. Mrs. Erdős was not only a devoted mother to Paul, but she was also an efficient secretary and would keep a record of his publications and look after his papers. When I visited them she would make us coffee and then leave us alone to “work”. Our meetings had no prepared agenda, sometimes we went through earlier proofs, sometimes we had to read a manuscript or proof sheets, but the main point of our conversations was always the discovery of new problems and to start thinking about them. Paul was fantastically fast in both making and understanding proofs and finding the new questions. Though I usually made some notes, they were never quite satisfactory. We both needed to rely on our memories. This was quite a good fit, he always remembered the theorems and then I could scrape together the old proofs. I think now that these visits were real highlights in my life.

Now I have to change strategy. I cannot continue telling the results paper by paper, and in any case they were not proved in the order of publication. Starting around 1957 or 1958, we agreed to write a triple paper with Rado on the partition calculus and the three of us set aside everything which we thought belonged there. Already in 1960 I visited Rado in Reading to work on the triple paper, carrying with me an almost completed manuscript. So, in this long section I will open subsections about the results of these years with an indication of where they appeared.

11.1 Canonization

Let f : [X]^r → γ be an r partition of length γ of X. Let $\langle Y _{\alpha } :\alpha <\varphi \rangle$ be a sequence of disjoint subsets of X , $Y =\bigcup _{\alpha <\varphi }Y _{\alpha }$ For a subset υ ∈ [Y ]^r there is a number s(υ) ≤ r an increasing sequence $\alpha (\upsilon ) =\langle \alpha _{i}(\upsilon ) : i < s(\upsilon )\rangle$ of ordinals and a sequence $r(\upsilon ) =\langle r_{i}(\upsilon ) : i < s(\upsilon )\rangle$ of integers, defining the position of υ in the partition $Y =\bigcup _{\alpha <\varphi }Y _{\alpha },$ so that $\sum \nolimits _{i<s(\upsilon )}r_{i}(\upsilon ) = r$ and $\vert \upsilon \cap Y _{\alpha _{i}(\upsilon )}\vert = r_{i}(\upsilon )$ for i < s(υ). Two r-element sets $\upsilon {,\upsilon }^{{\prime}}\in {[Y ]}^{r}$ have the same position if $\alpha (\upsilon ) =\alpha {(\upsilon }^{{\prime}})$ and $r(\upsilon ) = r{(\upsilon }^{{\prime}})$. f is canonical with respect to the sequence $(Y _{\alpha } :\alpha <\varphi )$ if for any two υ, υ ^′ having the same position

$$\displaystyle{f(\upsilon ) = f{(\upsilon }^{{\prime}})}$$

The “canonization” theorem of [43] tells us that: there is an integer k _r such that whenever $\langle X_{\alpha } :\alpha <\varphi \rangle$ is a sequence of subsets of X with fast enough increasing cardinalities,

$$\displaystyle{\vert X_{\alpha }\vert >\exp _{k_{r}}(\vert \bigcup _{\begin{array}{c}\beta <\alpha \end{array}}X_{\beta }\vert ),}$$

then there is a disjointed sequence $Y _{\alpha } \subset X_{\alpha }(\alpha <\varphi )$ also with fast increasing cardinalities, $\vert Y _{\alpha }\vert > \vert \bigcup _{\beta <\alpha }X_{\beta }\vert$ , such that f : [x] ^r →γ is canonical with respect to the sequence $\langle Y _{\alpha } :\alpha <\varphi \rangle$ , provided $\gamma ,\varphi < \vert X_{0}\vert$.

One corollary of this is the following. Assume κ is a singular strong limit cardinal then $\kappa \rightarrow (\kappa ,\lambda _{\nu })_{\nu <\gamma }^{2}$ if and only if $\mathrm{cf}(\kappa ) \rightarrow (\mathrm{cf}(\kappa ),\lambda _{\nu })_{\nu <\gamma }^{2}$. The ‘only if’ part comes easily using a canonical partition, and the ‘if’ part uses the canonization theorem. The reader should remember the Erdős; Dushnik, Miller theorem $\kappa \rightarrow {(\kappa ,\aleph _{0})}^{2}$. Now the above result tells us, at least with GCH, for which singular cardinals κ the relation $\kappa ,\rightarrow {(\kappa ,\aleph _{1})}^{2}$ holds. For example, $\aleph _{\omega _{1}} \nrightarrow {(\aleph _{\omega _{1}},\aleph _{1})}^{2}$ but $\aleph _{\omega _{2}} \rightarrow {(\aleph _{\omega _{2}},\aleph _{1})}^{2}$. By now I do not really have to tell the reader that this is the form discovered by Paul.

It would be nice to have a necessary and sufficient condition for the case of arbitrary singular κ. We knew that for a singular κ, say with $\mathrm{cf}(\kappa ) = {({2}^{\aleph _{0}})}^{+}$, to have $\kappa ,\rightarrow {(\kappa ,\aleph _{1})}^{2}$ it is necessary to have ${\lambda }^{\aleph _{0}} <\kappa$ for λ < κ We repeatedly asked if this is sufficient. It was proved by Shelah and Stanley in the 1980s that this is consistently false [SS1].

When preparing the material of our book with Attila Máté and Richard Rado [100] where we tried to discuss the ordinary partition relation is ZFC, we isolated the following problem. Assume there is an increasing sequence of integers n _k : k < ω such that

$$\displaystyle{\aleph _{\omega } < {2}^{\aleph _{n_{0}} } <\ldots < {2}^{\aleph _{n_{k}} } <\ldots }$$

Does it follow that ${2}^{<\aleph _{\omega }}\rightarrow (\aleph _{\omega })_{2}^{2}$ holds? Clearly our canonization does not work in this case. Shelah proved this with a new type of canonization theorem [S1], and parts of his results are given in the book. Further uses of “canonization” will be mentioned later.

One last remark. It is interesting to see how combinatorial ideas do pop up in different topics. When Shelah obtained with such miraculous speed his celebrated result on the bound in van der Waerden’s theorem, he was already the best expert on canonization, and one of the main lemmas in his proof is indeed a (finite) canonization theorem.

11.2 Square Brackets

Sierpiński proved ${2}^{\aleph _{0}} \nrightarrow (\aleph _{1})_{2}^{2}$ by well ordering the continuum and defining a partition of the pairs into two classes, so that a pair ordered in the same way in both the natural ordering and the well-ordering belongs to the first class.

Paul told me that he formulated a generalization of this in 1956 with the following question. Can one split the pairs of reals into three classes so that every subset of size $\aleph _{1}$ (or ${2}^{\aleph _{0}}$) contains a pair from each class?

He soon proved this assuming CH. We discovered that whenever a partition relation fails, one can ask for a corresponding weaker property, and in [43] we introduced the following square bracket relation

$$\displaystyle{\kappa \rightarrow [\lambda _{\nu }]_{\nu <\gamma }^{r}.}$$

This means that for every f : [κ]^r → γ there is a ν < γ and a subset H ⊂ κ, | H |  = λ _ν so that f does not take the value ν on the r-tuples of H.

It is worthwhile to formulate separately the negation of the “balanced” form of this (when all the λ _ν are equal). Thus $\kappa \nrightarrow [\lambda ]_{\gamma }^{r}$ means that there is an $f : {[\kappa ]}^{r} \rightarrow \gamma$ such that all subsets of size λ are completely inhomogeneous i.e. f takes all possible values on the r-tuples of any set of size λ.

Clearly we needed some test cases. We proved that ${2}^{\kappa } {=\kappa }^{+}$ mplies ${\kappa }^{+} \nrightarrow {[\kappa }^{+}]_{{\kappa }^{+}}^{2}$, and only later did we realize that this was also known to Sierpińiski in a different context. But probably the nicest result was the following:

If κ is a strong limit cardinal of cofinality ω, then $\kappa \rightarrow [\kappa ]_{3}^{2}.$

(Note that $\kappa \nrightarrow (\kappa ,{(cf(\kappa ))}^{+})2$ and $\kappa \nrightarrow [\kappa ]_{2}^{2}$ is a trivial corollary.) This follows from the “canonization” theorem of the previous section. Indeed it gives a stronger result. Under the above conditions on κ, for every f : [κ]² → γ, γ < κ, there is a set H ∈ [κ]^κ such that f takes at most two different values on the pairs of H.

So we introduced a third symbol, the strong square bracket. Let γ, δ be cardinals. $\kappa \rightarrow [\lambda ]_{\gamma ,\delta }^{r}(\kappa \rightarrow [\lambda ]_{\gamma ,<\delta }^{r})$ means that for every r-partition f : [κ]^r → γ with γ-colors, there is a subset H ⊂ κ of size λ such that f takes at most δ (fewer than δ) values on the r-tuples of H.

So the above theorem says that $\kappa \rightarrow [\kappa ]_{\gamma ,2}^{2}$ for singular strong limit κ of cofinality ω and γ < κ. We used this symbol to ask if $\aleph _{2} \rightarrow [\aleph _{1}]_{\aleph _{1},\aleph _{0}}^{2}$? Paul thought this was an old question of Ulam, but later we discovered that it is equivalent to a well-known model theoretical conjecture of C.C. Chang.

In §12, I will discuss the effect of our 1967 problem paper [67], but this is a good place to write down the present status of some of the square bracket problems stated in that paper. Let me begin with an innocent but very nice result of Fred Galvin

$$\displaystyle{\eta \rightarrow [\eta ]_{3}^{2}.}$$

Many generalizations of this were published later. Galvin and Shelah proved ${2}^{\aleph _{0}} \nrightarrow [{2}^{\aleph _{0}}]_{\aleph _{ 0}}^{2}$ and $\mathrm{cf}({2}^{\aleph _{0}}) \nrightarrow [\mathrm{cf}({2}^{\aleph _{0}})]_{\aleph _{ 0}}^{2}$ in 1968 [GS], they also proved some weak results like $\aleph _{1} \nrightarrow [\aleph _{1}]_{4}^{2}$ and $\aleph _{1} \nrightarrow [\aleph _{1}]_{\aleph _{1}}^{3}$ for the case when the underlying set has cardinality $\aleph _{1}$.

Again we had a false feeling. Although we did not state it explicitly, we clearly believed that $\aleph _{1} \nrightarrow [\aleph _{1}]_{\aleph _{1}}^{2}$ could not be proved in ZFC. But in 1987 Stevo Todorčević proved us wrong [T1]. He proved in ZFC that

$$\displaystyle{{\kappa }^{+} \nrightarrow [{\kappa }^{+}]_{{\kappa }^{ +}}^{2}}$$

holds for every regular κ. This was extended by Todorčević and Shelah for more successors, and inaccessibles. This was certainly one of the most significant discoveries in set theory in the 1980s requiring entirely new methods. I will come back to this for a moment in the next section. However, this still leaves open the question whether

$$\displaystyle{{2}^{\aleph _{0} } \nrightarrow [\aleph ]_{3}^{2}}$$

holds? Shelah [S2] proved that ${2}^{\aleph _{0}} \rightarrow [\aleph _{1}]_{3}^{2}$ is really consistent with ZFC. In his model ${2}^{\aleph _{0}}$ is quite large so it is still possible, but quite unlikely, that

$$\displaystyle{{2}^{\aleph _{0} } = \aleph _{2} \Rightarrow \aleph _{2} \nrightarrow [\aleph _{1}]_{3}^{2}.}$$

11.3 Jónsson Algebras-Negative Relations with Infinite Exponents

A Jónsson algebra is an infinite algebra A with countably many finitary operations such that all proper subalgebras have cardinality strictly less than IAI. The question is, for what infinite cardinals κ is there a Jónsson algebra of cardinality κ? I mention this here because of a connection with the square brackets. As pointed out by Shelah much later in the game, there is a Jónsson algebra on κ if and only if $\kappa \nrightarrow [\kappa ]_{\kappa }^{<\omega }$ holds.

I heard the problem from Tarski in 1964 and when I returned to Hungary and met Paul, we immediately had some remarks about this which we published in [45]. First we proved that if there is a Jónsson algebra on κ, then there is also one on κ ⁺, and hence there is one on $\aleph _{n}$ for n < ω. We also proved that ${2}^{\kappa } {=\kappa }^{+}$ implies that there is a Jónsson algebra on κ ⁺ since we knew that ${2}^{\kappa } {=\kappa }^{+} {\Rightarrow \kappa }^{+} \nrightarrow {[\kappa }^{+}]_{{\kappa }^{+}}^{2}$.

I must also mention that it was already proved by Kiesler and Rowbottom that there is a Jónsson algebra on every κ if V = L [KR].

It was a metatheorem for the two of us because of Rado’s theorem that “nothing is true for infinite exponents”. So we proved already in [24] that $\mathrm{Free}(\kappa ,2,\aleph _{0},\aleph _{0})$ fails for every κ and in [43] we strengthened Rado’s result to $\kappa \nrightarrow [\aleph _{0}]_{{2}^{\aleph _{0}}}^{\aleph _{0}}$. In this spirit we also proved in the Jónsson algebra paper that there is an infinitary Jónsson algebra on every κ in other words

$$\displaystyle{\kappa \nrightarrow [\kappa ]_{\kappa }^{\aleph _{0} }}$$

This became one of our best used theorems. Kunen used it for a simple proof of his famous theorem that there is no nontrivial elementary embedding of the universe into itself (disproving the hoped for existence of Reinhardt cardinals) and Solovay used it in his proof that GCH holds at every singular strong limit cardinal above a strongly compact cardinal.

Our “metatheorem” is not quite true since Foreman and Magidor [FM] recently proved that it is consistent that $\aleph _{3} \rightarrow [\aleph _{2}]_{\aleph _{2}}^{\aleph _{0}}$. It goes without saying that Erdős always assumed the axiom of choice, and I would not even mention this except that it happens that partition relations with infinite exponents may be true if we do not assume the axiom of choice, and indeed they became an important tool of set theory e.g. in investigations concern ing the Axiom of Determinacy and its consequences to descriptive set theory.

Back to the previous section, Shelah [S5] recently published quite a few theorems extending the class of cardinals κ for which there is a Jónsson algebra and then later proving the stronger result $\kappa \nrightarrow [\kappa ]_{\kappa }^{2}$. I presently do not know of any instance of the result where ${\kappa }^{+} \nrightarrow [{\kappa }^{+}]_{{\kappa }^{+}}^{<\omega }$ is true but ${\kappa }^{+} \nrightarrow [{\kappa }^{+}]_{{\kappa }^{+}}^{2}$ is not known.

11.4 Negative Stepping-Up

This result published in [43] says that, if r ≥ 2, κ ≥ ω and $\kappa \nrightarrow (\lambda _{\nu })_{\nu <\gamma }^{r}$, then

$$\displaystyle{{2}^{\kappa } \nrightarrow (\lambda _{\nu } + 1)_{\nu <\gamma }^{r+1}}$$

provided the sequence λ _ν satisfies certain simple conditions. The simplest of these is that two of them are infinite and one of them is regular. There are about six more conditions to cover relevant cases. These conditions become less restrictive as r grows, and there is no condition at all for r ≥ 5.

But even the one just stated tells us that the Erdős-Rado theorem of §7 is best possible, i.e.

$$\displaystyle{\exp _{n-1}(\kappa ) \nrightarrow {(\kappa }^{+})_{ 2}^{n}}$$

for n ≥ 2, since the result ${2}^{\kappa } \nrightarrow {(\kappa }^{+})_{2}^{2}$ can be lifted by induction on n.

Let me state another example. We know that if $\kappa \nrightarrow {(\kappa }^{+})_{2}^{2}$ then κ↛ (κ, 4)³. This should imply 2^κ ↛ (κ, 5)⁴, but to get this, a special argument is needed say if κ is singular.

Maybe the negative stepping up is true without any conditions at all on the λ _ν , but to the best of my knowledge this is still wide open. There are cases where we do not know what happens without GCH for n = 2. Let me explain this with an example. It is very easy to see that $\aleph _{\omega }^{\aleph _{0}} \nrightarrow {(\aleph _{\omega +1},(\aleph _{0})_{\aleph _{ 0}})}^{2}$, but this should still be true if the $\aleph _{0}$ entries are replaced by 3’s, and indeed we did prove this with GCH

$$\displaystyle{\aleph _{\omega +1} \nrightarrow {(\aleph _{\omega +1},(3)_{\aleph _{0}})}^{2}.}$$

To stick my neck out again, it seems inconceivable to prove this in ZFC, but no consistency proofs are known in the other direction.

Now a trivial canonization lifts this say to the first singular cardinal with cofinality $\aleph _{\omega +1}$ i.e. to $\aleph _{\omega _{\omega +1}} \nrightarrow (\aleph _{\omega _{\omega +1}},(3)_{\aleph _{0}}^{2})$ and this should be stepped up to

$$\displaystyle{\aleph _{\omega _{\omega +1}+1} \nrightarrow {(\aleph _{\omega _{\omega +1}},(4)_{\aleph _{0}})}^{3}.}$$

Unfortunately in this case, for r = 2, only one of the entries is infinite and even that is singular. So we had nothing to cover this case and it was stated as one of our open problems for a long time. I thought Shelah and Stanley had a proof of this ↛ from GCH, but I understand that it is still open.

A more significant problem is that our result suggests a negative stepping- up, for square brackets and set mappings as well.

It was recognized early in the game that for square brackets this is consistently false even assuming GCH. For example, ${2}^{\aleph _{0}} = \aleph _{1} \Rightarrow \aleph _{1} \nrightarrow [\aleph _{1}]_{\aleph _{ 1}}^{2}$, but it is very easy to see that $\aleph _{2} \nrightarrow [\aleph _{1}]_{\aleph _{1}}^{3}$ implies $\aleph _{2} \nrightarrow [\aleph _{1}]_{\aleph _{1},\aleph _{0}}^{2}$, the negation of Chang’s conjecture, which was proved to be consistent in an early paper of Silver.

Stevo Todorčević worked out stepping-up methods from combinatorial principles known to hold in L, which do give the stepping-up for square brackets and for set mappings in most cases. See [T2] and also [HK1] for more history.

Let me conclude this section with two more interesting recent results of Todorčević which show the present direction of research in this area. He proved that $\aleph _{2} \rightarrow [\aleph _{1}]_{\aleph _{1}}^{3}$ is equivalent to Chang’s conjecture in ZFC (without assuming CH), and $\aleph _{2} \nrightarrow [\aleph _{1}]_{\aleph _{0}}^{3}$ is true in ZFC [T3]. See also [57]. This is a very deep result, but Erdős had a hand in initiating of this type of theorem as well, in [81] we remarked that the stepping-up method yields ${2}^{\aleph _{1}} \nrightarrow [\aleph _{1}]_{4}^{3}$ in ZFC.

11.5 Polarized Partition Relations

While working on the triple paper [43], we had to draw the line somewhere, and we decided that we will only include results for polarized partitions of the form

$$\displaystyle{\left ({ \kappa \atop \lambda } \right ) \rightarrow \bigg {({ \kappa _{0} \atop \lambda _{0}} ,{ \kappa _{1} \atop \lambda _{1}} \bigg)}^{1,1}}$$

and we gave a number of results assuming GCH. Some of the results inherent in the methods were only stated in the second problem paper [81]. But the simplest problem we isolated was if

$$\displaystyle{{2}^{\aleph _{0} } = \aleph _{1} \Rightarrow \left ({ \aleph _{2} \atop \aleph _{1}} \right ) \rightarrow \bigg {({ \mu \atop \aleph _{1}} ,{ \nu \atop \aleph _{1}} \bigg)}^{1,1}}$$

holds for ℵ ₀ ≤ μ, ν ≤ ℵ ₁.

One of the first results proved after our problem list became public was due to Karel Prikry [P]. I state a special case:

$$\displaystyle{\left ({ \aleph _{2} \atop \aleph _{0}} \right ) \nrightarrow { \left ({ \aleph _{0} \atop \aleph _{1}} \right )}^{1,1}\mbox{ or even }\left ({ \aleph _{2} \atop \aleph _{0}} \right ) \nrightarrow \bigg [{ \aleph _{0} \atop \aleph _{1}} \bigg]_{\aleph _{1}}^{1,1}}$$

is consistent with ZFC and GCH.

Later, Richard Laver [L] proved that relative to a very large cardinal it is consistent with GCH that there is an ω ₁ complete ideal I on ω ₁ having the following strong saturation property: Given F ⊂ I ⁺, the complement of I, | F |  = ℵ ₂ (i.e. ℵ ₂ large subsets of ℵ ₁ there is an F ¹ ⊂ F, | F ¹ |  = ℵ ₂, such that the intersection of any countably many sets in F ¹ is in I ⁺. This easily yields

$$\displaystyle{\left ({ \aleph _{2} \atop \aleph _{1}} \right ) \rightarrow \left ({ \aleph _{1} \atop \aleph _{1}} \right )_{2}^{1,1}\mbox{ even }\left ({ \aleph _{2} \atop \aleph _{1}} \right ) \rightarrow \left ({ \aleph _{1} \atop \aleph _{1}} \right )_{\aleph _{0}}^{1,1},}$$

and it was one of the first corollaries of Jensen’s morasses, that Prikry’s result holds in L.

For lack of space and time, we did not include polarized partitions in the book [100] so there is no comprehensive account in the literature about the recent results. Let me state one problem of the form $\left ({ \aleph _{\alpha +1} \atop \aleph _{\alpha }} \right ) \rightarrow \big {(\,\cdot \,\big)}^{1,1}$ which is unsolved and for which there are no consistency results either. Does GCH imply

$$\displaystyle{\left ({ \aleph _{\omega _{1}+1} \atop \aleph _{\omega _{1}}} \right ) \rightarrow \left ({ \aleph _{\omega _{1}} \atop \aleph _{\omega _{1}}} \right )_{2}^{1,1}?}$$

A small hope here is an unpublished remark of Shelah from 1989. Assume $\langle \kappa _{\alpha } :\alpha <\omega _{1}\rangle$ is an increasing sequence of measurable cardinals, $\kappa =\sup _{\alpha }\kappa _{\alpha }$ and ${2}^{\kappa } {=\kappa }^{+}$ then

$$\displaystyle{\left ({{ \kappa }^{+} \atop \kappa } \right ) \rightarrow \left ({ \kappa \atop \kappa } \right )_{\tau }^{1,1}\quad \mbox{ holds.}}$$

Added in proof (March 1995). In September 1994, Shelah proved the following striking result. Assume $\kappa > \mathrm{cf}(\kappa )$, κ is strong limit and 2^κ > κ ⁺. Then

$$\displaystyle{\left ({{ \kappa }^{+} \atop \kappa } \right ) \rightarrow \left ({ \kappa \atop \kappa } \right )_{\tau }^{1,1}\quad \mbox{ holds for $\tau <\kappa $.}}$$

Writing up the second problem paper [81], I realized that our theorem in [43] yielding $\left ({ \aleph _{2} \atop \aleph _{2}} \right ) \rightarrow \left ({ \aleph _{1} \atop \aleph _{1}} \right )_{2}^{1,1}$ from CH can be generalized to give

$$\displaystyle{{2}^{\aleph _{0} } = \aleph _{1} \Rightarrow \left ({ \aleph _{2} \atop \aleph _{2}} \right ) \rightarrow \left ({ \aleph _{1} \atop \aleph _{1}} \right )_{3}^{1,1}}$$

but it is consistent with CH that

$$\displaystyle{\left ({ \aleph _{2} \atop \aleph _{2}} \right ) \nrightarrow \left ({ \aleph _{1} \atop \aleph _{1}} \right )_{4}^{1,1}}$$

holds. A recent still unpublished result of J. Baumgartner using a new kind of argument, says that assuming CH (but no more of GCH)

$$\displaystyle{\left ({ \aleph _{3} \atop \aleph _{2}} \right ) \rightarrow \left ({ \aleph _{1} \atop \aleph _{1}} \right )_{\aleph _{0}}^{1,1}}$$

holds.

11.6 Property B and Incompactness

Our second major joint paper [33] is about the following property of families of sets, F : There is a set B which meets every element of F but does not contain any member of F as a subset. This means, in a terminology introduced later, that the chromatic number of F is two. Before stating some results I want to tell how we came across property B. Property B was actually discovered by Felix Bernstein in 1908. He proved that for every κ ≥ ω, if F is a family of size κ of sets of size κ then F has this property. (He used it to get a subset $B \subset \mathbb{R}$, $\vert B\vert = \vert \mathbb{R} \setminus B\vert = {2}^{\aleph _{0}}$ and such that neither B nor $\mathbb{R} \setminus B$ contains a perfect subset of $\mathbb{R}$.

In those years I often visited Erdős at the summer house of the Academy in Mátraháza (a summer resort in the mountains), where he used to spend part of the summer with his mother. The place was reserved for members of the Academy and I was still young, so I had to find a place in the village for a couple of days. But I did get decently fed in the summer house during the day time. Usually there were other visitors or regular inhabitants to also work with Paul, and he would do this simultaneously. He led his usual life there, alternately proving, conjecturing, playing chess, ping pong, bridge, or walking to mountain tops. It was his habit to stop playing abruptly, when the rest of us were warming up to the game, and to return to work. In those days he went to bed around ten o-clock, but he woke up early, between four or five in the morning, so it was actually safer for me not to be living too close.

There was a vague plan to write a book on set theory and I arrived with a number of old journals. One of them was the 1937 volume of the Comptes Rendus Varsowie containing a long paper of Tarski, “Ideale in Vollständigen Mengenkörper”, in which we wanted to find something for the planned book. Erdős volunteered to look it up. I had something else to do and I left him alone for a while. When I returned, he was excitedly reading. But not Tarski’s paper, it was a forgotten paper [Mil] of an American set theorist E.W. Miller, which was next to Tarski’s paper in the same volume. (Yes, the same as in Dushnik-Miller.) Miller proved that, for n finite, if F is a family of infinite sets and any two members of F intersect in at most n elements, then F has property B. “Reading” meant reading the statements and trying to figure out the proofs. After a while, I gave up and started reading the paper in detail.

The proof was by a cardinal induction on κ =  | F | , the size of the family, and for a given κ, the underlying set was split into the increasing continuous union of κ smaller sets {A _α : α < κ}, each A _α , being closed with respect to certain operations. In this case, for each n + 1 element set, there is at most one set containing it, and the elements of this (possibly non-existent) set were the values of these operations. Then the induction hypothesis was applied to the families F | A _α . This is called nowadays, the method of elementary chains. Miller actually proved that F has the stronger property $\mathbf{B}(< \aleph _{0})$, i.e. there is a set B which meets each element A of F in a finite set.

Paul’s only comment was: “You see there are still things we do not know,” and before we actually read all the details, he started to ask questions. What if the sets are only almost disjoint (have finite intersections)? There is a counter-example on the second page of Miller’s paper, and I tried to return to the details. “Yes” he said, “but we should then assume that the sets are bigger.” So, instead of collecting data for the book, we wrote a long paper.

Let me state a special case of one of the main results: Assume GCH. If F is a family of very strongly almost disjoint sets of size $\aleph _{2}$ , i.e. $\vert A \cap B\vert < \aleph _{0}$ for A≠B ∈ F, then F has property B $(< \aleph _{2})$ . More importantly, if F consists of sets of size $\aleph _{1}$ just strongly almost disjoint, i.e. $\vert A \cap B\vert < \aleph _{0}$ for A≠B in F, then F still has property B $(< \aleph _{2})$ provided $\vert F\vert \leq \aleph _{\omega }$.

The reason why the proof broke down for $\aleph _{\omega +1}$ was quite clear. In the generalization of Miller’s proof we had to use infinitary operations, and alas $\aleph _{\omega }^{\aleph _{0}}$ is greater than $\aleph _{\omega }$ no matter what we assume.

We both felt that this is a real hard-core problem and we tried to find other methods. In doing so we formulated the following statement ( ∗ ): For $\alpha < \aleph _{\omega +1}$ there is a partition of $\alpha = \cup _{n<\omega }S_{\alpha ,n}$ into countably many pieces such that $\vert S_{\alpha ,n}\vert \leq \aleph _{n}$ and for any $\alpha < \aleph _{\omega +1}$ with $\mathrm{cf}(\alpha ) =\omega _{1}$ there is an increasing sequence $(\alpha _{\nu } :\nu <\omega _{1})$ of ordinals α _ν →α such that for each n < ω the sequences $\{S_{\alpha _{\nu ,n}} :\nu <\omega _{1}\}$ are increasing as well.

Of course, we could not prove this, but we could deduce from it the theorem for $\vert F\vert = \aleph _{\omega +1}$.

Later a young German set theorist W. Donder pointed out that our statement is an easy corollary of Jensen’s $\square _{\aleph _{\omega }}$ and as a corollary of this statement and some obvious generalizations, the theorem for families of sets of size $\aleph _{1}$ is true in L.

In 1986, in a paper with Juhász and Shelah [HJS], we proved that it is consistent, relative to a super compact cardinal, that there is a family of size $\aleph _{\omega +1}$ of strongly almost disjoint sets of size $\aleph _{1}$ not having property B and also GCH holds in the model.

Paul was of course immediately asking if in Miller’s theorem B $(< \aleph _{0})$ can be replaced by B(k) with some k < ω. Let us consider families F of countably infinite sets, such that for any two A≠B ∈ F, | A ∩ B | ≤ n < ω. First we proved that for countable familiesF, Fhas property B(n + 1) but not necessarily B(n). Then much to our surprise, we proved using GCH that, if $\vert F\vert = \aleph _{k}$, k < ωthenFmust have property $\mathbf{B}((k + 1)n + 1)$ but not necessarily B((k + 1)n). The reason for the surprise was, that these were strong incompactness results saying that there is a family of size ℵ _k + 1 of countable sets not having property $\mathbf{B}((k + 1)n + 1)$ but every subfamily of size $\aleph _{k}$ has this property and such incompactness results were not then in the literature (but we already knew of the Hanf-Tarski result by the time we finished the paper). At the end of the paper we gave a long list of incompactness problems for $\aleph _{2}$ which were later solved by different authors. Eventually, Paul’s persistent interest in these problems led to Shelah’s celebrated compactness theorem for singular cardinals [S3].

I just state here one of the problems, the fate of which I will describe in §10.9. Does there exist a graph on $\aleph _{2}$ vertices having uncountable chromatic number, such that all subgraphs of size $\aleph _{1}$ are at most $\aleph _{0}$ chromatic?

Finally, let me mention that due to the interest of Paul, property B had an even bigger career in finite combinatorics. But fortunately, this is not the subject of this note.

11.7 Chromatic Number

In our paper [42] we discovered r-shift graphs. Reference [42] is “Some remarks on set theory IX”. Its subject is a general problem involving reals, so I hope it fits into Komjáth’s paper. But I must mention that a few years ago, Fremlin and Talagrand obtained some very interesting results solving most of the problems stated there [FT].

The vertices of the κ, r-shift graph G(κ, r), 2 ≤ r < ω are the r-tuples of κ or rather the increasing sequences $\{\alpha _{0},\ldots ,\alpha _{r-1}\},\alpha _{0} <\ldots <\alpha _{r-1} <\kappa$ and we join $\{\alpha _{0},\alpha _{1},\ldots ,\alpha _{r-1}\}$ and $\{\alpha _{1},\alpha _{2},\ldots ,\alpha _{r}\}$. We proved, as a corollary of Ramsey’s theorem or the Erdős-Rado theorem, that these graphs have large chromatic number and that they do not contain odd circuits of length less than r + 2.

It was an early result of finite graph theory that there exist graphs having large chromatic number and not containing a K ₃ (see [46] for historical references). I think G(n, 2) is the simplest example of this and we were both surprised that this was not known earlier. Paul was always interested in this problem. He proved in 1959 using his probability method that for all k < ω and r < ω there are graphs of chromatic number ≥ k and of girth ≥ r (not containing circuits of length < r). He was always interested in infinitary generalizations and in [22] he proved with Rado that, for κ ≥ ω there is a K ₃-free graph on κ of chromatic number κ.

These results again suggested the wrong generalization, but this time we were not defeated. In [46] we proved that a graph not containing C ₄ (a circuit of length 4) has chromatic number at most $\aleph _{0}$. In fact, we proved a much stronger result. We defined $\mathrm{col}(G)$ the coloring number of G as the smallest cardinal κ such that the vertex set of G has a well ordering such that for each vertex x the number of edges having x as the larger element is smaller that κ. This concept was later introduced in finite combinatorics under a different name as well (G is k-degenerate if $\mathrm{col}(G) \leq k + 1$) [Bo]. Obviously, $\mathrm{chr}(G) \leq \mathrm{col}(G)$ and we proved that if G does not contain a complete bipartite graph $K_{k,\aleph _{1}}$ , for every k < ω then $\mathrm{col}(G) \leq \aleph _{0}$. We used the cardinal induction method described in the previous section. Again, the problem arose, what can be said if only larger complete bipartite graphs are excluded? Let me again state a special case of our result. Assume GCH. If G does not contain a $K_{\aleph _{0},\aleph _{3}}$ then $\mathrm{chr}(G) \leq \aleph _{2}$ and if G does not contain a $K_{\aleph _{0},\aleph _{2}}$ then $\mathrm{chr}(G) \leq \aleph _{1}$ provided $\vert G\vert \leq \aleph _{\omega }$.

The situation is analogous to the one described in the previous section. It is consistent that the second clause of the theorem is true for every G e.g. if V = L, and it is consistent (relative to a super compact cardinal) that the result strongly fails for $\aleph _{\omega +1}$ i.e. there exists a graph G on $\aleph _{\omega +1}$ of chromatic number $\aleph _{2}$ not containing a $K_{\aleph _{0},\aleph _{0}}$. This was shown in our paper with Juhász and Shelah mentioned in 10.6. The construction of this example from the one described there is a combinatorial argument, which uses that in the model we have many instances of $\diamond$ (the diamond principle).

I have to mention that we also introduced generalized Specker graphs to show that for κ ≥ ω there are graphs of sizeκ, with chromatic number κ having large odd girth.

There are quite a few generalizations of our theorem for $\mathrm{col}(G) > \aleph _{0}$ but I do not state these here, instead I offer the references [K 1, HK3] and [101]. Let me mention one typical Erdős question: Does $\mathrm{chr}(G) > \aleph _{0}$ imply that G contains all large odd circuits, say of length 2k + 1 for k ≥ k ₀ for some k ₀. Note that this is a typical problem where it is the chromatic number that has to be large as $\mathrm{col}(K_{\aleph _{0},\aleph _{1}}) = \aleph _{1}$. Later we proved this with Shelah in [79].

Rado asked if the de Bruijn-Erdős compactness theorem for finite chromatic number extends to finite coloring numbers. As the definition of the coloring number involves a well-ordering this can not be expected. Indeed we disproved it, but a surprising result of [46] is that still there is a uniform bound. We proved: If $\mathrm{col}({G}^{{\prime}}) \leq k(2 \leq k <\omega )$ for every finite subgraph G ^′ of G then $\mathrm{col}(G) \leq 2k - 2$, and there is a countable graph to show that this is best possible for each k.

There is an important finite theorem hidden at the end of [46]. We proved there, using the probabilistic method, that for every r, s, k, there are r-uniform hypergraphs of chromatic number greater than k and girth greater than s. In fact, defined on some n-element set, they do not contain an independent set of size n ^1 − d for some d > 0. This fit logically into the line of thought of [46] and it did not occur to us that no finite combinatorialist will look at, much less read, a 40 page paper full of alephs, to find an interesting probabilistic argument on the 35th page.

11.8 Another Miss

We first met Eric Milner in 1958 at the IMC meeting in Edinburgh. He was a former student of Rado and was working in Singapore. Rado interested him in partition problems and he settled one of their problems about countable ordinals [M1]. That was enough to induce Paul to visit and work with him in Singapore in 1960. He returned from there to Budapest with a new interesting problem which I solved and this began a long collaboration between the three of us. The Milners’ returned to England in 1961 and Eric joined Rado at Reading. On my way back from Berkeley to Budapest in 1965, I stayed in Reading for a month with them discussing a long half-finished manuscript. Although our long joint papers only appeared a few years later, in 1965 we were already deeply involved in our joint work and we thought it would probably help if all three of us could be together at the same place and at the same time. So it was arranged that Eric should visit us during the summer of 1965 to spend a week at the summer house of the Writer’s Union in Szigliget on Lake Balaton. Eric arrived with an interesting question about transversals, and as a consequence, instead of regularly working on manuscripts, we wrote another shorter paper [56] which became our first joint work to appear. As a side issue in that paper we proved the following theorem: Let $\lambda > \mathrm{cf}(\lambda ) =\kappa >\omega$ , and let λ _α (α < κ) be an increasing continuous sequence of cardinals cofinal in λ, and assume that τ ^κ < λ for τ < λ. If S is a stationary subset of κ and $\mathcal{F}\subset \Pi _{\alpha \in S}\lambda _{\alpha }$ is an almost disjoint set of transversals (i.e. $\vert \{\alpha \in S : f(\alpha ) = g(\alpha )\}\vert <\kappa forf\neq g \in \mathcal{F}$ ), then $\vert \mathcal{F}\vert \leq \lambda$ .

Eric made notes of our results and wrote it up and the pap er appeared in 1968. We forgot the whole thing, and the paper seems to have gone unnoticed. Even in 1967 when we wrote the first problems paper with Paul, where our intention was to write down all our interesting problems, we omitted any mention of this. However, it seems we were not the only blind ones. During the summer of 1971 Adrian Matthias organized a large conference on set theory in Cambridge, England. Karel Prikry was one of the invited speakers and he gave a talk on a generalization of Jensen’s work on Kurepa families. He discovered the following result: Under the assumptions of our theorem, if $\mathcal{H}\subseteq \mathbb{P}(\lambda )$ is a Kurepa family in the sense that $\vert \mathcal{H}\vert \lambda _{\alpha }\vert \leq \lambda _{\alpha }$ for α ∈ S (S a stationary subset of κ), then $\vert \mathcal{H}\leq \lambda$. ($\mathcal{H}\vert \lambda _{\alpha } =\{ H \cap \lambda _{\alpha } : H \in \mathcal{H}\}$.)

He told me this result the day before his lecture and it sounded vaguely familiar. But it took me the whole day to realize that this was just our earlier theorem applied to the sets $\mathcal{H}\vert \lambda _{\alpha }$ in place of λ _α . I managed to get a copy of our paper to give to Prikry before the lecture. Now there were about one hundred set-theorists in attendance, including all the leading ones, when Karel stated our result in a totally digestible form. But nobody asked, what happens if we replaced $\lambda _{\alpha }$ by $\lambda _{\alpha }^{+}$? I suppose the psychological barrier was too strong. In 1974, just before the ICM in Vancouver, I was visiting Eric again in Calgary (he moved there in 1967), when I received a preprint of Silver ’s ingenious discovery that: if $\lambda >\mathrm{ cf}(\lambda ) >\omega$ and if ${2}^{\tau } {=\tau }^{+}$ on a stationary set of cardinals τ < λ, then ${2}^{\lambda } {=\lambda }^{+}$. At the same time I received a preprint from Prikry giving a combinatorial proof of Silver ’s result. Prikry told me that the instant he saw Silver ’s manuscript it dawned on him that the only thing needed was to lift our old result with λ _α ⁺ in place of λ _α . Of course this requires a non-trivial argument. Baumgartner and Jensen also found elementary proofs of Silver ’s result without remembering our theorem. But the real miss, and so uncharacteristic of Paul, was not to have asked the question!

11.9 Incompactness for the Chromatic Number

In 1966, assuming CH, we solved the problem on chromatic numbers stated in §10.6. We proved in [54] that there is a graph of chromatic number at least $\aleph _{1}$ on ${({2}^{\aleph _{0}})}^{+}$ vertices all of whose subgraphs of cardinality at most ${2}^{\aleph _{0}}$ have chromatic number at most $\aleph _{0}$. This also comes with a story and some advice. During a working session at Paul’s apartment, we were talking about something totally unrelated to chromatic number and compactness. In the middle of an attempted proof, we found that the pairs of $\mathbb{R}$ are colored with countably many colors and our proof would be finished if there was a monochromatic increasing path of length 2, IP ₂, i.e. a triple $x_{1} < x_{2} < x_{3}$ with {x ₁, x ₂} and $\{x_{2},\ x_{3}\}$ having the same color. Unfortunately there was not, and I tried to get another proof. But Paul started to insist that we should know for what order types θ,

$$\displaystyle{\theta \rightarrow (IP_{2})_{\omega }^{2}}$$

holds. We parted unsuccessful in both attempts. But on the way home, I could not help thinking about his question. I remembered an old idea of Sierpiński which easily implied that there is a ↛ for every θ of cardinality $\vert \theta \vert \leq {2}^{\aleph _{0}}$. Then I saw in a flash that this just says that all subgraphs of size ${2}^{\aleph _{0}}$ of our shift graph $G({({2}^{\aleph _{0}})}^{+},2)$ have chromatic number $\leq \aleph _{0}$. As this was a 100 dollar problem, I immediately called Paul when I arrived home. (I think eventually I got only $50 for it, but with some reason). The advice is this: just answer his questions, you have time later to ponder if it is important or not.

This was the status of the problem when we published it in [67]. Let me tell some later developments. First Jim Baumgartner proved with a forcing argument that it is consistent that GCH holds and there is an $\aleph _{2}$ -chromatic graph on $\aleph _{2}$ vertices, such that the chromatic number of every subgraph of size $\aleph _{1}$ is at most $\aleph _{0}$ [B1].

M. Foreman and R. Laver proved that: it is consistent with GCH relative to a large cardinal that every graph on $\aleph _{2}$ , all of whose $\aleph _{1}$ subgraphs are $\aleph _{0}$ -chromatic is at most $\aleph _{1}$ -chromatic [FL].

Finally, Shelah proved, after improving his own results several times, that it is consistent (true in L) that: for every regular non-weakly compact κ, there is a κ-chromatic graph on κ all of whose subgraphs of size less that κ are $\aleph _{0}$ -chromatic [S4].

We also invented an interesting graph in [54]. Let C(ω ₂, ω) be a graph whose vertices are the elements of ${}^{\omega _{2}}\omega$, i.e., ω ₂-sequence of integers and we join two sequences if they are eventually different. We proved, and these are obvious facts, that every subgraph of size $\aleph _{1}$ of C(ω ₂ ,ω) has chromatic number $\leq \aleph _{0}$ , and moreover, that every graph of size $\aleph _{2}$ having this property embeds into C(ω ₂ ,ω). However, the chromatic number of C(ω ₂, ω) in ZFC is a mystery. Our result implies that CH$\Rightarrow \mathrm{chr}(C(\omega _{2},\omega )) \leq \aleph _{1}$ and Péter Komjáth proved this from the weaker assumption ${2}^{\aleph _{0}} \leq \aleph _{2}$, and he proved it consistent with GCH that $\mathrm{chr}(C(\omega _{2},\omega )) = \aleph _{3}$ [K 2]. On the other hand Foreman proved it is consistent relative to a large cardinal that $\mathrm{chr}(C(\omega _{2},\omega )) \leq \aleph _{1}$ [Fo]. It seems to be out of the question with the present methods to prove that our graph is consistently $\aleph _{0}$-chromatic.

11.10 Decomposition of Graphs

I just want to mention our paper [53] which appeared in 1967 but was written about 2 years earlier. In this paper we raised problems of the following type. Does there exist graphs G not containing a K _λ , for some cardinal λ, such that for every vertex partition or edge partition with few colors say a monochromatic K _τ appears. In present notation: For what λ, τ, γ is there a K _λ -free graph G such that

$$\displaystyle{G \rightarrow (K_{\tau })_{\gamma }^{1}\mbox{ or }G \rightarrow (K_{\tau })_{\gamma }^{2}}$$

holds? We had some results but I just want to restate two edge partition problems from the paper, one of them finite.

Does there exist a finite K ₄-free G with $G \rightarrow (K_{3})_{2}^{2}$? This was solved by Folkmann [Fol] affirmatively, but the question became one of the starting points of structural Ramsey theory (see §15).

The infinitary problem is the following. Does there exist a K ₄-free graph G of cardinality ${({2}^{\aleph _{0}})}^{+}$ such that $G \rightarrow (K_{3})_{\omega }^{2}$ holds? As far as I remember, this was the last set theory problem Paul offered a prize for (it was worth $250.) Shelah later proved this to be consistent, but I will speak about the status of this kind of problem in a more general context in §15.

12 $\Delta$-Systems and More Set Mappings

$\Delta$-Systems were introduced in a paper of Erdős and Rado which appeared in 1960 [26]. A family F of sets is a $\Delta$-system if there is a set D, the kernel of F, such that A ∩ B = D for all A≠B ∈ F. The paper set the task to determine $\Delta (\kappa ,\lambda ) =\delta$ the smallest cardinal for which every family F, of sets of size κ and cardinality δ contains a $\Delta$-system of size λ ≥ 3. As it is well known, for finite κ, the problem is still unsolved. A $1,000 reward is offered by Paul for the proof or disproof of the conjecture that for some c > 0

$$\displaystyle{\Delta (\kappa ,3) < {c}^{\kappa }\mbox{ for }\kappa <\omega }$$

However, for κ ≥ ω, Erdős and Rado settled the problem completely. Although some of the details were only cleared up in their second paper [60] on the subject, the main upper bounds were already obtained in [26]. One of the main results says that if $\kappa <\delta = \mathrm{cf}(\delta )$ , |F| = δ ≥ω and δ is inaccessible from κ, i.e. σ ^κ < δ for σ < δ then F contains a $\Delta$ -system of size δ. This is probably the most frequently used theorem of set theory, since it is the simplest tool to prove that certain partially ordered sets satisfy certain chain conditions. If $\langle P,\preccurlyeq \rangle$ is a partially ordered set p, q ∈ P are incompatible if there is no r ∈ P with $r \preccurlyeq p,q$ and P satisfies the κ-chain condition if every subset of pairwise incompatible elements has cardinality ≤ κ. It was already an important element of Cohen’s proof of the independence of the continuum hypothesis, that finite 0, 1 sequences from any index set, ordered by reverse inclusion satisfy the $\aleph _{0}$-chain condition. Cohen and his early followers did not know the Erdős-Rado theorem and they proved it for the special cases they needed. But soon it was discovered by logicians, and it is invoked almost any time forcing is used.

There is another theorem of Erdős and Specker [30], I should have mentioned in §5, which is used almost as often in forcing arguments to establish chain conditions as the $\Delta$-system theorem. Assume $f :\kappa \rightarrow \mathbb{P}(\kappa )$ is an ordinary set mapping. In §5 we saw that, if If | f(x) |  < τ < κ for some cardinal τ < κ then there is a free set of size κ and κ is the union of τ free sets. Now if κ is a successor cardinal λ ⁺ then the assumption that the type $\mathrm{tp}(f(x)) <\xi {<\kappa }^{+}$ for some fixed ξ < λ ⁺ is weaker than the assumption that | f(x) |  < τ for some cardinal τ < κ but by the Erdős-Specker theorem, this still implies the existence of a free set of size κ; however, Fodor’s theorem does not apply since the graph induced by f can be λ ⁺-chromatic. Most of the time that we want to construct or force an object on λ ⁺ such that each subset of size λ ⁺ contains a subset of size λ ⁺ of certain kind, but the whole set is not the union of λ sets of this kind, then the Erdős-Specker result is the first thing to remember.

13 The Unsolved Problems in Set Theory [67]

In 1967 the first major post Cohen conference was held at UCLA. By that time, Cohen’s method was generally known and developed, and the aim of the conference was to bring together all experts of set theory and to collect and make public all the fantastic new results available. We were both invited, Paul was there, but I could not make it. (It was the only time I did not get a passport from the Hungarian authorities.) The organizers convinced Paul that instead of mentioning a few interesting problems as the spirit moves him, he should write up all the difficult problems he came across during his work in combinatorial style set theory. He immediately promised that we will do it in a joint paper. This time we worked hard and fast. A mimeographed version of the manuscript containing 82 problems (or groups of problems really) was ready in the same year and we sent a copy to everyone we knew and who we thought would be interested. It included all the problems I mentioned in the previous sections and quite a few more. A large number of (then) young mathematicians started to work on these, and produced solutions either by applying the newly developed methods of independence proofs or simply divising new combinatorial methods. The paper only appeared 4 years later in 1971, and by that time the status of most of the problems had changed. We tried to keep the manuscript up to date by adding remarks, but in 1971 we decided to write a second problem paper [81] which contained the status of the problems up until that time.

It would clearly be impossible to write a similar survey today. In the previous sections, I tried to show on selected topics how the Erdős problems generated new questions and results and how they became integral parts of modern set theory, and how many of them are still alive. In this section I can only mention the status of a few more which I omitted earlier.

I did not finish the story of set mappings of type < ω. Shortly after our problem paper was distributed Jim Baumgartner proved in his thesis [B2] that if V = L then $\mathrm{Free}(\kappa ,2,<\omega ,\aleph _{0})$ is equivalent to $\kappa \rightarrow (\aleph _{0})_{2}^{<\omega }$ but on the other hand, it is still open if it is consistent relative to a large cardinal that $\mathrm{Free}(\aleph _{\omega },2,<\omega ,\aleph _{0})$ holds, or more strongly, there is no Jónsson algebra on $\aleph _{\omega }$. As I already mentioned, $\mathrm{Free}(\aleph _{\omega },2,<\omega ,\aleph _{0})$ was our first joint problem. We already suspected at Kalmár’s supper that it will be hard, but probably not quite as hard as it turned out to be.

I am afraid I have mentioned too many problems which led to independence results, so here is a difficult theorem of Shelah and Stanley solving one of our problems in ZFC:

$$\displaystyle{{({2}^{\aleph _{0} })}^{+}.\omega \rightarrow {({({2}^{\aleph _{0} })}^{+}\omega ,n)}^{2}}$$

for n < ω [SS2]. It is another matter that they also proved $\omega _{3}.\omega _{1} \rightarrow {(\omega _{3}.\omega _{1},3)}^{2}$ to be independent of ZFC and GCH.

Erdős proved with Alaoglu in 1950 in [5] that if κ is smaller than the first weakly inaccessible cardinal greater than $\aleph _{0}$, then one can not have $\aleph _{0}$ σ-additive 0, 1 measures so that every subset of S is measurable with respect to one of them. Erdős attributes the question to Stanislaw Ulam but he got the first result. We asked if $\aleph _{0}$ can be replaced by $\aleph _{1}$ here? Prikry proved it to be consistent, but this question became the forerunner of so many questions in the theory of large cardinals that I do not dare to write about later developments in detail.

Instead, here are some evergreen problems from the theory of ordinary partition relations for ordinals.

• 1. ${\omega }^{\omega } \rightarrow {({\omega }^{\omega },3)}^{2}$ was proved by C.C. Chang [C] and ${\omega }^{\omega } \rightarrow {({\omega }^{\omega },n)}^{2}n <\omega$ was proved by E.C. Milner [M2] and independently by Jean Larson [Lar]. But ${\omega }^{{\omega }^{2} } \rightarrow {({\omega }^{{\omega }^{2} },3)}^{2}$ or ${\omega }^{{\omega }^{\alpha }} \rightarrow {({\omega }^{{\omega }^{\alpha }},3)}^{2 }$ seem to be as hard as ever. Here of course α ^β means ordinal exponentiation.

• 2. Does there exist an α with α → (α, 3)² such that α↛ (α, 4)²?

• 3. I proved with Jim Baumgartner in 1970 [BH] that $\Phi \rightarrow (\omega )_{\omega }^{1} \Rightarrow \forall _{\alpha } <\omega _{1}\forall k <\omega \Phi \rightarrow (\alpha )_{k}^{2}$. But for exponents > 2 very little is known. For example, ω ₁ → (α, 4)³ is still open for α < ω ₁. The world record is presently held by Milner and Prikry; they proved this for α ≤ ω. 2 + 1. See [MP].

• 4. Is $\omega _{2} \rightarrow (\alpha )_{2}^{2}$ for α < ω ₂ consistent with GCH? I proved the consistency of $\omega _{2} \nrightarrow (\omega _{1}+\omega )_{2}^{2}$ and it follows from the existence of Laver’s ideal mentioned in §10.5 that $\omega _{2} \rightarrow (\omega _{1}.2)_{2}^{2}$.

• 5. It follows from a recent result of Baumgartner, myself and Todorčević [BHT] that GCH$\Rightarrow \omega _{3} \rightarrow (\omega _{2}+\xi )_{k}^{2}$ for ξ < ω ₁ and k < ω but $\omega _{3} \rightarrow (\omega _{2} + 2)_{\omega }^{2}$ is still open. See [BHT] for many new problems arising from our results.

14 Paradoxical Decompositions

Erdős has 12 major joint papers with Eric Milner, nine of those were written by the three of us. These are from a later period so the results and problems are more technical than the ones I described earlier, it is out of question to give a list of them. I want to speak about one idea which features in quite a few of them.

It was always clear that Ramsey’s theorem is a generalization of the pigeonhole principle of Dedekind. When partition relations $\kappa \rightarrow (\lambda _{\nu })_{\nu <\gamma }^{r}$ were formally introduced, it became apparent that the pigeonhole principle is just a partition relation for cardinals with exponent r = 1. For example, $nk + 1 \rightarrow (n + 1)_{k}^{1}$ for the finite case with k boxes, and $\aleph _{0} \rightarrow (\aleph _{0})_{k}^{1}$ for k < ω, and more generally, $\kappa \rightarrow (\kappa )_{\lambda }^{1}$ for $\lambda < \mathrm{cf}(\kappa )$, κ ≥ ω. It was discovered by Milner and Rado in [MR] which appeared in 1965 that the pigeonhole principle does not work the same way for ordinals. They proved that for any κ ≥ ω

• (i) $\xi \nrightarrow {(\kappa }^{n})_{n<\omega }^{1}$ if ξ < κ ⁺ and as a corollary of this $\xi \nrightarrow {(\kappa }^{\omega })_{\omega }^{1}$ for ξ < κ ⁺.

Here again α ^β denotes ordinal exponentiation. This phenomena, often called the Milner-Rado paradox, has to be kept in mind, just because it is so contrary to one’s first intuition. When partition relations proliferated it was discovered that this (as almost anything) can be written as a polarized partition relation:

• (ii) $\left ({ \omega \atop \xi } \right ) \nrightarrow \bigg {({ {1 \atop \kappa }^{\omega }} ,{ \omega \atop 1} \bigg)}^{1,1}$ for ξ < κ ⁺

and also as a square bracket relation:

• (iii) $\xi \nrightarrow {[\kappa }^{\omega }]_{\aleph _{0},<\aleph _{0}}^{1}$ for ξ < κ ⁺. In [63] we have investigated the polarized partition relation$\left ({ \kappa \atop \xi } \right ) \nrightarrow \bigg {({ 1 \atop \sigma } ,{ \delta \atop \tau } \bigg)}^{1,1}$ for κ = ω and κ = ω ₁, ξ < ω ₂.

We gave a complete discussion, relying heavily on the form (iii) of the paradox in the case κ = ω ₁, i.e.

• (iv) $\xi \nrightarrow [\omega _{1}^{\omega }]_{\aleph _{0},<\aleph _{0}}^{1}$ for ξ < ω ₂.

When we tried to lift our results to higher cardinals we realized that we would need to generalize (iv) to

• (v) $\xi \nrightarrow [\kappa _{2}^{\omega _{1}}]_{\aleph _{ 1},\aleph _{0}}^{1}$ for ξ < ω ₃.

We already discovered in 1967, that this will not be possible in ZFC, but we only wrote down the results which we called the $\aleph _{2}$-phenomenon in our 1978 paper [93] relying heavily on other people’s results. See [93] for references.

Since this is not so well known, I will write down the $\aleph _{2}$-phenomenon as it relates to (v).

• A.1 $\xi \nrightarrow [\kappa _{2}^{\omega _{1}}]_{\aleph _{ 0},\aleph _{0}}^{1}$ holds for $\xi <\omega _{ 2}^{\omega _{2}}$

• A.2 If ${2}^{\aleph _{1}} = \aleph _{2}$ then for some $\xi _{0} <\omega _{3}$, $\xi _{0} \rightarrow [\omega _{2}^{\omega _{1}}]_{\aleph _{ 1},\aleph _{0}}^{1}$

• A.3 It is consistent with ${2}^{\aleph _{1}} = \aleph _{3}$ that $\xi \rightarrow [\omega _{2}^{\omega _{1}}]_{\aleph _{ 1},\aleph _{0}}^{1}$ holds forξ < ω ₃

• A.4 $\omega _{2}^{\omega _{2}} \rightarrow [\omega _{2}^{\omega }]_{\aleph _{ 1},\aleph _{0}}^{1}$ and $\omega _{2}^{\omega _{2}} \nrightarrow [\omega _{2}^{\omega }]_{\aleph _{ 1},\aleph _{0}}^{1}$ are both consistent with ZFC and GCH. (The ↛ holds e.g. in L while the → follows from Chang’s conjecture.)

All this happens because a counterexample establishing the ↛ is really a sequence $\{A_{\alpha }^{\xi } :\alpha <\omega _{1}\} \subset \xi$ such that the order type $\mathrm{tp}(\bigcup _{\beta <\alpha },A_{\beta }) <\omega _{ 2}^{f_{\xi }(\alpha )+1}$ for a function $f_{\xi } :\omega _{1} \rightarrow \omega _{1}$ and, for $\zeta <\xi ,f_{\zeta }$ must be smaller than f _ξ in some well known ordering of these functions. In fact, this was the reason why we asked all the problems 19A–19E in the unsolved problems paper, about the relation of the transversal hypothesis and the Kurepa hypothesis.

Problem 19D was slightly out of the line there. Typically, Paul asked something that was quite new: are there ${2}^{\aleph _{1}}$ almost disjoint, stationary subsets of ω ₁? It is easy to see the consistency of a ‘yes’ answer, it is true e.g. in L, however the consistency of a ‘no’ answer with CH is not completely proved. Foreman, Magidor and Shelah proved in [FMS] that ‘no’ follows from a consistent set-theoretical principle called Martin’s Maximum (MM), but MM implies that ${2}^{\aleph _{0}} = \aleph _{2}$. They also proved it consistent with CH that there is a stationary subset of ω ₁ on which the nonstationary ideal is $\aleph _{2}$-saturated. All these very difficult consistency proofs of course are relative to the existence of some large cardinals.

15 A Mistake and Its Consequences

In §12 of our paper [46] about chromatic numbers, we claimed a false theorem. I just state a special case. Let $\mathcal{H} = (h,H)$ be a 3-uniform hypergraph (i.e. H ⊂ [h]³) such that every pair e ∈ [h]² is in at most countably many elements of H. Then we claimed that the chromatic number of $\mathcal{H}$ is at most $\aleph _{0}$.

As we know now, this is true if $\vert h\vert \leq \aleph _{1}$ and false for a triple system of cardinality ${({2}^{\aleph _{0}})}^{+}$. Now I have to disclose a not so surprising secret. Paul actually wrote up some of our joint papers, but these were the short ones. For the long ones it was my job to prepare the manuscript, but we always read the manuscript and even the proof sheets together. The trouble was that he often got bored with mechanical work like this, and he made up new conjectures and theorems and insisted that we should include them by adding remarks—even to the galley proofs. Taking the responsibility, I think I was the one who overlooked that the cardinal induction method breaks down from $\aleph _{1}$ to $\aleph _{2}$ in this case. Anyway, if the theorem was really true, the whole structure of the paper should have been changed but fortunately we did not have time for that.

As usual, I forgot the theorem, but Paul did not. I got a phone call from him from abroad about 4 years after the paper had appeared. He was trying to tell the proof of it to Bruce Rothschild, and got stuck. They soon discovered a counter-example. Let ${({2}^{\aleph _{0}})}^{+} =\kappa$, h = [κ]², $H =\{\{\{\alpha ,\beta \},\{\beta ,\gamma \},\{\alpha ,\gamma \}\}:\alpha <\beta <\gamma <\kappa \}$, Clearly, any two elements of H have at most one element in common, and the chromatic number is at least $\aleph _{1}$ by the Erdős-Rado theorem. We wrote a triple paper [76] about it. However, Paul got interested in this question: what kind of finite triple systems must appear in an $\aleph _{1}$-chromatic triple system? I think the first question was the 6 ∕ 3, i.e., are there three triples with empty intersection such that each pair has exactly one point in common? (This question for triple systems made quite a splash in finite combinatorics as well.) Fred Galvin came up with a negative answer. Later Fred spent the academic year 1972–1973 in Budapest, and the three of us started to work on this problem and we asked the same question for triple systems not containing large independent sets. Unfortunately, we did not find a general answer, maybe there isn’t one, every time that we constructed a large chromatic system avoiding concrete finite systems, Paul ingeniously invented new ones for which the construction did not work. The motivation behind this was the following. Clearly there is a cardinal κ with the following property. If for a finite triple system $\mathcal{H}$ there is a $(> \aleph _{0})$ -chromatic triple system $\mathcal{K}$ not containing $\mathcal{H}$ , then there is one of cardinality at most κ. Cardinals which satisfy a condition like this are quite often impossible to determine, and such was the case with this problem. For two triples with a common edge the number we found is ${({2}^{\aleph _{0}})}^{+}$. With GCH all our examples had cardinality $\aleph _{2}$ associated with them. We ended up with a concisely written paper almost 90 pages long [85] containing some really good theorems, but which remained relatively unknown. Again, it is not possible to give a list of the results, but I do want to mention one concept and problem from the paper that I really like.

We constructed large chromatic r-uniform hypergraphs by induction on r, and to support the induction from r to r + 1, we needed the r-tuple system $\mathcal{H}$, to have a stronger property than $\mathrm{chr}(\mathcal{H}) > \aleph _{0}$.

Let $\mathcal{H}_{\nu } =\langle h$, $H_{\nu }\rangle (\nu <\varphi )$, be a system of r-uniform hypergraphs on the same vertex set h. The system has simultaneous chromatic number $> \aleph _{0}$ if, for every partition of the vertex set $h =\bigcup _{n<\omega }h_{n}$ into $\aleph _{0}$ parts, there is an n < ω such that h _n contains “edges” from each $\mathcal{H}_{\nu }$ for $\nu <\varphi$.

We say that a $(> \aleph _{0})$-chromatic $\mathcal{H} =\langle h,H\rangle$ splits to δ parts, if there is a disjoint partition $H =\bigcup _{\nu <\delta }H_{\nu }$ so that the system $\mathcal{H}_{\nu } =\langle h,H_{\nu }\rangle (\nu <\delta )$ has simultaneous chromatic number $> \aleph _{0}$. We proved that quite a few known $(> \aleph _{0})$-chromatic graphs split to $\aleph _{1}$ parts and these served as a basis of our induction process.

In those days, before Todorčević’s result, we only knew with CH that $K_{{\aleph }_{1}}$ splits to $\aleph _{1}$-parts. Still, as we did not find anything that does not split, we asked the question: Is it true that every $(> \aleph _{0})$ -chromatic graph splits to two (or $\aleph _{1}$ ) parts?

This problem as it stands is still unsolved. With Péter Komjáth I have some unpublished partial results. Here are two of them.

• (1) It is consistent that every $\aleph _{1}$ -chromatic graph splits into $\aleph _{1}$ parts.

• (2) It is consistent relative to a measurable cardinal, that there is a $(> \aleph _{0})$ - chromatic graph which does not split into $\aleph _{1}$ parts. (We do not know this for two parts.)

16 Structural Ramsey Theory

As I already mentioned in §10.10, we asked the first questions of the following type: Does there exist a K ₄-free graph G such that $G \rightarrow (K_{3})_{2}^{2}$.

The following type of generalization appeared first in Deuber’s paper [D]. Let G, H be graphs; H embeds into G if G has an induced subgraph isomorphic to H. With present day partition calculus notation, we say $G \rightarrowtail (H)_{\kappa ,\lambda }^{2}$ if for arbitrary colorings $k : G \rightarrow \kappa ,\ell: {[g]}^{2} \setminus G \rightarrow \lambda$ of the edges of G with κ colors and non-edges with λ-colors, there is an induced subgraph H ^′ ⊂ G isomorphic to H such that k and ℓ are constant on the edges and on the non-edges of H ^′ respectively.

Deuber proved that for all finite H and k < ω, there is a finite G with $G >\rightarrowtail (H)_{k,k}^{2}$ and the combination of the two types of questions Paul raised became the starting points of the Nešetřil-Rödl type structural Ramsey theory.

With Erdős and Pósa we proved the first infinitary result of this kind [88]. The paper appeared in the volume of the Keszthely conference held for Paul’s 60th birthday in 1973, and this volume contains the first Něsetřil Rödl paper on the subject. The finitary theory developed very fast. The problem was generalized for coloring of substructures of a fixed kind instead of coloring pairs, but fortunately I do not have to give an account of this. I just want to say that this was not done in the infinitary case because here some basic problems are still open.

In the paper with Erdős and Pósa we proved that for every countable H and k < ω there is a G $(\vert G\vert = {2}^{\aleph _{0}})$ such that $G \rightarrowtail (H)_{k,k}^{2}$ and asked if this holds true for countably many colors, or for larger H.

We discovered a decade later with Péter Komjáth that it is consistent to have |H| = ω ₁ and $G\not\rightarrowtail (H)_{2,1}^{2}$ for every G [HK2] and Shelah proved that it is consistent that for all H and γ there is a G with $G \rightarrowtail (H)_{\gamma ,\gamma }^{2}$ [S6].

In 1989, [H 2] I proved in ZFC that for all finite H and arbitrary γ there is a G with $G \rightarrowtail (H)_{\gamma ,\gamma }^{2}$ but the problem of countable H and countable γ is open (though the ↣ is consistent by Shelah’s result). The answer may turn out to be to Paul’s liking (a theorem in ZFC) but I am sure it will be very difficult.

Shelah generalized his consistency results for K _r -free H as well, but at this point I feel I have to stop and refer the reader to a recent survey paper of mine on this subject [H 3].

17 Applications of Partition Relations in Set Theoretical Topology

In the last 30 years, set theoretical topology became a major area of research as shown e.g. in the Handbook of Set Theoretical Topology. The reason for this is that the new methods of set theory (forcing, large cardinals) made it possible to study topological spaces for what they are, namely set theoretical objects. The point I want to make is that, although Erdős did not take an active part in most of this, combinatorial set theory which he created is one of the major tools in this development.

This happens not just through the applications of positive theorems. There are of course some famous ones. Being closest to the fire, with István Juhász we showed, for example, as a consequence of ${({2}^{{2}^{\aleph _{0}} })}^{+} \rightarrow (\aleph _{1})_{4}^{2}$ that, every Hausdorff space of cardinality ${({2}^{{2}^{\aleph _{0}} })}^{+}$ has discrete subspaces of size $\aleph _{1}$. Also, as a consequence of the canonization theorem of §10 that, the spread (the supremum of the sizes of discrete subspaces) is attained in a Hausdorff space if this supremum is a singular strong limit cardinal.

More importantly, there are literally dozens and dozens of examples obtained as strengthenings of negative partition relations which would never have turned up in their present form without a detailed analysis of these relations. Let me try to make this clear with an example. I already mentioned Prikry ’s consistency proof of

$$\displaystyle{\left ({ \aleph _{2} \atop \aleph _{1}} \right ) \nrightarrow \left ({ \aleph _{0} \atop \aleph _{1}} \right )_{2}^{1,1}.}$$

To state it in “human language” (but already a little twisted for my purposes), it means that there is a sequence $\{f_{\alpha } :\alpha <\omega _{2}\} {\subset }^{\omega _{1}}2$ such that for all countable $I \in [\omega _{2}]\aleph _{0}$ there is a ν(I) < ω ₁ such that for ν(I) < ν < ω ₁ there are α ₀, α ₁ ∈ I with $f_{\alpha _{0}}(\nu ) = 0$ and $f_{\alpha _{1}}(\nu ) = 1$.

When in [HJ] with Juhász we discovered HFD’s (hereditarily finally dense sets) and proved the consistency of the existence of a hereditarily separable space of power $\aleph _{2}$ (assuming ${2}^{\aleph _{0}} = \aleph _{1}$) we only had to change the last clause of the above statement: there is a ν(I) < ω ₁ such that for every finite set F with ν(I) < F < ω ₁ and every 0, I-function ε defined on F there is an α ∈ I such that for all ν ∈ F, f _α (ν) = ε(ν). And now {f _α : α < ω ₂} is a hereditarily separable subspace of cardinality $\aleph _{2}$ of $D{(2)}^{\omega _{1}}$.

18 A Final Apology

I feel that I should stop at this point. One reason is that this is the 100th page of my handwritten manuscript, but there are other reasons. Paul has continued to work on set theory, stating new and old problems in the numerous problem papers he published. Our last major set theory paper with Jean Larson [109] appeared in 1993. It would not really be appropriate for me to speculate on the reactions that these latest problems may provoke, for we lack the perspective. It is also true, that his interest in set theory is slightly diminished, he does not like the technical problems which already in the assumptions involve consistency results. But he triumphantly continues to carry the flag of Georg Cantor.

I also have some doubts about my manuscript. It is as if I have been trying to sketch a rain forest, but with only enough time and ability to draw the trunks of what I thought to be the largest trees. Paul’s real strength is in the great variety of those hundreds of small questions which he has asked that have given some real insights into so many different topics. I can only admire his inventiveness and thank him for everything he has given us.

Finally, I also wish to thank our old friend Eric Milner for helping me to prepare this paper.

19 Paul Erdős Set Theory Papers