Open coloring and the cardinal invariant $\mathfrak b$

Nik Weaver asked for a direct proof of the fact that Todorcevic’s axiom implies the failure of CH fails. Here goes.

Notation. For a set $X$, we write $[X]^2$ for the set of unordered pairs $\{ \{x,x’\}\mid x,x’\in X, x\neq x’\}$.

Definition (Todorcevic’s axiom). If $X$ is a separable metric space, and $[X]^2=K_0\cup K_1$, with $K_0$ open in $[X]^2$, then at least one of the following hold:

  • there exists an uncountable subset $Y\subseteq X$ such that $[Y]^2\subseteq K_0$;
  • there is a partition $X=\bigcup_{n<\omega}Y_n$ such that $[Y_n]^2\subseteq K_1$ for all $n<\omega$.

Lemma. If $2^{\aleph_0}=\aleph_1$, then $\mathfrak b=\aleph_1$, i.e., there exists a sequence $\overrightarrow f=\langle f_\alpha\mid\alpha<\omega_1\rangle$ such that:

  1. $f_\alpha\in{}^\omega\omega$ is an increasing function for all $\alpha<\omega_1$;
  2. $\{ n<\omega\mid f_\alpha(n)\ge f_\beta(n)\}$ is finite, whenever $\alpha<\beta<\omega_1$;
  3. for every $g\in{}^\omega\omega$, there exists some $\alpha<\omega_1$ such that $\{ n<\omega\mid g(n)<f_\beta(n)\}$ is infinite, whenever $\alpha<\beta<\omega_1$.

Proof.  Since $2^{\aleph_0}=\aleph_1$, we can list ${}^\omega\omega$, as $\langle g_\alpha\mid\alpha<\omega_1\rangle$. We then construct $\langle f_\alpha\mid\alpha<\omega_1\rangle$ by recursion on $\alpha<\omega_1$. Suppose that $\langle f_\beta\mid\beta<\alpha\rangle$ has already been constructed. Let $\{h_n\mid n<\omega\}$ be some enumeration of $\{ f_\beta\mid\beta<\alpha\}\cup\{ g_\alpha\}$. Define $f_\alpha$ by letting $f_\alpha(n):=1+\sum_{i=0}^n\sum_{j=0}^n h_i(j)$ for all $n<\omega$. $\square$

Theorem (Todorcevic). Todorcevic’s axiom implies that $\mathfrak b>\aleph_1$.
Proof.  Assume TA. Towards a contradiction, suppose that $\langle f_\alpha\mid\alpha<\omega_1\rangle$ satisfies the above items (1)–(3). Consider $X:=\{ f_\alpha\mid\alpha<\omega_1\}$ as a subspace of the Baire space ${}^\omega\omega$. Let $K_1:=[X]^2\setminus K_0$, where $K_0:=\{ \{f,g\}\mid \exists i,j<\omega\ f(i)<g(i)\ \&\ g(j)<f(j)\}$. It is easy to see that $K_0$ is open. Now, let us examine each of the alternatives:

Alternative 2. There is a partition $X=\bigcup_{n<\omega}Y_n$ such that $[Y_n]^2\subseteq K_1$ for all $n<\omega$:
In particular, we may fix an uncountable subset $Y\subseteq X$ with $[Y]^2\subseteq K_1$. Then, for every $\alpha<\beta$ such that $f_\alpha,f_\beta\in Y$, we have that $\{ n<\omega\mid f_\alpha(n)> f_\beta(n)\}$ is empty. Write $B:=\{\beta<\omega_1\mid f_\beta\in Y\}$. Notice that if $\sup_{\beta\in B}f_\beta(n)$ is finite for all $n<\omega$, then we get a contradiction to item (3), hence, we may fix some $m<\omega$ such that $\sup\{f_\beta(m)\mid \beta\in B\}=\omega$. Pick a large enough $\delta\in B$ such that $\sup\{ f_\beta(m)\mid \beta\in B\cap\delta\}=\omega$. Then $f_\delta(m)$ cannot be an integer. This is a contradiction.

