This is an old revision of this page, as edited by Miguel~enwiki (talk | contribs) at 09:15, 4 May 2002 (*some rearrangement; posets as graphs; defined upper and lower bound). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
Revision as of 09:15, 4 May 2002 by Miguel~enwiki (talk | contribs) (*some rearrangement; posets as graphs; defined upper and lower bound)(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)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. Every poset (X,<=) has a unique dual poset (X,>=).
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).
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. This can be generalized: any discrete poset can be represented by a directed graph, where the nodes are elements of the poset and there is an directed edge a ->- b if, end 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 S has an upper bound u in X if s<=u for any s in S. Similarly, l is a lower bound of S if u<=s for all s in S. Upper and lower bounds of S may or may not exist, and they may or may not be in S.
Special cases of partially ordered sets are
- totally ordered sets, 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.
- lattices, where any two elements have both a greatest lower bound (infimum) and a least upper bound (supremum). Lattices are considered algebraic structures with the operations "sup" and "inf".
A related concept is that of a directed set, where every finite subset has an upper bound. Direvted sets are not required to have the antisymmetric property, so they are not necessarily posets.
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 best-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.