Editing Order theory (section)

=== Special elements within an order ===
In a partially ordered set there may be some elements that play a special role. The most basic example is given by the '''least element''' of a [[poset]]. For example, 1 is the [[least element]] of the positive integers and the [[empty set]] is the least set under the subset order. Formally, an element ''m'' is a least element if:

:  ''m'' ≤ ''a'', for all elements ''a'' of the order.

The notation 0 is frequently found for the least element, even when no numbers are concerned. However, in orders on sets of numbers, this notation might be inappropriate or ambiguous, since the number 0 is not always least. An example is given by the above divisibility order |, where 1 is the least element since it divides all other numbers. In contrast, 0 is the number that is divided by all other numbers. Hence it is the '''greatest element''' of the order.  Other frequent terms for the least and greatest elements is '''bottom''' and '''top''' or '''zero''' and '''unit'''.

Least and [[greatest element]]s may fail to exist, as the example of the real numbers shows. But if they exist, they are always unique. In contrast, consider the divisibility relation | on the set {2,3,4,5,6}. Although this set has neither top nor bottom, the elements 2, 3, and 5 have no elements below them, while 4, 5 and 6 have none above. Such elements are called '''minimal''' and '''maximal''', respectively. Formally, an element ''m'' is [[minimal element|minimal]] if:

: ''a'' ≤ ''m'' implies ''a'' = ''m'', for all elements ''a'' of the order.

Exchanging ≤ with ≥ yields the definition of [[maximal element|maximality]]. As the example shows, there can be many maximal elements and some elements may be both maximal and minimal (e.g. 5 above). However, if there is a least element, then it is the only minimal element of the order. Again, in infinite posets maximal elements do not always exist - the set of all ''finite'' subsets of a given infinite set, ordered by subset inclusion, provides one of many counterexamples. An important tool to ensure the existence of maximal elements under certain conditions is '''[[Zorn's Lemma]]'''.

Subsets of partially ordered sets inherit the order. We already applied this by considering the subset {2,3,4,5,6} of the natural numbers with the induced divisibility ordering. Now there are also elements of a poset that are special with respect to some subset of the order. This leads to the definition of '''[[upper bound]]s'''. Given a subset ''S'' of some poset ''P'', an upper bound of ''S'' is an element ''b'' of ''P'' that is above all elements of ''S''. Formally, this means that

: ''s'' ≤ ''b'', for all ''s'' in ''S''.

Lower bounds again are defined by inverting the order. For example, −5 is a lower bound of the natural numbers as a subset of the integers. Given a set of sets, an upper bound for these sets under the subset ordering is given by their [[union (set theory)|union]]. In fact, this upper bound is quite special: it is the smallest set that contains all of the sets. Hence, we have found the '''[[least upper bound]]''' of a set of sets. This concept is also called '''supremum''' or '''join''', and for a set ''S'' one writes sup(''S'') or <math>\bigvee S</math> for its least upper bound. Conversely, the '''[[greatest lower bound]]''' is known as '''[[infimum]]''' or '''meet''' and denoted inf(''S'') or <math>\bigwedge S</math>. These concepts play an important role in many applications of order theory. For two elements ''x'' and ''y'', one also writes <math>x\vee y</math> and <math>x\wedge y</math> for sup({''x'',''y''}) and inf({''x'',''y''}), respectively.

For example, 1 is the infimum of the positive integers as a subset of integers.

For another example, consider again the relation | on natural numbers. The least upper bound of two numbers is the smallest number that is divided by both of them, i.e. the [[least common multiple]] of the numbers. Greatest lower bounds in turn are given by the [[greatest common divisor]].