Relating subsets of a poset, and a partition theorem for WQOs

Reinhard Diestel

We point out some basic properties of the partial ordering which a poset P induces on its power set, defining A ⩽ B to mean that every element of A lies below some element of B. One result is that if P is a WQO then P decomposes uniquely into finitely many indivisible sets A_{1}, …, A_{n} (that are essential parts of P in the sense that P ⩽̸ P ∖ A_{i}).

This note collects together some observations I made in the context of comparing graph properties by the graph minor relation [ 2 ], but which apply more generally to arbitrary subsets of a given poset. They are all simple and ought to be well known, but I have been unable to find a source. The main observation is that the subsets of an infinite poset P can be decomposed in a way that resembles factoring: there are ‘indivisible’ sets that behave like primes, and if P is a WQO then it factors uniquely into such indivisible sets.

Let (P, ⩽) be any poset, typically infinite. (Countable will do to make things intersting, and a particularly interesting case will be that P is a WQO.) Given subsets A, B ⊆ P, let us write A ⩽ B to express that for every a ^{∈} A there is a b ^{∈} B such that a ⩽ b. This is a quasi-ordering on the power set of P, which induces a partial ordering on the set P of ∼-equivalence classes of subsets of P, where A ∼ B if A ⩽ B and B ⩽ A. Although we shall continue to speak about the subsets themselves rather their equivalence classes, we shall often distinguish them only up to equivalence to derive properties of this poset P. For A, B ⊆ P we write A < B if A ⩽ B but A ≁ B (ie. B ⩽̸ A).

The first problem we address is whether we can always find particularly typical representatives of these equivalence classes, in the following sense. Given an infinite set A ⊆ P, we can obtain numerous equivalent sets just by ‘adding junk’: for every A′ < A we clearly have A ∪ A′ ∼ A. This process is not easily reversible: if we are given A ∪ A′ as a single set, we may not be able to identify and discard its ‘inessential’ part A′. So it seems that ‘lean’ sets not containing large amounts of such junk are particularly desirable representatives of their equivalence classes.

To make this precise, let us call an infinite set A ⊆ P lean if A ⩽ A′ for every A′ ⊆ A with |A′| = |A|. (For example, the set of finite stars and the set of finite paths are both lean under the minor relation for graphs, but the set of finite trees is not lean.) Then our first question is: which infinite sets A ⊆ P are equivalent to some lean set A′ ⊆ P, possibly with A′ ⊆ A?

Clearly some are not: the union U of the set of finite stars and the set of finite paths, for instance, is not equivalent to any lean set of finite graphs. The reason is that U splits naturally into its two constituent subsets of stars and paths—which are incomparable under ⩽ and hence cannot be equivalent to all of U. One of our aims below will be to show that, for countable sets A, such splitting is the only possible obstruction to the existence of an equivalent lean set. So let us make this splitting precise.

Let A be any subset of P. We call A′ ⊆ A small in A if A′ < A (ie. if A ⩽̸ A′), and large in A if A ⩽ A′. The complements of small sets we call ‘essential’; thus, A′ ⊆ A is essential in A if A ⩽̸ A ∖ A′, or equivalently if A′ ⩽̸ A ∖ A′. Note that subsets of a small subset of A are also small in A (and hence supersets of large or essential sets are again large or essential, respectively), and that an essential subset A′ of A is also essential in every set A′′ with A′ ⊆ A′′ ⊆ A.

If A is the union of two small subsets A_{1}, A_{2} ⊆ A, we call A divisible. Replacing A_{2} by A_{2} ∖ A_{1} if necessary we can always ensure that these small subsets are disjoint; we then say that A splits into these two subsets.

The small subsets of an indivisible set A form a set-theoretic ideal: their finite unions (as well as their subsets) are again small in A. This follows from the following factoring lemma, in which the indivisible sets appear as primes:

Lemma 1. If A is indivisible and A ⩽ B_{1} ∪ B_{2}, then A ⩽ B_{1} or A ⩽ B_{2}.

Proof. For i = 1, 2 put A_{i} := { a ^{∈} A | ∃ b ^{∈} B_{i}: a ⩽ b }. Our assumption of A ⩽ B_{1} ∪ B_{2} implies that A = A_{1} ∪ A_{2}. So as A is indivisible the A_{i} cannot both be small, ie. one of them satisfies A ⩽ A_{i} ⩽ B_{i}. □

Lemma 1 implies that, unlike leanness, divisibility and indivisibility are invariant under equivalence:

Corollary 2. If A is indivisible and A ∼ B then B is indivisible.

Proof. If B = B_{1} ∪ B_{2} then B ⩽ A ⩽ B_{i} for some i ^{∈} { 1, 2 } by Lemma 1, so B_{i} is not small. □

Since lean sets are indivisible, Corollary 2 implies that only indivisible sets can be equivalent to lean sets. But is every infinite indivisible set equivalent to some lean set, perhaps even a lean subset? In general, this looks like a difficult problem: the naive approach of recursively splitting small subsets off a given indivisible set ‘until it becomes lean’ is obviously fraught with problems; for example, it may happen that after any finite number of steps one still has a non-lean indivisible set but after ω steps the entire set has disappeared.

