Editing Order theory (section)

== 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-founded relation|well-founded]]''', for which all non-empty subsets have a minimal element.  Generalizing well-orders from linear to partial orders, a set is '''[[well partial order|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 [[infimum|infima]] and [[supremum|suprema]] of certain sets is guaranteed. Focusing on this aspect, usually referred to as [[completeness (order theory)|completeness]] of orders, one obtains:

* [[Bounded poset]]s, i.e. posets with a [[least element|least]] and [[greatest element]] (which are just the supremum and infimum of the [[empty subset]]),
* [[lattice (order)|Lattices]], in which every non-empty finite set has a supremum and infimum,
* [[Complete lattice]]s, where every set has a supremum and infimum, and
* [[Directed complete partial order]]s (dcpos), that guarantee the existence of suprema of all [[directed set|directed subsets]] and that are studied in [[domain theory]].
* Partial orders with complements, or ''poc sets'',<ref>{{citation |first=Martin A. |last=Roller |title=Poc sets, median algebras and group actions. An extended study of Dunwoody's construction and Sageev's theorem |date=1998 |publisher=Southampton Preprint Archive |url=http://www.personal.soton.ac.uk/gan/Roller.pdf |access-date=2015-01-18 |archive-url=https://web.archive.org/web/20160304051111/http://www.personal.soton.ac.uk/gan/Roller.pdf |archive-date=2016-03-04 |url-status=dead }}</ref> are posets with a unique bottom element 0, as well as an order-reversing involution <math>*</math> such that <math>a \leq a^{*} \implies a = 0.</math>

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 ∨ are available, and one can define new properties by giving identities, such as

: ''x''&nbsp;∧&nbsp;(''y''&nbsp;∨&nbsp;''z'') &nbsp;=&nbsp; (''x''&nbsp;∧&nbsp;''y'')&nbsp;∨&nbsp;(''x''&nbsp;∧&nbsp;''z''), for all ''x'', ''y'', and ''z''.

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

* [[Heyting algebra]]s and
* [[Boolean algebra (structure)|Boolean algebra]]s,

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 [[quantale]]s, 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 (mathematics)|interval]] [''a'', ''b''] in it is [[finite set|finite]]. Locally finite posets give rise to [[incidence algebra]]s which in turn can be used to define the [[Euler characteristic#Generalizations|Euler characteristic]] of finite bounded posets.