Re: Dilworth's Easy Theorem

William Elliot wrote:
Dilworth's Theorem
Even easier than Dilworth's theorem is the proposition that every
partially ordered set S of finite length L(S) can be partitioned into
L(S) antichains. Simply observe that the set M of all minimal elements
is an antichain, and L(S\M) < L(S). Note that the inequality |S| <=
L(S)W(S), for *finite* S of course, follows from this simpler
proposition, as well as from Dilworth's theorem.

Also by same proof
|S| <= L(S) w(S) where w(S) supremum of size of antichains.
and that the antichains aren't empty, if S isn't.

Proof by induction on L(S).

The following is essentially the same proof, but without the induction.

We assume that S is a partially ordered set, and there is a positive
integer k such that max{|C|: C is a chain in S} = k.

Let [k] = {1, 2, 3, ..., k}.

Define a function f:S --> [k] by letting f(x) be the maximum
cardinality of a chain in the set {y in S: y <= x}.

Clearly, x < y implies f(x) < f(y). Hence, for each i in [k], the set
A_i = {x in S: f(x) = i} is an antichain, and S is the union of the
antichains A_1, ..., A_k.

.

Relevant Pages

  • Re: Dilworths Easy Theorem
    ... Subject: Dilworth's Easy Theorem ... Lantichains. ... We assume that S is a partially ordered set, ... Clearly no smaller antichain partition is possible. ...
    (sci.math)
  • Dilworths Easy Theorem
    ... partially ordered set S of finite length Lcan be partitioned into ... Lantichains. ... then let c be bottom element of C. ... some chain C within S with length C = n+1. ...
    (sci.math)
Quantcast