Largest and smallest element

The largest or smallest element are terms from the mathematical sub-area of order theory . The largest element is also referred to as the maximum ; accordingly, the smallest element is referred to as the minimum .

An element of an ordered set is the largest element of the set if all other elements are smaller. It is the smallest element of the set when all other elements are larger. Neither the largest nor the smallest element of a set has to exist, but in the case of its existence it is uniquely determined except for association.

A maximum function delivers the largest of its arguments as a value, a minimum function delivers the smallest of its arguments.

The abbreviations max and min are common, more rarely also max and min .

Definitions

${\displaystyle (X,\leq )}$be a quasi-order , a subset of the basic set and . ${\displaystyle M\subseteq X}$ ${\displaystyle X}$ ${\displaystyle x\in M}$

${\displaystyle x\ }$is largest element of ${\displaystyle M\ }$ ${\displaystyle :\Longleftrightarrow \forall y\in M:y\leq x}$

${\displaystyle x\ }$is the smallest element of ${\displaystyle M\ }$ ${\displaystyle :\Longleftrightarrow \forall y\in M:x\leq y}$

The smallest elements of are associated, i.e. they are related in both directions: If and the smallest element of are, then applies . The same applies to the largest elements. If is antisymmetric , it immediately follows that both the largest and the smallest element (if any) are uniquely determined. ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M}$ ${\displaystyle x\leq y\leq x}$ ${\displaystyle \leq }$

A largest element of is also called a maximum of , a smallest element a minimum . The notations and are used occasionally. Note, however, that the terms maximum element and minimum element are not equivalent if there is no total order. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle \max(M)}$ ${\displaystyle \min(M)}$

Smallest and largest elements of themselves (if they exist) are sometimes denoted with 0 and 1 or with and . ${\displaystyle X}$ ${\displaystyle \bot }$ ${\displaystyle \top }$

An order in which every non-empty subset has a smallest element is called a well-order .

Examples

• ${\displaystyle 1\ }$is the largest element of the set of rational numbers . The crowd has no smallest element. ${\displaystyle \left\{1,{\tfrac {1}{2}},{\tfrac {1}{3}},{\tfrac {1}{4}},\dots \right\}}$
• ${\displaystyle 0\ }$is the smallest element of the set of rational numbers. The crowd has no greatest element. ${\displaystyle \left\{0,{\tfrac {1}{2}},{\tfrac {2}{3}},{\tfrac {3}{4}},{\tfrac {4}{5}},\dots \right\}}$
• The set of positive integers has a smallest but no largest element. The reverse is true for the set of negative integers.
• In the power set ordered with respect to inclusion , the largest and the empty set is the smallest. ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle X}$ ${\displaystyle \varnothing }$
• The set of all finite subsets of an infinite set does not have a largest element (with regard to inclusion).
• In the (ordinary) order on the set of natural numbers, every non-empty subset has a smallest element, so it is a matter of a well-order.
• If you order the set of natural numbers (including 0) in terms of divisibility , 0 is the largest element, since 0 is divided by every natural number. The smallest element is 1, since 1 divides every natural number.
• In every ring , the path is , and thus , the largest element in terms of the divisibility relation . All units (divisors of ) in a unitary ring are the smallest elements. ${\displaystyle (R,\mid )}$ ${\displaystyle 0}$ ${\displaystyle \forall r\in R:r\cdot 0=0}$ ${\displaystyle \forall r\in R:r\mid 0}$ ${\displaystyle \mid }$ ${\displaystyle 1}$ ${\displaystyle (R,\mid )}$

properties

• Every finite non-empty chain has a largest and a smallest element.
• Is the largest element of , then is also the maximum element of (and all further maximum elements of are to be associated). The reverse is not true: even if it has exactly one maximum element, it does not have to have a largest element. ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle M}$

  An example of this is the quantity with regard to the divisibility relation. 3 is the only maximum element here, but it is not the largest element because it is not shared by all other elements. ${\displaystyle \{2^{i}\mid i\in \mathbb {N} \}\cup \{3\}}$

