Maximal element

From Wikipedia, the free encyclopedia

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.

1 Definition
2 Existence and uniqueness
3 Maximal elements and the greatest element
4 Directed sets
5 Preorder relations in economic theory

[edit] Definition

Let $P,\leq$ be a partially ordered set and $S\subset P$ , then $m\in S$ is a maximal element of S if

$s\in S$ and $m \leq s$ imply

m = s .

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

[edit] Existence and uniqueness

'A set with many upper bounds, a least upper bound (or supremum), many maximal elements, and no greatest element (or maximum).'

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: The figure represents the set $S=\{s\in \Bbb{R}^{2}:s_{1}^{2}+s_{2}^{2}\leq 1\}$ . It is clear that the only candidates to be maximal elements are those in the upper right arc of the circle. Check that they are indeed maximal elements: Let $0\leq m$ with $m_{1}^{2}+m_{2}^{2}=1$ and let $s\in S$ with $m\leq s$ . If

m 1 < s 1

m 2 < s 2

we have $1=m_{1}^{2}+m_{2}^{2}<s_{1}^{2}+s_{2}^{2}$ thus contradicting that $s\in S$ . It must then be the case that

m 1 = s 1

and

m 2 = s 2

, that is

m = s

Only one thing is for sure: if $m^{\prime }$ and $m^{\prime \prime }$ are distinct maximal elements of $S$ , then neither $m^{\prime }\leq m^{\prime \prime }$ nor $m^{\prime \prime }\leq m^{\prime }$ , for otherwise we would arrive to the conclusion that $m^{\prime}=m^{\prime \prime }$ .

Example 4: In example 3 it is clear that no two elements in the arc are ordered by $\leq$ .

Example 5: Let

A

be a set with at least two elements and let $S=\{\{a\}:a\in A\}$ be a subset of the power set

P (A)

, partially ordered by $\subset$ . Every element $\{a\}\in S$ is a 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 }\}$ .

[edit] Maximal elements and the greatest element

It looks like $m$ should be a greatest element or maximum but if 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.

Example 6: Let $S=\{s\in \Bbb{R}^{2}:s\leq z\}$ , then

z

is a maximal element that coincides with the greatest 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 $\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$ .

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 $x\in B$ implies $s\leq m$ . In other words, $m$ is a greatest element.

Example 6: Let $S=\{s\in \Bbb{R}^{2}:s_{1}=s_{2}\leq 4\}$ , then

s = (4,4)

is a maximal element and the 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; see example 6 above.

[edit] 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 (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 theory.

[edit] Preorder relations in economic theory

There is no reason to limit the notion of maximal element to orderings. However, the terminology changes from one type of relation to the other for reasons we shall see.

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 complete 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 indiference $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 \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)=\{x\in X:x$ is a maximal element of

Γ(p, m)}

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