Erdos 1974 unsolved solved problems set theory

../

problem_35: The survey's correction of Problem 35 of the 1967 list: a free set of power ℵ_ω under the problem's conditions was already proved as Theorem 49 of the 1965 Erdős–Hajnal–Rado paper, and the real problem is a free set of power ℵ_(ω+1).

problem_38: The survey's entry on Problem 38 of the 1967 list: Hechler's theorem that CH makes 38/A false even for convergent sequences, the independence of 38/A from ZFC + 2^ℵ0 > ℵ1, and the statement that MA makes 38/C false even for images of measure 0.

problem_viii: The survey's Problem VIII, which asks whether (ω_2, ω) →^0 (ω_1+ω, ω_1·ω)^2 is provable in ZFC + GCH or whether its negation is consistent with ZFC + GCH.

question_p270: The survey's open question whether ω^(ω^ρ) → (ω^(ω^ρ), n)^2 holds for n < ω and 0 < ρ < ω_1, with Galvin's remark that ω^α → (ω^α, 3)^2 for 2 < α < ω_1 forces α to be a power ω^ρ.

question_p272: The survey's question whether ω_2 → (ω_1 + ω)^2_2, or even ω_2 → (ξ)^2_2 for every ξ < ω_2, is consistent with GCH, posed after Hajnal's two negative consistency results and with the authors' ω_2 → (ω_1 + n)^2_2 for finite n.

theorem_p270_chang: The survey's report of Chang's theorem ω^ω → (ω^ω, 3)^2, of Milner's extension to ω^ω → (ω^ω, k)^2 for finite k, and of Jean Larson's two further theorems on (ω* + ω)^ω and κ^ω.

theorem_p271_baumgartner_hajnal: The survey's report of the Baumgartner–Hajnal theorem that an order type Φ with Φ → (ω)^1_ℵ0 satisfies Φ → (α)^2_k for every α < ω_1 and k < ω, answering several problems of the 1967 list.

theorem_p273_hajnal: The survey's report of Hajnal's theorem that under GCH, for regular ℵ_α, ω_(α+1)^2 ↛ (ω_(α+1)^2, 3)^2, of Baumgartner's extension to every α, and of the authors' question whether MA_ℵ1 + 2^ℵ0 = ℵ2 gives the positive relation at ω_1^2.

theorem_p278_shelah: The survey's report, under Problem 36, of Shelah's theorem that under GCH a set mapping on a set of type ω_(α+1), ℵ_α regular, whose images pairwise meet in fewer than ℵ_α points has a free subset of every type ξ < ω_(α+1).

theorem_p284: The survey's Definition 2 of the relation (a, b) →^0 (c, d)^r and its theorem that (ω_1, n+2) →^0 (ω_1, ω(n+1)+n+1)^2 for n < ω, while CH gives the negative relation with ω(n+1)+n+2 in the second place.

---

Paul Erdős, András Hajnal, Unsolved and solved problems in set theory. Proceedings of Symposia in Pure Mathematics 25 (1974), 269-287. No copyright line is printed in the scan, a Rényi archive copy (pp. 1--2 and 18--19 read); the publisher's volume page (https://pubs.ams.org/ebooks/pspum/025/, read 2026-10-02) carries the footer "© , American Mathematical Society", printed without a year, with a "Rights and Permissions" link, offers the chapters for purchase and names no open license, every other right reserved.

This is a status report on the Erdős-Hajnal problem list distributed in 1967, recording which problems were solved in the interim, correcting problems that were vaguely or incorrectly stated, and adding new ones. Section 2 reviews the ordinary partition relation: Chang's theorem omega^omega arrow (omega^omega, 3)^2 and Milner's and Larson's extensions, the Baumgartner-Hajnal theorem that phi arrow (omega)^1_{aleph_0} implies phi arrow (alpha)^2_k for alpha < omega_1 and k finite (a positive answer to Problem 10 with rho = 0 and to Problems 10/A, 11 and 11/A), and Laver's and Baumgartner's Martin's Axiom and consistency results relevant to Problem 8. Later sections introduce the generalized relation (a,b) arrow^0 (c,d)^r of Definition 2 and pose Problems VI-VIII; Problem VIII asks whether (omega_2, omega) arrow^0 (omega_1+omega, omega_1 . omega)^2 is provable in ZFC + GCH or whether its negation is consistent, noting that omega_2 does not arrow (omega_1+omega)^2_2 is itself consistent with GCH. For problem 1172 it poses on p. 272 the problem's closing consistency question in the same form, whether omega_2 arrow (omega_1+omega)^2_2, or even omega_2 arrow (xi)^2_2 for xi < omega_2, is consistent with GCH, after Hajnal's results that omega_2 does not arrow [omega_1+omega]^2_{aleph_1} and that omega_2 does not arrow (omega_1+2)^2_{aleph_0} are each consistent with ZFC + GCH; on p. 273, within that GCH discussion, it recalls the authors' earlier result omega_2 arrow (omega_1+n)^2_2 for n < omega. The three GCH relations of the problem's first part do not appear in the paper. For problem 1173 the relevant entries are Problems 35 and 36 on free sets for set mappings: the paper explicitly says Problem 35 was badly stated, since a free set of power aleph_omega under its conditions was already proved in Theorem 49 of Erdős, Hajnal and Rado's Partition relations for cardinal numbers (1965), and the real question is a free set of power aleph_{omega+1}, while Problem 36 is answered positively (it follows from omega_1 arrow (alpha)^2_2) and strengthened by theorems of Shelah (under GCH, for regular aleph_alpha and a set mapping on a set of order type omega_{alpha+1} whose images pairwise meet in fewer than aleph_alpha points, a free subset of every type xi < omega_{alpha+1}) and Prikry.

