Maximal and minimal elements

From Wikipedia, the free encyclopedia
Hasse diagram of the set P of divisors of 60, partially ordered by the relation "x divides y". The red subset = {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, 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 .

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 of a preordered set is an element of which is greater than or equal to any other element of and the minimum of is again defined dually. In the particular case of a partially ordered set, while there can be at most one maximum and at most one minimum there may be multiple maximal or minimal elements.[1][2] Specializing further to 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

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

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.

Definition[edit]

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 uniqueness[edit]

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 and least elements[edit]

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.[proof 1]

The greatest element of if it exists, is also a maximal element of [proof 2] and the only one.[proof 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.[proof 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.[proof 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 [proof 6]

Dual to greatest is the notion of least element that relates to minimal in the same way as greatest to maximal.

Directed sets[edit]

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 partially ordered set, 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,[proof 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.

Properties[edit]

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

Examples[edit]

Consumer theory[edit]

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 notions[edit]

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 also[edit]

Notes[edit]

Proofs
  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. Let be arbitrary. Then the common upper bound of and satisfies , so by maximality. Since holds by definition of , we have . Hence is the greatest element.

References[edit]

  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.