A hierarchy of clopen graphs on the Baire space

Arnold W. Miller Oct 2012

We say that E ⊆ X × X is a clopen graph on X iff E is symmetric and irreflexive and clopen relative to X^{2}\Δ where Δ = {(x, x) : x ∈ X} is the diagonal. Equivalently E ⊆ [X]^{2} and for all x ≠ y ∈ X there are open neighborhoods x ∈ U and y ∈ V such that either U × V ⊆ E or U × V ⊆ X^{2}\E.

For clopen graphs E_{1}, E_{2} on spaces X_{1}, X_{2}, we say that E_{1} continuously reduces to E_{2} iff there is a continuous map f : X_{1} → X_{2} such that for every x, y ∈ X_{1}

(x, y) ∈ E_{1} iff (f(x), f(y)) ∈ E_{2}.

Note that f need not be one-to-one but there should be no edges in the preimage of a point. If f is a homeomorphism to its image, then we say that E_{1} continuously embeds into E_{2}.

Theorem 1 There does not exist countably many clopen graphs on the Baire space, ω^{ω}, such that every clopen graph on ω^{ω} can be continuously reduced to one of them. However, there are ω_{1} clopen graphs on ω^{ω} such that every clopen graph on ω^{ω} continuously embeds into one of them.

Since one can take a countable clopen separated union of countably many clopen graphs on ω^{ω}, having countably many is the same as having one universal graph.

Definition 2 For R ⊆ ω^{ω} × ω^{ω}, C and D clopen subsets of ω^{ω}, and α an ordinal define

1. rank_{R}(C × D) = 0 iff C × D ⊆ R or R ∩ (C × D) = ∅

2. rank_{R}(C × D) ≤ α iff there are partitions of C and D into clopen sets: C = ⊔_{i<ω}C_{i} and D = ⊔_{j<ω}D_{j} such that rank_{R}(C_{i} × D_{j}) < α for all i, j in ω.

We use ⊔ to mean disjoint union.

Since we allow C_{i}’s and D_{j}’s to be empty, it is clear that:

Proposition 3 If rank_{R}(C × D) ≤ α and C′ ⊆ C and D′ ⊆ D, then rank_{R}(C′ × D′) ≤ α.

More generally:

Proposition 4 Suppose f : C ⊔ D → C′ ⊔ D′ is a continuous reduction of R ⊆ C × D to R′ ⊆ C′ × D′ and f^{−1}(C′) = C and f^{−1}(D′) = D. Then

rank_{R}(C × D) ≤ rank_{R′}(C′ × D′).

Proof Since f is continuous, clopen partitions C′ = ⊔C′_{i} and D′ = ⊔D′_{j} induce clopen partitions C = ⊔_{i}f^{−1}(C′_{i}) and D = ⊔_{j}f^{−1}(D′_{j}). QED

Definition 5 For E a clopen graph on ω^{ω} define

rank(E) = sup{rank_{E}(C × D) : C and D are disjoint clopen sets}.

Lemma 6 If E is a clopen graph on ω^{ω}, then rank(E) < ω_{1}.

Proof Given incomparable s_{0}, t_{0} ∈ ω^{<ω} with the same length look at the tree T:

(s, t) ∈ T iff

1. s_{0} ⊆ s, t_{0} ⊆ t, |s| = |t|, and

2. both ([s] × [t]) ∩ E and ([s] × [t]) \E are nonempty.

Let

T^{∗} = {(s_{0}, t_{0})} ∪ {(sˆ ⟨i⟩, tˆ ⟨j⟩) : (s, t) ∈ T and i, j ∈ ω}.

Since E ∩ ([s_{0}] × [t_{0}]) is clopen, T^{∗} is well-founded and T^{∗}\T is the set of the terminal nodes of T^{∗}. Let r be the standard rank function on T^{∗}, i.e.,

• r(s, t) = 0 iff (s, t) ∈ T^{∗}\T

• r(s, t) = sup{r(sˆ ⟨i⟩, tˆ ⟨j⟩) + 1 : i, j ∈ ω} if (s, t) ∈ T.

Note that rank_{E}([s] × [t]) ≤ r(s, t) for (s, t) ∈ T^{∗}. Take any countable ordinal α such that for every s ∈ ω^{<ω} and distinct i, j ∈ ω we have that rank_{E}([sˆ ⟨i⟩] × [sˆ ⟨j⟩]) ≤ α.

