ZFC status of the sharp free-set partition relation $\omega_{2}\cdot\alpha\nrightarrow[\omega_{1}^{\omega}+1,\omega_{2}\cdot\alpha]_{\aleph_{2}}$ without the hypothesis $2^{\aleph_{1}}=\aleph_{2}$ (Erdős–Hajnal–Milner, 1969)

In 1969, Erdős, Hajnal and Milner proved, under the cardinal-arithmetic hypothesis $2^{\aleph_{1}}=\aleph_{2}$, the negative free-set partition relation $\omega_{2}\cdot\alpha\nrightarrow[\omega_{1}^{\omega}+1,\omega_{2}\cdot\alpha]_{\aleph_{2}}$ for every ordinal $\alpha$ with $\omega\le\alpha<\omega_{1}$: there is a well-ordered set of order type $\omega_{2}\cdot\alpha$ carrying a family of $\aleph_{2}$ subsets, each of order type at most $\omega_{1}^{\omega}$, such that every subset of order type $\omega_{2}\cdot\alpha$ meets all but fewer than $\aleph_{2}$ of them. Together with their earlier ZFC theorem that the corresponding positive relation holds with threshold $\omega_{1}^{\omega}$, this shows that threshold to be best possible -- but only under the hypothesis. The problem asks whether this negative relation, already in the critical case $\alpha=\omega$, is provable in ZFC without any assumption on the value of $2^{\aleph_{1}}$, or whether its truth depends on $2^{\aleph_{1}}$. The question remains open.

Background

Let $\aleph_{1}$ and $\aleph_{2}$ be the first and second uncountable cardinals, with initial ordinals $\omega_{1}$ and $\omega_{2}$; ordinal arithmetic (products such as $\omega_{2}\cdot\alpha$ and the power $\omega_{1}^{\omega}$) is understood throughout in the ordinal sense. For ordinals $\alpha,\beta,\gamma$ and a cardinal $m$, Erdős, Hajnal and Milner introduced the free-set partition symbol $\alpha\Rightarrow[\beta,\gamma]_{m}$, defined as follows: whenever $S$ is a well-ordered set of order type $\alpha$ and $\mathcal{F}=(F_{\mu}:\mu\in M)$, $|M|=m$, is a family of subsets of $S$ each of order type less than $\beta$, there exists a subset $C\subseteq S$ of order type $\gamma$ with $|\{\mu\in M:F_{\mu}\cap C=\varnothing\}|=m$; such a $C$ is called $(\mathcal{F},m)$-free. The negation is written $\alpha\nrightarrow[\beta,\gamma]_{m}$ and asserts the existence of a well-ordered set of type $\alpha$ and a family of $m$ subsets, each of order type less than $\beta$, that blocks every subset of type $\gamma$. This symbol is an ordinal-partition analogue of free-set problems for set mappings, a line going back to the Erdős–Specker theorem on set mappings. In a 1966 paper the same authors proved in ZFC (the standard Zermelo-Fraenkel axioms with choice, no continuum hypothesis) Theorem 10.0: $\omega_{2}\cdot\alpha\Rightarrow[\omega_{1}^{\omega},\omega_{2}\cdot\alpha]_{\aleph_{2}}$ for all $\alpha<\omega_{1}$; their Problem 5 asked whether the threshold $\omega_{1}^{\omega}$ is best possible in the critical case $\alpha=\omega$, i.e. whether $\omega_{2}\cdot\omega\nrightarrow[\omega_{1}^{\omega}+1,\omega_{2}\cdot\omega]_{\aleph_{2}}$ holds. (Theorem 10.1 of the 1966 paper, as cited in the introduction of the 1969 paper, shows under $2^{\aleph_{1}}=\aleph_{2}$ that the restriction $\alpha<\omega_{1}$ in Theorem 10.0 is necessary, i.e. that the positive relation fails at the endpoint $\alpha=\omega_{1}$; the negative relation at $\alpha=\omega$ was posed as Problem 5 of the 1966 paper and remained open until the 1969 paper.) The 1969 paper 'A problem on well ordered sets' answers Problem 5 under the single cardinal-arithmetic hypothesis $2^{\aleph_{1}}=\aleph_{2}$ (a local instance of the generalized continuum hypothesis): THEOREM (5) states that if $2^{\aleph_{1}}=\aleph_{2}$ and $\omega\le\alpha<\omega_{1}$, then $\omega_{2}\cdot\alpha\nrightarrow[\omega_{1}^{\omega}+1,\omega_{2}\cdot\alpha]_{\aleph_{2}}$. In the proof the hypothesis is used at essentially one point: the obstruction family is indexed by a well-ordering of all 'patterns' of cardinality $\aleph_{1}$ arising in the construction, of which there are at most $2^{\aleph_{1}}=\aleph_{2}$, so they can be enumerated in length $\omega_{2}$. The rest of the argument is carried out in ZFC, using Neumer's theorem that the ordinals below $\omega_{2}$ of cofinality $\omega_{1}$ form a stationary set, Fodor's pressing-down lemma, and the Milner-Rado pigeon-hole principle for ordinal numbers (by which a set of order type at most $\omega_{1}^{\omega}$ decomposes into countably many pieces of bounded order type). Thus the positive half of the sharp-threshold statement is a ZFC theorem, while the negative half is known only under $2^{\aleph_{1}}=\aleph_{2}$; the dependence of the negative half on the value of $2^{\aleph_{1}}$ is the subject of this problem. Note that by König's theorem $2^{\aleph_{1}}>\aleph_{1}$ always, so the alternative to $2^{\aleph_{1}}=\aleph_{2}$ is $2^{\aleph_{1}}\ge\aleph_{3}$.

