Order (relation): Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Richard Pinch
(→‎Lattices: definition of Boolean lattice)
imported>Milton Beychok
m (Revised Wiki link)
 
(17 intermediate revisions by 2 users not shown)
Line 9: Line 9:


==Partial order==
==Partial order==
The most general form of order is the (strict) '''partial order''', a relation < on a set satisfying:
The most general form of order is the (weak) '''partial order''', a relation ≤ on a set satisfying:
* ''Reflexive'': <math>x \le x ; \,</math>
* ''Antisymmetric'': <math>x \le y, y \le x \Rightarrow x=y ; \,</math>
* ''Transitive'': <math>x \le y, y \le z \Rightarrow x \le z . \,</math>
 
The ''strict'' form &lt; of an order satisfies the variant conditions:
* ''Irreflexive'': <math>x \not< x ; \,</math>
* ''Irreflexive'': <math>x \not< x ; \,</math>
* ''Antisymmetric'': <math>x < y \Rightarrow y \not< x ; \,</math>
* ''Antisymmetric'': <math>x < y \Rightarrow y \not< x ; \,</math>
* ''Transitive'': <math>x < y, y < z \Rightarrow x < z . \,</math>
* ''Transitive'': <math>x < y, y < z \Rightarrow x < z . \,</math>


The ''weak'' form &le; of an order satisfies the variant conditions:
Weak and strict partial orders are equivalent via the following translations:
* ''Reflexive'': <math>x \le x ; \,</math>
:<math>x \le y</math> if and only if <math>x < y</math> or <math>x = y;</math>
* ''Antisymmetric'': <math>x \le y, y \le x \Rightarrow x=y ; \,</math>
:<math>x < y</math> if and only if <math>x \le y</math> and <math>x \ne y.</math>
* ''Transitive'': <math>x \le y, y \le z \Rightarrow x \le z . \,</math>
 
A reflexive and transitive relation is called a '''preorder'''. In a preorder the relation defined by <math>x \le y \le x</math> is an equivalence relation, and the preorder gives rise to a partial order on the corresponding equivalence classes.


==Total order==
==Total order==
Line 27: Line 33:
:<math>[a,b] = \{ x \in X : a \le x \le b \}.\,</math>
:<math>[a,b] = \{ x \in X : a \le x \le b \}.\,</math>


We say that ''b'' ''covers'' ''a'' if the interval <math>[a,b] = \{a,b\}</math>: that is, there is no ''x'' strictly between ''a'' and ''b''.
We say that ''b'' ''covers'' ''a'' if the interval <math>[a,b] = \{a,b\}</math>: that is, there is no ''x'' strictly between ''a'' and ''b''.  We write <math>a \prec b</math> or <math>b \succ a</math>.


Let ''S'' be a subset of a ordered set (''X'',&lt;).  An ''upper bound'' for ''S'' is an element ''U'' of ''X'' such that <math>U \ge s</math> for all elements <math>s \in S</math>.  A ''lower bound'' for ''S'' is an element ''L'' of ''X'' such that <math>L \le s</math> for all elements <math>s \in S</math>.  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.   
Let ''S'' be a subset of a ordered set (''X'',&lt;).  An ''upper bound'' for ''S'' is an element ''U'' of ''X'' such that <math>U \ge s</math> for all elements <math>s \in S</math>.  A ''lower bound'' for ''S'' is an element ''L'' of ''X'' such that <math>L \le s</math> for all elements <math>s \in S</math>.  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 ''directed set'' is one in which any finite set has an upper bound.
 
The set of upper bounds for ''S'' is denoted ''UB''(''S''); the set of lower bounds is ''LB''(''S'').   


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 ''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
Line 35: Line 43:
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'' 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 <math>\top</math> or '''1'''; a minimum element for the whole set may be termed ''bottom'', ''zero'' or ''false'' and denoted <math>\bot</math> or '''0'''.
A maximum element for the whole set may be termed ''top'', ''one'' or ''true'' and denoted by <math>\top</math> or '''1'''; a minimum element for the whole set may be termed ''bottom'', ''zero'' or ''false'' and denoted <math>\bot</math> or '''0'''.  An ordered set with a '''0''' and '''1''' is ''bounded''.
 
