Greatest element and least element

Last updated

Hasse diagram of the set
P
{\displaystyle P}
of divisors of 60, partially ordered by the relation "
x
{\displaystyle x}
divides
y
{\displaystyle y}
". The red subset
S
=
{
1
,
2
,
3
,
5
,
6
,
10
,
15
,
30
}
{\displaystyle S=\{1,2,3,5,6,10,15,30\}}
has one greatest element, viz. 30, and one least element, viz. 1. These elements are also maximal and minimal elements, respectively, of the red subset. Lattice of the divisors of 60, ordered by divisibility; with divisors of 30 in red.svg
Hasse diagram of the set of divisors of 60, partially ordered by the relation " divides ". The red subset has one greatest element, viz. 30, and one least element, viz. 1. These elements are also maximal and minimal elements, respectively, of the red subset.

In mathematics, especially in order theory, the greatest element of a subset of a partially ordered set (poset) is an element of that is greater than every other element of . The term least element is defined dually, that is, it is an element of that is smaller than every other element of

Contents

Definitions

Let be a preordered set and let An element is said to be a greatest element of if and if it also satisfies:

for all

By switching the side of the relation that is on in the above definition, the definition of a least element of is obtained. Explicitly, an element is said to be a least element of if and if it also satisfies:

for all

If is also a partially ordered set then can have at most one greatest element and it can have at most one least element. Whenever a greatest element of exists and is unique then this element is called the greatest element of . The terminology the least element of is defined similarly.

If has a greatest element (resp. a least element) then this element is also called a top (resp. a bottom) of

Relationship to upper/lower bounds

Greatest elements are closely related to upper bounds.

Let be a preordered set and let An upper bound of in is an element such that and for all Importantly, an upper bound of in is not required to be an element of

If then is a greatest element of if and only if is an upper bound of in and In particular, any greatest element of is also an upper bound of (in ) but an upper bound of in is a greatest element of if and only if it belongs to In the particular case where the definition of " is an upper bound of in " becomes: is an element such that and for all which is completely identical to the definition of a greatest element given before. Thus is a greatest element of if and only if is an upper bound of in .

If is an upper bound of in that is not an upper bound of in (which can happen if and only if ) then can not be a greatest element of (however, it may be possible that some other element is a greatest element of ). In particular, it is possible for to simultaneously not have a greatest element and for there to exist some upper bound of in .

Even if a set has some upper bounds, it need not have a greatest element, as shown by the example of the negative real numbers. This example also demonstrates that the existence of a least upper bound (the number 0 in this case) does not imply the existence of a greatest element either.

Contrast to maximal elements and local/absolute maximums

In the above divisibility order, the red subset
S
=
{
1
,
2
,
3
,
4
}
{\displaystyle S=\{1,2,3,4\}}
has two maximal elements, viz. 3 and 4, none of which is greatest. It has one minimal element, viz. 1, which is also its least element. Lattice of the divisibility of 60 narrow 1,2,3,4.svg
In the above divisibility order, the red subset has two maximal elements, viz. 3 and 4, none of which is greatest. It has one minimal element, viz. 1, which is also its least element.

A greatest element of a subset of a preordered set should not be confused with a maximal element of the set, which are elements that are not strictly smaller than any other element in the set.

Let be a preordered set and let An element is said to be a maximal element of if the following condition is satisfied:

whenever satisfies then necessarily

If is a partially ordered set then is a maximal element of if and only if there does not exist any such that and A maximal element of is defined to mean a maximal element of the subset

A set can have several maximal elements without having a greatest element. Like upper bounds and maximal elements, greatest elements may fail to exist.

In a totally ordered set the maximal element and the greatest element coincide; and it is also called maximum; in the case of function values it is also called the absolute maximum, to avoid confusion with a local maximum. [1] The dual terms are minimum and absolute minimum. Together they are called the absolute extrema . Similar conclusions hold for least elements.

Role of (in)comparability in distinguishing greatest vs. maximal elements

One of the most important differences between a greatest element and a maximal element of a preordered set has to do with what elements they are comparable to. Two elements are said to be comparable if or ; they are called incomparable if they are not comparable. Because preorders are reflexive (which means that is true for all elements ), every element is always comparable to itself. Consequently, the only pairs of elements that could possibly be incomparable are distinct pairs. In general, however, preordered sets (and even directed partially ordered sets) may have elements that are incomparable.

By definition, an element is a greatest element of if for every ; so by its very definition, a greatest element of must, in particular, be comparable to every element in This is not required of maximal elements. Maximal elements of are not required to be comparable to every element in This is because unlike the definition of "greatest element", the definition of "maximal element" includes an important if statement. The defining condition for to be a maximal element of can be reworded as:

For all IF (so elements that are incomparable to are ignored) then
Example where all elements are maximal but none are greatest

Suppose that is a set containing at least two (distinct) elements and define a partial order on by declaring that if and only if If belong to then neither nor holds, which shows that all pairs of distinct (i.e. non-equal) elements in are incomparable. Consequently, can not possibly have a greatest element (because a greatest element of would, in particular, have to be comparable to every element of but has no such element). However, every element is a maximal element of because there is exactly one element in that is both comparable to and that element being itself (which of course, is ). [note 1]

In contrast, if a preordered set does happen to have a greatest element then will necessarily be a maximal element of and moreover, as a consequence of the greatest element being comparable to every element of if is also partially ordered then it is possible to conclude that is the only maximal element of However, the uniqueness conclusion is no longer guaranteed if the preordered set is not also partially ordered. For example, suppose that is a non-empty set and define a preorder on by declaring that always holds for all The directed preordered set is partially ordered if and only if has exactly one element. All pairs of elements from are comparable and every element of is a greatest element (and thus also a maximal element) of So in particular, if has at least two elements then has multiple distinct greatest elements.

Properties

Throughout, let be a partially ordered set and let

Sufficient conditions

Top and bottom

The least and greatest element of the whole partially ordered set play a special role and are also called bottom (⊥) and top (⊤), or zero (0) and unit (1), respectively. If both exist, the poset is called a bounded poset. The notation of 0 and 1 is used preferably when the poset is a complemented lattice, and when no confusion is likely, i.e. when one is not talking about partial orders of numbers that already contain elements 0 and 1 different from bottom and top. The existence of least and greatest elements is a special completeness property of a partial order.

Further introductory information is found in the article on order theory.

Examples

Hasse diagram of example 2 KeinVerband.svg
Hasse diagram of example 2

See also

Notes

  1. Of course, in this particular example, there exists only one element in that is comparable to which is necessarily itself, so the second condition "and " was redundant.
  2. If and are both greatest, then and and hence by antisymmetry.
  3. If is the greatest element of and then By antisymmetry, this renders ( and ) impossible.
  4. If is a maximal element, then since is greatest, hence since is maximal.
  5. Only if: see above. If: Assume for contradiction that has just one maximal element, but no greatest element. Since is not greatest, some must exist that is incomparable to Hence cannot be maximal, that is, must hold for some The latter must be incomparable to too, since contradicts 's maximality while contradicts the incomparability of and Repeating this argument, an infinite ascending chain can be found (such that each is incomparable to and not maximal). This contradicts the ascending chain condition.
  6. Let be a maximal element, for any either or In the second case, the definition of maximal element requires that so it follows that In other words, is a greatest element.
  7. If were incomparable, then would have two maximal, but no greatest element, contradicting the coincidence.

Related Research Articles

In mathematics, a directed set is a nonempty set together with a reflexive and transitive binary relation , with the additional property that every pair of elements has an upper bound. In other words, for any and in there must exist in with and A directed set's preorder is called a direction.

In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. Basic examples of ordered fields are the rational numbers and the real numbers, both with their standard orderings.

<span class="mw-page-title-main">Partially ordered set</span> Mathematical set with an ordering

In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable.

In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation on some set , which satisfies the following for all and in :

  1. (reflexive).
  2. If and then (transitive).
  3. If and then (antisymmetric).
  4. or .

In mathematics, the infimum of a subset of a partially ordered set is the greatest element in that is less than or equal to each element of if such an element exists. If the infimum of exists, it is unique, and if b is a lower bound of , then b is less than or equal to the infimum of . Consequently, the term greatest lower bound is also commonly used. The supremum of a subset of a partially ordered set is the least element in that is greater than or equal to each element of if such an element exists. If the supremum of exists, it is unique, and if b is an upper bound of , then the supremum of is less than or equal to b. Consequently, the supremum is also referred to as the least upper bound.

In mathematics, particularly in order theory, an upper bound or majorant of a subset S of some preordered set (K, ≤) is an element of K that is greater than or equal to every element of S. Dually, a lower bound or minorant of S is defined to be an element of K that is less than or equal to every element of S. A set with an upper (respectively, lower) bound is said to be bounded from above or majorized (respectively bounded from below or minorized) by that bound. The terms bounded above (bounded below) are also used in the mathematical literature for sets that have upper (respectively lower) bounds.

<span class="mw-page-title-main">Zorn's lemma</span> Mathematical proposition equivalent to the axiom of choice

Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain necessarily contains at least one maximal element.

<span class="mw-page-title-main">Maximum and minimum</span> Largest and smallest value taken by a function takes at a given point

In mathematical analysis, the maximum and minimum of a function are, respectively, the largest and smallest value taken by the function. Known generically as extremum, they may be defined either within a given range or on the entire domain of a function. Pierre de Fermat was one of the first mathematicians to propose a general technique, adequality, for finding the maxima and minima of functions.

<span class="mw-page-title-main">Maximal and minimal elements</span> Element that is not ≤ (or ≥) any other element

In mathematics, especially in order theory, a maximal element of a subset of some preordered set is an element of that is not smaller than any other element in . A minimal element of a subset of some preordered set is defined dually as an element of that is not greater than any other element in .

Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.

<span class="mw-page-title-main">Tree (set theory)</span>

In set theory, a tree is a partially ordered set (T, <) such that for each tT, the set {sT : s < t} is well-ordered by the relation <. Frequently trees are assumed to have only one root (i.e. minimal element), as the typical questions investigated in this field are easily reduced to questions about single-rooted trees.

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth.

In mathematics, a subset of a preordered set is said to be cofinal or frequent in if for every it is possible to find an element in that is "larger than ".

<span class="mw-page-title-main">Upper set</span> Subset of a preorder that contains all larger elements

In mathematics, an upper set of a partially ordered set is a subset with the following property: if s is in S and if x in X is larger than s, then x is in S. In other words, this means that any x element of X that is to some element of S is necessarily also an element of S. The term lower set is defined similarly as being a subset S of X with the property that any element x of X that is to some element of S is necessarily also an element of S.

<span class="mw-page-title-main">Join and meet</span> Concept in order theory

In mathematics, specifically order theory, the join of a subset of a partially ordered set is the supremum of denoted and similarly, the meet of is the infimum, denoted In general, the join and meet of a subset of a partially ordered set need not exist. Join and meet are dual to one another with respect to order inversion.

In mathematics, a Riesz space, lattice-ordered vector space or vector lattice is a partially ordered vector space where the order structure is a lattice.

<span class="mw-page-title-main">Ordered vector space</span> Vector space with a partial order

In mathematics, an ordered vector space or partially ordered vector space is a vector space equipped with a partial order that is compatible with the vector space operations.

<span class="mw-page-title-main">Dedekind–MacNeille completion</span> Smallest complete lattice containing a partial order

In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed it, and after Richard Dedekind because its construction generalizes the Dedekind cuts used by Dedekind to construct the real numbers from the rational numbers. It is also called the completion by cuts or normal completion.

References

  1. The notion of locality requires the function's domain to be at least a topological space.