HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, especially in
order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
, a maximal element of a
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
''S'' of some preordered 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 preordered 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 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 ele ...
which are also known, respectively, as maximum and minimum. The maximum of a subset S of a preordered 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. In the particular case of a
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes 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 ...
, while there can be at most one maximum and at most one minimum there may be multiple maximal or minimal elements. Specializing further to
totally ordered set In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
s, the notions of maximal element and maximum coincide, and the notions of minimal element and minimum coincide. As an example, in the collection S := \left\ ordered by
containment Containment was a geopolitical strategic foreign policy pursued by the United States during the Cold War to prevent the spread of communism after the end of World War II. The name was loosely related to the term '' cordon sanitaire'', which ...
, 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 In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...
contains at least one maximal element. This lemma is equivalent to the
well-ordering theorem In mathematics, the well-ordering theorem, also known as Zermelo's theorem, states that every set can be well-ordered. A set ''X'' is ''well-ordered'' by a strict total order if every non-empty subset of ''X'' has a least element under the orde ...
and the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
and implies major results in other mathematical areas like the
Hahn–Banach theorem The Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear functionals defined on a subspace of some vector space to the whole space, and it also shows that there are "enough" continuous linear f ...
, 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 (P, \leq) be a preordered set and let S \subseteq P. is an element m \in S such that :if s \in S satisfies m \leq s, then necessarily s \leq m. Similarly, is an element m \in S such that :if s \in S satisfies s \leq m, then necessarily m \leq s. Equivalently, m \in S is a minimal element of S with respect to \,\leq\, if and only if m is a maximal element of S with respect to \,\geq,\, where by definition, q \geq p if and only if p \leq q (for all p, q \in P). If the subset S is not specified then it should be assumed that S := P. Explicitly, a (respectively, ) is a maximal (resp. minimal) element of S := P with respect to \,\leq. If the preordered set (P, \leq) also happens to be a
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes 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 ...
(or more generally, if the restriction (S, \leq) is a partially ordered set) then m \in S is a maximal element of S if and only if S contains no element strictly greater than m; explicitly, this means that there does not exist any element s \in S such that m \leq s and m \neq s. The characterization for minimal elements is obtained by using \,\geq\, in place of \,\leq.


Existence and uniqueness

Maximal elements need not exist. *Example 1: Let S = , \infty) \subseteq \R where \R denotes the real numbers. For all m \in S, s = m + 1 \in S but m < s (that is, m \leq s but not m = s). *Example 2: Let S = \, where \Q denotes the rational numbers and where Square_root_of_2#Proofs_of_irrationality, \sqrt is irrational. In general \,\leq\, is only a partial order on S. If m is a maximal element and s \in S, then it remains possible that neither s \leq m nor m \leq s. This leaves open the possibility that there exist more than one maximal elements. *Example 3: In the
fence A fence is a structure that encloses an area, typically outdoors, and is usually constructed from posts that are connected by boards, wire, rails or netting. A fence differs from a wall in not having a solid foundation along its whole length. ...
a_1 < b_1 > a_2 < b_2 > a_3 < b_3 > \ldots, all the a_i are minimal and all b_i are maximal, as shown in the image. *Example 4: Let ''A'' be a set with at least two elements and let S = \ be the subset of the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
\wp(A) consisting of singleton subsets, partially ordered by \,\subseteq. This is the discrete poset where no two elements are comparable and thus every element \ \in S is maximal (and minimal); moreover, for any distinct a, b \in A, neither \ \subseteq \ nor \ \subseteq \.


Greatest elements

