We continue our discussion of Dilworth’s theorem from last time. To recall, we proved by (a very algorithmic) induction that, if is a *finite* poset whose largest antichain has elements, then is the union of chains. Today we’ll see how a batch of standard (and important) techniques can prove the theorem for general , from the finite case. As before, we will often refer to decompositions of into chains as *colorings* of , which will always be subject to the restriction that two similarly colored elements be comparable. When we wish to emphasize this property, we may employ the term *consistent* coloring. It is easy to see that colorings using colors are equivalent to decompositions into chains.

The standard move for infinite would be Zorn’s lemma. By going carefully through the second part of our proof, where we “concentrate” each color on top of only one chain, we see that it can be adapted to arbitrary without too much trouble: instead of looking for the squiggle with the smallest dark red element in its upper monochromatic set, we choose one which has “arbitrarily small” dark red elements there, and put all the dark red on top of it. This gives us the incremental part of a standard argument by Zorn’s Lemma, but our increment potentially involves a lot of fiddling with the chains, so we will probably not be able to define a very demanding order on the set of partially-built structures. As we saw, this will probably make it difficult to prove the existence of upper bounds for metachains.

So, let’s scale back the difficulty and consider the case of denumerable ; with countable sets, we can usually build stuff “one element at a time”. Suppose, then, that is a countable poset without antichains bigger than . Let be an antichain, and start with a partial decomposition of into chains , where initially. Put for definiteness. Using the finite form of Dilworth’s theorem, whereby each finite subset of can be arranged into chains, we hope to find such a decomposition of all of .

Let’s just bulldoze our way forward and see what goes wrong. Stick in whatever it will fit ( must be comparable to at least one , otherwise we’d have an -antichain), and continue by putting each in whatever is possible. If this can be done indefinitely, we get a decomposition of . Otherwise, we run into trouble at some , meaning each contains, at that point, some not comparable to .

An obvious reaction is to use Dilworth’s: we know that can in fact be put consistently into the chains . We do that, and continue on our merry way.

Unfortunately, it’s not that easy. Decomposing ever larger subsets of into chains is not enough: we need to harness that information into a *single* decomposition of . Let me spell it out in the simple case.

Suppose we don’t run into trouble adding elements of to the , one at a time. How exactly do we specify a decomposition of from that? That is, given , to which does it belong to? What we had in mind was pretty simple: it belongs to whatever it was assigned to, when it was its turn to be added!

Simple as it may be, we must answer a couple of questions. First, is that decomposition well-defined, unambiguous? In this case, yes, since each is assigned a unique in the trouble-free case. Second, is each really a chain when all is said and done? Also yes: suppose , with . By construction, when was added to (at step ), it was comparable to all the elements that had been assigned to at that point. In particular, since was added earlier (at step ), must have been comparable to .

Contrast this with the case where we do run into trouble, say at . Invoking Dilworth’s will cause a few among to jump around between the . If we keep doing this indefinitely, who’s to say that all the eventually settle down and can be assigned a definite ? And if they don’t, what should we assign them?

Maybe if we take more care in assigning each to a , we won’t have to change it afterwards. That is, we won’t have to apply Dilworth again and again. So what should we look out for?

It isn’t very clear how to express the obstructions to avoid in a succint form, e.g. involving only a few kinds of sentence about . Therefore, we resort to another venerable custom of mathematics: just state what you want, flat out, and use the structure arising from that alone.

There are possible colors for : . We want to choose the one which runs into the least trouble. Suppose coloring with inevitably runs into trouble at , in the sense that any extension into a coloring of has incomparable elements of the same color. A natural choice for the color of would be that with the biggest , ie, that which runs into trouble the latest.

A pleasant fact now asserts itself: there must be a without a corresponding ! That is, a choice of color for which admits arbitrarily large extensions. It’s obvious once you think about it: if all colors ran into dead-ends at , there would be a largest dead-end , and we would be unable to color beyond . However, we know that all finite subsets, including , admit consistent colorings.

Another way to see it is the following: let be the sequence of colors assigned to in consistent colorings of , , etc. Since there are only possible colors, at least one must be repeated infinitely many times.

That seems as good a color to give as any; say it is . What next? Well, since there are arbitrarily large colorings with painted , we can run the argument again using only those, and choose a color for which admits arbitrarily large extensions. And so forth.

To sum up, here’s how we define a coloring of . For each , let be a coloring of , that is, a map such that two equally colored elements are comparable. Let be a color such that arbitrarily large have , and let be the subsequence of those which do. Inductively, given a subsequence of colorings , all of which have the same first colors, choose a subsequence whose elements also have the same -th color. This is possible because there are only different colors. Finally, let the “actual” color of be that assigned by the .

This process assigns each a definite color, and the result is consistent. Indeed, if , then extends (being, in fact, for some ); thus, if and are assigned the same color by , they are assigned the same color by , which, being a consistent coloring, makes and comparable.

So that’s it for countable . For general , much the same idea works, with the caveat that we recast the argument in the language of ordinals (for the “step-by-step” angle) or nets in topological spaces (for the “subsequences” angle). We briefly work out the second approach. Let be the set of finite subsets of , and give it the structure of a directed set via ; an upper bound for two elements is just their set-theoretic union. Give the product topology (over the discrete topology in ) and define a net by setting equal to a consistent coloring of (given by finite Dilworth) plus some random coloring of . Since is compact by Tychonoff’s theorem, there must be a convergent subnet . It is straightforward to check that is a consistent coloring of all of .

There is some crucial finiteness phenomenon underlying the results and arguments above, and it is more clearly seen in the contrapositive form of Dilworth’s theorem: if a poset *cannot* be decomposed into chains, then it must contain an antichain of size at least . Therefore, to demonstrate the impossibility of such a decomposition, it suffices to pick out a finite *witness*: a large, but finite, antichain of . Such a witness may be expressed by a finite number of statements of the form .

These considerations suggest another approach to the infinite form of Dilworth’s theorem: mathematical logic. In particular, the compactness theorem for first-order logic.

Let be a language consisting of the usual symbols for variables, logical connectives and quantifiers, plus a family of constants , a binary relation symbol and a unary function symbol . We can encode all the information about in an -theory consisting of the poset axioms plus the sentences:

- , for each such that ;
- , for each such that is not the case;
- ;
- ;

Suppose has a model with constants . We claim that the map is an order-theoretic embedding of in .

First, all the are distinct: if , then one of , fails to be the case (by antisymmetry), whence either or is in . It follows that either or fails; and since is the model of a poset, would imply both.

Next, the first two types of sentence of obviously imply that is order-isomorphic to its image by the map . Therefore, if it is possible to decompose into the union of chains, the same goes for . But that’s just what the last two types of sentence of say, with the aid of the function symbol : its realization splits up into subsets (one for each ), and each subset is a chain.

To summarize: if has a model , it can be decomposed into chains, and has as a subposet; thus can be decomposed into chains.

On the other hand, if *didn’t* have a model, by the compactness theorem in first-order logic there would be some finite subtheory of that didn’t have a model. However, a finite subtheory, having only a finite number of sentences, can only mention a finite number of the constants ; and the finite subposet of corresponding to those constants, endowed with a decomposition into chains (finite Dilworth), is a model for that subtheory. Therefore, does have a model, and is decomposable, as we wished.

Next time, we’ll look at some applications of Dilworth’s theorem in combinatorics, and its relationship to various other famous theorems in that field.

## Leave a Reply