Alternative 1. There exists an uncountable subset $Y$ with $[Y]^2\subseteq K_0$:
In particular, for every $\alpha<\beta$ such that $f_\alpha,f_\beta\in Y$, we have that $\{ n<\omega\mid f_\alpha(n)\ge f_\beta(n)\}$ is nonempty. Write $B:=\{\beta<\omega_1\mid f_\beta\in Y\}$. Then, for all $\alpha<\beta$ in $B$, we have $\Delta(\alpha,\beta)>0$, where $$\Delta(\alpha,\beta):=\min\{ m<\omega\mid m\le n<\omega\rightarrow(f_\alpha(n)\le f_\beta(n))\}.$$

Thus, to meet the desired contradiction, it suffices to establish the following.

Subclaim. There exists $\alpha<\beta$ in $B$ such that $\Delta(\alpha,\beta)=0$.
Proof. Since ${}^{<\omega}\omega$ is countable, let us fix a large enough $\delta\in B$ such that for every $t\in {}^{<\omega}\omega$: if there exists $\alpha\in B$ with $t\subseteq f_\alpha$, then there exists such $\alpha\in B$ below $\delta$.

Write $B_n:=\{\beta\in B\setminus(\delta+1)\mid \Delta(\delta,\beta)=n\}$. As $B\setminus(\delta+1)=\bigcup_{n<\omega}B_n$, let us fix some $n<\omega$ such that $B_n$ is uncountable. By item (3) above, we get that the set $$M:=\{ m<\omega\mid \sup\{ f_\beta(m)\mid \beta\in B_n\}=\omega\}$$ is nonempty (in fact, infinite), so consider its minimal element, $m:=\min(M)$.
For $t\in{}^m\omega$, denote $B^t_n:=\{ \beta\in B_n\mid t\subseteq f_\beta\}$. By minimality of $m$, the set $\{ t\in{}^m\omega\mid B^t_n\neq\emptyset\}$ is finite, so  we can easily find some $t\in{}^m\omega$ such that $$\sup\{ f_\beta(m)\mid \beta\in B^t_n\}=\omega.$$ Since $\{ \beta\in B\mid t\subseteq f_\beta\}$ is nonempty, let us fix some $\alpha\in B$ below $\delta$ such that $t\subseteq f_\alpha$. Put $k:=\Delta(\alpha,\delta)$, and then pick $\beta\in B^t_n$ such that $f_\beta(m)>f_\alpha(k+n)$. Of course, $\alpha<\delta<\beta$. We claim that $\Delta(\alpha,\beta)=0$. This is best seen by dividing into three cases:

  • if $i<m$, then $f_\alpha(i)=t(i)=f_\beta(i)$;
  • if $m\le i\le k+n$, then $f_\alpha(i)\le f_\alpha(k+n)<f_\beta(m)\le f_\beta(i)$ (recall that the elements of $\overrightarrow f$ are increasing functions!);
  •  if $k+n<i<\omega$, then $\Delta(\alpha,\delta)=k<i$ and $f_\alpha(i)\le f_\delta(i)$, as well as $\Delta(\delta,\beta)=n<i$ and $f_\delta(i)\le f_\beta(i)$. Altogether, $f_\alpha(i)\le f_\beta(i)$. End of subclaim

This complete the proof. $\square$

Ari B. pointed out (see his comment bel0w) that the proof shows that the axiom SOCA already implies that $\mathfrak b>\omega_1$, where SOCA is the outcome of weakening the second alternative of TA to “there exists an uncountable subset $Y\subseteq X$ such that $[Y]^2\subseteq K_1$”.


This entry was posted in Blog, Expository and tagged , . Bookmark the permalink.