For a partially ordered set (P, \leq), the
irreflexive kernel In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself. An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal to ...
of \,\leq\, is denoted as \,<\, and is defined by x < y if x \leq y and x \neq y. For arbitrary members x, y \in P, exactly one of the following cases applies: #x < y; #x = y; #y < x; #x and y are incomparable. Given a subset S \subseteq P and some x \in S, * if case 1 never applies for any y \in S, then x is a maximal element of S, as defined above; * if case 1 and 4 never applies for any y \in S, then x is called a of S. Thus the definition of a greatest element is stronger than that of a maximal element. Equivalently, a greatest element of a subset S can be defined as an element of S that is greater than every other element of S. A subset may have at most one greatest element.If g_1 and g_2 are both greatest, then g_1 \leq g_2 and g_2 \leq g_1, and hence g_1 = g_2 by
antisymmetry In linguistics, antisymmetry is a syntactic theory presented in Richard S. Kayne's 1994 monograph ''The Antisymmetry of Syntax''. It asserts that grammatical hierarchies in natural language follow a universal order, namely specifier-head-comple ...
. \blacksquare
The greatest element of S, if it exists, is also a maximal element of S,If g is the greatest element of S and s \in S, then s \leq g. By
antisymmetry In linguistics, antisymmetry is a syntactic theory presented in Richard S. Kayne's 1994 monograph ''The Antisymmetry of Syntax''. It asserts that grammatical hierarchies in natural language follow a universal order, namely specifier-head-comple ...
, this renders (g \leq s and g \neq s) impossible. \blacksquare
and the only one.If m is a maximal element then m \leq g (because g is greatest) and thus m = g since m is maximal. \blacksquare By
contraposition In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a stateme ...
, if S has several maximal elements, it cannot have a greatest element; see example 3. If P satisfies the
ascending chain condition In mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly ideals in certain commutative rings.Jacobson (2009), p. 142 and 147 These c ...
, a subset S of P has a greatest element
if, and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicon ...
, it has one maximal element.: see above. — : Assume for contradiction that S has just one maximal element, m, but no greatest element. Since m is not greatest, some s_1 \in S must exist that is incomparable to m. Hence s_1 \in S cannot be maximal, that is, s_1 < s_2 must hold for some s_2 \in S. The latter must be incomparable to m, too, since m < s_2 contradicts m's maximality while s_2 \leq m contradicts the incomparability of m and s_1. Repeating this argument, an infinite ascending chain s_1 < s_2 < \ldots < s_n < \cdots can be found (such that each s_i is incomparable to m and not maximal). This contradicts the ascending chain condition. \blacksquare When the restriction of \,\leq\, to S is a
total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive ...
(S = \ in the topmost picture is an example), then the notions of maximal element and greatest element coincide.Let m \in S be a maximal element, for any s \in S either s \leq m or m \leq s. In the second case, the definition of maximal element requires that s = m, so it follows that s \leq m. In other words, m is a greatest element. \blacksquare This is not a necessary condition: 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 \,\leq\, is a total order on P.If a, b \in P were incomparable, then S = \ would have two maximal, but no greatest element, contradicting the coincidence. \blacksquare


Directed sets

