Duality (mathematics) - Order-reversing Dualities

Order-reversing Dualities

A particularly simple form of duality comes from order theory. The dual of a poset P = (X, ≤) is the poset Pd = (X, ≥) comprising the same ground set but the converse relation. Familiar examples of dual partial orders include

• the subset and superset relations ⊂ and ⊃ on any collection of sets,
• the divides and multiple-of relations on the integers, and
• the descendant-of and ancestor-of relations on the set of humans.

A concept defined for a partial order P will correspond to a dual concept on the dual poset Pd. For instance, a minimal element of P will be a maximal element of Pd: minimality and maximality are dual concepts in order theory. Other pairs of dual concepts are upper and lower bounds, lower sets and upper sets, and ideals and filters.

A particular order reversal of this type occurs in the family of all subsets of some set S: if denotes the complement set, then A ⊂ B if and only if . In topology, open sets and closed sets are dual concepts: the complement of an open set is closed, and vice versa. In matroid theory, the family of sets complementary to the independent sets of a given matroid themselves form another matroid, called the dual matroid. In logic, one may represent a truth assignment to the variables of an unquantified formula as a set, the variables that are true for the assignment. A truth assignment satisfies the formula if and only if the complementary truth assignment satisfies the De Morgan dual of its formula. The existential and universal quantifiers in logic are similarly dual.

A partial order may be interpreted as a category in which there is an arrow from x to y in the category if and only if x ≤ y in the partial order. The order-reversing duality of partial orders can be extended to the concept of a dual category, the category formed by reversing all the arrows in a given category. Many of the specific dualities described later are dualities of categories in this sense.

According to Artstein-Avidan and Milman, a duality transform is just an involutive antiautomorphism of a partially ordered set S, that is, an order-reversing involution Surprisingly, in several important cases these simple properties determine the transform uniquely up to some simple symmetries. If are two duality transforms then their composition is an order automorphism of S; thus, any two duality transforms differ only by an order automorphism. For example, all order automorphisms of a power set S = 2R are induced by permutations of R. The papers cited above treat only sets S of functions on Rn satisfying some condition of convexity and prove that all order automorphisms are induced by linear or affine transformations of Rn.