13 Responses to Open coloring and the cardinal invariant $\mathfrak b$

  1. Ari B. says:

    There’s a problem with your statement of Todorcevic’s Axiom. What you’ve stated here is actually the Semi-Open Colouring Axiom.

    So it seems that you’ve shown the stronger result that SOCA implies $\mathfrak b > \aleph_1$ and therefore contradicts CH.

    Incidentally, Kunen’s new textbook shows that SOCA implies that there are no weakly Luzin sets in $\mathbb R^n$ when $n \geq 2$ and therefore contradicts CH.


  2. Dani says:

    Hi Assaf,
    Isn’t Todorcevic OCA states that either there is uncoutable 0 homogeneous set or a countable decomposition of X into 1-homogeneous pieces?


  3. Dani says:

    – We might simplify your proof if we note that since $f_{\alpha}$ are increasing, $K_0$ is the set of couples that are not “totally” increasing (has at least one contra-example).

    – Now since in alternative 2 we get $\aleph_1$ such pairs of functions, there must be some $n<\omega$ that is the witness for $\aleph_1$ decreasinesses-pairs. Looking only at this coordinate, since a decreasing serie of $f_{\alpha}(n)$ can only be finite, we get a contradication to the fact that we have $\aleph_1$ witnesses.


  4. Nik Weaver says:

    Thank you for the detailed proof. This is essentially the argument I was already using in my book when I asked the question. I guess the consensus is that it is the most direct proof that OCA $\to$ $\neg\,$CH, although I still wonder if anyone has seriously tried to directly construct a counterexample to OCA using CH.

    Incidentally, your proof of “Alternative 2” is not correct — you only have $\{ n< \omega\mid f_\alpha(n)> f_\beta(n)\}=\emptyset$. I noticed the same error in Velickovic’s paper. I don’t have access to Todorcevic’s book at the moment, I wonder if the error tracks back to it?


  5. saf says:

    Thanks, Nik. I’m afraid I don’t have a copy of neither, but you are of course right concerning Alternative 2.

    Nevertheless, this is easy to fix: by item (3), we may find some $n<\omega$ such that $\sup\{ f_\beta(n)\mid \beta\in B\}=\omega$. Pick $\delta\in B$ such that $\sup\{ f_\beta(n)\mid \beta\in B\cap\delta\}=\omega$. Then $f_\delta(n)$ cannot be an integer.

    The post has just been corrected.


    • Nik Weaver says:

      Nice! I had a slightly different way of fixing the problem, but yours is faster. (Extend each $f_\beta$ to a piecewise linear function from $\mathbb{R}^+$ to $\mathbb{R}^+$, then look at the graphs of these functions in $\mathbb{R}^2$. The gap between the graph of each function and its successor is open, and you can’t have uncountably many disjoint open subsets of $\mathbb{R}^2$.)


      • saf says:

        btw, there is a somewhat different proof: use properties (1)–(3) of the $\mathfrak b$-scale to construct a subfamily $\mathcal F$ of $\mathcal P(\omega\times\omega)$ such that $\langle \mathcal F,\subset\rangle$ admits no uncoutnable chains or antichains. Then, prove that SOCA entails that any uncountable subposet of $\langle \mathcal P(\omega),\subset\rangle$ either contains an uncounatble chain, or an uncountable antichain.


  6. Literature says:

    I think that the discussion went deeper than it should if one is interested only in why OGA (TA) implies non-CH. However, it should be pointed out that the
    relevance of the $\mathfrak b\neq\omega_1$ proof is of twofold independent interest.
    First, it forms a part of the much deeper fact that OGA (TA) implies that $\mathfrak b=\omega_2$ (see Todorcevic’s ‘Partition Problem in Topology’ , Theorems 3.4 and 8.5 , or the proof of Theorem 8.6). Second, it shows that there exist two sets of reals of cardinality $\mathfrak b$ which are orthogonal to each other in the sense that they contain no isomorphic copy of the same linear ordering of cardinality $\mathfrak b$. Thus, $\mathfrak b=\omega_1$ also contradicts Baumgartner’s axiom.
    If you are interested in mathematically and historically more basic reasons of why OGA (TA) implies non-CH simply remember that there is a mapping from the reals into the reals which is not continuous on any set of reals of cardinality continuum or remember that under CH were is a Luzin subset of the Cantor set and consider the natural open graphs associated to these objects.


Leave a Reply

Your email address will not be published. Required fields are marked *