In a bounded order, an '''atom''' is an element that covers '''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.
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.


===Chains===
A subset ''S'' of an ordered set ''X'' is ''downward closed'' or a ''lower set'' if it satisfies
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) is every strictly increasing chain if 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''.
 
:<math>x \le s \in S \Rightarrow x \in S .\,</math>
 
Similarly, a subset ''S'' of an ordered set ''X'' is ''upward closed'' or an ''upper set'' if it satisfies
 
:<math>x \ge s \in S \Rightarrow x \in S .\,</math>


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 (set theory)|inclusion]]).
A (''Dedekind'') ''cut'' in an ordered set ''X'' is a pair (''A'',''B'') of subsets of ''X'' such that ''B'' is the set of upper bounds of ''A'' and ''A'' is the set of lower bounds of ''B'': ''B'' = ''UB''(''A'') and ''A'' = ''LB''(''B'').  We may equivalently define a cut by ''A'' = ''LB''(''UB''(''A'')), whereas in general ''A'' is merely a subset of ''LB''(''UB''(''A'')).


===Mappings of ordered sets===
===Mappings of ordered sets===
A [[function (mathematics)]] from an ordered set (''X'',&lt;) to (''Y'',&lt;)is ''monotonic'' or ''monotone increasing'' if it preserves order: that is, when ''x'' and ''y'' satisfy <math>x \le y</math> then <math>f(x) \le f(y)</math>.  A ''monotone decreasing'' function similarly reverses the order.  A function is ''strictly monotonic'' if <math>x < y</math> implies <math>f(x) < f(y)</math>: such a function is necessarily [[injective function|injective]].
A [[function (mathematics)|function]] from an ordered set (''X'',&lt;) to (''Y'',&lt;) is ''monotonic'' or ''monotone increasing'' if it preserves order: that is, when ''x'' and ''y'' satisfy <math>x \le y</math> then <math>f(x) \le f(y)</math>.  A ''monotone decreasing'' function similarly reverses the order.  A function is ''strictly monotonic'' if <math>x < y</math> implies <math>f(x) < f(y)</math>: such a function is necessarily [[injective function|injective]].


An ''order isomorphism'', or simply ''isomorphism'' between ordered sets is a monotonic [[bijection]].
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 (set theory)|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===
Line 59: Line 81:
* [[Commutativity]]: <math>x \vee y = y \vee x;~ x \wedge y = y \wedge x ;\,</math>
* [[Commutativity]]: <math>x \vee y = y \vee x;~ x \wedge y = y \wedge x ;\,</math>
* [[Associativity]]: <math>x \vee (y \vee z) = (x \vee y) \vee z;~ x \wedge (y \wedge z) = (x \wedge y) \wedge z ;\,</math>
* [[Associativity]]: <math>x \vee (y \vee z) = (x \vee y) \vee z;~ x \wedge (y \wedge z) = (x \wedge y) \wedge z ;\,</math>
* [[Absorption]]: <math>x \wedge (x \vee y) = x;~ x \vee (x \wedge y) = x;\,</math>
* [[Absorption (mathematics)]]: <math>x \wedge (x \vee y) = x;~ x \vee (x \wedge y) = x;\,</math>


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


:<math>a \vee b = b \Leftrightarrow a \le b \Leftrightarrow a \wedge b = a . \,</math>
:<math>a \vee b = b \Leftrightarrow a \le b \Leftrightarrow a \wedge b = a . \,</math>
===Semi-modular lattices===
An '''upper semi-modular lattice''' satisfies the further property:
* [[Upper semi-modularity]]: If <math>a \wedge b \prec a</math> then <math>b \prec a \vee b</math>.
Dually, a '''lower semi-modular lattice''' satisfies
* [[Lower semi-modularity]]: If <math>b \prec a \vee b</math> then <math>a \wedge b \prec a</math>.
The ''Jordan-Dedekind chain condition'' holds in a semi-modular (lower or upper) lattice: all finite maximal chains between two given elements have the same length.


===Modular lattices===
===Modular lattices===
Line 69: Line 99:
* [[Modularity]]: If <math>x \ge y</math> then <math>x \wedge (y \vee z) = y \vee (x \wedge z) . \,</math>
* [[Modularity]]: If <math>x \ge y</math> then <math>x \wedge (y \vee z) = y \vee (x \wedge z) . \,</math>


A pair of intervals of the form <math>[a\vee b,b]</math> and <math>[a,a\wedge b]</math> are said to be ''in perspective''.  In a modular lattice, perspective intervals are isomorphic.
A pair of intervals of the form <math>[b,a\vee b]</math> and <math>[a\wedge b,a]</math> are said to be ''in perspective''.  In a modular lattice, perspective intervals are isomorphic: the maps <math>x \mapsto a\vee x</math> and <math>y \mapsto y\wedge b</math> are order-isomorphisms.
 
Modularity implies both forms of semi-modularity and hence the Jordan-Dedekind chain condition.  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 dimension is related to the join and meet in a modular lattice by
 
:<math>d(x) + d(y) = d(x \wedge y) + d(x \vee y) .\,</math>


===Distributive lattices===
===Distributive lattices===
Line 78: Line 114:


===Complemented lattices===
===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 '''complete lattice''' is one in which every set has a supremum and an infimum.  In particular the lattice must be a bounded order, with 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 <math>a \wedge b = \mathbf{0}</math> and <math>a \vee b = \mathbf{1}</math>.  If the lattice is distributive then the ''complement'' of ''a'', denoted <math>\bar a</math> or <math>a'</math> is unique.
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 <math>a \wedge b = \mathbf{0}</math> and <math>a \vee b = \mathbf{1}</math>.  If the lattice is distributive then the ''complement'' of ''a'', denoted <math>\bar a</math> or <math>a'</math> is unique.


===Subjunctive lattice===
A '''subjunctive''' or '''Brouwerian lattice''' has the property that for any two elements ''a'',''b'', there exists an element ''a''→''b'' with the properties
:<math>x \wedge a \le b \Leftrightarrow x \le (a\rarr b) .\,</math>
This element is the '''pseudo-complement''' of ''a'' '''relative to''' ''b'' and is unique.  We note that ''a''→''a'' = '''1'''.
A '''Heyting algebra''' is a bounded subjunctive lattice.  The '''pseudo-complement''' ~''a'' is the relative pseudo-complement ''a''→'''0'''.  We have <math>\sim a \wedge a = \mathbf{0}</math> but <math>\sim a \vee a</math> need not be '''1'''.  A Heyting algebra is necessarily distributive.
===Boolean lattice===
A '''Boolean lattice''' is a distributive complemented lattice, and hence with a uniquely defined complement.
A '''Boolean lattice''' is a distributive complemented lattice, and hence with a uniquely defined complement.
A Boolean lattice is subjunctive.
===Lattice homomorphisms===
A '''lattice homomorphism''' is a map between lattices which preserves join and meet.  It is necessarily montone, but not every monotone map is a lattice homomorphism.  A lattice isomorphism is just an order isomorphism.
===Ideals and filters===
An '''ideal''' in a lattice is a non-empty join-closed downward-closed subset.  A '''filter''' is a non-empty meet-closed upward-closed subset.  Every cut defines an ideal, but not conversely.  The downset <math>{\downarrow} a = \{ x \le a \}</math> is the ''principal ideal'' on ''a''; the upset <math>{\uparrow} a = \{ x \ge a \}</math> is the ''principal filter'' on ''a''.

Latest revision as of 18:23, 17 January 2010

This article is a stub and thus not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

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 ,; ,; , are also common. We also use the traditional notational convention that .

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 (weak) partial order, a relation ≤ on a set satisfying:

  • Reflexive:
  • Antisymmetric:
  • Transitive:

The strict form < of an order satisfies the variant conditions:

  • Irreflexive:
  • Antisymmetric:
  • Transitive:

Weak and strict partial orders are equivalent via the following translations:

if and only if or
if and only if and

A reflexive and transitive relation is called a preorder. In a preorder the relation defined by is an equivalence relation, and the preorder gives rise to a partial order on the corresponding equivalence classes.

Total order

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

Associated concepts

If ab in an ordered set (X,<) then the interval

We say that b covers a if the interval : that is, there is no x strictly between a and b. We write or .

Let S be a subset of a ordered set (X,<). An upper bound for S is an element U of X such that for all elements . A lower bound for S is an element L of X such that for all elements . 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 directed set is one in which any finite set has an upper bound.

The set of upper bounds for S is denoted UB(S); the set of lower bounds is LB(S).

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 or 1; a minimum element for the whole set may be termed bottom, zero or false and denoted or 0. An ordered set with a 0 and 1 is bounded.

In a bounded order, an atom is an element that covers 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.

A subset S of an ordered set X is downward closed or a lower set if it satisfies

Similarly, a subset S of an ordered set X is upward closed or an upper set if it satisfies

A (Dedekind) cut in an ordered set X is a pair (A,B) of subsets of X such that B is the set of upper bounds of A and A is the set of lower bounds of B: B = UB(A) and A = LB(B). We may equivalently define a cut by A = LB(UB(A)), whereas in general A is merely a subset of LB(UB(A)).

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 then . A monotone decreasing function similarly reverses the order. A function is strictly monotonic if implies : 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 has a supremum and an infimum. We call the supremum the join and the infimum the meet of the elements a and b, denoted and respectively.

The join and meet satisfy the properties:

  • Idempotence:
  • Commutativity:
  • Associativity:
  • Absorption (mathematics):

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

Semi-modular lattices

An upper semi-modular lattice satisfies the further property:

  • Upper semi-modularity: If then .

Dually, a lower semi-modular lattice satisfies

  • Lower semi-modularity: If then .

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

Modular lattices

A modular lattice satisfies the further property:

  • Modularity: If then

A pair of intervals of the form and are said to be in perspective. In a modular lattice, perspective intervals are isomorphic: the maps and are order-isomorphisms.

Modularity implies both forms of semi-modularity and hence the Jordan-Dedekind chain condition. 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 dimension is related to the join and meet in a modular lattice by

Distributive lattices

A distributive lattice satisfies the further property:

  • Distributivity:

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 be a bounded order, with 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 and . If the lattice is distributive then the complement of a, denoted or is unique.

Subjunctive lattice

A subjunctive or Brouwerian lattice has the property that for any two elements a,b, there exists an element ab with the properties

This element is the pseudo-complement of a relative to b and is unique. We note that aa = 1.

A Heyting algebra is a bounded subjunctive lattice. The pseudo-complement ~a is the relative pseudo-complement a0. We have but need not be 1. A Heyting algebra is necessarily distributive.

Boolean lattice

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

A Boolean lattice is subjunctive.

Lattice homomorphisms

A lattice homomorphism is a map between lattices which preserves join and meet. It is necessarily montone, but not every monotone map is a lattice homomorphism. A lattice isomorphism is just an order isomorphism.

Ideals and filters

An ideal in a lattice is a non-empty join-closed downward-closed subset. A filter is a non-empty meet-closed upward-closed subset. Every cut defines an ideal, but not conversely. The downset is the principal ideal on a; the upset is the principal filter on a.