16
$\begingroup$

This may be inappropriate for MO, but here goes: if I have understood the statement of the Erdős–Rado theorem correctly, then it contains as a special case the following result:

if $\mu$ is an infinite cardinal then $(2^\mu)^+ \to (\mu^+)_\mu^2$

that is, every $\mu$-colouring of the $2$-elements subsets of a set $X$ of cardinality $> 2^\mu$ has a monochromatic subset of cardinality $>\mu$.

Looking online, the usual citation given for the ER-theorem is

P. Erdős, R. Rado, A partition calculus in set theory. Bull. Amer. Math. Soc. 62 (1956), 427–489

I am trying to track down where in this paper one can find the statement of the E-R theorem, or at least the special case described above. Unfortunately, partition calculus lies well outside my usual routes for mathematical excursions, and some of the notation E&R use seems slightly at odds with the notation I see in all the various online notes describing or proving the E-R theorem. I am hoping that the set theorists among the MO readership may be more familiar with the notation of the paper and hence be able to quickly locate the statement.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Theorem 39. The fact that $(2^\kappa)^+\to(\kappa^+)^2_2$ is older and due to Erdős. $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 23, 2014 at 1:04
  • $\begingroup$ @AndresCaicedo Thanks. Did you mean subscript 2 in your comment? Or is the subscript $\kappa$ case a straightforward consequence of the subscript 2 case? $\endgroup$
    – Yemon Choi
    Commented Dec 23, 2014 at 1:09
  • 1
    $\begingroup$ Oh, I meant $\kappa$. $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 23, 2014 at 1:13

2 Answers 2

Reset to default
10
$\begingroup$

It is also stated as Theorem 4.(i), I think, and again on pages 470 and 472 where the reference is given to earlier results.

For a recent easy-to-read presentation of the proof, see Theorem 5.1.4 in David Marker's Introduction to Model Theory.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! Now you point it out, it does seem clearer; I guess I was just left dazed by the length of the paper $\endgroup$
    – Yemon Choi
    Commented Dec 23, 2014 at 1:16
  • 3
    $\begingroup$ (@Yemon The paper is a bit intimidating. I have studied it in reasonable detail, and still keep finding results in it I had missed all previous times.) $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 23, 2014 at 1:26
17
$\begingroup$

This is Theorem 39 in the paper (see Theorem 4.(i) for a user-friendly preview). But the fact that $(2^\kappa)^+\to(\kappa^+)^2_\kappa$ is older (1946) and due to Erdős, see here:

Paul Erdős. Some set-theoretical properties of graphs, Univ. Nac. Tucumán. Revista A. 3 (1942), 363-367 MR0009444 (5,151d).

(Anyway, it is probably easier to read a more modern presentation, such as in Paul Erdős, Andras Hajnal, Attila Máté, and Richard Rado. Combinatorial set theory: partition relations for cardinals, volume 106 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, 1984.)

There are still more modern presentations, using the language of elementary substructures, but if you are not familiar with it, this may not be too accessible.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ Thanks! Avshalom and you answered almost simultaneously. Since the system only allows me to accept one answer, I am accepting Avshalom's in the spirit of "redistributing wealth" :) no offence intended $\endgroup$
    – Yemon Choi
    Commented Dec 23, 2014 at 1:15
  • 2
    $\begingroup$ Couple of historical comments concerning the Erdos Rado Theorem and its proof: (1) The model theortic proof is due to Simpson from 1970. (2) Duro Kurepa already in 1935 published this theorem (under GCH), in the introduction of the 1965 ecylopedic paper by Erdos, Hajnal and Rado the authors gave full credit for this tehorem to Kurepa. Sadly all the modern writers omit Kurepa's name. $\endgroup$
    – Rami Grossberg
    Commented Mar 11, 2015 at 18:15
  • 1
    $\begingroup$ Is anything stronger known if the final $\kappa$ in the subscript is replaced by a 2? That is, can the $(2^\kappa)^+$ be made smaller, or the $\kappa^+$ be made larger? $\endgroup$
    – Louis D
    Commented Jan 5, 2023 at 18:11
  • 2
    $\begingroup$ @Louis Not really. The parameters are basically optimal. The basically refers to the use of cardinals in the equation. If instead we look at ordinals (so, rather than just a homogeneous set of size $\kappa^+$, we look at it as an ordered set of ordinals, and try to see how large its order type can be), we can say more. The place to start is MR1261193 Baumgartner, James E.; Hajnal, András; Todorčević, Stevo. Extensions of the Erdős-Rado theorem. In Finite and infinite combinatorics in sets and logic, 1–17, Kluwer Acad. Publ., Dordrecht, 1993. $\endgroup$
    – Andrés E. Caicedo
    Commented Jan 5, 2023 at 19:49
  • $\begingroup$ Thank you for that reference. On page 2, they mention some open problems under the assumption of GHC. What I'm interested in (assuming GHC) is whether $\omega_2\to (\beta)^2_2$ for all ordinals $\beta<\omega_2$? If this has a positive answer, then based on what they say on page 2, I imagine it should be hard to prove. However, if it has a negative answer, perhaps there is already a reference which answers my question? $\endgroup$
    – Louis D
    Commented Jan 6, 2023 at 19:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .