Set Theory – Does X ? (?)?? for Every Infinite X Imply AC?

axiom-of-choiceinfinite-combinatoricslo.logicramsey-theoryset-theory

For any set $X$ and cardinal $\mu \neq \emptyset$, we denote by $[X]^\mu$ the collection of subsets of cardinality $\mu$. If $\kappa, \mu \neq \emptyset$ are cardinals and $f: [X]^\mu\to \kappa$ is a map, we say that $H\subseteq X$ is homogeneous with respect to $f$ if the restriction $f|_{[H]^\mu}: [H]^\mu \to \kappa$ is constant.

For cardinals $\lambda, \mu, \kappa\neq \emptyset$ and any set $X\neq \emptyset$ we write $$X \to (\lambda)^\mu_\kappa$$ if for every map $f: [X]^\mu\to\kappa$ there is $H\subseteq X$ such that $H$ is homogeneous with respect to $f$ and $|H|=\lambda$.

With the help of the Axiom of Choice ${\sf (AC)}$ one can prove that $X \not\to (\omega)^\omega_2$ for every infinite $X$ (see Theorem 7, p. 5 of this recommended introduction to infinite combinatorics, thank you to Burak for writing it!).

Question. Does the statement "$X \not\to (\omega)^\omega_2$ for every infinite set $X$" imply ${\sf (AC)}$?

Best Answer

The answer is no, the statement that for every set $X$ we have $$X\not\to(\omega)^\omega_2$$ does not imply the axiom of choice.

This was shown by Kleinberg and Seiferas in 1973, see

MR0340025 (49 #4782) Kleinberg, E. M.; Seiferas, J. I. Infinite exponent partition relations and well-ordered choice. J. Symbolic Logic 38 (1973), 299–308. https://doi.org/10.2307/2272066

For $\kappa$ a (well-ordered) infinite cardinal, $\kappa$-well-ordered choice, $\mathsf{AC}_\kappa$, is the statement that every $\kappa$-sequence of nonempty sets admits a choice function.

The axiom of well-ordered choice $\mathsf{WOC}$ is the statement that $\mathsf{AC}_\kappa$ holds for all infinite well-ordered $\kappa$.

This statement is strictly weaker than the axiom of choice: it does not imply that $\mathbb R$ is well-orderable, and even if we add this assumption, the result is still weaker than choice. See for instance theorem 5.1 in

MR1351415 (96h:03087) Higasikawa, Masasi Partition principles and infinite sums of cardinal numbers. Notre Dame J. Formal Logic 36 (1995), no. 3, 425–434. https://doi.org/10.1305/ndjfl/1040149358

However, as shown in the paper by Kleinberg and Seiferas, $\mathsf{WOC}$ plus the existence of a well-ordering of $[\omega]^\omega$ rules out all infinite exponent partition relations. It is still open (as far as I know) whether $\mathsf{WOC}$ suffices for this result. What Kleinberg and Seiferas show is that, under $\mathsf{WOC}$, either all infinite exponent partition relations fail, or else $\omega\to(\omega)^\omega_2$. (And the latter fails if $[\omega]^\omega$ is well-orderable.)

Related Question