Lower bounds and upper bounds

Suppose that we have some poset \(\left \langle S, \leq \right \rangle\), where \(\leq\) is an arbitrary partial order. Given a set \(x \in S\), we can ask which elements are less than \(x\) and which elements are greater than \(x\). These are the lower bounds and upper bounds of \(x\). This is an important notion, and it can be generalized from a single member of \(S\) to whole subsets of \(S\).

Bounds for single elements

The definition for lower and upper bounds of a single element in a poset is straightforward.

Let \(\left \langle S, \leq \right \rangle\) be an arbitrary poset and \(x\) an arbitrary member of \(S\). Then \(y \in S\) is a lower bound for \(x\) iff \(y \leq x\). We call \(y\) an upper bound iff \(x \leq y\).

Consider the poset below, which consists of all subsets of \(\left \{ 1,2,3 \right \}\) ordered by the subset relation \(\subseteq\).

lattice_123.svg

The upper bounds of \(\left \{ 1 \right \}\) are \(\left \{ 1 \right \}\), \(\left \{ 1,2 \right \}\), \(\left \{ 1,3 \right \}\), and \(\left \{ 1,2,3 \right \}\). Its lower bounds are \(\left \{ 1 \right \}\) and \(\emptyset\).

Thinking of upper and lower bounds in pictorial terms may strengthen your intuitions. In the figure below, upper bounds are in dashed boxes, and lower bounds in dashed circles. We underline \(\left \{ 1 \right \}\) to indicate that this is the element for which we are computing upper and lower bounds.

lattice_123_bounds1.svg

Draw corresponding diagrams indicating the upper and lower bounds of

  • \(\left \{ 1,3 \right \}\)
  • \(\emptyset\)

Say whether the following is true or false, and justify your answer: if \(\left \langle S, \leq \right \rangle\) is a poset, then it holds for all \(x, y \in S\) that \(y\) is both an upper and a lower bound for \(x\) iff \(x = y\).

Generalizing bounds to subsets

While it can be interesting to know the lower and upper bounds for a given element, very often we want to know the bounds for multiple elements. For instance, which elements are such that they are greater than both \(x\) and \(y\)? To this end, we generalize bounds from elements of a poset to subsets of the poset. We say that \(y\) is an upper (or lower) bound for subset \(T\) iff \(y\) is an upper (or lower) bound for every member of \(T\).

Let \(\left \langle S, \leq \right \rangle\) be a poset and \(T\) and arbitrary subset of \(S\). Then the set of upper bounds of \(T\) is \[\mathrm{ub}(T) \mathrel{\mathop:}=\left \{ y \in S \mid x \leq y \text{ for all } x \in T \right \}.\] Similarly, the set of lower bounds of \(T\) is \[\mathrm{lb}(T) \mathrel{\mathop:}=\left \{ y \in S \mid y \leq x \text{ for all } x \in T \right \}.\]

Consider the poset \(\left \langle \left \{ 0,1,2,3,4 \right \}, \leq \right \rangle\), the set of the first five natural numbers ordered in the usual fashion via \(\leq\). The lower bounds of \(2\) and \(4\) are \(0\), \(1\), and \(2\) as these are the only elements that are less than \(2\) and less than \(4\). More succinctly, \(\mathrm{lb}(\left \{ 2,4 \right \}) = \left \{ 0,1,2 \right \}\).

The only upper bound of \(2\) and \(4\) is \(4\) as no other member of the carrier \(\left \{ 0,1,2,3,4 \right \}\) is greater than both of those numbers. Hence we write \(\mathrm{ub}(\left \{ 2,4 \right \}) = \left \{ 4 \right \}\).

Given some arbitrary poset \(\left \langle S, \leq \right \rangle\), what are \(\mathrm{lb}(\emptyset)\) and \(\mathrm{ub}(\emptyset)\)? Justify your answer.

