Maximal and minimal elements

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

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.

The notions of maximal and minimal elements are weaker than those of greatest element and least element which are also known, respectively, as maximum and minimum. The maximum of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S, and the minimum of S is again defined dually. While a partially ordered set can have at most one each maximum and minimum it may have multiple maximal and minimal elements.[1][2] For totally ordered sets, the notions of maximal element and maximum coincide, and the notions of minimal element and minimum coincide.

As an example, in the collection

S = {{d, o}, {d, o, g}, {g, o, a, d}, {o, a, f}}

ordered by containment, the element {d, o} is minimal as it contains no sets in the collection, the element {g, o, a, d} is maximal as there are no sets in the collection which contain it, the element {d, o, g} is neither, and the element {o, a, f} is both minimal and maximal. By contrast, neither a maximum nor a minimum exists for S.

Zorn's lemma states that every partially ordered set for which every totally ordered subset has an upper bound contains at least one maximal element. This lemma is equivalent to the well-ordering theorem and the axiom of choice[3] and implies major results in other mathematical areas like the Hahn–Banach theorem, the Kirszbraun theorem, Tychonoff's theorem, the existence of a Hamel basis for every vector space, and the existence of an algebraic closure for every field.

DefinitionEdit

Let   be a preordered set and let   A maximal element of   with respect to   is an element   such that

if   satisfies   then necessarily  

Similarly, a minimal element of   with respect to   is an element   such that

if   satisfies   then necessarily  

Equivalently,   is a minimal element of   with respect to   if and only if   is a maximal element of   with respect to   where by definition,   if and only if   (for all  ).

If the subset   is not specified then it should be assumed that   Explicitly, a maximal element (respectively, minimal element) of   is a maximal (resp. minimal) element of   with respect to  

If the preordered set   also happens to be a partially ordered set (or more generally, if the restriction   is a partially ordered set) then   is a maximal element of   if and only if   contains no element strictly greater than  ; explicitly, this means that there does not exist any element   such that   and   The characterization for minimal elements is obtained by using   in place of  

Existence and uniquenessEdit

 
A fence consists of minimal and maximal elements only (Example 3).

Maximal elements need not exist.

Example 1: Let   where   denotes the real numbers. For all     but   (that is,   but not  ).
Example 2: Let   where   denotes the rational numbers and where   is irrational.

In general   is only a partial order on   If   is a maximal element and   then it remains possible that neither   nor   This leaves open the possibility that there exist more than one maximal elements.

Example 3: In the fence   all the   are minimal and all   are maximal, as shown in the image.
Example 4: Let A be a set with at least two elements and let   be the subset of the power set   consisting of singleton subsets, partially ordered by   This is the discrete poset where no two elements are comparable and thus every element   is maximal (and minimal); moreover, for any distinct   neither   nor  

Greatest elementsEdit

For a partially ordered set   the irreflexive kernel of   is denoted as   and is defined by   if   and   For arbitrary members   exactly one of the following cases applies:

  1.  ;
  2.  ;
  3.  ;
  4.   and   are incomparable.

Given a subset   and some  

  • if case 1 never applies for any   then   is a maximal element of   as defined above;
  • if case 1 and 4 never applies for any   then   is called a greatest element of  

Thus the definition of a greatest element is stronger than that of a maximal element.

Equivalently, a greatest element of a subset   can be defined as an element of   that is greater than every other element of   A subset may have at most one greatest element.[note 1]

The greatest element of   if it exists, is also a maximal element of  [note 2] and the only one.[note 3] By contraposition, if   has several maximal elements, it cannot have a greatest element; see example 3. If   satisfies the ascending chain condition, a subset   of   has a greatest element if, and only if, it has one maximal element.[note 4]

When the restriction of   to   is a total order (  in the topmost picture is an example), then the notions of maximal element and greatest element coincide.[note 5] This is not a necessary condition: whenever   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   of   then   is a total order on P.[note 6]

Directed setsEdit

