Upper Bounds 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 a partially ordered set \(A\). If there is an element \(a\) of \(A\) that is greater than or equal to every element of \(X\), that is, if \[
\exists a\in A,\ \forall x\in X:x\leq a
\]holds, then \(a\) is called an upper bound of \(X\). By definition, an upper bound of \(X\) need not be an element of \(X\). In this respect, an upper bound differs from a greatest element or a maximal element.
Conversely, an element \(a\) of \(A\) is not an upper bound 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, this is equivalent to \[
\exists x\in X:a<x.
\]Thus, in a totally ordered set, if there is an element of \(X\) greater than \(a\in A\), then \(a\) is not an upper bound of \(X\).
\left[ 0,1\right] =\left\{ x\in\mathbb{R} \ |\ 0\leq x\leq1\right\} .
\]For every \(x\in\left[ 0,1\right] \), \[
x\leq1
\]holds. Therefore, the real number \(1\in\mathbb{R} \) is an upper bound of \(\left[ 0,1\right] \).
\left( x_{1},y_{1}\right) \leq\left( x_{2},y_{2}\right) \Leftrightarrow x_{1}\leq x_{2}\wedge y_{1}\leq y_{2}.
\]Here, the \(\leq\) on the right-hand side denotes the usual order on \(\mathbb{R} \). Then \(\left(\mathbb{R} ^{2},\leq\right) \) is a partially ordered set. Consider the subset of \(\mathbb{R} ^{2}\) \[
A=\left\{ \left( x_{1},x_{2}\right) \in\mathbb{R} ^{2}\ |\ x_{1}^{2}+x_{2}^{2}\leq1\right\} .
\]For every point \(\left( x_{1},x_{2}\right) \in A\), \[
x_{1}\leq1\wedge x_{2}\leq1,
\]that is,
\[
\left( x_{1},x_{2}\right) \leq\left( 1,1\right) ,
\]holds. Therefore, the point \(\left( 1,1\right) \in\mathbb{R} ^{2}\) is an upper bound of \(A\).
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\} .
\]Then \(\left( 2^{A},\subset\right) \) is a partially ordered set. Consider the subset \[
X=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} ,\left\{ a,b,c\right\}
\right\} .
\]Since \(\left\{ a,b,c\right\} \in2^{A}\) 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*}the set \(\left\{ a,b,c\right\} \) is an upper bound of \(X\).
A=\left\{ 2,3,4,5,8,10,12,24,30\right\} .
\]Thus, for arbitrary \(x,y\in A\), \[
x|y\Leftrightarrow y\text{ is a multiple of }x.
\]Then \(\left( A,|\right) \) is a partially ordered set. Consider the subset \[
X=\left\{ 8,12\right\} .
\]The number \(24\) is a multiple of both \(8\) and \(12\), so \begin{align*}
& 8|24\\
& 12|24
\end{align*}both hold. Therefore, \(24\) is an upper bound of \(X\).
Lower Bounds of Ordered Subsets
Let \(X\) be a nonempty subset of a partially ordered set \(\left( A,\leq\right) \). If there is an element \(a\) of \(A\) that is less than or equal to every element of \(X\), that is, if \[
\exists a\in A,\ \forall x\in X:a\leq x
\]holds, then \(a\) is called a lower bound of \(X\). By definition, a lower bound of \(X\) need not be an element of \(X\). In this respect, a lower bound differs from a least element or a minimal element.
Conversely, an element \(a\) of \(A\) is not a lower bound 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, this is equivalent to \[
\exists x\in X:x<a.
\]Thus, in a totally ordered set, if there is an element of \(X\) smaller than \(a\in A\), then \(a\) is not a lower bound of \(X\).
\left[ 0,1\right] =\left\{ x\in\mathbb{R} \ |\ 0\leq x\leq1\right\} .
\]For every \(x\in\left[ 0,1\right] \), \[
0\leq x
\]holds. Therefore, the real number \(0\in\mathbb{R} \) is a lower bound of \(\left[ 0,1\right] \).
A=\left\{ \left( x_{1},x_{2}\right) \in\mathbb{R} ^{2}\ |\ x_{1}^{2}+x_{2}^{2}\leq1\right\} .
\]For every point \(\left( x_{1},x_{2}\right) \in A\), \[
-1\leq x_{1}\wedge-1\leq x_{2},
\]that is,
\[
\left( -1,-1\right) \leq\left( x_{1},x_{2}\right) ,
\]holds. Therefore, \(\left( -1,-1\right) \in\mathbb{R} ^{2}\) is a lower bound of \(A\).
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\} .
\]Then \(\left( 2^{A},\subset\right) \) is a partially ordered set. Consider \[
X=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} ,\left\{ a,b,c\right\}
\right\} .
\]Since \(\left\{ a\right\} \in2^{A}\) 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*}the set \(\left\{ a\right\} \) is a lower bound of \(X\).
A=\left\{ 2,3,4,5,8,10,12,24,30\right\} .
\]Then \(\left( A,|\right) \) is a partially ordered set. Consider \[
X=\left\{ 8,12\right\} .
\]The number \(2\) is a divisor of both \(8\) and \(12\), so \begin{align*}
& 2|8\\
& 2|12
\end{align*}both hold. Therefore, \(2\) is a lower bound of \(X\).
Existence of Upper and Lower Bounds
In general, a nonempty subset of an ordered set need not have an upper bound or a lower bound, as the following example shows.
\exists z\in\mathbb{Z} :a<z.
\]This contradicts the assumption that \(a\) is an upper bound of \(\mathbb{Z} \). Therefore, \(\mathbb{Z} \) has no upper bound. Similarly, if there were a real number \(a\in\mathbb{R} \) that was a lower bound of \(\mathbb{Z} \), then by the Archimedean property there would exist an integer smaller than \(a\), that is, \[
\exists z\in\mathbb{Z} :z<a.
\]This contradicts the assumption that \(a\) is a lower bound of \(\mathbb{Z} \). Hence \(\mathbb{Z} \) has no lower bound.
However, if the ordered set \(\left( A,\leq\right) \) is totally ordered and a nonempty subset \(X\) is finite, then \(X\) is guaranteed to have both an upper bound and a lower bound.
Number of Upper and Lower Bounds
We have seen that a nonempty subset of an ordered set need not have an upper bound or a lower bound. Even when upper or lower bounds exist, they need not be unique. This contrasts with greatest and least elements, which are unique whenever they exist.
\left[ 0,1\right] =\left\{ x\in\mathbb{R} \ |\ 0\leq x\leq1\right\} .
\]Every real number greater than or equal to \(1\) is an upper bound of \(\left[ 0,1\right] \), and every real number less than or equal to \(0\) is a lower bound. Thus, \(\left[ 0,1\right] \) has infinitely many upper bounds and infinitely many lower bounds.
A=\left\{ 2,3,4,5,8,10,12,24,30\right\} .
\]Then \(\left( A,|\right) \) is a partially ordered set. Consider \[
X=\left\{ 8,12\right\} .
\]The only upper bound of \(X\) is \(24\), whereas the lower bounds of \(X\) are \(2\) and \(4\).
Bounded Above, Bounded Below, and Bounded
Let \(X\) be a nonempty subset of a partially ordered set \(\left( A,\leq\right) \). As seen above, upper and lower bounds of \(X\) need not exist, and when they do exist, they need not be unique. We denote the set of all upper bounds of \(X\) by \(U\left( X\right) \) and the set of all lower bounds of \(X\) by \(L\left( X\right) \). Thus, \begin{align*}
U\left( X\right) & =\left\{ a\in A\ |\ \forall x\in X:x\leq a\right\} \\
L\left( X\right) & =\left\{ a\in A\ |\ \forall x\in X:a\leq x\right\} .
\end{align*}If \(U\left( X\right) \not =\phi\), that is, if \(X\) has an upper bound, then \(X\) is said to be bounded above. If \(L\left( X\right) \not =\phi\), that is, if \(X\) has a lower bound, then \(X\) is said to be bounded below. If \(X\) is both bounded above and bounded below, that is, if both \(U\left( X\right) \not =\phi\) and \(L\left( X\right) \not =\phi\) hold, then \(X\) is said to be bounded.
\left[ 0,1\right] =\left\{ x\in\mathbb{R} \ |\ 0\leq x\leq1\right\} .
\]Its sets of upper and lower bounds are
\begin{align*}
U\left( \left[ 0,1\right] \right) & =\left\{ x\in\mathbb{R} \ |\ x\geq1\right\} =[1,+\infty)\\
L\left( \left[ 0,1\right] \right) & =\left\{ x\in\mathbb{R} \ |\ x\leq0\right\} =(-\infty,0].
\end{align*}Both are nonempty, so \(\left[ 0,1\right] \) is bounded.
A=\left\{ \left( x_{1},x_{2}\right) \in\mathbb{R} ^{2}\ |\ x_{1}^{2}+x_{2}^{2}\leq1\right\} .
\]The sets of upper and lower bounds of \(A\) are \begin{align*}
U\left( A\right) & =\left\{ \left( x,y\right) \in\mathbb{R} ^{2}\ |\ x\geq1\wedge y\geq1\right\} \\
L\left( A\right) & =\left\{ \left( x,y\right) \in\mathbb{R} ^{2}\ |\ x\leq-1\wedge y\leq-1\right\} .
\end{align*}Both are nonempty, so \(A\) is bounded.
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\} .
\]Then \(\left( 2^{A},\subset\right) \) is a partially ordered set. Consider \[
X=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} ,\left\{ a,b,c\right\}
\right\} .
\]The sets of upper and lower bounds of \(X\) are \begin{align*}
U\left( X\right) & =\left\{ \left\{ a,b,c\right\} \right\} \\
L\left( X\right) & =\left\{ \left\{ a\right\} \right\} .
\end{align*}Both are nonempty, so \(X\) is bounded.
A=\left\{ 2,3,4,5,8,10,12,24,30\right\} .
\]Then \(\left( A,|\right) \) is a partially ordered set. Consider \[
X=\left\{ 8,12\right\} .
\]The sets of upper and lower bounds of \(X\) are \begin{align*}
U\left( X\right) & =\left\{ 24\right\} \\
L\left( X\right) & =\left\{ 2,4\right\} .
\end{align*}Both are nonempty, so \(X\) is bounded.
Relationship Between Upper Bounds and Greatest Elements, and Between Lower Bounds and Least Elements
If a nonempty subset of a partially ordered set has a greatest element, then that element is also an upper bound. Likewise, a least element is also a lower bound.
X=\left\{ 2,4,6,8,10,30,60,120,240\right\} .
\]The number \(240\) belongs to \(X\) and is a multiple of every element of \(X\), so \(240\) is the greatest element of \(X\). By the preceding proposition, \(240\) is therefore also an upper bound of \(X\). Likewise, \(2\) belongs to \(X\) and divides every element of \(X\), so \(2\) is the least element of \(X\). Hence, by the preceding proposition, \(2\) is also a lower bound of \(X\).
The converse of the preceding proposition does not hold. That is, if a nonempty subset \(X\) of a partially ordered set has an upper bound, that upper bound need not be the greatest element of \(X\). Indeed, an upper bound of \(X\) need not belong to \(X\), whereas the greatest element of \(X\) must belong to \(X\). Likewise, if \(X\) has a lower bound, that lower bound need not be the least element of \(X\).
\left[ 0,1\right] =\left\{ x\in\mathbb{R} \ |\ 0\leq x\leq1\right\} .
\]As noted above, its sets of upper and lower bounds are
\begin{align*}
U\left( \left[ 0,1\right] \right) & =\left\{ x\in\mathbb{R} \ |\ x\geq1\right\} =[1,+\infty)\\
L\left( \left[ 0,1\right] \right) & =\left\{ x\in\mathbb{R} \ |\ x\leq0\right\} =(-\infty,0].
\end{align*}Thus every real number greater than \(1\) is an upper bound of \(\left[ 0,1\right] \) but is not its greatest element, and every real number smaller than \(0\) is a lower bound of \(\left[ 0,1\right] \) but is not its least element.
Upper and Lower Bounds of the Empty Set
So far, we have considered upper and lower bounds of nonempty ordered subsets. Since the empty set is a subset of every set, it is also an ordered subset of every ordered set. Do upper and lower bounds of the empty set exist? The following proposition provides the answer.
U\left( \phi\right) & =A\\
L\left( \phi\right) & =A
\end{align*}hold.
Exercises
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\} .
\]Then \(\left( 2^{A},\subset\right) \) is a partially ordered set. For the subset \[
X=\left\{ \left\{ a\right\} ,\left\{ b\right\} ,\left\{ c\right\}
\right\} ,
\]find the greatest element, least element, upper bounds, and lower bounds of
\(X\).
A=\left\{ 2,4,6,8,10,30,60,120,240\right\} .
\]Then \(\left( A,|\right) \) is a partially ordered set. For the subset \[
X=\left\{ 30,60\right\} ,
\]find the greatest element, least element, upper bounds, and lower bounds of
\(X\).
A=\left\{ x\in\mathbb{Q} \ |\ x^{3}<3\right\} .
\]Is \(A\) bounded? Discuss.
\[
A=\left\{ 1,2,3,4\right\}
\]and define set inclusion \(\subset\) on the power set \(2^{A}\). For the subset \[
X=\left\{ \left\{ 1,2\right\} ,\left\{ 1,3\right\} \right\} ,
\]find the set \(U\left( X\right) \) of upper bounds and the set \(L\left( X\right) \) of lower bounds. Also determine whether \(X\) has a greatest element or a least element.
A=\left\{ 1,2,3,4,6,8,12,24\right\} .
\]For the subset
\[
X=\left\{ 4,6\right\} ,
\]find the set \(U\left( X\right) \) of upper bounds and the set \(L\left( X\right) \) of lower bounds. Also determine whether \(X\) is bounded above, bounded below, or bounded.
X=\left\{ \left( 0,1\right) ,\left( 1,0\right) \right\} ,
\]find its sets of upper and lower bounds. Also determine whether \(X\) has a greatest element or a least element.
X\subset Y.
\]Show that
\[
U\left( Y\right) \subset U\left( X\right)
\]and
\[
L\left( Y\right) \subset L\left( X\right)
\]hold.
U\left( X\cup Y\right) =U\left( X\right) \cap U\left( Y\right)
\]and
\[
L\left( X\cup Y\right) =L\left( X\right) \cap L\left( Y\right)
\]hold.
\max X\text{ exists} & \Leftrightarrow X\cap U\left( X\right) \not =\phi,\\
\min X\text{ exists} & \Leftrightarrow X\cap L\left( X\right) \not =\phi.
\end{align*}Furthermore, show that if \(\max X\) exists, then \[
X\cap U\left( X\right) =\left\{ \max X\right\} ,
\]and if \(\min X\) exists, then \[
X\cap L\left( X\right) =\left\{ \min X\right\} .
\]