For countable sets, however, there is a very simple characterization of divisibility which essentially implies a positive answer to the above question:

Proposition 3. For every countable set A ⊆ P the following statements are equivalent:

(i) A is indivisible; (ii) A has an equivalent lean subset or a greatest element; (iii) A contains a chain C such that A ⩽ C; (iv) every two elements of A have a common upper bound in A.

Proof. (i)→(iv) Suppose a_{1}, a_{2} ^{∈} A have no commen upper bound in A. Then the sets A_{1} := { a ^{∈} A | a_{1} ⩽̸ a } and A_{2} := { a ^{∈} A | a_{2} ⩽̸ a } are small in A but have union A, so A is divisible.

(iv)→(iii) Enumerate A as { a_{1}, a_{2}, … } and use (iv) to construct the desired chain c_{1} ⩽ c_{2} ⩽ … inductively, choosing each c_{n} above (⩾) both a_{n} and c_{n−1}.

(iii)→(ii) If C has a maximal element, then this is the greatest element of A. If not, then C has a cofinal subchain of order type ω. This subchain is lean and equivalent to C, and hence also to A.

(ii)→(i) If A has a greatest element x then a subset of A is large if and only if it contains x. So A cannot split into two small subsets (which would also be large). If A is equivalent to a lean (and thus indivisible) set, then A is indivisible by Corollary 2. □

What about uncountable sets A? As it turns out, the equivalence of (i) and (iv) above remains valid, but these conditions no longer imply (ii) and (iii):

Proposition 4. An arbitrary set A ⊆ P is indivisible if and only if every two elements of A have a common upper bound in A.

Proof. The forward implication was shown in the proof of Propositions 3, which made no use of countability in this part. For the converse, let A = A_{1} ∪A_{2} and assume that A_{1} is small; we show that A_{2} is large, ie. that A ⩽ A_{2}.

Since A ⩽̸ A_{1}, there exists an x ^{∈} A such that A_{1} fails to meet the upclosure ⌊x⌋ = { a ^{∈} A | x ⩽ a } of x in A. So ⌊x⌋ ⊆ A_{2}. By assumption, there exists for every a ^{∈} A some b ^{∈} A such that a, x ⩽ b, ie. with b ^{∈} ⌊x⌋ ⊆ A_{2}. So A ⩽ A_{2} as desired. □

Here is an example of an uncountable poset P that is indivisible but fails (for A = P) to satisfy (ii) and (iii) of Proposition 3. We construct P recursively in ω steps, starting with a set of ℵ_{1} minimal elements. At each step, we add one element z above every pair x, y of elements from previous steps, leaving z unrelated to all the other elements.

By construction, any two elements of P have a common upper bound in P, so by Proposition 4 the set P is indivisible. On the other hand, every downset ⌈x⌉ is finite, and so any chain C in P (which is clearly countable) has a countable down-closure and thus fails to satisfy P ⩽ C as required in (iii). For the same reason, any A ⊆ P equivalent to P must be uncountable. Then A meets one of the ω levels of P in an uncountable subset A′. Thus |A′| = |A| = ℵ_{1} but P ⩽̸ A′, and hence A ⩽̸ A′ as A ∼ P. Therefore A is not lean, showing that P is a counterexample to (ii).

Let us now leave the subject of equivalent lean sets or subsets, and take a closer look at divisible and indivisible sets A for their own sake. Since now all that matters is the structure of A, we lose nothing by just considering the divisibility of P itself.

Lemma 1 suggests that the analogy to factoring which the word ‘divisibility’ suggests may be deeper than one would at first expect. And indeed, we have the following pretty ‘prime factor theorem’ for WQOs:

Theorem 5. If P is a WQO, then P can be partitioned into finitely many indivisible essential subsets A_{1}, …, A_{n}. This partition is unique up to equivalence; in fact, every indivisible essential subset of P is equivalent to one of the A_{i}.

For the proof we need as a lemma the forward implication of the following observation relating the ordering on P to that on its power set. Again, I expect this lemma to be folklore among WQO specialists but include the proof for completeness.

Lemma 6. P is a WQO if and only if all chains A_{1} > A_{2} > … of subsets of P are finite.

Proof. For the forward implication, let A_{1} > A_{2} > … be a strictly descending chain of subsets of P. Since A_{1} ⩽̸ A_{2}, there is an a_{1} ^{∈} A_{1} such that a_{1} ⩽̸ a for all a ^{∈} A_{2}. Then a_{1} ⩽̸ a even for all a ^{∈} A_{i} with i ⩾ 2, because A_{i} ⩽ A_{2}. Similarly, A_{2} has an element a_{2} ⩽̸ a for all a ^{∈} A_{i} with i ⩾ 3, and so on. We thus obtain a sequence a_{1}, a_{2}, … with a_{i} ^{∈} A_{i} for each i and such that a_{i} ⩽̸ a_{j} whenever i < j. As P is a WQO every such sequence is finite, and hence so is our chain A_{1} > A_{2} > ….

