# Dilworth's theorem

A set P is partially ordered if for every x, y, and z in P:
• Reflexivity: x is less than or equal to x;
• Antisymmetry: If x is less than or equal to y and y is less than or equal to x, then x equals y; and
• Transitivity: If x is less than or equal to y and y is less than or equal to z, then x is less than or equal to z.
If x is less than or equal to y or y is less than or equal to x, then we say that x and y are comparable.  If it is neither the case that x is less than or equal to y or y is less than or equal to x, then we say x and y are incomparable.

A chain in P is a subset of P where every two members of the subset are comparable.

An antichain in P is a subset of P where no two members of the subset are comparable (unless they are equal).

The width of a finite partial order is the size of its largest antichain.

Dilworth's theorem says that the width of P is equal to the smallest n such that P can be written as the union of n chains.

I keep nibbling away at the proof of this one, but it's slippery.

Offering:
Doors are solemn things, guarding entrances,
Opening to the favored,
Closing to thieves and weather.
Doors are solemn things, but
Cat doors are for cats.
• #### Julie

Julie had surgery today to remove her left lung, a treatment for asbestos-caused lung cancer. But tonight her daughter posted: Mom is doing really…

Not what I expected to hear when I stopped at Sheetz coming home from the SpiralHeart meeting: Some folks are born made to wave the flag, Ooh,…

• #### Handpan Dissonance

Here is a (very naive) attempt to estimate the potential dissonance for Pantheon Steel's Sound Models. The idea is to calculate the dissonance you…

• Post a new comment

#### Error

default userpic