Source: https://users.renyi.hu/~p_erdos/1974-36.pdf.

Bears on. Each row states what the survey records on the problem; it proves none of these results itself.

• #1172: the question on p. 272 (question_p272) is the problem's consistency part in the same words; the survey poses it and gives no answer. The problem's three GCH relations do not appear in the survey.
• #1173: the entry on Problem 35, p. 278 (problem_35), names a free set of power $\aleph_{\omega+1}$ as the real problem and records a free set of power $\aleph_\omega$ as known from Theorem 49 of the 1965 Erdős–Hajnal–Rado paper; Shelah's theorem under Problem 36, p. 278 (theorem_p278_shelah), needs $\aleph_\alpha$ regular and gives free subsets of every type below $\omega_{\alpha+1}$. Neither answers the problem.
• #501: the entry on Problem 38, p. 279 (problem_38), states without proof that under MA part 38/C of the 1967 list fails even when every $f(x)$ has measure $0$, in a paragraph opened by Hechler's preprint [18]; the survey does not restate 38/C.
• #1169: Hajnal's theorem on p. 273 (theorem_p273_hajnal) gives $\omega_1^2\not\to(\omega_1^2,3)^2$ under G.C.H. at $\alpha=0$, a consistency result; p. 274 asks whether $\mathrm{MA}_{\aleph_1}+2^{\aleph_0}=\aleph_2$ gives the positive relation, with no answer.
• #1171: p. 274 (theorem_p273_hajnal) says without proof that the authors proved $\omega_1^2\to(\omega_1\cdot\alpha,3)^2$ for $\alpha<\omega_1$ in their 1970 paper [7]; its case $\alpha=\omega$ is the problem's case $k=1$. The survey gives no case $k\ge2$.
• #1170: the second form of the question on p. 272 asks for the consistency of $\omega_2\to(\xi)^2_2$ for every $\xi<\omega_2$ with GCH, more than the problem asks; no answer is given.
• #590: Chang's theorem, reported on p. 270 (theorem_p270_chang), is the problem's statement; the survey cites Chang's paper and gives no proof.
• #592: the question on p. 270 (question_p270) asks at $n=3$ whether every $\beta=\omega^\rho$, $0<\rho<\omega_1$, has the problem's property, and Galvin's remark there says no other $\beta$ with $2<\beta<\omega_1$ has it; the survey records the question as open.
• #591: the case $\rho=2$, $n=3$ of the same question is the problem's relation; the survey records it as open.

Results. Labels and pages are the print's; the survey proves none of the reported theorems.

• Theorem (Chang), p. 270: $\omega^\omega\to(\omega^\omega,3)^2$, with Milner's $\omega^\omega\to(\omega^\omega,k)^2$ for $k<\omega$ and Jean Larson's theorems on $(\omega^*+\omega)^\omega$ and $\kappa^\omega$.
• Question, p. 270: whether $\omega^{\omega^\rho}\to(\omega^{\omega^\rho},n)^2$ for $n<\omega$, $0<\rho<\omega_1$, with Galvin's remark.
• Theorem (Baumgartner–Hajnal), p. 271: if $\Phi\to(\omega)^1_{\aleph_0}$ then $\Phi\to(\alpha)^2_k$ for $\alpha<\omega_1$ and $k<\omega$, a positive answer to Problem 10 with $\rho=0$ and to Problems 10/A, 11 and 11/A.
• Question, p. 272: whether $\omega_2\to(\omega_1+\omega)^2_2$, or even $\omega_2\to(\xi)^2_2$ for $\xi<\omega_2$, is consistent with G.C.H., with Hajnal's two negative consistency results and the authors' $\omega_2\to(\omega_1+n)^2_2$ for $n<\omega$ (p. 273).
• Theorem (Hajnal), p. 273: G.C.H. and $\aleph_\alpha$ regular give $\omega_{\alpha+1}^2\not\to(\omega_{\alpha+1}^2,3)^2$, with Baumgartner's extension to every $\alpha$ and the MA question of p. 274.
• Problem 35, p. 278: badly stated; a free set of power $\aleph_\omega$ was already proved, and the real problem is a free set of power $\aleph_{\omega+1}$.
• Theorem (Shelah), p. 278: under G.C.H., for $\aleph_\alpha$ regular and a set mapping on a set of type $\omega_{\alpha+1}$ with $|f(x)\cap f(y)|<\aleph_\alpha$, a free subset of every type $\xi<\omega_{\alpha+1}$.
• Problem 38, p. 279: Hechler's CH theorem on 38/A, the independence of 38/A from ZFC + $2^{\aleph_0}>\aleph_1$, and the MA statement on 38/C.
• Definition 2 and Theorem, p. 284: $(\omega_1,n+2)\xrightarrow{0}(\omega_1,\omega(n+1)+n+1)^2$ for $n<\omega$, while C.H. gives $(\omega_1,n+2)\not\xrightarrow{0}(\omega_1,\omega(n+1)+n+2)^2$.
• Problem VIII, p. 285: whether $(\omega_2,\omega)\xrightarrow{0}(\omega_1+\omega,\omega_1\cdot\omega)^2$ is provable in ZFC + G.C.H. or its negation consistent with it.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.