Warning 19.5.1.
- An upper or lower bound does not need to belong to the subset for which it is a bound.
- A set (or subset) does not necessarily have either a maximum or minimum element.
Section 19.5 Maximal/minimal elements
Each of the following definitions are for a subset \(B\) of a partially ordered set \(A\text{.}\)
- upper bound
- an element \(u \in A\) such that \(b \partorder u\) for all \(b \in B\)
- least upper bound
- an upper bound for \(B \subseteq A\) that is less than every other upper bound
- maximum element
- an upper bound for \(B\) that is contained in \(B\)
- lower bound
- an element \(\ell \in A\) such that \(\ell \partorder b\) for all \(b \in B\)
- greatest lower bound
- a lower bound for \(B \subseteq A\) that is greater than every other lower bound
- minimum element
- a lower bound for \(B\) that is contained in \(B\)
Fact 19.5.2.
If a subset of a partially ordered set contains a maximum element, then that maximum element is unique. And similarly for a minimum element.
Proof.
You are asked to prove this in Activity 19.5.
Example 19.5.3. Maximums, minimums, and bounds in \(\R\).
Consider the usual (total) order \(\mathord{\leq}\) on \(\R\text{.}\)
- The full set \(\R\) has neither a maximum nor minimum element.
- The subset \((0,1)\) has many upper bounds (anything \(\geq 1\)) and many lower bounds (anything \(\leq 0\)). However, we would refer to \(1\) as the least upper bound and to \(0\) as the greatest lower bound of \((0,1)\text{.}\)
- The subset \((0,1)\) has no maximum or minimum element. However, the subset \([0,1]\) has maximum \(1\) and minimum \(0\text{.}\)
Example 19.5.4. Maximums, minimums, and bounds in a power set.
Suppose \(U\) is a universal set, and consider \(\powset{U}\) partially ordered by \(\mathord{\subseteq}\) as usual. In the full set \(\powset{U}\text{,}\) the unique maximum element is \(U\text{,}\) which is just another way of saying that every element of \(\powset{U}\) is a subset of \(U\text{.}\) And the unique minimum element is \(\emptyset\text{,}\) which is just another way of saying that the empty set is a subset of every subset of \(U\text{.}\)
Now consider a subset \(\mathscr{A} \subseteq \powset{U}\text{,}\) so that \(\mathscr{A}\) is a collection of subsets of \(U\text{.}\) Because of the existence of maximum and minimum elements, these elements also serve as an upper and lower bound, respectively, for \(\mathscr{A}\text{.}\) However, one can also find a least upper bound for \(\mathscr{A}\) by taking the union of all the subsets of \(U\) contained in \(\mathscr{A}\text{,}\) and one can find a greatest lower bound by taking the intersection of all the subsets of \(U\) contained in \(\mathscr{A}\text{.}\)
The next two definitions are stated for elements in a partially ordered set, but could also be understood for elements in a subset of a partially ordered set, as every subset of a partially ordered set is also a partially ordered set.
- maximal element
- an element for which no other element is larger
- minimal element
- an element for which no other element is smaller
Remark 19.5.5.
The difference between maximum and maximal is subtle. A maximum element must be larger than (and hence comparable to) every other element of \(A\text{,}\) while a maximal element must only be larger than every other element of \(A\) to which it is comparable. The distinction between minimum and minimal is similar.
Test 19.5.6. Maximal/minimal elements.
- To verify that \(\overline{m} \in A\) is maximal, prove either the original definition\begin{equation*} (\forall x \in A)({x \neq \overline{m}} \lgcimplies {\overline{m} \npartorder x}) \text{,} \end{equation*}or prove the equivalent contrapositive formulation\begin{equation*} (\forall x \in A)({\overline{m} \partorder x} \lgcimplies {x = \overline{m}}) \text{.} \end{equation*}
- To verify that \(\underline{m} \in A\) is minimal, prove either the original definition\begin{equation*} (\forall x \in A)({x \neq \underline{m}} \lgcimplies {x \npartorder \underline{m}}) \text{,} \end{equation*}or prove the equivalent contrapositive formulation\begin{equation*} (\forall x \in A)({x \partorder \underline{m}} \lgcimplies {x = \underline{m}}) \text{.} \end{equation*}
Example 19.5.7. Connected components are maximal.
Consider the graph \(G\) in Figure 19.5.8.
Let \(\subgraphset{G}\) represent the collection of subgraphs of \(G\text{,}\) partially ordered by the subgraph relation. (By my count, \(\card{\subgraphset{G}} = 110\text{.}\)) Let \(\connectedsubgraphset{G}\) represent the collection of connected subgraphs of \(G\text{.}\) (By my count, \(\card{\connectedsubgraphset{G}} = 15\text{.}\)) A maximal elements of \(\connectedsubgraphset{G}\) would have to be a connected subgraph of \(G\) that is contained in no larger connected subgraph of \(G\) — but this is precisely the definition of connected component. Hence \(\connectedsubgraphset{G}\) has three maximal elements, the three connected components you see in Figure 19.5.8. However, a maximum element of \(\connectedsubgraphset{G}\) would be a connected subgraph of \(G\) which contains every other connected subgraph of \(G\text{,}\) and the existence of multiple connected components in this example non-connected graph makes such a subgraph impossible.
Remark 19.5.9.
If you compare both our informal definition and formal definition of connected component with our definition of maximal element and our Test for Maximal/Minimal Elements, you should find that the definition of connected component means precisely a maximal subgraph with respect to the property of being connected.
Worked Example 19.5.10.
Let \(A = \{a,b,c\}\text{.}\) Given the Hasse diagram for \(\mathord{\subseteq}\) on \(P = \powset{A}\smallsetminus\{A\}\) in Figure 19.5.11, determine all maximal/maximum/minimal/minimum elements, if they exist.
Solution.
The element \(\{a,b\}\) is maximal, since each node in the Hasse diagram that is adjacent to \(\{a,b\}\) is below it. The same reasoning confirms that \(\{a,c\}\text{,}\) and \(\{b,c\}\) of are also maximal. However, none of them is a maximum, since none of them is larger than the other two.
The element \(\emptyset\) of \(P\) is a minimal element, since each node that is adjacent to it is above it. And it is the only minimal element. Furthermore, \(\emptyset\) is the minimum element, since for every other node there is a walk upwards from \(\emptyset\) to that node.
Warning 19.5.12.
Just drawing a node higher or lower in a Hasse diagram does not necessarily make it larger or smaller, respectively, when compared to other elements via the partial order. For example, in the Hasse diagram of Figure 19.5.11, we could have drawn the node for \(\{a,c\}\) at a higher location, but that would not make it larger than \(\{a,b\}\) and \(\{b,c\}\text{,}\) since there still would not have been any edges or chains of edges from \(\{a,c\}\) downward to those other two nodes.
Fact 19.5.13.
If the partially ordered set \(A\) has a maximum element, then that element is also the only maximal element of \(A\text{.}\) Similarly, the minimum element, if it exists, is the only minimal element of \(A\text{.}\)
Proof idea.
Assume \(A\) has a maximum element. Then every element of \(A\) is both comparable to and smaller than that maximum element, so no element is larger than it. Therefore, this maximum must be maximal. And no other element could be maximal, because to be maximal means there are no elements which are larger. But our maximum element is always larger.
Warning 19.5.14.
A maximum element must be maximal and must be the only maximal. But a maximal element, even if it is the only one, need not be the maximum.
Example 19.5.15. A partially ordered set with exactly one maximal element but no maximum element.
Consider
\begin{equation*}
A = \{3\} \union \{2,4,8,16,32,64,\dotsc,2^n,\dotsc\},
\end{equation*}
partially ordered by \(\mathord{\mid}\text{,}\) the “divides” relation. There is no element of \(A\) that is divisible by \(3\) (except \(3\) itself), so there is no element of \(A\) that is larger than \(3\text{.}\) Therefore, \(3\) is maximal. Moreover, \(3\) is the only maximal element in \(A\text{,}\) since every power of \(2\) divides the next power of \(2\text{.}\) However, there is no maximum element in \(A\text{,}\) since there is no element of \(A\) which is divisible by every other element of \(A\text{.}\)
Example 19.5.16. A partially ordered set with infinitely many maximal/minimal elements but no maximum/minimum element.
Consider \(\mathscr{A} \subsetneqq \powset{\N}\text{,}\) where
\begin{equation*}
\mathscr{A} = \powset{\N} \relcmplmnt \{\emptyset,\N\} \text{.}
\end{equation*}
So \(\mathscr{A}\) is the set of all nonempty, proper subsets of \(\N\text{.}\) Under the partial order \(\mathord{\subseteq}\text{,}\) \(\mathscr{A}\) has neither a maximum nor a minimum element, but for every \(n \in \N\text{,}\) \(\{n\}\) is a minimal element and \(\N \relcmplmnt \{n\}\) is a maximal element of \(\mathscr{A}\text{.}\)