For any s, t ∈ ω^{<ω} which are incomparable, let n be the least such that s ↾ n ≠ t ↾ n. Then [s] ⊆ [s ↾ n] and [t] ⊆ [t ↾ n] and so by Proposition 3, rank_{E}([s] × [t]) ≤ α. But any nonempty open set U can be written as pairwise disjoint basic clopen sets, i.e., U = ⊔_{i<ω}[s_{i}] where s_{i} ∈ ω^{<ω}. (To see this just take for any x ∈ U the least n with [x ↾ n] ⊆ U.) Hence for any disjoint clopen sets C, D we have that rank_{E}(C × D) ≤ α + 1. And so rank(E) ≤ α + 1. QED

Lemma 7 For any α < ω_{1} there exists a clopen graph E_{α} on ω^{ω} such that if E is any clopen graph on the Baire space such that E_{α} is continuously reducible to E, then rank(E) ≥ α.

Proof Let Q = {in, out} and α any countable limit ordinal. Put Γ_{α} = ω × (Q ∪ α) with the discrete topology and define a clopen relation R_{α} ⊆ ω^{ω} × Γ_{α}^{ω} as follows. Given x ∈ ω^{ω} and y ∈ Γ_{α}^{ω} construct sequences m_{i}, n_{i} ∈ ω and α_{i} ∈ α ∪ Q as follows.

• x(0) = m_{0} and y(m_{0}) = (n_{0}, α_{0})

• x(n_{i−1}) = m_{i} and y(m_{i}) = (n_{i}, α_{i}) for i ≥ 1.

To determine whether or not (x, y) ∈ R_{α} look at the first i such that either α_{i} ∈ Q or (i > 0 and α_{i} ∈ α but not α_{i} < α_{i−1}). Note that such an i must always occur since otherwise we would get an infinite descending sequence of ordinals. Let i_{0} be the first such i and put (x, y) ∈ R_{α} iff α_{i_{0}} = in.

Note that R_{α} is clopen since given any x, y ∈ ω^{ω} we can choose N sufficiently large so that every pair in [x ↾ N] × [y ↾ N] will terminate the same way (x, y) did.

Claim 7.1. Suppose s ∈ ω^{<ω} and t ∈ Γ_{α}^{<ω} have the property that we can define the sequences m_{i} and (n_{i}, α_{i}) for i < N using the same prescription as above:

1. s(0) = m_{0} and t(m_{0}) = (n_{0}, α_{0}), 2. s(n_{i−1}) = m_{i} and t(m_{i}) = (n_{i}, α_{i}) for 1 ≤ i < N,

3. α_{0} > α_{1} > ⋯ > α_{N−1} are all ordinals, and

4. s(n_{N−1}) = m_{N},

5. however m_{N} ≥ |t| so we have not yet determined α_{N}.

Then rank_{R_{α}}([s] × [t]) ≥ α_{N−1}.

Proof Suppose that α_{N−1} is the least ordinal for which this could be false (for any s, t, N) and let rank_{R_{α}}([s] × [t]) = β < α_{N−1}. It is easy to check that if α_{N−1} > 0 then β cannot be zero since we may find extensions t_{in}, t_{out} of t with t_{in}(m_{N}) = (·, in) and t_{out}(m_{N}) = (·, out).

Let [s] = ⊔_{i}C_{i} and [t] = ⊔_{j}D_{j} be clopen partitions with rank_{R_{α}}(C_{i}×D_{j}) < β for all i, j. Extend s ⊆ s′ so that [s′] ⊆ C_{i} for some i. Extend t to t′ so that t′(m_{N}) = (|s′|, β) =^{def} (n_{N}, α_{N}) and [t′] ⊆ D_{j} for some j. Finally extend s′ by putting s′′ = s′ˆ ⟨|t′|⟩ so s′′(α_{N}) = m_{N} = |t′|. Now we are in the same situation as before except α_{N} = β is now defined. But

rank_{R_{α}}([s′′] × [t′]) ≤ rank_{R_{α}}(C_{i} × D_{j}) < β = α_{N}.

This violates the minimality of α_{N−1} and so proves the Claim. QED

Now for any limit ordinal α and β < α let |s| = 2 and |t| = 1 be defined by s(0) = 0, s(1) = 1 and t(0) = (1, β). By the claim rank_{R_{α}}([s] × [t]) ≥ β and since these exist for every β < α, it follows that rank(R_{α}) ≥ α.

