ON THE WEAKNESS OF AN ORDERED SET

In this paper we extend the notion of a ranking of elements in a weak order to a ranking of elements in general ordered sets. The weakness o f an ordered set P = (X, curly less than) (denoted wk(P)) is the minim um integer k for which there exists an integer-valued function lev : X --> Z satisfying: (i) if x curly less than y, then lev(x) < lev(y); a nd (ii) if x parallel to y, then \lev(x) - lev(y)\ less than or equal to k (where ''parallel to'' denotes incomparability). A forcing cycle L in P is a sequence of elements L : x = v(0), v(1),..., v(m) = x of P so that for each i is an element of {0, 1,..., m - 1} either v(i) cur ly less than v(i+1) or v(i) parallel to v(i+1). Our main result relate s these two concepts; we prove wk(P) = max(L) inverted right perpendic ularup(L)/side(L)inverted left perpendicular, where up(L) = # {i : v(i ) curly less than v(i+1)}, side(L) = #{i : v(i) parallel to v(i+1)} an d the maximum is taken over all forcing cycles L in P. We also discuss algorithms for computing wk(P) and prove that wk(P) is a comparabilit y invariant.