| Revision as of 15:51, 25 February 2002 editConversion script (talk | contribs)10 editsm Automated conversion← Previous edit | Revision as of 07:46, 4 May 2002 edit undoMiguel~enwiki (talk | contribs)3,710 editsNo edit summaryNext edit → | ||
| Line 6: | Line 6: | ||
| 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''. | 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''. | ||
| Examples of partial orders include implications and inclusions ("is a subset of" and the more general "is a subobject of" in the sense of ]). |
Examples of partial orders include implications and inclusions ("is a subset of" and the more general "is a subobject of" in the sense of ]). | ||
| Special cases of partially ordered sets are | |||
| *], is also a partially ordered set, for example <= on the real numbers. | |||
| *A poset where any two elements have both a greatest lower bound and a least upper bound forms an algebraic structure called a ]. | |||
| Finite posets are most easily visualized as ''Hasse diagrams'', that is, graphs where the vertices are the elements of the poset and the ordering relation is indicated by edges 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. | Finite posets are most easily visualized as ''Hasse diagrams'', that is, graphs where the vertices are the elements of the poset and the ordering relation is indicated by edges 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. | ||
| Line 12: | Line 16: | ||
| New partially ordered sets can be constructed from other partially ordered sets by cartesian products, disjoint unions and so on. | New partially ordered sets can be constructed from other partially ordered sets by cartesian products, disjoint unions and so on. | ||
| Every poset (''X'',<=) has a unique dual poset (''X'',>=). | |||
| A partially ordered set is ''complete'' if any increasing chain of elements has a least upper bound. Various types of complete partially ordered sets are used in, for example, ]. The most well-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. | A partially ordered set is ''complete'' if any increasing chain of elements has a least upper bound. Various types of complete partially ordered sets are used in, for example, ]. The most well-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. | ||
Revision as of 07:46, 4 May 2002
A partial order <= on a set X is a binary relation 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
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.
Examples of partial orders include implications and inclusions ("is a subset of" and the more general "is a subobject of" in the sense of category theory).
Special cases of partially ordered sets are
- totally ordered sets, is also a partially ordered set, for example <= on the real numbers.
- A poset where any two elements have both a greatest lower bound and a least upper bound forms an algebraic structure called a lattice.
Finite posets are most easily visualized as Hasse diagrams, that is, graphs where the vertices are the elements of the poset and the ordering relation is indicated by edges 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.
New partially ordered sets can be constructed from other partially ordered sets by cartesian products, disjoint unions and so on.
Every poset (X,<=) has a unique dual poset (X,>=).
A partially ordered set is complete if any increasing chain of elements has a least upper bound. Various types of complete partially ordered sets are used in, for example, program semantics. The most well-known type of complete partially ordered sets are the Scott-Ershov domains. These structures are important in that they constitute a cartesian closed category 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 topology, 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.
See also: