Maximal element

Maximal element

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. The term minimal element is defined dually. The notion of a maximal is weaker than that of the greatest element and least element (which are also known, respectively, as maximum and minimum); indeed a partially ordered set may have multiple maximal and minimal elements. As an example, in the collection

S = {{d, o}, {d, o, g}, {g, o, a, d}, {o, a, f}}

ordered by containment, the element {d, o} is minimal, the element {g, o, a, d} is maximal, 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 S.

Contents

Definition

Let (P,\leq) be a partially ordered set and S\subset P. Then m\in S is a maximal element of S if

for all s\in S, m \leq s implies m = s.

The definition for minimal elements is obtained by using ≥ instead of ≤.

Existence and uniqueness

Maximal elements need not exist.

Example 1: Let S=[1,\infty)\subset \Bbb{R}, for all m\in S we have s=m+1\in S but m < s (that is, m\leq s but not m = s).
Example 2: Let S=\{s\in \Bbb{Q}:1\leq s^{2}\leq 2\}\subset \Bbb{Q} and recall that \sqrt{2}\notin \Bbb{Q}.

In general \leq is only a partial order on S. If m is a maximal element and s\in S, it remains the possibility that neither s\leq m nor m\leq s. This leaves open the possibility that there are many maximal elements.

Example 3: In the fence a_1 > b_1 < a_2 > b_2 < a_3 > \cdots, all the ai are maximal, and all the bi are minimal.
Example 4: Let A be a set with at least two elements and let S=\{\{a\}:a\in A\} be the subset of the power set P(A) consisting of singletons, partially ordered by \subset . This is the discrete poset – no two elements are comparable – and thus every element \{a\}\in S is maximal (and minimal) and for any a^{\prime },a^{\prime \prime} neither \{a^{\prime }\} \subset \{a^{\prime \prime}\} nor \{a^{\prime\prime }\} \subset \{a^{\prime }\}.

Maximal elements and the greatest element

It looks like m should be a greatest element or maximum but in fact it is not necessarily the case: the definition of maximal element is somewhat weaker. Suppose we find s\in S with \max S\leq s, then, by the definition of greatest element, s\leq \max S so that s = max S. In other words, a maximum, if it exists, is the (unique) maximal element.

The converse 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 \leq is only a partial order on S. If m is a maximal element and s\in S, it remains the possibility that neither s\leq m nor m\leq s.

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 \leq to S is a total order, 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 m = s so we conclude that s\leq m. In other words, m is a greatest element.

Finally, let us remark that S 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 analysis 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 sets. In a directed set, every pair of elements (particularly 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 theory.

Examples

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\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 \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\subset X, we call x\in B a maximal element if

y\in B implies  y\preceq x

and 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˜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 \Bbb{R}_+. The budget correspondence is a correspondence \Gamma : P\times \Bbb{R}_+ \rightarrow X mapping any price system and any level of income into a subset

\Gamma (p,m)=\{x\in X:p(x)\leq m\}.

The demand correspondence maps any price p and any level of income m into the set of \preceq -maximal elements of Γ(p,m).

D(p,m)=\big\{x\in X:x is a maximal element of \Gamma (p,m)\big\}.

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).

See also


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Maximal — may refer to: Maximal element, a mathematical definition Maximal (Transformers), a faction of Transformers Maximalism, an artistic style Maximal set Maxim (magazine), a men s magazine marketed as Maximal in several countries See also Minimal… …   Wikipedia

  • Maximal subgroup — Lattice of subgroups of the symmetric group S4 M. s. are A4, three Dih4 and four S3 (Compare: Subgroups of S …   Wikipedia

  • Element maximal — Élément maximal Sommaire 1 Définition 2 Exemples 3 Notions connexes 4 Voir aussi // …   Wikipédia en Français

  • Élément minimal — Élément maximal Sommaire 1 Définition 2 Exemples 3 Notions connexes 4 Voir aussi // …   Wikipédia en Français

  • maximal — maximal, ale, aux [ maksimal, o ] adj. • 1877; de maximum ♦ Qui constitue un maximum. ⇒ maximum. Températures maximales. Condamné à la peine maximale. ♢ Par ext. (v. 1953) Vitesse maximale autorisée. ⊗ CONTR. Minimal. ● maximal, maximale,… …   Encyclopédie Universelle

  • Élément maximal d'un ensemble ordonné E — ● Élément maximal d un ensemble ordonné E élément a de E tel qu il n existe aucun élément de E qui lui soit strictement supérieur …   Encyclopédie Universelle

  • Maximal — bezeichnet: das deutsche Adjektiv zu Maximum mit der Bedeutung sehr groß oder größte ein maximales Element ist aber in der Mathematik nicht immer ein Maximum Diese Seite ist eine Begriffsklärung zur Unte …   Deutsch Wikipedia

  • Élément maximal — Dans un ensemble ordonné, un élément maximal est un élément tel qu il n existe aucun autre élément de cet ensemble qui lui soit supérieur, c est à dire que a est dit élément maximal d un ensemble ordonné (E, ≤) si a est un élément de E tel… …   Wikipédia en Français

  • Maximal torus — In the mathematical theory of compact Lie groups a special role is played by torus subgroups, in particular by the maximal torus subgroups. A torus in a Lie group G is a compact, connected, abelian Lie subgroup of G (and therefore isomorphic to… …   Wikipedia

  • Maximal compact subgroup — In mathematics, a maximal compact subgroup K of a topological group G is a subgroup K that is a compact space, in the subspace topology, and maximal amongst such subgroups. Maximal compact subgroups play an important role in the classification of …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”