Maximal and minimal elements
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set 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.
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. 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
ordered by containment, the element is minimal as it contains no sets in the collection, the element is maximal as there are no sets in the collection which contain it, the element is neither, and the element 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 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
Let be a partially ordered set and. Then is a maximal element of if contains no element greater than, formally: if there is no such that both andThe definition for minimal elements is obtained by using ≥ instead of ≤.
Existence and uniqueness
Maximal elements need not exist.In general ≤ is only a partial order on S. If m is a maximal element and s∈S, it remains the possibility that neither s≤m nor m≤s. This leaves open the possibility that there are many maximal elements.
Greatest elements
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:- ,
- ,
- ,
- are incomparable.
- 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.
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.
The greatest element of, if it exists, is also a maximal element of, and the only one.
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.
When the restriction of to is a total order, then the notions of maximal element and greatest element coincide.
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.
Directed sets
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 has a common upper bound within the set. If a directed set has a maximal element, it is also its greatest element, 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
- Each finite nonempty subset S has both maximal and minimal elements. An infinite subst need not have any of them, e.g. ℤ with the usual order.
- The set of maximal elements of a subset S is always an anti-chain, that is, no two different maximal elements of S are comparable. The same applies to minimal elements.
Examples
- In Pareto efficiency, a Pareto optimum is a maximal element with respect to the partial order of Pareto improvement, and the set of maximal elements is called the Pareto frontier.
- In decision theory, an admissible decision rule is a maximal element with respect to the partial order of dominating decision rule.
- In modern portfolio theory, the set of maximal elements with respect to the product order on risk and return is called the efficient frontier.
- In set theory, a set is finite if and only if every non-empty family of subsets has a minimal element when ordered by the inclusion relation.
- In abstract algebra, the concept of a maximal common divisor is needed to generalize greatest common divisors to number systems in which the common divisors of a set of elements may have more than one maximal element.
- In computational geometry, the maxima of a point set are maximal with respect to the partial order of coordinatewise domination.
Consumer theory
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, we call a maximal element if
and 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 . The notion of greatest element for a preference preorder would be that of most preferred choice. That is, some with
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
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.