Consider once more the poset of all subsets of \(\left \{ 1,2,3 \right \}\) ordered by the subset relation \(\subseteq\).

lattice_123.svg

The upper bounds of \(\left \{ 1 \right \}\) and \(\left \{ 2 \right \}\) are \(\left \{ 1,2 \right \}\) and \(\left \{ 1,2,3 \right \}\). Their only lower bound is \(\emptyset\). In mathematical notation, this is \[\mathrm{ub}(\left \{ \left \{ 1 \right \}, \left \{ 2 \right \} \right \}) = \left \{ \left \{ 1,2 \right \}, \left \{ 1,2,3 \right \} \right \}\] and \[\mathrm{lb}(\left \{ \left \{ 1 \right \}, \left \{ 2 \right \} \right \}) = \left \{ \emptyset \right \}.\]

Yes, those are sets of sets. You have to keep in mind that \(\mathrm{lb}\) and \(\mathrm{ub}\) always apply to the set of things whose lower and upper bounds we want to compute. In the case at hand, these things themselves are sets, so \(\mathrm{lb}\) and \(\mathrm{ub}\) take a set of sets as their argument. And since they return a set of things that are lower/upper bounds, we get back a set of sets.

We can also depict this in the graphical format that we used for the lower and upper bounds of individual elements.

lattice_123_bounds1-2.svg

Given the same poset, the upper bounds of \(\left \{ 1 \right \}\) are \(\left \{ 1 \right \}\), \(\left \{ 1,2 \right \}\), \(\left \{ 1,3 \right \}\), and \(\left \{ 1,2,3 \right \}\), while the lower bounds are \(\left \{ 1 \right \}\) and \(\emptyset\). Hence we have \(\mathrm{ub}(\left \{ \left \{ 1 \right \} \right \}) = \left \{ \left \{ 1 \right \}, \left \{ 1,2 \right \}, \left \{ 1,3 \right \}, \left \{ 1,2,3 \right \} \right \}\) and \(\mathrm{lb}(\left \{ \left \{ 1 \right \} \right \}) = \left \{ \emptyset, \left \{ 1 \right \} \right \}\). Again the notation is slightly confusing as we are looking at sets of elements of the poset, and these elements just so happen to be sets themselves. Relying once more on our graphical format, we see that \(\mathrm{ub}(\left \{ \left \{ 1 \right \} \right \})\) and \(\mathrm{lb}(\left \{ \left \{ 1 \right \} \right \})\) yield the same upper and lower bounds that we computed for \(\left \{ 1 \right \}\) at the beginning of this unit.

lattice_123_bounds1.svg

Explain why the set of upper bounds of some element \(x\) of a poset is identical to \(\mathrm{ub}(\left \{ x \right \})\).

One more example with the same poset. The upper bounds of \(\left \{ 2 \right \}\), \(\left \{ 3 \right \}\), and \(\left \{ 2,3 \right \}\) are \(\left \{ 2,3 \right \}\) and \(\left \{ 1,2,3 \right \}\), whereas their only lower bound is \(\emptyset\). We write this more succinctly as \(\mathrm{ub}(\left \{ \left \{ 2 \right \}, \left \{ 3 \right \}, \left \{ 2,3 \right \} \right \}) = \left \{ \left \{ 2,3 \right \} \left \{ 1,2,3 \right \} \right \}\) and \(\mathrm{lb}(\left \{ \left \{ 2 \right \}, \left \{ 3 \right \}, \left \{ 2,3 \right \} \right \}) = \left \{ \emptyset \right \}\). Once again we can also depict this in the graphical format:

lattice_123_bounds2-3-23.svg

