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 ab and ba. 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.

Read more about this topic:  Order Theory

Other articles related to "types, type":

Small Boat Anchors - Bruce or Claw Anchor
... Claw-types set quickly in most seabeds and although not an articulated design, they have the reputation of not breaking out with tide or wind changes, instead slowly turning in the bottom to ... Claw types have difficulty penetrating weedy bottoms and grass ... holding-power-to-weight ratio and generally have to be oversized to compete with other types ...
Prolog - Extensions - Types
... Attempts to introduce types date back to the 1980s, and as of 2008 there are still attempts to extend Prolog with types ... Type information is useful not only for type safety but also for reasoning about Prolog programs ...
Netwar - Network Structures
... may also take on hybrid forms as well, blending different types of networks and hierarchies ... of the same group may be networked to each other through different types of network structures ...
Types of Graphemes
... The principal types of graphemes are logograms, which represent words or morphemes (for example, Chinese characters, or the ampersand representing the English word and also Arabic numerals ... For a full discussion of the different types, see Writing system Functional classification of writing systems ...

Famous quotes containing the words orders, special and/or types:

    The newspapers, especially those in the East, are amazingly superficial and ... a large number of news gatherers are either cynics at heart or are following the orders and the policies of the owners of their papers.
    Franklin D. Roosevelt (1882–1945)

    Here in the U.S., culture is not that delicious panacea which we Europeans consume in a sacramental mental space and which has its own special columns in the newspapers—and in people’s minds. Culture is space, speed, cinema, technology. This culture is authentic, if anything can be said to be authentic.
    Jean Baudrillard (b. 1929)

    ... there are two types of happiness and I have chosen that of the murderers. For I am happy. There was a time when I thought I had reached the limit of distress. Beyond that limit, there is a sterile and magnificent happiness.
    Albert Camus (1913–1960)