Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$.

A hypergraph $H=(V,E)$ consists of a set $V$ and a collection of subsets $E \subseteq {\cal P}(V)$. A coloring is a map $c: V\to \kappa$, where $\kappa \neq \emptyset$ is a cardinal, such that for every $e\in E$ with $|e|\geq 2$ the restriction $c|_e$ is non-constant. We denote the minimal cardinal $\kappa$ such that there is a coloring $c: V\to \kappa$ by $\chi(H)$ and call it the chromatic number of $H$

If $A\subseteq [\omega]^\omega$ is finite or countable, then the chromatic number of $(\omega, A)$ equals $2$. This motivates the following cardinals: for any integer $n\geq 2$ let ${\bf k}_n$ be the minimum cardinality of a set $A\subseteq [\omega]^\omega$ such that $\chi(\omega, A) > n$.

Is it consistent in ${\sf ZFC}$ that $${\bf k}_n < {\bf k}_{n+1} < 2^{\aleph_0}$$ for all integers $n\geq 2$?


1 Answer 1


The cardinals $\bf k_n$ ($2\le n\lt\omega$) are all equal.

Lemma. Let $\kappa$ be an infinite cardinal. Given a set $A\subseteq[\omega]^\omega$ with $|A|=\kappa$ and $\chi(\omega,A)\gt n$, we can construct a set $B\subseteq[\omega]^\omega$ with $|B|=\kappa$ and $\chi(\omega,B)\gt n^2$.

Proof. For each $a\in A$ choose a collection $B_a\subseteq[a]^\omega$ so that the hypergraph $(a,B_a)$ is isomorphic to $(\omega,A)$, and let $B=\bigcup_{a\in A}B_a$.

Let $(\omega,B)$ be colored with $n^2$ colors; let $[n]\times[n]$ be the set of colors, and let $x\mapsto(f(x),g(x))$ be the coloring. Since $\chi(\omega,A)\gt n$, there is a set $a\in A$ such that $f$ is constant on $a$. Then, since $\chi(a,B_a)\gt n$, there is a set $b\in B_a$ such that $g$ is constant on $b$.

Corollary. If there is a set $A\subseteq[\omega]^\omega$ with $|A|=\kappa$ and $\chi(\omega,A)\gt2$, then there is a set $B\subseteq[\omega]^\omega$ with $|B|=\kappa$ and $\chi(\omega,B)=\aleph_0$.

  • $\begingroup$ Wonderful @bof - and happy new year! - Do you happen to know whether ${\bf k}_2 < 2^{\aleph_0}$ is consistent? $\endgroup$ Jan 3, 2021 at 17:26
  • $\begingroup$ I was wondering whether ${\bf k}_2 \in \{{\frak r}, {\frak s}\}$, denoting the reaping and splitting numbers respectively, could be proved, but I haven't had time to check this. $\endgroup$ Jan 3, 2021 at 17:44
  • 4
    $\begingroup$ $\mathbf k_2=\mathfrak r$. The only difference between the definitions is that the former is about splitting into two nonempty sets where the latter is about splitting into two infinite sets. But that doesn't affect the cardinality because you can adjoin to any hypergraph $A$ all those sets that differ only finitely from members of $A$, and this won't increase the cardinality of $A$. $\endgroup$ Jan 4, 2021 at 0:11
  • $\begingroup$ Thank you @AndreasBlass - and happy new year. $\endgroup$ Jan 4, 2021 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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