Order (relation)

In mathematics, an order relation is a relation on a set which generalises the notion of comparison between numbers and magnitudes, or inclusion between sets or algebraic structures.

Throughout the discussion of various forms of order, it is necessary to distinguish between a strict or strong form and a weak form of an order: the difference being that the weak form includes the possibility that the objects being compared are equal. We shall usually denote a general order by the traditional symbols < or > for the strict form and ≤ or ≥ for the weak form, but notations such as ${\subset },{\supset }$,${\subseteq },{\supseteq }$; ${\prec },{\succ }$,${\preceq },{\succeq }$; ${\sqsubset },{\sqsupset }$,${\sqsubseteq },{\sqsupseteq }$ are also common. We also use the traditional notational convention that $x<y\Leftrightarrow y>x$.

An ordered set is a pair (X,<) consisting of a set and an order relation.

Partial order

The most general form of order is the (strict) partial order, a relation < on a set satisfying:

• Irreflexive: $x\not <x;\,$
• Antisymmetric: $x<y\Rightarrow y\not <x;\,$
• Transitive: $x<y,y<z\Rightarrow x<z.\,$

The weak form ≤ of an order satisfies the variant conditions:

• Reflexive: $x\leq x;\,$
• Antisymmetric: $x\leq y,y\leq x\Rightarrow x=y;\,$
• Transitive: $x\leq y,y\leq z\Rightarrow x\leq z.\,$

Total order

A total or linear order is one which has the trichotomy property: for any x, y exactly one of the three statements $x<y$, $x=y$, $x>y$ holds.

Associated concepts

If a ≤ b in an ordered set (X,<) then the interval

$[a,b]=\{x\in X:a\leq x\leq b\}.\,$

We say that b covers a if the interval $[a,b]=\{a,b\}$: that is, there is no x strictly between a and b.

Let S be a subset of a ordered set (X,<). An upper bound for S is an element u of X such that $u\geq s$ for all elements $s\in S$. A lower bound for S is an element l of X such that $\ell \geq s$ for all elements $s\in S$. In general a set need not have either an upper or a lower bound.

A supremum for S is an upper bound which is less than or equal to any other upper bound for S; an infimum is a lower bound for S which is greater than or equal to any other lower bound for S. In general a set with upper bounds need not have a supremum; a set with lower bounds need not have an infimum. The supremum or infimum of S, if one exists, is unique

A maximum for S is an upper bound which is in S; a minimum for S is a lower bound which is in S. A maximum is necessarily a supremum, but a supremum for a set need not be a maximum (that is, need not be an element of the set); similarly an infimum need not a minimum.

Lattices

A lattice is an ordered set in which any two element set $\{a,b\}$ has a supremum and an infimum. We call the supremum the join and the infimum the meet of the elements a and b, denoted $a\vee b$ and $a\wedge b$ respectively.

The join and meet satisfy the properties:

• Idempotence: $x\vee x=x=x\wedge x;\,$
• Commutativity: $x\vee y=y\vee x;~x\wedge y=y\wedge x;\,$
• Associativity: $x\vee (y\vee z)=(x\vee y)\vee z;~x\wedge (y\wedge z)=(x\wedge y)\wedge z;\,$
• Absorption: $x\wedge (x\vee y)=x;~x\vee (x\wedge y)=x;\,$

These four properties characterise a lattice.

A distributive lattice satisfies the further property:

• Distributivity: $x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z);~x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z).\,$