Now we adjust R_{α} to make its domain and range disjoint. Identify Γ_{α} with ω and define S_{α} = {(0ˆ ⟨x⟩, 1ˆ ⟨y⟩) : (x, y) ∈ R_{α}}. Then S_{α} ⊆ C × D where C = [⟨0⟩] and D = [⟨1⟩] are disjoint clopen sets. Clearly rank(S_{α}) ≥ α as it is a copy of R_{α}. Let C_{1} and D_{1} be nonempty clopen sets such that C ⊔ C_{1} ⊔ D ⊔ D_{1} = ω^{ω}. Let

P_{α} = S_{α} ∪ (C_{1} × D) ∪ (C × D_{1})

Since P_{α} ∩ (C × D) = S_{α} we know rank(P_{α}) ≥ α. If we let A = C ∪ C_{1} and B = D ∪ D_{1} then A and B are complementary clopen sets with P_{α} ⊆ A × B and for every x ∈ A there is a y ∈ B with (x, y) ∈ P_{α} and for every y ∈ B there is an x ∈ A with (x, y) ∈ P_{α}. (This property that everything is connected to something else might have already been true of R_{α} but if not, in this step we have added it.)

Finally we define the clopen graph E_{α}. We put

(x, y) ∈ E_{α} iff (x, y) ∈ P_{α} or (y, x) ∈ P_{α}.

Then E_{α} is a true clopen graph, i.e., E_{α} is a clopen relation in (ω^{ω})^{2} which is symmetric and irreflexive. Also ω^{ω} = A ⊔ B where every element ω^{ω} is connected to something else, but neither A nor B contain two elements which are connected.

Claim 7.2. Suppose α a countable limit ordinal and there is a continuous reduction of E_{α} to a clopen graph E. Then rank(E) ≥ α. Proof Let f : ω^{ω} → ω^{ω} be a continuous reduction and suppose for contraction that rank(E) = β < α. Then in particular for every (x, y) ∈ A × B

(x, y) ∈ P_{α} iff (f(x), f(y)) ∈ E.

Let A′ = f(A) and B′ = f(B) We show that not only are these sets disjoint but they have a stronger separation property.

For every z ∈ A′ ∪ B′ there exists some n such that f^{−1}([z ↾ n]) ⊆ A or f^{−1}([z ↾ n]) ⊆ B. To see why let z = f(x) for some x ∈ A. By our construction of P_{α} there is a y ∈ B with (x, y) ∈ P_{α}. By the reduction (f(x), f(y)) ∈ E and since E is clopen [f(x) ↾ n] × [f(y) ↾ n] ⊆ E for some n. So if f(u) ∈ [f(x) ↾ n] then (f(u), f(y)) ∈ E and so (u, y) ∈ P_{α}. But this implies u ∈ A since y ∈ B.

Now define Σ ⊆ ω^{<ω} by

Σ = {s ∈ ω^{<ω} : f^{−1}[s] ⊆ A or f^{−1}[s] ⊆ B}

and let

Σ_{0} = {s ∈ Σ : ∀t ∈ Σ t ⊆ s → t = s}.

Note that the elements of Σ_{0} are pairwise incomparable and that

A = ⊔_{s∈Σ_{0}}{f^{−1}[s] : f^{−1}[s] ⊆ A}

and

B = ⊔_{t∈Σ_{0}}{f^{−1}[t] : f^{−1}[t] ⊆ B}

are clopen partitions of A and B. Since rank(E) ≤ β for any distinct s, t ∈ Σ_{0} we have that rank_{E}([s] × [t]) ≤ β. By Proposition 4 we get that rank(P_{α}) ≤ β + 1 < α, which is a contradiction. This proves Lemma 7.

QED

Lemma 8 There exists U_{α} for α < ω_{1} clopen graphs on ω^{ω} such that for every clopen graph E on ω^{ω} there exists α < ω_{1} such that E continuously embeds into U_{α}.

Proof

For any s ∈ ω^{<ω} except the trivial sequence ⟨⟩ let s^{∗} be the parent of s, i.e., the unique s^{∗} ⊆ s and |s^{∗}| = |s| − 1.

Let α be a countable ordinal, Q = {in, out} (or more generally any countable set). A pair (T, l) is an α-tree iff T is a subtree of ω^{<ω} and l : D → α∪Q where D = {{s, t} ∈ [T]^{2} : |s| = |t| and s ≠ t} and l satisfies:

if (s, t) ∈ D and s^{∗} ≠ t^{∗} then

