Weak orders, ordered partitions, and generalized weak orders

A binary relation R on X is a complete weak order if and only if it is reflexive, complete and transitive. A binary relation R on X is an asymmetric weak order if and only if it is asymmetric and negatively transitive. For any binary relation R on a nonempty set X , let aR , cR and sR. denote, respectively, the asymmetric part of R , the complement of R , and the symmetric part of R , that is, aR = {xy|xy ∈ R and yx ∈ R} , CR = (X x X) - R , and sR = {xy|xy ∈ R and yx ∈ R} . When R is a complete weak order, equivalence classes of X are determined by the symmetric part of R . When R is an asymmetric weak order, X is partitioned into equivalences classes determined by the symmetric part of the complement of R . The partitions X = X/sR and X = X/scR induced, respectively, by a complete weak order R , and an asymmetric weak order R , have a natural linear ordering > . We show that there exists a one-to-one correspondence between complete weak orders, asymmetric weak orders and linearly ordered partitions of X . We enumerate the complete weak orders on an n-element set X by enumerating the ordered partitions of X .

A feature common to both types of weak orders already mentioned is used as the basis of a definition of a generalized weak order. When R is a generalized weak order, X is partitioned into equivalence classes determined by the symmetric part of the complement of the asymmetric part of R . The partition X = X/scaR has a linear ordering defined as follows: For all A, B X, A > B if and only if A x B aR . A linearly ordered partition of X is a Fishburn partition if each of its equivalence classes is equipped with some symmetric relation. We show a one-to-one correspondence exists between generalized weak orders on X and Fishburn partitions on X .

Special types of generalized weak orders include the transitive generalized weak orders, the negatively transitive generalized weak orders, and the generalized weak orders that are both transitive and negatively transitive. We show that the transitive generalized weak orders are just those generalized weak orders with transitive symmetric part; the negatively transitive generalized weak orders are just those generalized weak orders, the symmetric part of whose complement is transitive; and the transitive, negatively transitive generalized weak orders are just the transitive, negatively transitive binary relations.