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

Improve this question
$\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
    Commented Mar 21, 2022 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$
    – Dominic van der Zypen
    Commented Mar 21, 2022 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$
    – Andrés E. Caicedo
    Commented Mar 21, 2022 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$
    – Emil Jeřábek
    Commented Mar 23, 2022 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
    Commented Mar 24, 2022 at 0:44

1 Answer 1

Reset to default
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.)

Improve this answer
$\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 ♦
    Commented Mar 29, 2022 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$
    – Andrés E. Caicedo
    Commented Mar 29, 2022 at 17:55
  • $\begingroup$ Do we even know that WOC is forceable over Solovay models (without forcing full AC, that is)? $\endgroup$
    – Asaf Karagila ♦
    Commented Mar 29, 2022 at 20:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .