Greatest element and least element

From Wikipedia, the free encyclopedia
  (Redirected from Greatest and least elements)
Jump to navigation Jump to search

Hasse diagram of the set P of divisors of 60, partially ordered by the relation "x divides y". The red subset S = {1,2,3,4} has two maximal elements, viz. 3 and 4, and one minimal element, viz. 1, which is also its least element.

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

Definition[edit]

Throughout, let (P, ≤) be a partially ordered set and let SP.

Definition: An element g of a subset S of P is said to be a greatest element of S if it satisfies
sg, for all sS.

If S has a greatest element then it is necessarily unique so we may speak of the greatest element of S.

By using instead of in the above definition, one defines the least element of S.

Contrast to maximal elements, upper bounds, and local/absolute maximums[edit]

The greatest element of a partially ordered subset must not be confused with maximal elements of the set, which are elements that are not smaller than any other element in the set. A set can have several maximal elements without having a greatest element. Like upper bounds and maximal elements, greatest elements may fail to exist.

Definitions:
  1. An element mS is said to be a maximal element of S if there does not exist any sS such that ms and sm.
  2. An upper bound of S in P is an element u such that uP and su for all sS.

In the particular case where P = S, the definition of "u is an upper bound of S in S" becomes: u is an element such that uS and su for all sS, which is completely identical to the definition of a greatest element given before. Thus g is a greatest element of S if and only if g is an upper bound of S in S.

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

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.

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.

Properties[edit]

Throughout, let (P, ≤) be a partially ordered set and let SP.

  • A set S can have at most one greatest element.[note 1] Thus if a set has a greatest element then it is necessarily unique.
  • If it exists, then the greatest element of S is an upper bound of S that is also contained in S.
  • If g is the greatest element of S then g is also a maximal element of S[note 2] and moreover, any other maximal element of S will necessarily be equal to g.[note 3]
    • Thus if a set S has several maximal elements then it cannot have a greatest element.
  • If P satisfies the ascending chain condition, a subset S of P has a greatest element if, and only if, it has one maximal element.[note 4]
  • When the restriction of to S is a total order (S = { 1, 2, 4  } in the topmost picture is an example), then the notions of maximal element and greatest element coincide.[note 5]
    • However, this is not a necessary condition for whenever S has a greatest element, the notions coincide, too, as stated above.
  • If the notions of maximal element and greatest element coincide on every two-element subset S of P, then is a total order on P.[note 6]

Sufficient conditions[edit]

  • A finite chain always has a greatest and a least element.

Top and bottom[edit]

The least and greatest element of the whole partially ordered set plays a special role and is also called bottom and top, or zero (0) and unit (1), or ⊥ and ⊤, respectively. If both exists, the poset is called a bounded poset. The notation of 0 and 1 is used preferably when the poset is even 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[edit]

Hasse diagram of example 2
  • The subset of integers has no upper bound in the set of real numbers.
  • Let the relation on { a, b, c, d} be given by ac, ad, bc, bd. The set { a, b} has upper bounds c and d, but no least upper bound, and no greatest element (cf. picture).
  • In the rational numbers, the set of numbers with their square less than 2 has upper bounds but no greatest element and no least upper bound.
  • In , the set of numbers less than 1 has a least upper bound, viz. 1, but no greatest element.
  • In , the set of numbers less than or equal to 1 has a greatest element, viz. 1, which is also its least upper bound.
  • In ℝ² with the product order, the set of pairs (x, y) with 0 < x < 1 has no upper bound.
  • In ℝ² with the lexicographical order, this set has upper bounds, e.g. (1, 0). It has no least upper bound.

See also[edit]

Notes[edit]

  1. ^ If g1 and g2 are both greatest, then g1g2 and g2g1, and hence g1 = g2 by antisymmetry.
  2. ^ If g is the greatest element of S and sS, then sg. By antisymmetry, this renders (gs and gs) impossible.
  3. ^ If m' is a maximal element, then m'g since g is greatest, hence m' = g since m' is maximal.
  4. ^ Only if: see above. — If: Assume for contradiction that S has just one maximal element, m, but no greatest element. Since m is not greatest, some s1S must exist that is incomparable to m. Hence s1S cannot be maximal, that is, s1 < s2 must hold for some s2S. The latter must be incomparable to m, too, since m < s2 contradicts m's maximality while s2m contradicts the incomparability of m and s1. Repeating this argument, an infinite ascending chain s1 < s2 < ⋅⋅⋅ < sn < ⋅⋅⋅ can be found (such that each si is incomparable to m and not maximal). This contradicts the ascending chain condition.
  5. ^ Let mS be a maximal element, for any sS either sm or ms. In the second case, the definition of maximal element requires that m = s, so it follows that sm. In other words, m is a greatest element.
  6. ^ If a, bP were incomparable, then S = { a, b} would have two maximal, but no greatest element, contradicting the coincidence.

References[edit]

  1. ^ The notion of locality requires the function's domain to be at least a topological space.
  • Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press. ISBN 978-0-521-78451-1.