| Revision as of 17:58, 6 April 2003 editAxelBoldt (talk | contribs)Administrators44,502 edits +well-order link← Previous edit |
Latest revision as of 18:59, 2 September 2024 edit undoTule-hog (talk | contribs)Extended confirmed users4,451 edits add rcat |
| (31 intermediate revisions by 18 users not shown) |
| Line 1: |
Line 1: |
|
|
#REDIRECT ] |
|
In ], a '''partial order''' ≤ on a ] ''X'' is a ] that is reflexive, ] and transitive, i.e., it holds for all ''a'', ''b'' and ''c'' in ''X'' that: |
|
|
|
|
|
|
|
{{Rcatsh| |
|
:''a'' ≤ ''a'' (reflexivity) |
|
|
|
{{R to section}} |
|
: if ''a'' ≤ ''b'' and ''b'' ≤ ''c'' then ''a'' ≤ ''c'' (transitivity) |
|
|
|
{{R with Wikidata item}} |
|
: if ''a'' ≤ ''b'' and ''b'' ≤ ''a'' then ''a'' = ''b'' (antisymmetry) |
|
|
|
{{R with history}} |
|
|
}} |
|
|
|
|
|
|
{{Authority control}} |
|
A set with a partial order on it is called a '''partially ordered set''', '''poset''', or, often, simply an '''ordered set'''. |
|
|
|
|
|
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 ''Hasse diagrams'', 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 S'' if the only element ''s'' of ''S'' with ''m''≤''s'' is ''s''=''m''. |
|
|
* the element ''u'' of ''X'' is ''an upper bound for S'' if ''s''≤''u'' for all ''s'' in ''S'' |
|
|
* the element ''l'' is the ''largest element in S'' 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 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. |
|
|
*], 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". |
|
|
*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. |
|
|
|
|
|
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 Alexandrov topology, 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 Scott topology. |
|
|
|
|
|
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. |
|