Problem Statement

Work in ZFC. Recall the definition: for ordinals $\alpha,\beta,\gamma$ and a cardinal $m$, the free-set partition relation $\alpha\Rightarrow[\beta,\gamma]_{m}$ holds if for every well-ordered set $S$ of order type $\alpha$ and every family $\mathcal{F}=(F_{\mu}:\mu\in M)$ with $|M|=m$ of subsets of $S$, each of order type less than $\beta$, there is a subset $C\subseteq S$ of order type $\gamma$ with $|\{\mu\in M:F_{\mu}\cap C=\varnothing\}|=m$ ($C$ is $(\mathcal{F},m)$-free); the negation $\alpha\nrightarrow[\beta,\gamma]_{m}$ asserts the existence of a set $S$ of order type $\alpha$ and such a family $\mathcal{F}$ of $m$ sets of order type less than $\beta$ for which no subset of order type $\gamma$ is $(\mathcal{F},m)$-free. It is known in ZFC that $\omega_{2}\cdot\alpha\Rightarrow[\omega_{1}^{\omega},\omega_{2}\cdot\alpha]_{\aleph_{2}}$ for all $\alpha<\omega_{1}$, and it is known under $2^{\aleph_{1}}=\aleph_{2}$ that $\omega_{2}\cdot\alpha\nrightarrow[\omega_{1}^{\omega}+1,\omega_{2}\cdot\alpha]_{\aleph_{2}}$ for all $\omega\le\alpha<\omega_{1}$. The question is the ZFC status of the latter, negative half at the successor threshold: determine whether $\omega_{2}\cdot\alpha\nrightarrow[\omega_{1}^{\omega}+1,\omega_{2}\cdot\alpha]_{\aleph_{2}}$ is provable in ZFC alone -- without any assumption on the value of $2^{\aleph_{1}}$ -- with the critical instance being $\alpha=\omega$. The negative relation is sought for all $\omega\le\alpha<\omega_{1}$, and the question also asks whether its truth can depend on the value of $2^{\aleph_{1}}$: by König's theorem $2^{\aleph_{1}}>\aleph_{1}$ always, so the relevant alternative to $2^{\aleph_{1}}=\aleph_{2}$ is $2^{\aleph_{1}}\ge\aleph_{3}$, under which the negative relation at $\alpha=\omega$ can fail, that is, the positive relation $\omega_{2}\cdot\omega\Rightarrow[\omega_{1}^{\omega}+1,\omega_{2}\cdot\omega]_{\aleph_{2}}$ can hold. Note that the companion positive relation at threshold $\omega_{1}^{\omega}$ is already a ZFC theorem, so only the successor threshold $\omega_{1}^{\omega}+1$ is at issue.

References

1. P. Erdős, A. Hajnal, E. C. Milner, A problem on well ordered sets, Acta Mathematica Academiae Scientiarum Hungaricae 20(3-4) (1969) 323-329, DOI 10.1007/BF01894901, https://doi.org/10.1007/BF01894901, zbMATH Zbl 0193.30803.
2. P. Erdős, A. Hajnal, E. C. Milner, On the complete subgraphs of graphs defined by systems of sets, Acta Mathematica Academiae Scientiarum Hungaricae 17(1-2) (1966) 159-229, DOI 10.1007/BF02020452, https://doi.org/10.1007/BF02020452, zbMATH Zbl 0151.33702, https://zbmath.org/0151.33702.
3. E. Harzheim, review of 'A problem on well ordered sets' (Erdős–Hajnal–Milner 1969), zbMATH Zbl 0193.30803, https://zbmath.org/0193.30803.
4. P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1(1) (1981) 25-42, DOI 10.1007/BF02579174, https://doi.org/10.1007/BF02579174.
5. P. Erdős, A. Hajnal, A. Máté, R. Rado, Combinatorial set theory: Partition relations for cardinals, Studies in Logic and the Foundations of Mathematics 106, North-Holland Publishing Company / Akadémiai Kiadó, 347 pp. (1984), zbMATH Zbl 0573.03019, https://zbmath.org/0573.03019.
6. C. St. J. A. Nash-Williams, Obituary: Eric Charles Milner (May 17, 1928 – July 20, 1997), Bulletin of the London Mathematical Society 32(1) (2000) 91-104, DOI 10.1112/S0024609399006062, https://doi.org/10.1112/S0024609399006062, zbMATH Zbl 1015.01011.
7. A. Hajnal, Paul Erdős' set theory, in R. L. Graham et al. (eds.), The mathematics of Paul Erdős. Vol. II, Algorithms and Combinatorics 14, Springer, pp. 352-393 (1997; zbMATH Zbl 0865.01010, https://zbmath.org/0865.01010); reissued in 2013 with this chapter on pp. 379-418, DOI 10.1007/978-1-4614-7254-4_23, https://doi.org/10.1007/978-1-4614-7254-4_23.
8. A. Hajnal, J. A. Larson, Partition relations, in M. Foreman et al. (eds.), Handbook of set theory, Springer, Dordrecht, pp. 129-213 (2010), DOI 10.1007/978-1-4020-5764-9_3, https://doi.org/10.1007/978-1-4020-5764-9_3.
9. A. Kanamori, Erdős and set theory, Bulletin of Symbolic Logic 20(4) (2014) 449-490, DOI 10.1017/bsl.2014.38, https://doi.org/10.1017/bsl.2014.38.