In a
totally ordered set In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
, the terms maximal element and greatest element coincide, which is why both terms are used interchangeably in fields like
analysis Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (3 ...
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 set In mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty set A together with a reflexive and transitive binary relation \,\leq\, (that is, a preorder), with the additional property that every pair of elements has ...
s. 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,Let m \in D be maximal. Let x \in D be arbitrary. Then the common upper bound u of m and x satisfies u \ge m, so u=m by maximality. Since x\le u holds by definition of u, we have x\le m. Hence m is the greatest element. \blacksquare 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 Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
.


Properties

* Each finite nonempty subset S has both maximal and minimal elements. An infinite subset need not have any of them, for example, the
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s \Z with the usual order. * The set of maximal elements of a subset S is always an
antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wi ...
, that is, no two different maximal elements of S are comparable. The same applies to minimal elements.


Examples

* In
Pareto efficiency Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engi ...
, 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 Decision theory (or the theory of choice; not to be confused with choice theory) is a branch of applied probability theory concerned with the theory of making decisions based on assigning probabilities to various factors and assigning numerical ...
, an
admissible decision rule In statistical decision theory, an admissible decision rule is a rule for making a decision such that there is no other rule that is always "better" than it (or at least sometimes better and never worse), in the precise sense of "better" defined ...
is a maximal element with respect to the partial order of '' dominating decision rule.'' * In
modern portfolio theory Modern portfolio theory (MPT), or mean-variance analysis, is a mathematical framework for assembling a portfolio of assets such that the expected return is maximized for a given level of risk. It is a formalization and extension of diversificati ...
, the set of maximal elements with respect to the product order on risk and return is called the
efficient frontier In modern portfolio theory, the efficient frontier (or portfolio frontier) is an investment portfolio which occupies the "efficient" parts of the risk–return spectrum. Formally, it is the set of portfolios which satisfy the condition that no o ...
. * In
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
, a set is
finite Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marke ...
if and only if every non-empty
family Family (from la, familia) is a group of people related either by consanguinity (by recognized birth) or affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its members and of society. Idea ...
of
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
s has a minimal element when ordered by the inclusion relation. * In
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The ter ...
, the concept of a maximal common divisor is needed to generalize
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
s to number systems in which the common divisors of a set of elements may have more than one maximal element. * In
computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
, the maxima of a point set are maximal with respect to the partial order of coordinatewise domination.


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 theory The theory of consumer choice is the branch of microeconomics that relates preferences to consumption expenditures and to consumer demand curves. It analyzes how consumers maximize the desirability of their consumption as measured by their pref ...
the consumption space is some set X, usually the positive orthant of some vector space so that each x\in X represents a quantity of consumption specified for each existing commodity in the economy.
Preferences In psychology, economics and philosophy, preference is a technical term usually used in relation to choosing between alternatives. For example, someone prefers A over B if they would rather choose A than B. Preferences are central to decision t ...
of a consumer are usually represented by a total preorder \preceq so that x, y \in X and x \preceq y reads: x is at most as preferred as y. When x\preceq y and y \preceq x it is interpreted that the consumer is indifferent between x and y but is no reason to conclude that x = y. preference relations are never assumed to be antisymmetric. In this context, for any B \subseteq X, an element x \in B is said to be a maximal element if y \in B implies y \preceq x where it is interpreted as a consumption bundle that is not dominated by any other bundle in the sense that x \prec y, that is x \preceq y and not y \preceq x. It should be remarked that the formal definition looks very much like that of a greatest element for an ordered set. However, when \preceq is only a preorder, an element x with the property above behaves very much like a maximal element in an ordering. For instance, a maximal element x \in B is not unique for y \preceq x does not preclude the possibility that x \preceq y (while y \preceq x and x \preceq y do not imply x = y but simply indifference x \sim y). The notion of greatest element for a preference preorder would be that of most preferred choice. That is, some x\in B with y \in B implies y \prec x. An obvious application is to the definition of demand correspondence. Let P be the class of functionals on X. An element p\in P is called a price functional or price system and maps every consumption bundle x\in X into its market value p(x)\in \R_+. The budget correspondence is a correspondence \Gamma \colon P \times \R_ \rightarrow X mapping any price system and any level of income into a subset \Gamma (p,m) = \. The demand correspondence maps any price p and any level of income m into the set of \preceq -maximal elements of \Gamma (p, m). D(p,m) = \left\. It is called demand correspondence because the theory predicts that for p and m given, the rational choice of a consumer x^* will be some element x^* \in D(p,m).


Related notions

A subset Q of a partially ordered set P is said to be cofinal if for every x \in P there exists some y \in Q such that x \leq y. Every cofinal subset of a partially ordered set with maximal elements must contain all maximal elements. A subset L of a partially ordered set P is said to be a
lower set In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
of P if it is downward closed: if y \in L and x \leq y then x \in L. Every lower set L of a finite ordered set P is equal to the smallest lower set containing all maximal elements of L.


See also

* * *


Notes

;Proofs


References

{{DEFAULTSORT:Maximal Element Order theory