Greatest and Least Elements of Ordered Subsets

If an element of a nonempty ordered subset is greater than or equal to every other element of the subset, it is called the greatest element. If an element of a nonempty ordered subset is less than or equal to every other element of the subset, it is called the least element.

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

Example (Greatest Element Under the Usual Order on the Real Numbers)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. Consider the subset \[
\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.
\]
Example (Greatest Element Under Set Inclusion)
Let \(A=\left\{ a,b,c\right\} \). The inclusion relation \(\subset\) on the power set \[
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\} .
\]
Example (Greatest Element Under Divisibility on the Natural Numbers)
The divisibility relation \(|\) on the set of natural numbers \(\mathbb{N} \) is a partial order. It is defined by \[
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\).

Example (Least Element Under the Usual Order on the Real Numbers)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. Consider the subset \[
\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.
\]
Example (Least Element Under Set Inclusion)
Let \(A=\left\{ a,b,c\right\} \). The inclusion relation \(\subset\) on the power set \[
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\} .
\]
Example (Least Element Under Divisibility on the Natural Numbers)
The divisibility relation \(|\) on the set of natural numbers \(\mathbb{N} \) is a partial order. It is defined by \[
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.

Example (When the Greatest and Least Elements Are Distinct)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. Choose arbitrary real numbers \(a,b\in\mathbb{R} \) satisfying \(a<b\), and define \[
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.

Example (When the Greatest and Least Elements Coincide)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. Choose an arbitrary real number \(a\in\mathbb{R} \) and consider the singleton \[
\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.

Example (Greatest and Least Elements Need Not Exist)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. Choose arbitrary real numbers \(a,b\in\mathbb{R} \) satisfying \(a<b\), and define \[
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.
Example (Greatest and Least Elements Need Not Exist)
Let \(A=\left\{ a,b,c\right\} \). The inclusion relation \(\subset\) on the power set \[
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.

Example (Greatest and Least Elements Need Not Exist)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. Choose arbitrary real numbers \(a,b\in\mathbb{R} \) satisfying \(a<b\), and define \[
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.

Proposition (Finite Totally Ordered Sets Have Greatest and Least Elements)
Let \(\left( A,\leq\right) \) be a totally ordered set. If a nonempty subset \(X\) of \(A\) is finite, then both the greatest element \(\max X\) and the least element \(\min X\) exist.
Proof

Members-Only Content
【Log In】【Sign Up】

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.

Example (Greatest and Least Elements Need Not Exist)
Let \(A=\left\{ a,b,c\right\} \). The inclusion relation \(\subset\) on the power set \[
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.

Proposition (Uniqueness of Greatest and Least Elements)
Let \(\left( A,\leq\right) \) be an ordered set and let \(X\) be a nonempty subset of \(A\). If the greatest element \(\max X\) exists, then it is unique. Likewise, if the least element \(\min X\) exists, then it is unique.
Proof

Members-Only Content
【Log In】【Sign Up】

 

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

Problem (Greatest and Least Elements Under Divisibility on the Natural Numbers)
The divisibility relation \(|\) on the set of natural numbers \(\mathbb{N} \) is a partial order. It is defined by \[
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.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Greatest and Least Elements Under the Usual Order on the Real Numbers)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. The set of natural numbers \[\mathbb{N} =\left\{ 1,2,3,\cdots\right\}
\]is a nonempty subset of \(\mathbb{R} \). Determine whether \(\mathbb{N} \) has a greatest element or a least element.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Greatest and Least Elements Under the Usual Order on the Real Numbers)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. Choose arbitrary real numbers \(a,b\in\mathbb{R} \) satisfying \(a<b\), and define the nonempty subset \[
A=\left\{ x\in\mathbb{R} \ |\ a<x<b\right\} .
\]Does \(A\) have a least element? Discuss.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Greatest and Least Elements)
Give a concrete example of an ordered subset that has a greatest element but no least element.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Greatest and Least Elements Under Set Inclusion)
Let
\[
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.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Greatest and Least Elements Under Divisibility)
Define divisibility \(|\) on \[
X=\left\{ 2,4,8,12,24\right\} .
\]Find the greatest and least elements of \(X\).
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (A Finite Partially Ordered Set with Neither a Greatest nor a Least Element)
Construct a concrete finite ordered subset that, although partially ordered, has neither a greatest element nor a least element.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Characterization of a Greatest Element in a Total Order)
Let \(\left( A,\leq\right) \) be a totally ordered set, let \(X\) be a nonempty subset of \(A\), and let \(a\in X\). Show that the following two conditions are equivalent: \begin{align*}
& \left( a\right) \quad a=\max X\\
& \left( b\right) \quad\forall x\in X:\lnot\left( a<x\right) .
\end{align*}

View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Greatest and Least Elements in the Product Order)
Let
\[
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.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Greatest and Least Elements of a Finite Totally Ordered Set)
Let \(\left( X,\leq\right) \) be a nonempty finite totally ordered set. Prove, without using mathematical induction, that both a greatest element and a least element exist.
View Solution

Members-Only Content
【Log In】【Sign Up】

Discussion

To ask questions about this material or discuss it with other learners, you need to register as a member and log in.

  • Members can post comments
  • You can reply to other users
  • You can search and view past discussions
  • You can edit your posts later

At WIIS, we believe that all users are equal as learners, regardless of age, gender, educational background, occupation, or social status.

This is not a place to compete over knowledge, but a space to deepen understanding while respecting one another’s ideas. Questions and opinions are welcome, and you are also encouraged to ask openly about anything you do not understand.

To help maintain a constructive and welcoming learning environment, please review the guidelines before posting.

If you find a typo, broken link, or error in the content, please let us know using the form below.

User Posts Related to This Lesson

Table of Contents

MEMBERSHIP

Take your learning further.

Join WIIS to access
members-only content,
downloadable PDF textbooks,
AI Tutor, forums,
and other member benefits.

MEMBERS-ONLY CONTENT

Access exclusive materials designed for deeper learning.

PDF TEXTBOOKS

Download textbooks and study them anywhere.

AI Tutor

Use AI-powered support to deepen your understanding.

COMMUNITY FEATURES

Connect with other learners and join discussions and research.

ログイン

アカウントにログインして、学習ノートやブックマーク、投稿記事などを管理できます。

Recently Viewed Pages