| Revision as of 00:34, 9 January 2003 edit131.183.85.71 (talk) math mode← Previous edit |
Latest revision as of 18:59, 2 September 2024 edit undoTule-hog (talk | contribs)Extended confirmed users4,451 edits add rcat |
| (41 intermediate revisions by 20 users not shown) |
| Line 1: |
Line 1: |
|
|
#REDIRECT ] |
|
A '''partial order''' <math>\leq</math> on a ] ''X'' is a ] that is '''reflexive''', '''antisymmetric''' and '''transitive''', i.e., it holds for all ''a'', ''b'' and ''c'' in ''X'' that: |
|
|
* (reflexivity) ''a'' <= ''a'' |
|
|
* (antisymmetry) if ''a'' <= ''b'' and ''b'' <= ''a'' then ''a'' = ''b'' |
|
|
* (transitivity) if ''a'' <= ''b'' and ''b'' <= ''c'' then ''a'' <= ''c'' |
|
|
|
|
|
|
|
{{Rcatsh| |
|
A set with a partial order on it is called a '''partially ordered set''', or '''poset'''. We can then also define an irreflexive relation <, where ''a'' < ''b'' if and only if ''a'' <= ''b'' and ''a'' ≠ ''b''. Every poset (''X'',<=) has a unique dual poset (''X'',>=), where we define ''a'' >= ''b'' if and only if ''b'' <= ''a''. |
|
|
|
{{R to section}} |
|
|
{{R with Wikidata item}} |
|
|
{{R with history}} |
|
|
}} |
|
|
|
|
|
|
{{Authority control}} |
|
Examples of partial orders include implications and inclusions ("is a subset of" and the more general "is a subobject of" in the sense of ]) as well as ] of ]s and ]s. |
|
|
|
|
|
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 elements of the poset and there is a directed path from ''a'' to ''b'' if and only if ''a''<=''b''. |
|
|
|
|
|
A subset of a partially ordered set inherits a partial order. New partially ordered sets can also be constructed by cartesian products, disjoint unions and other set-theoretic operations. |
|
|
|
|
|
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. |
|
|
|
|
|
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 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 ]. 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. |
|