Open coloring and the cardinal invariant $\mathfrak b$

Open coloring and the cardinal invariant

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^{'}} ∣ 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 = ⋃_{n < ω} Y_{n}$ such that $[Y_{n}]^{2} \subseteq K_{1}$ for all $n < ω$ .

Lemma. If $2^{ℵ_{0}} = ℵ_{1}$ , then $b = ℵ_{1}$ , i.e., there exists a sequence $\vec{f} = ⟨ f_{α} ∣ α < ω_{1} ⟩$ such that:

$f_{α} \in^{ω} ω$ is an increasing function for all $α < ω_{1}$ ;
${n < ω ∣ f_{α} (n) \geq f_{β} (n)}$ is finite, whenever $α < β < ω_{1}$ ;
for every $g \in^{ω} ω$ , there exists some $α < ω_{1}$ such that ${n < ω ∣ g (n) < f_{β} (n)}$ is infinite, whenever $α < β < ω_{1}$ .

Proof. Since $2^{ℵ_{0}} = ℵ_{1}$ , we can list $^{ω} ω$ , as $⟨ g_{α} ∣ α < ω_{1} ⟩$ . We then construct $⟨ f_{α} ∣ α < ω_{1} ⟩$ by recursion on $α < ω_{1}$ . Suppose that $⟨ f_{β} ∣ β < α ⟩$ has already been constructed. Let ${h_{n} ∣ n < ω}$ be some enumeration of ${f_{β} ∣ β < α} \cup {g_{α}}$ . Define $f_{α}$ by letting $f_{α} (n) := 1 + \sum_{i = 0}^{n} \sum_{j = 0}^{n} h_{i} (j)$ for all $n < ω$ .

Theorem (Todorcevic). Todorcevic’s axiom implies that $b > ℵ_{1}$ .
Proof. Assume TA. Towards a contradiction, suppose that $⟨ f_{α} ∣ α < ω_{1} ⟩$ satisfies the above items (1)–(3). Consider $X := {f_{α} ∣ α < ω_{1}}$ as a subspace of the Baire space $^{ω} ω$ . Let $K_{1} := [X]^{2} ∖ K_{0}$ , where $K_{0} := {{f, g} ∣ \exists i, j < ω 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 = ⋃_{n < ω} Y_{n}$ such that $[Y_{n}]^{2} \subseteq K_{1}$ for all $n < ω$ :
In particular, we may fix an uncountable subset $Y \subseteq X$ with $[Y]^{2} \subseteq K_{1}$ . Then, for every $α < β$ such that $f_{α}, f_{β} \in Y$ , we have that ${n < ω ∣ f_{α} (n) > f_{β} (n)}$ is empty. Write $B := {β < ω_{1} ∣ f_{β} \in Y}$ . Notice that if $sup_{β \in B} f_{β} (n)$ is finite for all $n < ω$ , then we get a contradiction to item (3), hence, we may fix some $m < ω$ such that $sup {f_{β} (m) ∣ β \in B} = ω$ . Pick a large enough $δ \in B$ such that $sup {f_{β} (m) ∣ β \in B \cap δ} = ω$ . Then $f_{δ} (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 $α < β$ such that $f_{α}, f_{β} \in Y$ , we have that ${n < ω ∣ f_{α} (n) \geq f_{β} (n)}$ is nonempty. Write $B := {β < ω_{1} ∣ f_{β} \in Y}$ . Then, for all $α < β$ in $B$ , we have $Δ (α, β) > 0$ , where $Δ (α, β) := min {m < ω ∣ m \leq n < ω \to (f_{α} (n) \leq f_{β} (n))} .$

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

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

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

if $i < m$ , then $f_{α} (i) = t (i) = f_{β} (i)$ ;
if $m \leq i \leq k + n$ , then $f_{α} (i) \leq f_{α} (k + n) < f_{β} (m) \leq f_{β} (i)$ (recall that the elements of $\vec{f}$ are increasing functions!);
if $k + n < i < ω$ , then $Δ (α, δ) = k < i$ and $f_{α} (i) \leq f_{δ} (i)$ , as well as $Δ (δ, β) = n < i$ and $f_{δ} (i) \leq f_{β} (i)$ . Altogether, $f_{α} (i) \leq f_{β} (i)$ . End of subclaim

This complete the proof.

Ari B. pointed out (see his comment bel0w) that the proof shows that the axiom SOCA already implies that $b > ω_{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 b-scale, OCA. Bookmark the permalink.

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

Ari B. says:

October 9, 2013 at 3:06 am

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 $b > ℵ_{1}$ and therefore contradicts CH.

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

- saf says:
  
  October 9, 2013 at 3:17 am
  
  Thanks. I fixed this, and added your remark about SOCA.
  
  - Ari B. says:
    
    October 9, 2013 at 3:25 am
    
    Thanks. But now your paragraphs “Alternative 1” and “…2” in the proof don’t match the alternatives in the statement.
    
    - saf says:
      
      October 9, 2013 at 3:30 am
      
      Thanks. Perfected:)
      
Dani says:

October 9, 2013 at 4:28 am

– We might simplify your proof if we note that since $f_{α}$ 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 $ℵ_{1}$ such pairs of functions, there must be some $n < ω$ that is the witness for $ℵ_{1}$ decreasinesses-pairs. Looking only at this coordinate, since a decreasing serie of $f_{α} (n)$ can only be finite, we get a contradication to the fact that we have $ℵ_{1}$ witnesses.

- saf says:
  
  October 9, 2013 at 4:35 am
  
  But it sounds like you are invoking a pigenhole principle for pairs at the level of $ω_{1}$ — a no-go when it comes to successor cardinals.
  
Dani says:

October 9, 2013 at 3:09 am

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?

- saf says:
  
  October 9, 2013 at 3:16 am
  
  You are right! I will now correct this.
  
Nik Weaver says:

October 9, 2013 at 8:15 am

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 $t o$ $\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 < ω ∣ f_{α} (n) > f_{β} (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?

saf says:

October 9, 2013 at 9:10 am

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 < ω$ such that $sup {f_{β} (n) ∣ β \in B} = ω$ . Pick $δ \in B$ such that $s u p f_{β} (n) ∣ β \in B \cap δ = ω$ . Then $f_{δ} (n)$ cannot be an integer.

The post has just been corrected.

- Nik Weaver says:
  
  October 9, 2013 at 9:34 am
  
  Nice! I had a slightly different way of fixing the problem, but yours is faster. (Extend each $f_{β}$ to a piecewise linear function from $R^{+}$ to $R^{+}$ , then look at the graphs of these functions in $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 $R^{2}$ .)
  
  - saf says:
    
    October 9, 2013 at 12:23 pm
    
    btw, there is a somewhat different proof: use properties (1)–(3) of the $b$ -scale to construct a subfamily $F$ of $P (ω \times ω)$ such that $⟨ F, \subset ⟩$ admits no uncoutnable chains or antichains. Then, prove that SOCA entails that any uncountable subposet of $⟨ P (ω), \subset ⟩$ either contains an uncounatble chain, or an uncountable antichain.
    
Literature says:

November 28, 2015 at 12:17 am

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 $b \neq ω_{1}$ proof is of twofold independent interest.
First, it forms a part of the much deeper fact that OGA (TA) implies that $b = ω_{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 $b$ which are orthogonal to each other in the sense that they contain no isomorphic copy of the same linear ordering of cardinality $b$ . Thus, $b = ω_{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.

Open coloring and the cardinal invariant $b$

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

Leave a Reply Cancel reply

Archives

Keywords

Set Theory Colloquium

Friends’ Blogs

Recent Comments

Open coloring and the cardinal invariant b

13 Responses to Open coloring and the cardinal invariant b

Leave a Reply Cancel reply

Archives

Keywords

Open coloring and the cardinal invariant $b$

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