1. if l(s^{∗}, t^{∗}) ∈ α then l(s, t) < l(s^{∗}, t^{∗}) or l(s, t) ∈ Q

2. if l(s^{∗}, t^{∗}) ∈ Q then l(s, t) = l(s^{∗}, t^{∗}).

Note that l is only defined on pairs with s ≠ t of the same length. Also if s^{∗} = t^{∗}, then l(s, t) can be anything in α ∪ Q. A compact way of stating the above two conditions would be by taking the binary relation ◁ on α ∪ Q defined by x ◁ y iff

1. x, y ∈ α and x < y,

2. x ∈ Q and y ∈ α, or

3. x, y ∈ Q and x = y.

Then our condition on l is equivalent to:

if (s, t) ∈ D and s^{∗} ≠ t^{∗} then l(s, t) ◁ l(s^{∗}, t^{∗}).

Given any clopen graph E we describe the canonical α-tree (ω^{<ω}, l) associated with it. For any distinct s, t of the same length if [s] × [t] ⊆ E, then put l(s, t) = in, if ([s] × [t]) ∩ E = ∅, then put l(s, t) = out.

Let P = {(s, t) : l(s, t) ∈ Q} and note that P is closed downward. For any s and distinct i, j ∈ ω the tree

T_{s,i,j} = {(t_{1}, t_{2}) : sˆ ⟨i⟩ ⊆ t_{1}, sˆ ⟨j⟩ ⊆ t_{2}, |t_{1}| = |t_{2}|, and (t_{1}, t_{2}) ∉ P }

is a well-founded tree because E is clopen. Let l ↾ T_{s,i,j} be its rank function. Picking α large enough makes (ω^{<ω}, l) an α-tree.

Next we construct a universal α-tree (ω^{<ω}, L). It will be very strongly universal in the following sense: Suppose that (T, l) is any α-tree. Then there will exists σ : ω^{<ω} → ω^{<ω} which is tree embedding, i.e,

1. σ is one-to-one and level preserving, i.e., |σ(s)| = |s|

2. σ preserves the tree ordering, i.e., s ⊆ t implies σ(s) ⊆ σ(t)

3. σ preserves the labeling on edges, i.e., l(s, t) = L(σ(s), σ(t)) for any distinct s, t of the same length.

It easy to see that σ induces a continuous embedding f : [T] → ω^{ω} by f(x) = ⋃_{n<ω} σ(x ↾ n) which reduces the graph associated to l to the one associated with L.

We construct L to have the following property:

For any n < ω, p ∈ ω^{n}, finite F ⊆ ω^{n+1}, and f : F → α ∪ Q consistent with L, there will be infinitely many t ∈ ω^{n+1} with t^{∗} = p such that L(t, s) = f(s) for all s ∈ F. By f consistent with L we mean: for all s ∈ F if s^{∗} ≠ p, then f(s) ◁ L(p, s^{∗}).

First let us check that it is possible to construct L with this property. Let (p_{n}, F_{n}, f_{n}) list with infinitely many repetitions all triples (p, F, f) with p ∈ ω^{<ω}, F ⊆ T ∩ ω^{k+1} where |p| = k, and f : F → α ∪ Q arbitrary. Construct (T_{n}, L_{n}) an α-tree with T_{n} finite, T_{n} ⊆ T_{n+1} and L_{n} ⊆ L_{n+1} and if p_{n} ∈ T_{n}, F_{n} ⊆ T_{n}, and f_{n} consistent with L_{n}, then there exists t ∈ T_{n+1}\T_{n} with p_{n} = t^{∗} such that L_{n+1}(s, t) = f_{n}(s) for all s ∈ F_{n}. This can be done as follows: choose any t ∉ T_{n} with t^{∗} = p_{n}. For s ∈ F_{n} define L_{n+1}(s, t) = f_{n}(s). For all other s ∈ T_{n} with |s| = |t| and s^{∗} ≠ t^{∗} put L_{n+1}(s, t) = q for any q ∈ Q with q ◁ L_{n}(s^{∗}, t^{∗}).

Second let us check that this property is all that is needed for universality. Write any α-tree as an increasing union of finite subtrees T_{n} gotten by adding one new child to some node from T_{n}, i.e., T_{n+1} = T_{n} ∪{r_{n}} where r_{n}^{∗} ∈ T_{n} but r_{n} ∉ T_{n}. The map σ is constructed by extending σ ↾ T_{n} to T_{n+1} by defining σ at r_{n}. Without all the subscripts one step looks like this:

