9
$\begingroup$

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)}$?

$\endgroup$
15
  • 5
    $\begingroup$ As the author of the notes, I tried to use the standard notation (known as the Erdös-Rado arrow notation) instead of inventing a new notation. $\endgroup$
    – Burak
    Mar 21 at 17:46
  • 2
    $\begingroup$ @ToddTrimble I have encountered the notation so many times that I am quite certain that it is standard in that field. For instance Saharon Shelah uses it in many articles. (By the way, I didn't find what "Egad" stands for, I took it to be an abbreviation like "WLG") $\endgroup$ Mar 21 at 18:18
  • 4
    $\begingroup$ Why all this bad publicity? It is useful, and compact. No one who works in the field gets confused. $\endgroup$ Mar 21 at 22:13
  • 6
    $\begingroup$ Compact it is, but for the life of me I can’t remember which number in the notation denotes which parameter. $\endgroup$ Mar 23 at 8:01
  • 3
    $\begingroup$ If only cardinal and ordinal numbers were under consideration, we could just define $(b)^r_k$ to be the corresponding "Ramsey number" and then we could write $a\ge(b)^r_k$ or $a\lt(b)^r_k$ instead of $a\to(b)^r)_k$ or $a\not\to(b)^r_k$. $\endgroup$
    – bof
    Mar 24 at 0:44

1 Answer 1

11
$\begingroup$

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.)

$\endgroup$
3
  • 1
    $\begingroup$ So, really it's just WOC + $\omega\nrightarrow(\omega)^\omega_2$, which is a consequence of WOC + well-orderable continuum. And the question remains whether or not the partition relation just follows from WOC, and can therefore be eliminated as an explicit assumption? If $\omega\to(\omega)^\omega_2$ has some LC strength to it, that means that we can arrange all kind of models where the continuum is not well-orderable, but the partition relation fails and WOC holds, just by taking symmetric extensions over some LC-challenged model. $\endgroup$
    – Asaf Karagila
    Mar 29 at 16:50
  • 1
    $\begingroup$ Yes, that's the situation at the moment. And sure, if we knew that the Mathias relation gives you an inaccessible, we would be done. The alternative is to force $\mathsf{WOC}$ over, say, a Solovay model, while preserving the relation. $\endgroup$ Mar 29 at 17:55
  • $\begingroup$ Do we even know that WOC is forceable over Solovay models (without forcing full AC, that is)? $\endgroup$
    – Asaf Karagila
    Mar 29 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.