Given the poset in the previous example, compute all of the following:

  • \(\mathrm{ub}(\left \{ \left \{ 1,2 \right \}, \left \{ 2,3 \right \} \right \})\)
  • \(\mathrm{lb}(\left \{ \left \{ 1,2 \right \}, \left \{ 2,3 \right \} \right \})\)
  • \(\mathrm{ub}(\left \{ \emptyset \right \})\)
  • \(\mathrm{ub}(\emptyset)\)
  • \(\mathrm{lb}(\left \{ \emptyset, \left \{ 1,2,3 \right \} \right \})\)
  • \(\mathrm{lb}(\left \{ \left \{ 1 \right \}, \left \{ 2,3 \right \}, \left \{ 1,2,3 \right \} \right \})\)
  • \(\mathrm{ub}(\left \{ \left \{ 1 \right \}, \left \{ 2 \right \}, \left \{ 3 \right \} \right \})\)

Consider \(\left \langle \left \{ 0,1,2,3,4 \right \}, \leq \right \rangle\), the set of the first five natural numbers ordered in the usual fashion via \(\leq\). Using the pictorial format described above, indicate the lower and upper bounds for the following subsets:

  • \(\left \{ 2 \right \}\)
  • \(\left \{ 1,4 \right \}\)
  • \(\left \{ 2,3 \right \}\)
  • \(\left \{ 0,3 \right \}\)

Since \(\mathrm{lb}\) and \(\mathrm{ub}\) are functions from sets to sets, the output of one can be the input for the other. Compute \(\mathrm{lb}(\mathrm{ub}({\left \{ 0,3 \right \}}))\) over \(\left \{ 0,1,2,3,4 \right \}\) ordered by \(\leq\). By comparison, what is \(\mathrm{ub}(\mathrm{lb}(\left \{ 0,3 \right \}))\)?

Now consider \(\left \langle \mathbb{N}, \leq \right \rangle\) instead, the set of all natural numbers ordered via \(\leq\). For each one of the following statements, say whether it is true or false and justify your answer.

  • Any two natural numbers \(x\) and \(y\) have infinitely many upper bounds.
  • Any two natural numbers \(x\) and \(y\) have infinitely many lower bounds.

Note that the existence of upper and lower bounds isn’t guaranteed once we move from individual elements of the posets to subsets. Take for instance the poset \(\left \langle \left \{ 1,2 \right \}, R \right \rangle\) where \(x \mathrel{R} y\) iff \(x = y\). Yes, this is still a poset (there is an order, and it is partial). In this case, \(\mathrm{lb}(\left \{ 1,2 \right \}) = \emptyset\) because there simply is no \(y\) such that \(y \mathrel{R} 1\) and \(y \mathrel{R} 2\). In other words, \(1\) and \(2\) don’t have any lower bounds. For the same reason, they don’t have any upper bounds either.

You might think that the poset in the previous example is somehow defective or pathological because no element is related to any element except itself. But that’s not really the issue, as is witnessed by the structure below.

poset_nobounds.svg

Find the smallest subset \(S\) such that \(\mathrm{ub}(S) = \emptyset\) and \(\mathrm{lb}(S) = \emptyset\).

Say whether the following is true or false, and justify your answer:

Given some poset \(\left \langle S, \leq \right \rangle\), it holds for every finite subset \(\left \{ s_1, \ldots, s_n \right \}\) of \(S\) that \[\mathrm{ub}(\left \{ s_1, \ldots, s_n \right \}) = \mathrm{ub}(\left \{ s_1 \right \}) \cap \mathrm{ub}(\left \{ s_2 \right \} \cap \cdots \cap \mathrm{ub}(\left \{ s_n \right \})\]

Say whether the following is true or false, and justify your answer:

Given some poset \(\left \langle S, \leq \right \rangle\), it holds for every finite subset \(\left \{ s_1, \ldots, s_n \right \}\) of \(S\) that \[\mathrm{lb}(\left \{ s_1, \ldots, s_n \right \}) = \mathrm{lb}(\left \{ s_1 \right \}) \cup \mathrm{lb}(\left \{ s_2 \right \} \cup \cdots \cup \mathrm{lb}(\left \{ s_n \right \})\]