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''.
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
:''S'' =
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 $(P,\; \backslash leq)$ be a preordered set and let $S\; \backslash subseteq\; P.$ is an element $m\; \backslash in\; S$ such that
:if $s\; \backslash in\; S$ satisfies $m\; \backslash leq\; s,$ then necessarily $s\; \backslash leq\; m.$
Similarly, is an element $m\; \backslash in\; S$ such that
:if $s\; \backslash in\; S$ satisfies $s\; \backslash leq\; m,$ then necessarily $m\; \backslash leq\; s.$
Equivalently, $m\; \backslash in\; S$ is a minimal element of $S$ with respect to $\backslash ,\backslash leq\backslash ,$ if and only if $m$ is a maximal element of $S$ with respect to $\backslash ,\backslash geq,\backslash ,$ where by definition, $q\; \backslash geq\; p$ if and only if $p\; \backslash leq\; q$ (for all $p,\; q\; \backslash 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 $\backslash ,\backslash leq.$
If the preordered set $(P,\; \backslash leq)$ also happens to be a partially ordered set (or more generally, if the restriction $(S,\; \backslash leq)$ is a partially ordered set) then $m\; \backslash in\; S$ is a maximal element of $S$ if and only if $S$ contains no element strictly greater than explicitly, this means that there does not exist any element $s\; \backslash in\; S$ such that $m\; \backslash leq\; s$ and $m\; \backslash neq\; s.$
The characterization for minimal elements is obtained by using $\backslash ,\backslash geq\backslash ,$ in place of $\backslash ,\backslash leq.$

** Existence and uniqueness **

Maximal elements need not exist.
:Example 1: Let $S\; =$ where $\backslash mathbb$ denotes the [[real numbers. For all $m\; \backslash in\; S,$ $s\; =\; m\; +\; 1\; \backslash in\; S$ but $m\; <\; s$ (that is, $m\; \backslash leq\; s$ but not $m\; =\; s$).
:Example 2: Let $S\; =\; \backslash ,$ where $\backslash mathbb$ denotes the [[rational numbers]] and where [[Square_root_of_2#Proofs_of_irrationality|$\backslash sqrt$]] is irrational.
In general $\backslash ,\backslash leq\backslash ,$ is only a partial order on $S.$ If $m$ is a maximal element and $s\; \backslash in\; S,$ then it remains possible that neither $s\; \backslash leq\; m$ nor $m\; \backslash leq\; s.$ This leaves open the possibility that there exist more than one maximal elements.
:Example 3: In the fence $a\_1\; <\; b\_1\; >\; a\_2\; <\; b\_2\; >\; a\_3\; <\; b\_3\; >\; \backslash 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\; =\; \backslash $ be the subset of the power set $\backslash wp(A)$ consisting of singleton subsets, partially ordered by $\backslash ,\backslash subseteq.$ This is the discrete poset where no two elements are comparable and thus every element $\backslash \; \backslash in\; S$ is maximal (and minimal); moreover, for any distinct $a,\; b\; \backslash in\; A,$ neither $\backslash \; \backslash subseteq\; \backslash $ nor $\backslash \; \backslash subseteq\; \backslash .$

** Greatest elements **

For a partially ordered set $(P,\; \backslash leq),$ the irreflexive kernel of $\backslash ,\backslash leq\backslash ,$ is denoted as $\backslash ,<\backslash ,$ and is defined by $x\; <\; y$ if $x\; \backslash leq\; y$ and $x\; \backslash neq\; y.$
For arbitrary members $x,\; y\; \backslash in\; P,$ exactly one of the following cases applies:
#$x\; <\; y$;
#$x\; =\; y$;
#$y\; <\; x$;
#$x$ and $y$ are incomparable.
Given a subset $S\; \backslash subseteq\; P$ and some $x\; \backslash in\; S,$
* if case 1 never applies for any $y\; \backslash in\; S,$ then $x$ is a maximal element of $S,$ as defined above;
* if case 1 and 4 never applies for any $y\; \backslash 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\; \backslash leq\; g\_2$ and $g\_2\; \backslash leq\; g\_1,$ and hence $g\_1\; =\; g\_2$ by antisymmetry.
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\; \backslash in\; S,$ then $s\; \backslash leq\; g.$ By antisymmetry, this renders ($g\; \backslash leq\; s$ and $g\; \backslash neq\; s$) impossible. and the only one.If $n$ is a maximal element then $n\; \backslash leq\; h$ (because $g$ is greatest) and thus $n\; =\; g$ since $n$ is maximal.
By contraposition, if $S$ has several maximal elements, it cannot have a greatest element; see example 3.
If $P$ satisfies the ascending chain condition, a subset $S$ of $P$ has a greatest element if, and only if, 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\; \backslash in\; S$ must exist that is incomparable to $m.$ Hence $s\_1\; \backslash in\; S$ cannot be maximal, that is, $s\_1\; <\; s\_2$ must hold for some $s\_2\; \backslash in\; S.$ The latter must be incomparable to $m,$ too, since $m\; <\; s\_2$ contradicts $m$'s maximality while $s\_2\; \backslash leq\; m$ contradicts the incomparability of $m$ and $s\_1.$ Repeating this argument, an infinite ascending chain $s\_1\; <\; s\_2\; <\; \backslash ldots\; <\; s\_n\; <\; \backslash cdots$ can be found (such that each $s\_i$ is incomparable to $m$ and not maximal). This contradicts the ascending chain condition.
When the restriction of $\backslash ,\backslash leq\backslash ,$ to $S$ is a total order ($S\; =\; \backslash $ in the topmost picture is an example), then the notions of maximal element and greatest element coincide.Let $m\; \backslash in\; S$ be a maximal element, for any $s\; \backslash in\; S$ either $s\; \backslash leq\; m$ or $m\; \backslash leq\; s.$ In the second case, the definition of maximal element requires that $s\; =\; m,$ so it follows that $s\; \backslash leq\; m.$ In other words, $m$ is a greatest element.
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 $\backslash ,\backslash leq\backslash ,$ is a total order on .If $a,\; b\; \backslash in\; P$ were incomparable, then $S\; =\; \backslash $ would have two maximal, but no greatest element, contradicting the coincidence.

** 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 (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\; \backslash in\; D$ be maximal. Assume for contradiction some arbitrary $x\; \backslash in\; D$ is incomparable to $m$, then the common upper bound $u$ of $m$ and $x$ is comparable with $x$ and therefore cannot equal $m$, hence $m\; <\; u$, contradicting maximality. Hence $m$ is the 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 subset need not have any of them, e.g. $\backslash mathbb$ 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 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 $X$, usually the positive orthant of some vector space so that each $x\backslash in\; X$ represents a quantity of consumption specified for each existing commodity in the economy. Preferences of a consumer are usually represented by a total preorder $\backslash preceq$ so that $x,\; y\; \backslash in\; X$ and $x\; \backslash preceq\; y$ reads: $x$ is at most as preferred as $y$. When $x\backslash preceq\; y$ and $y\; \backslash 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\; \backslash subseteq\; X,$ an element $x\; \backslash in\; B$ is said to be a maximal element if :$y\; \backslash in\; B$ implies $y\; \backslash preceq\; x$ where it is interpreted as a consumption bundle that is not dominated by any other bundle in the sense that $x\; \backslash prec\; y,$ that is $x\; \backslash preceq\; y$ and not $y\; \backslash 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 $\backslash 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\; \backslash in\; B$ is not unique for $y\; \backslash preceq\; x$ does not preclude the possibility that $x\; \backslash preceq\; y$ (while $y\; \backslash preceq\; x$ and $x\; \backslash preceq\; y$ do not imply $x\; =\; y$ but simply indifference $x\; \backslash sim\; y$). The notion of greatest element for a preference preorder would be that of most preferred choice. That is, some $x\backslash in\; B$ with :$y\; \backslash in\; B$ implies $y\; \backslash prec\; x.$ An obvious application is to the definition of demand correspondence. Let $P$ be the class of functionals on $X$. An element $p\backslash in\; P$ is called a price functional or price system and maps every consumption bundle $x\backslash in\; X$ into its market value $p(x)\backslash in\; \backslash mathbb\_+$. The budget correspondence is a correspondence $\backslash Gamma\; \backslash colon\; P\; \backslash times\; \backslash mathbb\_\; \backslash rightarrow\; X$ mapping any price system and any level of income into a subset :$\backslash Gamma\; (p,m)\; =\; \backslash .$ The demand correspondence maps any price $p$ and any level of income $m$ into the set of $\backslash preceq$-maximal elements of $\backslash Gamma\; (p,\; m)$. :$D(p,m)\; =\; \backslash left\backslash .$ 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^*\; \backslash in\; D(p,m).$

** Related notions **

A subset $Q$ of a partially ordered set $P$ is said to be cofinal if for every $x\; \backslash in\; P$ there exists some $y\; \backslash in\; Q$ such that $x\; \backslash 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 of $P$ if it is downward closed: if $y\; \backslash in\; L$ and $x\; \backslash leq\; y$ then $x\; \backslash 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 **

* Greatest element and least element
* Infimum and supremum
* Upper and lower bounds

** Notes **

References

{{DEFAULTSORT:Maximal Element Category:Order theory

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 consumption space is some set $X$, usually the positive orthant of some vector space so that each $x\backslash in\; X$ represents a quantity of consumption specified for each existing commodity in the economy. Preferences of a consumer are usually represented by a total preorder $\backslash preceq$ so that $x,\; y\; \backslash in\; X$ and $x\; \backslash preceq\; y$ reads: $x$ is at most as preferred as $y$. When $x\backslash preceq\; y$ and $y\; \backslash 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\; \backslash subseteq\; X,$ an element $x\; \backslash in\; B$ is said to be a maximal element if :$y\; \backslash in\; B$ implies $y\; \backslash preceq\; x$ where it is interpreted as a consumption bundle that is not dominated by any other bundle in the sense that $x\; \backslash prec\; y,$ that is $x\; \backslash preceq\; y$ and not $y\; \backslash 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 $\backslash 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\; \backslash in\; B$ is not unique for $y\; \backslash preceq\; x$ does not preclude the possibility that $x\; \backslash preceq\; y$ (while $y\; \backslash preceq\; x$ and $x\; \backslash preceq\; y$ do not imply $x\; =\; y$ but simply indifference $x\; \backslash sim\; y$). The notion of greatest element for a preference preorder would be that of most preferred choice. That is, some $x\backslash in\; B$ with :$y\; \backslash in\; B$ implies $y\; \backslash prec\; x.$ An obvious application is to the definition of demand correspondence. Let $P$ be the class of functionals on $X$. An element $p\backslash in\; P$ is called a price functional or price system and maps every consumption bundle $x\backslash in\; X$ into its market value $p(x)\backslash in\; \backslash mathbb\_+$. The budget correspondence is a correspondence $\backslash Gamma\; \backslash colon\; P\; \backslash times\; \backslash mathbb\_\; \backslash rightarrow\; X$ mapping any price system and any level of income into a subset :$\backslash Gamma\; (p,m)\; =\; \backslash .$ The demand correspondence maps any price $p$ and any level of income $m$ into the set of $\backslash preceq$-maximal elements of $\backslash Gamma\; (p,\; m)$. :$D(p,m)\; =\; \backslash left\backslash .$ 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^*\; \backslash in\; D(p,m).$

References

{{DEFAULTSORT:Maximal Element Category:Order theory