Dushnik-Miller for regular cardinals (part 2)

In this post, we shall provide a proof of Todorcevic’s theorem, that b=ω1 implies ω1(ω1,ω+2)2. This will show that the Erdos-Rado theorem that we discussed in an earlier post, is consistently optimal. Our exposition of Todorcevic’s theorem would be slightly more general, with the benefit of yielding another famous theorem of Todorcevic: ω1[ω1]ω12.

We commence by fixing two sequences (whose existence are basic ZFC facts):

  • Let eα:αωα<ω1 be a sequence of injections such that {eαδα<ω1} is countable for every δ<ω1;
  • Let fα:ωωα<ω1 be a sequence of strictly increasing functions, such that α<β implies that {n<ωfα(n)fβ(n)} is finite.

Denote Δ(α,β):=min{n<ωfα(n)fβ(n)}.

This post will center around the analysis of the following object: let H:[ω1]2P(ω1) be the function satisfying for all α<β<ω1: H(α,β):={δ[α,β)fβ(Δ(α,β))eβ(δ)}.

Define c:[ω1]22 and d:[ω1]2ω1 by letting for all α<β<ω1:

  • c(α,β):=1 iff α=d(α,β), where:
  • d(α,β):=min(H(α,β){β}).

Proposition 1. For every subset Bω1 of order-type ω+2, we have c[B]2{1}.
Proof. Towards a contradiction, suppose that Bω1 is of order-type ω+2 and c[B]2={1}. Let β:=max(B)α:=max(Bβ), and L:=Bα.
Fix n<ω such that fα(m)<fβ(m) whenever nm<ω. Let n:=fβ(n). Put Dβ:={δ<βeβ(δ)n}, and likewise Dα:={δ<αeα(δ)n}. Since eα and eβ are injective, each of the sets Dα,Dβ is finite, so we may find some δL which is not in DαDβ.
By c(δ,β)=1, we get that fβ(Δ(δ,β))eβ(δ)>n=fβ(n). As fβ is strictly increasing, this means that Δ(δ,β)>n. Likewise, fα(Δ(δ,α))>n=fβ(n)>fα(n), and Δ(δ,α)>n. It follows that fδ(n)=fβ(n) and fδ(n)=fα(n), contradicting the fact that fα(n)<fβ(n). ◻

For a set Aω1 and t<ωω, denote At:={αAtfα}.

Proposition 2. Every uncountable Aω1, admits an uncountable subset BA such that {|Bt|t<ωω}={0,1}.
Proof. Let B:=A{Att<ωω,|At|0}. Then B is uncountable and for every t<ωω, either Bt is empty, or Bt is uncountable. Fix α<β in B. Let

  • n:=Δ(α,β);
  • t:=fαn+1;
  • C:=BBt.

Then {|Ct|t<ωω}={0,1}. ◻

Proposition 3.  For every uncountable Aω1, the set d[A]2 contains a club.
Proof. Suppose that A is a given uncountable set. By restricting our attention to an uncountable subset, we may assume that A satisfies {|At|t<ωω}={0,1}. Denote Ct:={α<ω1sup(Atα)=α}. Then C:={Ctt<ωω,At} is the intersection of countably many clubs. Thus, it suffices to show that for every δC, there exists some α<β in A for which c(α,β)=δ.

Fix δC.
Pick βA above δ. Put n:=eβ(δ), and t:=fβn. Since βAt, the set At is non-empty, and hence uncountable, so let us pick σAt above β. Put n:=Δ(β,σ), s:=fσ(n+1), n:=fβ(n), and G={γ<δeβ(γ)n}. Note:

  • G is finite, since eβ is injective;
  • CCt, since σ witnesses that As;
  • sup(Asδ)=δ, since δCCs.

