Editing Domain theory (section)

=== Directed sets as converging specifications ===
As mentioned before, domain theory deals with [[partially ordered set]]s to model a domain of computation. The goal is to interpret the elements of such an order as ''pieces of information'' or ''(partial) results of a computation'', where elements that are higher in the order extend the information of the elements below them in a consistent way. From this simple intuition it is already clear that domains often do not have a [[greatest element]], since this would mean that there is an element that contains the information of ''all'' other elements—a rather uninteresting situation.

A concept that plays an important role in the theory is that of a '''[[directed set|directed subset]]''' of a domain; a directed subset is a non-empty subset of the order in which any two elements have an [[upper bound]] that is an element of this subset. In view of our intuition about domains, this means that any two pieces of information within the directed subset are ''consistently'' extended by some other element in the subset. Hence we can view directed subsets as ''consistent specifications'', i.e. as sets of partial results in which no two elements are contradictory. This interpretation can be compared with the notion of a [[convergent sequence]] in [[Mathematical analysis|analysis]], where each element is more specific than the preceding one. Indeed, in the theory of [[metric space]]s, sequences play a role that is in many aspects analogous to the role of directed sets in domain theory.

Now, as in the case of sequences, we are interested in the ''limit'' of a directed set. According to what was said above, this would be an element that is the most general piece of information that extends the information of all elements of the directed set, i.e. the unique element that contains ''exactly'' the information that was present in the directed set, and nothing more. In the formalization of order theory, this is just the '''[[least upper bound]]''' of the directed set. As in the case of the limit of a sequence, the least upper bound of a directed set does not always exist.

Naturally, one has a special interest in those domains of computations in which all consistent specifications ''converge'', i.e. in orders in which all directed sets have a least upper bound. This property defines the class of '''[[directed complete partial order|directed-complete partial order]]s''', or '''dcpo''' for short. Indeed, most considerations of domain theory do only consider orders that are at least directed complete.

From the underlying idea of partially specified results as representing incomplete knowledge, one derives another desirable property: the existence of a '''[[least element]]'''. Such an element models that state of no information—the place where most computations start. It also can be regarded as the output of a computation that does not return any result at all.