Suppose (T, l) is a finite α-tree and r ∈ T has no child and let T_{0} = T \{r}. Suppose that σ : T_{0} → ω^{<ω} is a tree embedding of (T_{0}, l ↾ [T_{0}]^{2}) into (ω^{<ω}, L).

Suppose |r| = n, F = σ(T_{0}) ∩ ω^{n}, p = σ(r^{∗}), and f : F → α ∪ Q is defined by f(σ(s)) = l(r, s). By our property there are infinitely many t such that we can extend σ to T by defining σ(r) = t. This proves the Lemma.^{1} QED

Theorem 1 follows immediately from the three Lemmas.

Remarks

Theorem 1 settles a question of Stefan Geschke [1]. It was motivated by his result that the smallest cardinality of a family of clopen graphs on the Cantor space, 2^{ω}, such that every such graph can be continuously embedded into some member of the family is exactly 𝔡, the dominating number. Geschke also showed that there is a clopen graph on ω^{ω} universal for all clopen graphs on 2^{ω}.

The family of U_{α} in Lemma 8 are also universal for all clopen graphs on closed subsets of ω^{ω} and hence for all clopen graphs on zero dimensional Polish spaces.

Recall that a clopen graph E on X is true clopen iff E ⊆ X^{2} is symmetric irreflexive and clopen in X^{2} - not just clopen in X^{2}\Δ. The proof of Lemma 7 shows that in fact there is no clopen graph on ω^{ω} which is universal for all true clopen graphs on ω^{ω}. Note that if E_{1} is continuously reducible to E_{2} and E_{2} is true clopen, then E_{1} is true clopen. Also if E is true clopen, then there exists a clopen partition ω^{ω} = ⊔_{i<ω}C_{i} such that C_{i}^{2} ∩ E = ∅ for each i < ω. Using this we can vary the proof of Lemma 8 to produce true clopen U′_{α} for α < ω_{1} such that every true clopen graph continuously embeds into one of them. Construct a α-universal tree L′ similar to L but satisfying: if s, t are distinct, |s| = |t| = n > 1, and s(0) = t(0), then L′(s, t) = out. Hence we are thinking of replacing C_{i} with [⟨i⟩].

In the case of unary predicates continuous reducibility is called Wadge reducibility, i.e., for A, B ⊆ ω^{ω} define A ≤_{W} B iff there exists a continuous f : ω^{ω} → ω^{ω} such that x ∈ A iff f(x) ∈ B. For a generalization of Wadge reducibility to Borel labellings in a better-quasi-order see van Engelen, Miller, and Steel [3]. Louveau and Saint-Raymond [2] contains some results about the quasi-order of Borel linear orders under embeddability. Even for finite graphs the n-cycles are pairwise incomparable under graph embedding, so we don’t get a well-quasi-order. However there are weaker notions of reducibility under which finite graphs are well-quasi-ordered, see Robertson and Dale [4]. Perhaps there is a natural notion of reducibility for clopen graphs that gives a well-quasi-ordering.

1This type of argument is familiar to model theorists who would refer to it as joint embedding, amalgamation, and universal Fraisse structure. Set theorists would say its like Cantor’s proof that every countable linear order embeds into the rationals.

References

[1] Geschke, Stefan; Clopen graphs, eprint 2012

    http://www.hcm.uni-bonn.de/fileadmin/geschke/papers/MoreOnPaircolorings9.pdf

[2] Louveau, Alain; Saint-Raymond, Jean; On the quasi-ordering of Borel linear orders under embeddability. J. Symbolic Logic 55 (1990), no. 2, 537-560.

    http://dx.doi.org/10.2307/2274645

[3] van Engelen, Fons; Miller, Arnold W.; Steel, John; Rigid Borel sets and better quasi-order theory. Logic and combinatorics (Arcata, Calif., 1985), 199-222, Contemp. Math., 65, Amer. Math. Soc., Providence, RI, 1987.

    http://www.math.wisc.edu/~miller/res/rigid.pdf

[4] Robertson, Neil; Seymour, P. D.; Graph minors. XX. Wagner’s conjecture. J. Combin. Theory Ser. B 92 (2004), no. 2, 325-357.

    http://www.sciencedirect.com/science/article/pii/S0095895604000784

Arnold W. Miller miller@math.wisc.edu http://www.math.wisc.edu/∼miller University of Wisconsin-Madison Department of Mathematics, Van Vleck Hall 480 Lincoln Drive Madison, Wisconsin 53706-1388