Fix αAsδ above max(G). Then:

  • fσn=t, since σAt;
  • t=fβn, and hence Δ(β,σ)n. That is, nn;
  • fα(n+1)=s, since αAs;
  • s=fσ(n+1), and hence Δ(α,σ)n+1;
  • Δ(β,σ)=n<Δ(α,σ), and hence Δ(α,β)=n;
  • fβ(Δ(α,β))=fβ(n)=nnn, since fβ is strictly increasing;
  • δH(α,β), since fβ(Δ(α,β))n=eβ(δ);
  • if γH(α,β), then neβ(γ) and γα>max(G);
  • if γ<δ and neβ(γ), then γG.

If follows that δ=min(H(α,β)). In particular, d(α,β)=δ. ◻

Proposition 4. Suppose that F={fαα<ω1} is unbounded in ωω,.
Then c[A]2{0} for every uncountable subset Aω1.
Proof. Suppose that A is a given uncountable set. As in the proof of Propositon 3, we may assume that {|At|t<ωω}={0,1}, and consider the club  C={Ctt<ωω,At}.

Fix δC. Since {fαδαA} is countable, let us find an injection e:δω and an uncountable subset AAδ for which {fαδαA}={e}. Define g:ωω+1, by letting g(n):=sup{fα(n)αA} for all n<ω. Note that ωRng(g). [For suppose that g is an element of ωω. As F is unbounded in ωω,, there exists some α<ω1 such that {n<ωg(n)<fα(n)} is infinite, but then also {n<ωg(n)<fα(n)} is infinite for α:=min(Aα), contradicting the fact that fα(n)g(n) as the definition of g dictates.]

Let n<ω be the least integer such that g(n)=ω. Fix a sequence of ordinals βii<ω} in A such that fβi(n)>i for all i<ω. By minimality of n, there exists some k<ω such that {fβini<ω}nk. Thus, let us fix some tnk for which {i<ωfβin=t} is infinite.
As β0 witnesses that At, we infer that δCt, and hence we may pick some αAtδ. Put l:=e(α), and let i be least integer greater than l for which fβin=t. Then:

  • α<δ<βi, and α,βiA.
  • Δ(fα,fβi)n, since fαn=t=fβin;
  • fβi(Δ(fα,fβi))fβi(n)>i>l=e(α), since fβi is order-preserving;
  • fβi(Δ(fα,fβi))>e(α)=eβi(α), since βiA.

It follows that αH(α,βi), and hence c(α,βi)=1. ◻.

Corollary 1 (Todorcevic, 1989). b=ω1 entails ω1(ω1,ω+2)2.
Proof. Recall that b=ω1 iff there exists a sequence fα:ωωα<ω1 which is increasing and unbounded in ωω,. ◻

Corollary 2 (Hajnal, 1960). CH entails ω1(ω1,ω+2)2.
Proof. CH implies b=ω1. ◻

Corollary 3 (Todorcevic, 1987). ω1[ω1]ω12.
Proof. Let Sδδ<ω1 be a partition of ω1 into mutually disjoint stationary sets. Define d:[ω1]2ω1, by letting d(α,β)=min{δ<ω1d(α,β)Sδ}. Then, for every uncountable Aω1, d[A]2 contains a club, and hence d[A]2=ω1. ◻

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

5 Responses to Dushnik-Miller for regular cardinals (part 2)

  1. Pingback: Rectangles vs. squares at the level of the first uncountable cardinal | Assaf Rinot

  2. Dani Soukup says:

    Hey,

    Great post, I really enjoyed reading this today! Do you know if the graph (omega1,c1(1)) is uncountably chromatic regardless of the value of the bounding number? Or is it countably chromatic if your sequence F is <*-bounded?

    Thanks!

    • saf says:

      Thanks, Dani!
      Under Martin’s Axiom, this graph is countably chromatic. Can’t tell at the moment whether the boundedness of F suffices, but I suspect that, at least, for every bounded F, there is a choice of eα:αωα<ω1, for which the corresponding graph is countably chromatic.

      p.s.
      Let me draw your attention to slide #65 (onwards) from here.

Leave a Reply

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