In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, especially in
order theoryOrder theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of ordering, providing a framework for saying when one thing is "less than" or "precedes" another. This article gives a detailed introduction to the field and includes some of...
, a
maximal element of a subset
S of some
partially ordered setIn mathematics, especially order theory, a partially ordered set formalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that describes, for certain pairs of elements in the set, the requirement...
is an element of
S that is not smaller than any other element in
S. The term
minimal element is defined
duallyIn the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop iff y ≤ x...
. It is a
weaker notion than
greatest elementIn mathematics, especially in order theory, the greatest element 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. The term least element is defined dually...
and least element, and there may be
many maximal and minimal elements.
Let be a partially ordered set and . Then is a maximal element of if
for all , implies
The definition for minimal elements is obtained by using ≥ instead of ≤.
Maximal elements need not exist.
- Example 1: Let , for all we have but (that is, but not ).
- Example 2: Let and recall that .
In general is only a partial order on .
In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, especially in
order theoryOrder theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of ordering, providing a framework for saying when one thing is "less than" or "precedes" another. This article gives a detailed introduction to the field and includes some of...
, a
maximal element of a subset
S of some
partially ordered setIn mathematics, especially order theory, a partially ordered set formalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that describes, for certain pairs of elements in the set, the requirement...
is an element of
S that is not smaller than any other element in
S. The term
minimal element is defined
duallyIn the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop iff y ≤ x...
. It is a
weaker notion than
greatest elementIn mathematics, especially in order theory, the greatest element 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. The term least element is defined dually...
and least element, and there may be
many maximal and minimal elements.
Definition
Let be a partially ordered set and . Then is a maximal element of if
for all , implies
The definition for minimal elements is obtained by using ≥ instead of ≤.
Existence and uniqueness
Maximal elements need not exist.
- Example 1: Let , for all we have but (that is, but not ).
- Example 2: Let and recall that .
In general is only a partial order on . If is a maximal element and , it remains the possibility that neither nor . This leaves open the possibility that there are many maximal elements.
- Example 3: In the fence
In mathematics, a fence, also called a zigzag poset, is a partially ordered set in which the order relations form a path with alternating orientations:orA fence may be finite, or it may be formed by an infinite alternating sequence extending in both directions.A linear extension of a fence is...
, all the are maximal, and all the are minimal.
- Example 4: Let be a set with at least two elements and let be the subset of the power set
In mathematics, given a set S, the power set of S, written , P, ℘ or 2
S, is the set of all subsets of S. In axiomatic set theory In mathematics, given a set S, the power set (or powerset) of S, written , P(S), ℘(S) or 2
S, is the set of all subsets of S. In...
consisting of singletonsIn mathematics, a singleton is a set with exactly one element. For example, the set {0} is a singleton.-Properties:Note that a set such as is also a singleton: the only element is a set ....
, partially ordered by . This is the discrete poset – no two elements are comparable – and thus every element is maximal (and minimal) and for any neither nor .
Maximal elements and the greatest element
It looks like should be a
greatest elementIn mathematics, especially in order theory, the greatest element 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. The term least element is defined dually...
or maximum but in fact it is not necessarily the case: the definition of maximal element is somewhat weaker. Suppose we find with , then, by the definition of greatest element, so that . In other words, a maximum, if it exists, is the (unique) maximal element.
The reverse is not true: there can be maximal elements despite there being no maximum. Example 3 is an instance of existence of many maximal elements and no maximum. The reason is, again, that in general is only a partial order on . If is a maximal element and , it remains the possibility that neither nor .
If there are many maximal elements, they are in some contexts called a
frontier, as in the
Pareto frontier.
Of course, when the restriction of to is a
total orderIn mathematics and set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
, the notions of maximal element and greatest element coincide. Let be a maximal element, for any either or . In the second case the definition of maximal element requires so we conclude that implies . In other words, is a greatest element.
Finally, let us remark that being totally ordered is sufficient to ensure that a maximal element is a greatest element, but it is not necessary.
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
analysisMathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of calculus. It is the branch of pure mathematics most explicitly concerned with the notion of a limit, whether the limit of a sequence or the limit of a function...
where only total orders are considered. This observation does not only apply to totally ordered subsets of any poset, but also to their order theoretic generalization via
directed setIn mathematics, a directed set is a nonempty set A together with a reflexive and transitive binary relation ≤ , with the additional property that every pair of elements has an upper bound.Directed sets are a generalization of nonempty totally ordered sets, that is, all totally ordered sets are...
s. In a directed set, every pair of elements (especially pairs of incomparable elements) has a common upper bound within the set. It is easy to see that any maximal element of such a subset will be unique (unlike in a poset). Furthermore, this unique maximal element will also be the greatest element.
Similar conclusions are true for minimal elements.
Further introductory information is found in the article on
order theoryOrder theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of ordering, providing a framework for saying when one thing is "less than" or "precedes" another. This article gives a detailed introduction to the field and includes some of...
.
Examples
- In Pareto efficiency
Pareto efficiency, or Pareto optimality, is an important concept in economics with broad applications in game theory, engineering and the social sciences. The term is named after Vilfredo Pareto, an Italian economist who used the concept in his studies of economic efficiency and income distribution...
, a Pareto optimal 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
Decision theory in mathematics and statistics is concerned with identifying the values, uncertainties and other issues relevant in a given decision and the resulting optimal decision...
, an admissible decision ruleIn classical decision theory, an admissible decision rule is a rule for making a decision such that there isn't any other rule that is always "better" than it, in a specific sense defined below: it is a maximal element with respect to the below defined partial order.Generally speaking, in most...
is a maximal element with respect to the partial order of dominating decision ruleIn decision theory, a decision rule is said to dominate another if the performance of the former is sometimes better, and never worse, than that of the latter.Formally, let and be two decision rules, and let be the risk of rule for parameter...
.
- In modern portfolio theory
Modern portfolio theory is a theory of investment which attempts to explain how investors can maximize return and minimize risk. Although MPT is widely used in practice in the financial industry and several of its creators won a Nobel prize for the theory, in recent years the basic assumptions of...
, the set of maximal elements with respect to the product orderIn mathematics, given two ordered sets A and B, one can induce an ordering on the Cartesian product A × B. Giventwo pairs and in A × B, one sets...
on risk and return is called the efficient frontier.
Consumer theory
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 theoryConsumer theory is a theory of microeconomics that relates preferences to consumer demand curves. The link between personal preferences, consumption, and the demand curve is one of the most complex relations in economics...
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
- implies
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 (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 .
- is a maximal element of .
It is called demand correspondence because the theory predicts that for and given, the rational choice of a consumer will be some element .
See also
- Greatest element
In mathematics, especially in order theory, the greatest element 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. The term least element is defined dually...
- Upper and lower bounds
- Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Every partially ordered set in which every chain has an upper bound contains at least one maximal element....