Order Theory - Special Types of Orders

Special Types of Orders

Many of the structures that are studied in order theory employ order relations with further properties. In fact, even some relations that are not partial orders are of special interest. Mainly the concept of a preorder has to be mentioned. A preorder is a relation that is reflexive and transitive, but not necessarily antisymmetric. Each preorder induces an equivalence relation between elements, where a is equivalent to b, if a ≤ b and b ≤ a. Preorders can be turned into orders by identifying all elements that are equivalent with respect to this relation.

Several types of orders can be defined from numerical data on the items of the order: a total order results from attaching distinct real numbers to each item and using the numerical comparisons to order the items; instead, if distinct items are allowed to have equal numerical scores, one obtains a strict weak ordering. Requiring two scores to be separated by a fixed threshold before they may be compared leads to the concept of a semiorder, while allowing the threshold to vary on a per-item basis produces an interval order.

An additional simple but useful property leads to so-called well-orders, for which all non-empty subsets have a minimal element. Generalizing well-orders from linear to partial orders, a set is well partially ordered if all its non-empty subsets have a finite number of minimal elements.

Many other types of orders arise when the existence of infima and suprema of certain sets is guaranteed. Focusing on this aspect, usually referred to as completeness of orders, one obtains:

• Bounded posets, i.e. posets with a least and greatest element (which are just the supremum and infimum of the empty subset),
• Lattices, in which every non-empty finite set has a supremum and infimum,
• Complete lattices, where every set has a supremum and infimum, and
• Directed complete partial orders (dcpos), that guarantee the existence of suprema of all directed subsets and that are studied in domain theory.

However, one can go even further: if all finite non-empty infima exist, then ^ can be viewed as a total binary operation in the sense of universal algebra. Hence, in a lattice, two operations ^ and v are available, and one can define new properties by giving identities, such as

x ^ (y v z) = (x ^ y) v (x ^ z), for all x, y, and z.

This condition is called distributivity and gives rise to distributive lattices. There are some other important distributivity laws which are discussed in the article on distributivity in order theory. Some additional order structures that are often specified via algebraic operations and defining identities are

• Heyting algebras and
• Boolean algebras,

which both introduce a new operation ~ called negation. Both structures play a role in mathematical logic and especially Boolean algebras have major applications in computer science. Finally, various structures in mathematics combine orders with even more algebraic operations, as in the case of quantales, that allow for the definition of an addition operation.

Many other important properties of posets exist. For example, a poset is locally finite if every closed interval in it is finite. Locally finite posets give rise to incidence algebras which in turn can be used to define the Euler characteristic of finite bounded posets.