Greatest Elements of Ordered Subsets
A binary relation \(\leq\) on a set \(A\) is a partial order if it satisfies reflexivity, antisymmetry, and transitivity, that is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:x\leq x\\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right]
\end{align*}hold. If, in addition to these three properties, the binary relation \(\leq\) on \(A\) satisfies completeness, \[
\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\]then \(\leq\) is called a total order. Hereafter, the term order refers collectively to both partial orders and total orders. A set \(A\) equipped with an order \(\leq\) is called an ordered set. Given an order \(\leq\) on a set \(A\), the binary relation \(<\) on \(A\) defined by \[
x<y\Leftrightarrow\left( x\leq y\wedge x\not =y\right)
\]for arbitrary \(x,y\in A\) is called the strict order associated with \(\leq\).
Let \(X\) be a nonempty subset of an ordered set \(A\). If there is an element \(a\in X\) that is greater than or equal to every element of \(X\), that is, if \[
\exists a\in X,\ \forall x\in X:x\leq a
\]holds, then \(a\) is called the greatest element (maximum element) or last element of \(X\), and we write \[
a=\max X.
\]Thus, the greatest element \(\max X\) of \(X\) is defined as an element of \(X\) satisfying
\[
\forall x\in X:x\leq\max X.
\]The greatest element of \(X\) must itself belong to \(X\). That is, \[
\max X\in X.
\]An element that does not belong to \(X\) cannot be the greatest element of \(X\).
Conversely, an element \(a\in X\) is not the greatest element of \(X\) if \[
\exists x\in X:\lnot\left( x\leq a\right)
\]holds. In particular, if \(\leq\) satisfies completeness, that is, if \(\leq\) is a total order, then \[
\lnot\left( x\leq a\right) \Leftrightarrow a<x
\]holds. Therefore, \(a\) is not the greatest element of \(X\) if and only if \[
\exists x\in X:a<x
\]holds. In other words, when \(\leq\) is a total order, if there is an element of \(X\) greater than \(a\in X\), then \(a\) is not the greatest element of \(X\).
\left[ 0,1\right] =\left\{ x\in\mathbb{R} \ |\ 0\leq x\leq1\right\} .
\]Since \(1\in\left[ 0,1\right] \) satisfies \[
\forall x\in\left[ 0,1\right] :x\leq1,
\]we have
\[
\max\left[ 0,1\right] =1.
\]
2^{A}=\left\{ \phi,\left\{ a\right\} ,\left\{ b\right\} ,\left\{
c\right\} ,\left\{ a,b\right\} ,\left\{ b,c\right\} ,\left\{
a,c\right\} ,\left\{ a,b,c\right\} \right\}
\]is a partial order. Consider the subset
\[
X=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} ,\left\{ a,b,c\right\}
\right\} .
\]The element \(\left\{ a,b,c\right\} \in X\) satisfies \begin{align*}
\left\{ a\right\} & \subset\left\{ a,b,c\right\} \\
\left\{ a,b\right\} & \subset\left\{ a,b,c\right\} \\
\left\{ a,b,c\right\} & \subset\left\{ a,b,c\right\} ,
\end{align*}that is,
\[
\forall A\in X:A\subset\left\{ a,b,c\right\} .
\]Hence,
\[
\max X=\left\{ a,b,c\right\} .
\]
x|y\Leftrightarrow y\text{ is a multiple of }x
\]for arbitrary \(x,y\in\mathbb{N} \). Consider the subset \[
X=\left\{ 2,4,6,8,10,30,60,120,240\right\} .
\]The element \(240\in X\) satisfies \[
\forall x\in X:240\text{ is a multiple of }x,
\]that is,
\[
\forall x\in X:x|240.
\]Hence,
\[
\max X=240.
\]
Least Elements of Ordered Subsets
Let \(X\) be a nonempty subset of an ordered set \(A\). If there is an element \(a\in X\) that is less than or equal to every element of \(X\), that is, if \[
\exists a\in X,\ \forall x\in X:a\leq x
\]holds, then \(a\) is called the least element (minimum element) or first element of \(X\), and we write \[
a=\min X.
\]Thus, the least element \(\min X\) of \(X\) is defined as an element of \(X\) satisfying
\[
\forall x\in X:\min X\leq x.
\]The least element of \(X\) must itself belong to \(X\). That is, \[
\min X\in X.
\]An element that does not belong to \(X\) cannot be the least element of \(X\).
Conversely, an element \(a\in X\) is not the least element of \(X\) if \[
\exists x\in X:\lnot\left( a\leq x\right)
\]holds. In particular, if \(\leq\) satisfies completeness, that is, if \(\leq\) is a total order, then \[
\lnot\left( a\leq x\right) \Leftrightarrow x<a
\]holds. Therefore, \(a\) is not the least element of \(X\) if and only if \[
\exists x\in X:x<a
\]holds. In other words, when \(\leq\) is a total order, if there is an element of \(X\) smaller than \(a\in X\), then \(a\) is not the least element of \(X\).
\left[ 0,1\right] =\left\{ x\in\mathbb{R} \ |\ 0\leq x\leq1\right\} .
\]Since \(0\in\left[ 0,1\right] \) satisfies \[
\forall x\in\left[ 0,1\right] :0\leq x,
\]we have
\[
\min\left[ 0,1\right] =0.
\]
2^{A}=\left\{ \phi,\left\{ a\right\} ,\left\{ b\right\} ,\left\{
c\right\} ,\left\{ a,b\right\} ,\left\{ b,c\right\} ,\left\{
a,c\right\} ,\left\{ a,b,c\right\} \right\}
\]is a partial order. Consider the subset
\[
X=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} ,\left\{ a,b,c\right\}
\right\} .
\]The element \(\left\{ a\right\} \in X\) satisfies \begin{align*}
\left\{ a\right\} & \subset\left\{ a\right\} \\
\left\{ a\right\} & \subset\left\{ a,b\right\} \\
\left\{ a\right\} & \subset\left\{ a,b,c\right\} ,
\end{align*}that is,
\[
\forall A\in X:\left\{ a\right\} \subset A.
\]Hence,
\[
\min X=\left\{ a\right\} .
\]
x|y\Leftrightarrow y\text{ is a multiple of }x
\]for arbitrary \(x,y\in\mathbb{N} \). Consider the subset \[
X=\left\{ 2,4,6,8,10,30,60,120,240\right\} .
\]The element \(2\in X\) satisfies \[
\forall x\in X:x\text{ is a multiple of }2,
\]that is,
\[
\forall x\in X:2|x.
\]Hence,
\[
\min X=2.
\]
The Greatest and Least Elements Need Not Be Distinct
The following is an example of an ordered subset whose greatest and least elements are distinct.
A=\left\{ x\in\mathbb{R} \ |\ a\leq x\leq b\right\} .
\]Then
\begin{align*}
\max A & =b\\
\min A & =a.
\end{align*}Since \(a<b\) by assumption, \[
\max A\not =\min A.
\]
The greatest element and the least element of an ordered subset may also coincide, as the following example shows.
\left\{ a\right\} .
\]Since \(a\in\left\{ a\right\} \), the set \(\left\{ a\right\} \) is nonempty. By reflexivity of \(\leq\), \[
\forall a\in\left\{ a\right\} :a\leq a
\]holds. Therefore, by the definitions of the greatest and least elements,
\begin{align*}
\max\left\{ a\right\} & =a\\
\min\left\{ a\right\} & =a.
\end{align*}Hence,
\[
\max\left\{ a\right\} =\min\left\{ a\right\} .
\]
Greatest and Least Elements Need Not Exist
An ordered subset need not have a greatest element or a least element, as the following examples show.
A=\left\{ x\in\mathbb{R} \ |\ a<x<b\right\} .
\]To show that \(\max A\) does not exist, suppose to the contrary that it does. By definition of a greatest element, \(\max A\in A\), and hence, by definition of \(A\), \begin{equation}
a<\max A<b.\quad \cdots (1)\end{equation}Since \(\max A\) and \(b\) are both real numbers, density of the rational numbers implies that there exists a rational number \(x\) satisfying \begin{equation}
\max A<x<b.\quad \cdots (2)\end{equation}Every rational number is a real number, so \(x\) is real. By \(\left( 1\right) \), \(\left( 2\right) \), and transitivity of \(<\), \[
a<x<b.
\]By definition of \(A\), this means that \(x\in A\). Thus there exists an element \(x\in A\) greater than \(\max A\), contradicting the assumption that \(\max A\) is the greatest element of \(A\). Therefore, by contradiction, \(\max A\) does not exist. The nonexistence of \(\min A\) can be shown in the same way.
2^{A}=\left\{ \phi,\left\{ a\right\} ,\left\{ b\right\} ,\left\{
c\right\} ,\left\{ a,b\right\} ,\left\{ b,c\right\} ,\left\{
a,c\right\} ,\left\{ a,b,c\right\} \right\}
\]is a partial order. Consider the subset
\[
X=\left\{ \left\{ a\right\} ,\left\{ b\right\} ,\left\{ c\right\}
\right\} .
\]No inclusion relation holds among \(\left\{ a\right\} \), \(\left\{ b\right\} \), and \(\left\{ c\right\} \). Hence there is no element of \(X\) that contains every element of \(X\) as a subset, so \(\max X\) does not exist. Likewise, there is no element of \(X\) that is a subset of every element of \(X\), so \(\min X\) does not exist.
It is also possible for an ordered subset to have only one of a greatest element and a least element. The following is an example of an ordered subset that has a least element but no greatest element.
A=\left\{ x\in\mathbb{R} \ |\ a\leq x<b\right\} .
\]Since \(a\in A\) and \[
\forall x\in A:a\leq x
\]holds,
\[
\min A=a.
\]On the other hand, the nonexistence of the greatest element \(\max A\) can be shown in the same way as in the preceding example.
Finite Totally Ordered Sets Have Greatest and Least Elements
If an ordered subset of a totally ordered set is finite, that is, if it contains only finitely many elements, then it is guaranteed to have both a greatest element and a least element. This can be proved by mathematical induction on the number \(n\) of elements in the finite set.
Note that the preceding proposition concerns subsets of totally ordered sets. For a partially ordered set, even a finite subset need not have a greatest element or a least element, as the following example shows.
2^{A}=\left\{ \phi,\left\{ a\right\} ,\left\{ b\right\} ,\left\{
c\right\} ,\left\{ a,b\right\} ,\left\{ b,c\right\} ,\left\{
a,c\right\} ,\left\{ a,b,c\right\} \right\}
\]is a partial order but not a total order. Consider the subset
\[
X=\left\{ \left\{ a\right\} ,\left\{ b\right\} ,\left\{ c\right\}
\right\} .
\]This is a finite set. As shown above, \(X\) has neither a greatest element nor a least element.
Uniqueness of Greatest and Least Elements
As shown above, an ordered subset need not have a greatest element or a least element. However, if a greatest or least element exists, it is unique.
Greatest and Least Elements of the Empty Set
So far, we have considered greatest and least elements only for nonempty subsets of an ordered set \(A\). Since the empty set is a subset of every set, \(\phi\subset A\). Do greatest and least elements of the empty set exist?
Suppose that an element \(\max\phi\in A\) corresponding to a greatest element of \(\phi\) exists. By definition of a greatest element, we must have \(\max\phi \in\phi\), but the empty set has no elements, which is a contradiction. Therefore, by contradiction, \(\phi\) has no greatest element.
The proof that the empty set \(\phi\) has no least element is analogous.
Exercises
x|y\Leftrightarrow y\text{ is a multiple of }x
\]for arbitrary \(x,y\in\mathbb{N} \). For the subset \[
X=\left\{ 2,3,4,5,8,10,12,24,30\right\} ,
\]determine whether a greatest element or a least element exists.
\]is a nonempty subset of \(\mathbb{R} \). Determine whether \(\mathbb{N} \) has a greatest element or a least element.
A=\left\{ x\in\mathbb{R} \ |\ a<x<b\right\} .
\]Does \(A\) have a least element? Discuss.
\[
U=\left\{ 1,2,3,4\right\} .
\]Define the inclusion relation \(\subset\) on the power set \(2^{U}\). For the subset \[
X=\left\{ \left\{ 1\right\} ,\left\{ 2\right\} ,\left\{ 1,2\right\}
,\left\{ 1,2,3\right\} \right\} ,
\]determine whether a greatest element and a least element exist.
X=\left\{ 2,4,8,12,24\right\} .
\]Find the greatest and least elements of \(X\).
& \left( a\right) \quad a=\max X\\
& \left( b\right) \quad\forall x\in X:\lnot\left( a<x\right) .
\end{align*}
\[
A=\left\{ 1,2,3\right\} \times\left\{ 1,2,3\right\}
\]and define the product order \(\leq\) on \(A\) by \[
\left( x_{1},x_{2}\right) \leq\left( y_{1},y_{2}\right) \Leftrightarrow
\left( x_{1}\leq y_{1}\wedge x_{2}\leq y_{2}\right) .
\]For the subset
\[
X=\left\{ \left( 1,1\right) ,\left( 1,3\right) ,\left( 2,2\right)
,\left( 3,1\right) ,\left( 3,3\right) \right\} ,
\]find the greatest and least elements.
