| Revision as of 08:32, 1 March 2004 editAltenmann (talk | contribs)Autopatrolled, Extended confirmed users, Pending changes reviewers218,011 editsm ]← Previous edit |
Revision as of 17:39, 13 March 2004 edit undoMarkus Krötzsch (talk | contribs)Extended confirmed users703 edits moved main page to "order theory", added redirectNext edit → |
| Line 1: |
Line 1: |
|
|
#REDIRECT |
|
] ] |
|
|
|
|
|
In ], a '''partial order''' ≤ on a ] ''X'' is a ] that is reflexive, ], and ], i.e., it holds for all ''a'', ''b'' and ''c'' in ''X'' that: |
|
|
|
|
|
:''a'' ≤ ''a'' (reflexivity) |
|
|
: if ''a'' ≤ ''b'' and ''b'' ≤ ''c'' then ''a'' ≤ ''c'' (transitivity) |
|
|
: if ''a'' ≤ ''b'' and ''b'' ≤ ''a'' then ''a'' = ''b'' (antisymmetry) |
|
|
|
|
|
A set with a partial order on it is called a '''partially ordered set''', '''poset''', or, often, simply an '''ordered set'''. '''Order theory''' is the branch of mathematics that studies these structures. Misplaced Pages contains both a ] which gives a structured guide to the field, and an ] that serves as a look-up for the relevant definitions. |
|
|
|
|
|
Examples of posets include the ]s and ]s with their ordinary ordering, ]s of a given set ordered by ], ]s ordered lexicographically (as in a phone book), and ]s ordered by ]. |
|
|
|
|
|
Finite posets are most easily visualized as "]s", that is, ]s where the ] are the elements of the poset and the ordering relation is indicated by ]s and the relative positioning of the vertices. The element ''x'' is smaller than ''y'' if and only if there exists a path from ''x'' to ''y'' always going upwards. This can be generalized: any poset can be represented by a ], where the nodes are the elements of the poset and there is a directed path from ''a'' to ''b'' if and only if ''a''≤''b''. |
|
|
|
|
|
If ''S'' is a subset of the poset ''X'', we say that |
|
|
* the element ''m'' of ''S'' is a ''maximal'' element of <i>S</i> if the only element ''s'' of ''S'' with ''m''≤''s'' is ''s''=''m''. |
|
|
* the element ''u'' of ''X'' is an ''upper bound'' for <i>S</i> if ''s''≤''u'' for all ''s'' in ''S'' |
|
|
* the element ''l'' is the ''largest'' (or ''greatest'', or ''top'') element in <i>S</i> if ''l'' is an upper bound for ''S'' and an element of ''S''. |
|
|
There can be many maximal elements but at most one largest element of ''S''; if a largest element exists, then it is the unique maximal element of ''S''. ''Minimal'' elements, ''lower bounds'' and ''smallest'' (''least'', ''bottom'') elements are defined analogously. |
|
|
|
|
|
A subset of a partially ordered set inherits a partial order. New partially ordered sets can also be constructed by ]s, disjoint unions and other set-theoretic operations. Since the ] of partial orders on a given set ''X'' is again a partial order on ''X'', every relation ''R'' on ''X'' generates a unique partial order on ''X'', the smallest partial order containing ''R''. Every poset (''X'',≤) has a unique dual poset (''X'',≥), where we define ''a'' >= ''b'' if and only if ''b'' ≤ ''a''. Every poset also gives rise to an irreflexive relation <, where ''a'' < ''b'' if and only if ''a'' ≤ ''b'' and ''a'' ≠ ''b''. |
|
|
|
|
|
Special cases of partially ordered sets are |
|
|
*], where for any pair of elements ''a'',''b'', either ''a''≤''b'' or ''b''≤''a''. For example the real numbers with the usual order relation ≤ form a totally ordered set. Another name for totally ordered set is "linearly ordered set". A '''chain''' is a linearly ordered subset of a poset. |
|
|
*], where all non-empty subsets have smallest elements. |
|
|
*]s, where any two elements have both a greatest lower bound (infimum) and a least upper bound (supremum). Lattices are considered ] with the operations "sup" and "inf". |
|
|
*]s, which are lattices with additional properties that allow for the definition of a ]. |
|
|
*bounded posets, which have a largest and a smallest element. |
|
|
|
|
|
A related concept is that of a ], where every finite subset has an upper bound. Directed sets are not required to have the antisymmetric property, so they are not necessarily posets. However, if one speaks of a directed set as a subset of some partially ordered set, then antisymmetry is inherited. |
|
|
|
|
|
A partially ordered set is ''complete'' if every one of its subsets has a least upper bound and a greatest lower bound. Various types of complete partially ordered sets are used in, for example, ]. The best-known type of complete partially ordered sets are the ]s. These structures are important in that they constitute a ] and in that they provide a natural theory of approximations. |
|
|
That the class of Scott-Ershov domains is cartesian closed category enables the solution of so-called domain equations, e.g., ''D'' = , where the right-hand side denotes the space of all continuous functions on ''D''. |
|
|
|
|
|
Partially ordered sets can be given a ], for example, the ], consisting of all upwards closed subsets. A subset ''U'' of a partially ordered set is ''upwards closed'' if ''x'' in ''U'' and ''x'' ≤ ''y'' implies that ''y'' belongs to ''U''. For special types of partially ordered sets other topologies may be more interesting. For example, the natural topology on Scott-Ershov domains is the ]. |
|
|
|
|
|
A poset is '''locally finite''' if every closed ] in it is ]. Locally finite posets give rise to ]s which in turn can be used to define the Euler characteristic of finite bounded posets. |
|