Conversely, if P is not a WQO it contains a is a bad sequence a_{1}, a_{2}, …: an infinite sequence such that a_{i} ⩽̸ a_{j} for all i < j. Then the tails { a_{i}, a_{i+1}, … } of this sequence form an infinite strictly descending chain of subsets of P. □

Proof of Theorem 5. Let us begin by constructing some sets A_{1}^{∗}, …, A_{n}^{∗} similar to the desired partition sets A_{1}, …, A_{n}. We do this recursively in finitely many steps, at each step modifying a finite list L of subsets of P until no further modifications are possible. We start with the one-element list L = { P }. At each step of the construction, we first check whether any element of L is inessential in ⋃ L; if so, we delete it from the list and proceed to the next step. If not, we try to find a divisible element of L. If none exists, we terminate the construction. If some A ^{∈} L is divisible, we split it into disjoint small subsets A′ and A′′ to replace A in L, and proceed to the next step.

If this construction continues indefinitely, then by König’s infinity lemma [ 1 ] there is an infinite chain C_{1} > C_{2} > … of subsets of P (each chosen as a small subset of the previous), which by Lemma 6 cannot exist. So the construction terminates after finitely many steps, with a list L^{∗} = { A_{1}^{∗}, …, A_{n}^{∗} } of disjoint indivisible subsets of P that are essential in P^{∗} := ⋃ L^{∗}. Since every construction step (in particular, the deletion of inessential subsets) preserves the initial property of L that P ⩽ ⋃ L, we have P ⩽ P^{∗}. We can therefore find a partition A_{1} ∪ … ∪ A_{n} of P such that

A_{i} ⩽ A_{i}^{∗} ⊆ A_{i}  (1)

(and hence A_{i} ∼ A_{i}^{∗}) for every i: the sets

A′_{i} := { x ^{∈} P | ∃ a ^{∈} A_{i}^{∗}: x ⩽ a } ⊇ A_{i}^{∗}

cover P, and to obtain the A_{i} we just make them disjoint by trimming off any overlaps outside the (disjoint) A_{i}^{∗}; then A_{i}^{∗} ⊆ A_{i} ⊆ A′_{i} ⩽ A_{i}^{∗} for all i, as required.

Since the A_{i}^{∗} are indivisible and A_{i} ∼ A_{i}^{∗}, the A_{i} are indivisible by Corollary 2. Let us now show that every A_{i} is essential in P. If not, then A_{i} ⩽ ⋃_{j≠i} A_{j} and therefore

A_{i}^{∗} ⊆ A_{i} ⩽ ⋃_{j≠i} A_{j} ⩽ ⋃_{j≠i} A_{j}^{∗}

by (1), which contradicts the fact that A_{i}^{∗} is essential in P^{∗}.

To complete the proof, it remains to show that every essential indivisible subset B of P is equivalent to one of the sets A_{1}, …, A_{n}. For each i = 1, …, n, put B_{i} := B ∩ A_{i}. Then B = B_{1} ∪ … ∪ B_{n}, and since B is indivisible we have B ⩽ B_{i} for some i by Lemma 1, and hence B ∼ B_{i} ⊆ A_{i}. If B ∼ A_{i} we are done; if not, then B_{i} is small in A_{i}. Then A_{i} ∖ B_{i} is large in A_{i} (because A_{i} is indivisible), ie. A_{i} ⩽ A_{i} ∖ B_{i}. Thus

B ⩽ B_{i} ⊆ A_{i} ⩽ A_{i} ∖ B_{i} ⊆ P ∖ B,

which contradicts our assumption that B is essential in P. □

We remark that the essential sets A_{1}^{∗}, …, A_{n}^{∗} from the proof of Theorem 5 can easily be ‘constructed’ directly (and seen to be essential in P), as follows. Note first that a subset of P is essential if and only if it contains the entire up-closure ⌊x⌋ in P of one of its points x. Using Proposition 4 and the fact that P contains no infinite antichain, one easily shows that above each point of P there is a point x whose up-closure ⌊x⌋ in P is indivisible. Thus if { a_{1}, …, a_{n} } is any maximal set of points with disjoint indivisible up-closures, then these up-closures A_{i}^{∗} := ⌊a_{i}⌋ are indivisible essential subsets of P such that P ⩽ A_{1}^{∗} ∪ ⋯ ∪ A_{n}^{∗}. The partition P = A_{1} ∪ ⋯ ∪ A_{n} for the theorem is then obained exactly as in the proof: by replacing each A_{i}^{∗} with its down-closure and making these disjoint by trimming off overlaps.

Note that in this proof we only use that P has no infinite antichain, or indeed that P contains no induced copy of the binary tree. Therefore either of these assumptions can replace the stronger WQO assumption in Theorem 5. A full characterization of the countable posets that factor into indivisible essential subsets will be given in [ 3 ]; the corresponding problem for larger posets remains open.

References

[1] R. Diestel, Graph theory, 2nd edition, Springer-Verlag 2000 and

     http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/download.html

[2] R. Diestel & D. Kühn, Graph minor hierarchies, preprint 2001.

[3] R. Diestel & O. Pikhurko, On the cofinality of infinite partially ordered sets: factoring a poset into lean essential subsets, in preparation.