| Completeness (order Theory) |
Article Index for Completeness |
Information AboutCompleteness (order Theory) |
|
The motivation for considering completeness properties derives from the great importance of suprema (least upper bounds, joins, "") and infima (greatest lower bounds, meets, "") to the theory of partial orders. Finding a supremum means to single out one distinguished least element from the set of upper bounds. On the one hand, these special elements often embody certain concrete properties that are interesting for the given application (such as being the Least Common Multiple of a set of numbers or the Union of a collection of sets). On the other hand, the knowledge that certain types of subsets are guaranteed to have suprema or infima enables us to consider the computation of these elements as ''total operations'' on a partially ordered set. For this reason, posets with certain completeness properties can often be described as Algebraic Structure s of a certain kind. In addition, studying the properties of the newly obtained operations yields further interesting subjects. TYPES OF COMPLETENESS PROPERTIES All completeness properties are described along a similar scheme: one describes a certain class of subsets of a partial order that are required to have a supremum or infimum. Hence every completeness property has its Dual , obtained by inverting the order-dependent definitions in the given statement. Some of the notions are usually not dualized while others may be self-dual (i.e. equivalent to their dual statements). Least and greatest elements The easiest example of a supremum is the empty one, i.e. the supremum of the Empty Set . By definition, this is the least element among all elements that are greater than each member of the empty set. But this is just the Least Element of the whole poset. Other common names for the least element are '''bottom''' and '''zero''' (0). The dual notion, the empty lower bound, is the ''' Greatest Element ''', '''top''', or '''unit''' (1). Posets that have a bottom are sometimes called pointed, while posets with a top are called '''unital''' or '''topped'''. An order that has both a least and a greatest element is '''bounded'''. However, this should not be confused with the notion of ''bounded completeness'' given below. Finite completeness Further simple completeness conditions arise from the consideration of all non-empty finite sets. An order in which all finite sets have both a supremum and an infimum is called a Lattice . It is easy to see that it suffices to require that all suprema and infima of ''two'' elements exist to obtain all finite ones. A straightforward Induction shows that every finite non-empty supremum/infimum can be decomposed into a finite number of binary suprema/infima. Thus the central operations of lattices are binary suprema ^ and infima v. It is in this context that the terms meet for ^ and join for v are most common. A poset in which only non-empty finite suprema are known to exist is therefore called a Join-semilattice . The dual notion is ''' Meet-semilattice '''. Further completeness conditions The strongest form of completeness is the existence of all suprema and all infima. The posets with this property are the Complete Lattice s. However, using the given order, one can restrict to further classes of (possibly infinite) subsets, that do not yield this strong completeness at once. If all Directed Subsets of a poset have a supremum, then the order is a Directed Complete Partial Order or '''dcpo'''. These are especially important in Domain Theory . The seldom considered dual notion of a dcpo is the '''filtered complete poset'''. Dcpos with a least element ("pointed dcpos") are called ''' Complete Partial Order ''' or '''cpo'''. If every subset that has ''some'' upper bounds has also a least upper bound, then the respective poset is called Bounded Complete . The term is used widely with this definition that focuses on suprema and there is no common name for the dual property. However, bounded completeness can be expressed in terms of other completeness conditions that are easily dualized (see below). Although concepts with the names "complete" and "bounded" were already defined, confusion is unlikely to occur since one would rarely speak of a "bounded complete poset" when meaning a "bounded cpo" (which is just a "cpo with greatest element"). Likewise, "bounded complete lattice" is almost unambiguous, since one would not state the boundedness property for complete lattices, where it is implied anyway. Also note that the empty set usually has upper bounds (if the poset is non-empty) and thus a bounded complete poset has a least element. One may also consider the subsets of a poset which are Totally Ordered , i.e. the chains. If all chains have a supremum, the order is called chain-complete (sometimes also "omega-complete", written '''ω-complete'''). Again, this concept is rarely needed in the dual form. RELATIONSHIPS BETWEEN COMPLETENESS PROPERTIES It was already observed that binary meets/joins yield all non-empty finite meets/joins. Likewise, many other (combinations) of the above conditions are equivalent.
:: A poset is chain-complete iff it is a dcpo. COMPLETIONS OF DOMAINS According to Clinger {Link without Title} , often there is an intuitive sense in which some elements of partially ordered sets are finite. ''E.g.'', in Denotational Semantics , they may be partial functions defined for only finitely many values or they may be finite partial computations in the Actor Model . This sense of finiteness lies behind the following abstract definition: :Let (''D'', ≤) be a partially ordered set. An element ''x''∈''D'' is ''isolated'' if and only if whenever ''A''⊆''D'' is directed, ∪''A'' exists and ''x''≤∪''A'', there exists ''a''∈''A'' with ''x''≤''a''. In other words, ''x'' is isolated if one must go through ''x'' in order to get up to or above ''x'' via the limit process. As examples, the finite sets are the isolated elements of the power set of ω ordered by inclusion; the ordinal ω+1 is isolated in the set of countable ordinals under the usual ordering. The least element of a partially ordered set is always isolated provided it exists. 0 is the least element of the nonnegative rationals under the usual ordering, and it is also the only isolated element. The entire set of rationals has no isolated elements under the usual ordering. For purposes of programming language semantics, partially ordered sets with least elements form too general a category. The partially ordered sets of greatest interest for computer science are those whose isolated elements are ''dense'' in the sense that every element is a least upper bound of a countable set of isolated elements. To avoid transfinite induction, and to make directed completeness equivalent to ω-completeness, it is convenient to assume also that there are only countably many isolated elements which motivates the following definition. :Definition. A domain is a partially ordered set (''D'', ≤) such that :#''D'' has a least element Λ :#Every element of ''D'' is the least upper bound of a countable increasing sequence of isolated elements. :#The isolated elements of ''D'' are countable. The above definition is a generalization of the traditional definition. The traditional definition requires also that ''D'' be ω-complete, so that ω-continuous functions from ''D'' to ''D'' will have fixed points. An ω-complete domain is ''complete'' in the sense that every directed subset has a least upper bound. An ω-complete domain is also known as a countably algebraic complete partial order 1978 . Every domain ''D'' can be embedded in an ω-complete domain ''completion'' (called the ω-''completion'' or simply the ''completion'' of ''D'') that is, in a precise sense, the smallest ω-complete domain containing ''D''. The isolated elements of ''completion''[''D'' are precisely the isolated elements of ''D'', but in general ''completion'' contains limit points that are not found in ''D''. ''completion''[''D'' is uniquely determined up to isomorphism. In Clinger it is shown that for any domain ''D'' the power domain of ''D'' is isomorphic to the power domain of ''completion''[''D'' . So why not use ω-complete domains only, as is traditional? Because the power domain is interpreted with reference to the domain from which it is built. As explained in Denotational Semantics Of Concurrency , the underlying domain is incomplete in Actor Semantics . COMPLETENESS IN TERMS OF UNIVERSAL ALGEBRA As explained above, the presence of certain completeness conditions allows to regard the formation of certain suprema and infima as total operations of an ordered set. It turns out that in many cases it is possible to characterize completeness solely by considering appropriate , Lattice , Heyting Algebra , and Boolean Algebra . Note that the latter two structures extend the application of these principles beyond mere completeness requirements by introducing an additional operation of ''negation''. COMPLETENESS IN TERMS OF ADJUNCTIONS Another interesting and way to characterize completeness properties is provided through the concept of (monotone) Galois Connection s, i.e. adjunctions between partial orders. In fact this approach offers additional insights both in the nature of many completeness properties and in the importance of Galois connections for order theory. The general observation on which this reformulation of completeness is based is that the construction of certain suprema or infima provides left or right adjoint parts of suitable Galois connections.
Another simple mapping is the function ''q'': ''X'' → (''X'' x ''X'') given by ''q''(''x'') = (''x'', ''x''). Naturally, the intended ordering relation for (''X'' x ''X'') is just the usual -- another important special class of partial orders. Further completeness statements can be obtained by exploiting suitable and Distributivity (order Theory) . The considerations in this section suggest a reformulation of (parts of) order theory in terms of . SEE ALSO Limit-preserving Function (order Theory) on the ''preservation'' of existing suprema/infima. NOTES |
|
|