On a problem of Erdös, Hajnal and Rado

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


Erdös, Hajnal and Rado asked whether N2 N1 → N0 N0 N1 N1. We show that N2 N1 {not right arrow} N0 N0 N1 N1 is consistent with ZF + GCH. The above symbol means that there exists a coloring of pairs (αβ), α ∈ ω2, β ∈ ω1, by two colors such that each A × B, where A ⊆ ω2, B ⊆ ω1, |A| = א0. |B| = א1, has a pair of each color. N2 N1 {not right arrow} N0 N0 N1 N1 is implied by the following statement (*): There are sets Aαη ⊆ ω1, α ∈ ω2, η ∈ ω1, such that (∀α, η, ξ) (η ≠ ξ → Aαη ∩ Aαξ - 0), (∀α) ∪ {Aαη: η ∈ ω1} = ω1, and for every sequence of distinct αn ∈ ω2 and every sequence of (not necessarily distinct) ηn ∈ ω1, |ω1 - ∪ {Aαnηn : η ∈ ω} | ≤ א0. Another consequence of (*) is. For every א1 nonprincipal countably additive ideals lρ ⊆ P(ω1), ρ ∈ ω1, there is a set X ⊆ ω1 such that for all ρ ∈ ω1 neither X nor ω1 - X ∈ lρ. This shows the independence of a problem of Ulam.

Original languageEnglish (US)
Pages (from-to)51-59
Number of pages9
JournalDiscrete Mathematics
Issue number1
StatePublished - Mar 1972


Dive into the research topics of 'On a problem of Erdös, Hajnal and Rado'. Together they form a unique fingerprint.

Cite this