Английская Википедия:Greatest element and least element
Шаблон:Use American English Шаблон:Short description
In mathematics, especially in order theory, the greatest element of a subset <math>S</math> of a partially ordered set (poset) is an element of <math>S</math> that is greater than every other element of <math>S</math>. The term least element is defined dually, that is, it is an element of <math>S</math> that is smaller than every other element of <math>S.</math>
Definitions
Let <math>(P, \leq)</math> be a preordered set and let <math>S \subseteq P.</math> An element <math>g \in P</math> is said to be Шаблон:Em if <math>g \in S</math> and if it also satisfies:
- <math>s \leq g</math> for all <math>s \in S.</math>
By switching the side of the relation that <math>s</math> is on in the above definition, the definition of a least element of <math>S</math> is obtained. Explicitly, an element <math>l \in P</math> is said to be Шаблон:Em if <math>l \in S</math> and if it also satisfies:
- <math>l \leq s</math> for all <math>s \in S.</math>
If <math>(P, \leq)</math> is also a partially ordered set then <math>S</math> can have at most one greatest element and it can have at most one least element. Whenever a greatest element of <math>S</math> exists and is unique then this element is called Шаблон:Em greatest element of <math>S</math>. The terminology Шаблон:Em least element of <math>S</math> is defined similarly.
If <math>(P, \leq)</math> has a greatest element (resp. a least element) then this element is also called Шаблон:Em (resp. Шаблон:Em) of <math>(P, \leq).</math>
Relationship to upper/lower bounds
Greatest elements are closely related to upper bounds.
Let <math>(P, \leq)</math> be a preordered set and let <math>S \subseteq P.</math> An Шаблон:Em is an element <math>u</math> such that <math>u \in P</math> and <math>s \leq u</math> for all <math>s \in S.</math> Importantly, an upper bound of <math>S</math> in <math>P</math> is Шаблон:Em required to be an element of <math>S.</math>
If <math>g \in P</math> then <math>g</math> is a greatest element of <math>S</math> if and only if <math>g</math> is an upper bound of <math>S</math> in <math>(P, \leq)</math> Шаблон:Em <math>g \in S.</math> In particular, any greatest element of <math>S</math> is also an upper bound of <math>S</math> (in <math>P</math>) but an upper bound of <math>S</math> in <math>P</math> is a greatest element of <math>S</math> if and only if it Шаблон:Em to <math>S.</math> In the particular case where <math>P = S,</math> the definition of "<math>u</math> is an upper bound of <math>S</math> Шаблон:Em" becomes: <math>u</math> is an element such that <math>u \in S</math> and <math>s \leq u</math> for all <math>s \in S,</math> which is Шаблон:Em to the definition of a greatest element given before. Thus <math>g</math> is a greatest element of <math>S</math> if and only if <math>g</math> is an upper bound of <math>S</math> Шаблон:Em.
If <math>u</math> is an upper bound of <math>S</math> Шаблон:Em that is not an upper bound of <math>S</math> Шаблон:Em (which can happen if and only if <math>u \not\in S</math>) then <math>u</math> can Шаблон:Em be a greatest element of <math>S</math> (however, it may be possible that some other element Шаблон:Em a greatest element of <math>S</math>). In particular, it is possible for <math>S</math> to simultaneously Шаблон:Em have a greatest element Шаблон:Em for there to exist some upper bound of <math>S</math> Шаблон:Em.
Even if a set has some upper bounds, it need not have a greatest element, as shown by the example of the negative real numbers. This example also demonstrates that the existence of a least upper bound (the number 0 in this case) does not imply the existence of a greatest element either.
Contrast to maximal elements and local/absolute maximums
A greatest element of a subset of a preordered set should not be confused with a maximal element of the set, which are elements that are not strictly smaller than any other element in the set.
Let <math>(P, \leq)</math> be a preordered set and let <math>S \subseteq P.</math> An element <math>m \in S</math> is said to be a Шаблон:Em if the following condition is satisfied:
- whenever <math>s \in S</math> satisfies <math>m \leq s,</math> then necessarily <math>s \leq m.</math>
If <math>(P, \leq)</math> is a partially ordered set then <math>m \in S</math> is a maximal element of <math>S</math> if and only if there does Шаблон:Em exist any <math>s \in S</math> such that <math>m \leq s</math> and <math>s \neq m.</math> A Шаблон:Em is defined to mean a maximal element of the subset <math>S := P.</math>
A set can have several maximal elements without having a greatest element. Like upper bounds and maximal elements, greatest elements may fail to exist.
In a totally ordered set the maximal element and the greatest element coincide; and it is also called maximum; in the case of function values it is also called the absolute maximum, to avoid confusion with a local maximum.[1] The dual terms are minimum and absolute minimum. Together they are called the absolute extrema. Similar conclusions hold for least elements.
- Role of (in)comparability in distinguishing greatest vs. maximal elements
One of the most important differences between a greatest element <math>g</math> and a maximal element <math>m</math> of a preordered set <math>(P, \leq)</math> has to do with what elements they are comparable to. Two elements <math>x, y \in P</math> are said to be Шаблон:Em if <math>x \leq y</math> or <math>y \leq x</math>; they are called Шаблон:Em if they are not comparable. Because preorders are reflexive (which means that <math>x \leq x</math> is true for all elements <math>x</math>), every element <math>x</math> is always comparable to itself. Consequently, the only pairs of elements that could possibly be incomparable are Шаблон:Em pairs. In general, however, preordered sets (and even directed partially ordered sets) may have elements that are incomparable.
By definition, an element <math>g \in P</math> is a greatest element of <math>(P, \leq)</math> if <math>s \leq g,</math> for every <math>s \in P</math>; so by its very definition, a greatest element of <math>(P, \leq)</math> must, in particular, be comparable to Шаблон:Em element in <math>P.</math> This is not required of maximal elements. Maximal elements of <math>(P, \leq)</math> are Шаблон:Em required to be comparable to every element in <math>P.</math> This is because unlike the definition of "greatest element", the definition of "maximal element" includes an important Шаблон:Em statement. The defining condition for <math>m \in P</math> to be a maximal element of <math>(P, \leq)</math> can be reworded as:
- For all <math>s \in P,</math> Шаблон:Em <math>m \leq s</math> (so elements that are incomparable to <math>m</math> are ignored) then <math>s \leq m.</math>
- Example where all elements are maximal but none are greatest
Suppose that <math>S</math> is a set containing Шаблон:Em (distinct) elements and define a partial order <math>\,\leq\,</math> on <math>S</math> by declaring that <math>i \leq j</math> if and only if <math>i = j.</math> If <math>i \neq j</math> belong to <math>S</math> then neither <math>i \leq j</math> nor <math>j \leq i</math> holds, which shows that all pairs of distinct (i.e. non-equal) elements in <math>S</math> are Шаблон:Emcomparable. Consequently, <math>(S, \leq)</math> can not possibly have a greatest element (because a greatest element of <math>S</math> would, in particular, have to be comparable to Шаблон:Em element of <math>S</math> but <math>S</math> has no such element). However, Шаблон:Em element <math>m \in S</math> is a maximal element of <math>(S, \leq)</math> because there is exactly one element in <math>S</math> that is both comparable to <math>m</math> and <math>\geq m,</math> that element being <math>m</math> itself (which of course, is <math>\leq m</math>).[note 1]
In contrast, if a preordered set <math>(P, \leq)</math> does happen to have a greatest element <math>g</math> then <math>g</math> will necessarily be a maximal element of <math>(P, \leq)</math> and moreover, as a consequence of the greatest element <math>g</math> being comparable to Шаблон:Em element of <math>P,</math> if <math>(P, \leq)</math> is also partially ordered then it is possible to conclude that <math>g</math> is the Шаблон:Em maximal element of <math>(P, \leq).</math> However, the uniqueness conclusion is no longer guaranteed if the preordered set <math>(P, \leq)</math> is Шаблон:Em also partially ordered. For example, suppose that <math>R</math> is a non-empty set and define a preorder <math>\,\leq\,</math> on <math>R</math> by declaring that <math>i \leq j</math> Шаблон:Em holds for all <math>i, j \in R.</math> The directed preordered set <math>(R, \leq)</math> is partially ordered if and only if <math>R</math> has exactly one element. All pairs of elements from <math>R</math> are comparable and Шаблон:Em element of <math>R</math> is a greatest element (and thus also a maximal element) of <math>(R, \leq).</math> So in particular, if <math>R</math> has at least two elements then <math>(R, \leq)</math> has multiple Шаблон:Em greatest elements.
Properties
Throughout, let <math>(P, \leq)</math> be a partially ordered set and let <math>S \subseteq P.</math>
- A set <math>S</math> can have at most Шаблон:Em greatest element.[note 2] Thus if a set has a greatest element then it is necessarily unique.
- If it exists, then the greatest element of <math>S</math> is an upper bound of <math>S</math> that is also contained in <math>S.</math>
- If <math>g</math> is the greatest element of <math>S</math> then <math>g</math> is also a maximal element of <math>S</math>[note 3] and moreover, any other maximal element of <math>S</math> will necessarily be equal to <math>g.</math>[note 4]
- Thus if a set <math>S</math> has several maximal elements then it cannot have a greatest element.
- If <math>P</math> satisfies the ascending chain condition, a subset <math>S</math> of <math>P</math> has a greatest element if, and only if, it has one maximal element.[note 5]
- When the restriction of <math>\,\leq\,</math> to <math>S</math> is a total order (<math>S = \{ 1, 2, 4 \}</math> in the topmost picture is an example), then the notions of maximal element and greatest element coincide.[note 6]
- However, this is not a necessary condition for whenever <math>S</math> 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 <math>S</math> of <math>P,</math> then <math>\,\leq\,</math> is a total order on <math>P.</math>[note 7]
Sufficient conditions
- A finite chain always has a greatest and a least element.
Top and bottom
The least and greatest element of the whole partially ordered set play a special role and are also called bottom (⊥) and top (⊤), or zero (0) and unit (1), respectively. If both exist, the poset is called a bounded poset. The notation of 0 and 1 is used preferably when the poset is a complemented lattice, and when no confusion is likely, i.e. when one is not talking about partial orders of numbers that already contain elements 0 and 1 different from bottom and top. The existence of least and greatest elements is a special completeness property of a partial order.
Further introductory information is found in the article on order theory.
Examples
- The subset of integers has no upper bound in the set <math>\mathbb{R}</math> of real numbers.
- Let the relation <math>\,\leq\,</math> on <math>\{ a, b, c, d \}</math> be given by <math>a \leq c,</math> <math>a \leq d,</math> <math>b \leq c,</math> <math>b \leq d.</math> The set <math>\{ a, b \}</math> has upper bounds <math>c</math> and <math>d,</math> but no least upper bound, and no greatest element (cf. picture).
- In the rational numbers, the set of numbers with their square less than 2 has upper bounds but no greatest element and no least upper bound.
- In <math>\mathbb{R},</math> the set of numbers less than 1 has a least upper bound, viz. 1, but no greatest element.
- In <math>\mathbb{R},</math> the set of numbers less than or equal to 1 has a greatest element, viz. 1, which is also its least upper bound.
- In <math>\mathbb{R}^2</math> with the product order, the set of pairs <math>(x, y)</math> with <math>0 < x < 1</math> has no upper bound.
- In <math>\mathbb{R}^2</math> with the lexicographical order, this set has upper bounds, e.g. <math>(1, 0).</math> It has no least upper bound.
See also
- Essential supremum and essential infimum
- Initial and terminal objects
- Maximal and minimal elements
- Limit superior and limit inferior (infimum limit)
- Upper and lower bounds
Notes
References
- ↑ The notion of locality requires the function's domain to be at least a topological space.
Ошибка цитирования Для существующих тегов <ref> группы «note» не найдено соответствующего тега <references group="note"/>