In a totally ordered set, the terms maximal element and greatest element coincide, which is why both terms are used interchangeably in fields like analysis where only total orders are considered. This observation applies not only to totally ordered subsets of any poset, but also to their order theoretic generalization via directed sets. In a directed set, every pair of elements (particularly pairs of incomparable elements) has a common upper bound within the set. If a directed set has a maximal element, it is also its greatest element,[note 7] and hence its only maximal element. For a directed set without maximal or greatest elements, see examples 1 and 2 above.

Similar conclusions are true for minimal elements.

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

PropertiesEdit

  • Each finite nonempty subset   has both maximal and minimal elements. An infinite subset need not have any of them, e.g.   with the usual order.
  • The set of maximal elements of a subset   is always an anti-chain, that is, no two different maximal elements of   are comparable. The same applies to minimal elements.

ExamplesEdit

Consumer theoryEdit

In economics, one may relax the axiom of antisymmetry, using preorders (generally total preorders) instead of partial orders; the notion analogous to maximal element is very similar, but different terminology is used, as detailed below.

In consumer theory the consumption space is some set  , usually the positive orthant of some vector space so that each   represents a quantity of consumption specified for each existing commodity in the economy. Preferences of a consumer are usually represented by a total preorder   so that   and   reads:   is at most as preferred as  . When   and   it is interpreted that the consumer is indifferent between   and   but is no reason to conclude that   preference relations are never assumed to be antisymmetric. In this context, for any   an element   is said to be a maximal element if

  implies  

where it is interpreted as a consumption bundle that is not dominated by any other bundle in the sense that   that is   and not  

It should be remarked that the formal definition looks very much like that of a greatest element for an ordered set. However, when   is only a preorder, an element   with the property above behaves very much like a maximal element in an ordering. For instance, a maximal element   is not unique for   does not preclude the possibility that   (while   and   do not imply   but simply indifference  ). The notion of greatest element for a preference preorder would be that of most preferred choice. That is, some   with

  implies  

An obvious application is to the definition of demand correspondence. Let   be the class of functionals on  . An element   is called a price functional or price system and maps every consumption bundle   into its market value  . The budget correspondence is a correspondence   mapping any price system and any level of income into a subset

 

The demand correspondence maps any price   and any level of income   into the set of  -maximal elements of  .

 

It is called demand correspondence because the theory predicts that for   and   given, the rational choice of a consumer   will be some element  

Related notionsEdit

A subset   of a partially ordered set   is said to be cofinal if for every   there exists some   such that   Every cofinal subset of a partially ordered set with maximal elements must contain all maximal elements.

A subset   of a partially ordered set   is said to be a lower set of   if it is downward closed: if   and   then   Every lower set   of a finite ordered set   is equal to the smallest lower set containing all maximal elements of  

See alsoEdit

NotesEdit

  1. ^ If   and   are both greatest, then   and   and hence   by antisymmetry.
  2. ^ If   is the greatest element of   and   then   By antisymmetry, this renders (  and  ) impossible.
  3. ^ If   is a maximal element then   (because   is greatest) and thus   since   is maximal.
  4. ^ 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.
  5. ^ 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.
  6. ^ If   were incomparable, then   would have two maximal, but no greatest element, contradicting the coincidence.
  7. ^ Let   be maximal. Assume for contradiction some arbitrary   is incomparable to  , then the common upper bound   of   and   is comparable with   and therefore cannot equal  , hence  , contradicting maximality. Hence   is the greatest element.

ReferencesEdit

  1. ^ Richmond, Bettina; Richmond, Thomas (2009), A Discrete Transition to Advanced Mathematics, American Mathematical Society, p. 181, ISBN 978-0-8218-4789-3.
  2. ^ Scott, William Raymond (1987), Group Theory (2nd ed.), Dover, p. 22, ISBN 978-0-486-65377-8
  3. ^ Jech, Thomas (2008) [originally published in 1973]. The Axiom of Choice. Dover Publications. ISBN 978-0-486-46624-8.