• And mirrored: If the smallest element is of , then that is also the only minimal element of, apart from association . The reverse is not true: even if it has exactly one minimal element, it does not have to have a smallest element. ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$
• For total orders, the terms largest element and maximum element coincide. The smallest element and the minimum element also match.
• Is the greatest element of , then is also a supremum of . The opposite applies: ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle M}$

  Has no supremum, then also no greatest element. ${\displaystyle M}$

  Has a supremum that is not in , then has no greatest element. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

  If there is a supremum that is in, then that is the greatest element of . ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

• Is the smallest element of , then there is also an infimum of . The opposite applies: ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle M}$

  Has no infimum, then also no smallest element. ${\displaystyle M}$

  Has an infimum that is not in , then has no smallest element. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

  If there is an infimum that lies in, then this is a smallest element of . ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

• If a set has at least two unassociated maximal elements, then it has no largest element. If it has at least two unassociated minimal elements, then it has no smallest element.

Maximum and minimum functions

In a total order (e.g. the ordinary order on the real numbers ) every finite non-empty set has a maximum and a minimum. For are therefore the function values ${\displaystyle n\geq 2}$

${\displaystyle \max(x_{1},x_{2},\dotsc ,x_{n})}$

${\displaystyle \min(x_{1},x_{2},\dotsc ,x_{n})}$

as a maximum or minimum of well-defined. ${\displaystyle \left\{x_{1},x_{2},\dotsc ,x_{n}\right\}}$

The higher- digit functions can be traced back recursively to the two-digit:

${\displaystyle \max(x_{1},x_{2},\dotsc ,x_{n})=\max(x_{1},\max(x_{2},\dotsc ,x_{n}))}$

${\displaystyle \min(x_{1},x_{2},\dotsc ,x_{n})=\min(x_{1},\min(x_{2},\dotsc ,x_{n}))}$

In the area of ​​real numbers, the two-digit functions can also be specified as follows:

${\displaystyle \max(x_{1},x_{2})={\frac {x_{1}+x_{2}+|x_{1}-x_{2}|}{2}}}$

${\displaystyle \min(x_{1},x_{2})={\frac {x_{1}+x_{2}-|x_{1}-x_{2}|}{2}}}$

This proves that and are continuous functions because sum, difference, absolute value, quotient are continuous functions and compositions of continuous functions are also continuous. ${\displaystyle \operatorname {max} }$ ${\displaystyle \operatorname {min} }$

The relationship between - and - function quickly becomes clear from the above equations : ${\displaystyle \operatorname {max} }$ ${\displaystyle \operatorname {min} }$

${\displaystyle \max(x_{1},x_{2})=-\min(-x_{1},-x_{2})}$

Furthermore, the following calculation rules apply to all of them ${\displaystyle x_{1},x_{2},x_{3}\in \mathbb {R} }$

${\displaystyle \max(x_{1},x_{2})+x_{3}=\max(x_{1}+x_{3},x_{2}+x_{3})}$

${\displaystyle \min(x_{1},x_{2})+x_{3}=\min(x_{1}+x_{3},x_{2}+x_{3})}$

and, if so , too ${\displaystyle \lambda \geq 0}$

${\displaystyle \lambda \max(x_{1},x_{2})=\max(\lambda x_{1},\lambda x_{2})}$

${\displaystyle \lambda \min(x_{1},x_{2})=\min(\lambda x_{1},\lambda x_{2}).}$

Remarks

1. ↑ Has no largest element, then it can be embedded in order-preserving with as the supremum of and of . ${\displaystyle (X,\leq )}$ ${\displaystyle X\cup \{\infty \}}$ ${\displaystyle \infty }$ ${\displaystyle X}$ ${\displaystyle X\cup \{\infty \}}$

Individual evidence

1. ^ Paul Taylor: Practical Foundations of Mathematics . Cambridge University Press, Cambridge 1999, ISBN 0-521-63107-6 , pp. 131 .

literature

• Deiser, Oliver: Introduction to set theory, 2nd edition, Springer, Berlin 2004, ISBN 3-540-20401-6