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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\subset},{\supset}} ,Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\subseteq},{\supseteq}} ; Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\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: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \not< x ; \,}
• Antisymmetric: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y \Rightarrow y \not< x ; \,}
• Transitive: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y, y < z \Rightarrow x < z . \,}

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

• Reflexive: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \le x ; \,}
• Antisymmetric: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \le y, y \le x \Rightarrow x=y ; \,}
• Transitive: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \le y, y \le z \Rightarrow x \le 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = y} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x > y} holds.

Associated concepts

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a,b] = \{ x \in X : a \le x \le b \}.\,}

We say that b covers a if the interval Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U \ge s} for all elements Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s \in S} . A lower bound for S is an element L of X such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L \le s} for all elements Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s \in S} . A set is bounded if it has both lower and upper bounds. 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 be a minimum.

A maximum element for the whole set may be termed top, one or true and denoted by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \top} or 1; a minimum element for the whole set may be termed bottom, zero or false and denoted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bot} or 0.

An antichain is a subset of an ordered set in which no two elements are comparable. The width of a partially ordered set is the largest cardinality of an antichain.

Mappings of ordered sets

A function from an ordered set (X,<) to (Y,<) is monotonic or monotone increasing if it preserves order: that is, when x and y satisfy Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \le y} then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) \le f(y)} . A monotone decreasing function similarly reverses the order. A function is strictly monotonic if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y} implies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) < f(y)} : such a function is necessarily injective.

An order isomorphism, or simply isomorphism between ordered sets is a monotonic bijection.

Chains

A chain is a subset of an ordered set for which the induced order is total. An ordered set satisfies the ascending chain condition (ACC) if every strictly increasing chain is finite, and the descending chain condition (DCC) if every strictly decreasing chain is finite. An order relation satisfying the DCC is also termed well-founded.

A maximal chain is a chain which cannot be extended by any element and still be linearly ordered (it is maximal within the family of chains ordered by set-theoretic inclusion).

The dimension of an element x in an ordered set with 0 is the length d(x) of a longest maximal chain from 0 to x.

Dilworth's theorem

Dilworth's theorem states that the width of an ordered set, the maximal size of an antichain, is equal to the minimal number of chains which together covers the set.

Lattices

A lattice is an ordered set in which any two element set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \vee b} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \wedge b} respectively.

The join and meet satisfy the properties:

• Idempotence: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \vee x = x = x \wedge x ; \,}
• Commutativity: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \vee y = y \vee x;~ x \wedge y = y \wedge x ;\,}
• Associativity: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \vee (y \vee z) = (x \vee y) \vee z;~ x \wedge (y \wedge z) = (x \wedge y) \wedge z ;\,}
• Absorption: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \wedge (x \vee y) = x;~ x \vee (x \wedge y) = x;\,}

These four properties characterize a lattice. The order relation may be recovered from the join and meet by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \vee b = b \Leftrightarrow a \le b \Leftrightarrow a \wedge b = a . \,}

Modular lattices

A modular lattice satisfies the further property:

• Modularity: If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \ge y} then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \wedge (y \vee z) = y \vee (x \wedge z) . \,}

A pair of intervals of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a\vee b,b]} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a,a\wedge b]} are said to be in perspective. In a modular lattice, perspective intervals are isomorphic.

In a modular lattice with 0, if an element x has finite dimension d, then all maximal chains from 0 to x have the same length d.

The Jordan-Dedekind chain condition holds in a modular lattice: all finite maximal chains between two given elements have the same length.

The dimension is related to the join and meet in a modular lattice by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d(x) + d(y) = d(x \wedge y) + d(x \vee y) .\,}

Distributive lattices

A distributive lattice satisfies the further property:

• Distributivity: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z);~ x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z ).\,}

Distributivity implies modularity for a lattice.

Complemented lattices

A complete lattice is one in which every set has a supremum and an infimum. In particular the lattice must have bottom and top elements, usually denoted 0 and 1.

A complemented lattice is a lattice with 0 and 1 with the property that for every element a there is some element b such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \wedge b = \mathbf{0}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \vee b = \mathbf{1}} . If the lattice is distributive then the complement of a, denoted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bar a} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a'} is unique.

A Boolean lattice is a distributive complemented lattice, and hence with a uniquely defined complement.