12.1: Posets Revisited
- Last updated
- Sep 29, 2021
- Save as PDF
- Page ID
- 86177
( \newcommand{\kernel}{\mathrm{null}\,}\)
We recall the definition a partially ordering:
Definition 12.1.1: Partial Ordering
Let ⪯ be a relation on a set L. We say that ⪯ is a partial ordering on L if it is reflexive, antisymmetric, and transitive. That is:
- ⪯ is reflexive: a⪯a∀a∈L
- ⪯ is antisymmetric: a⪯b and a≠b⇒b⋠a∀a,b∈L
- ⪯ is transitive: a⪯b and b⪯c⇒a⪯c∀a,b,c∈L
The set together with the relation (L,⪯) is called a poset.
Example 12.1.1: Some Posets
We recall a few examples of posets:
- (R,≤) is a poset. Notice that our generic symbol for the partial ordering, ⪯, is selected to remind us that a partial ordering is similar to “less than or equal to.”
- Let A={a,b}. Then (P(A),⊆) is a poset.
- Let L={1,2,3,6}. Then (L,∣) is a poset.
The posets we will concentrate on in this chapter will be those which have upper and lower bounds in relation to any pair of elements. Next, we define this concept precisely.
Definition 12.1.2: Lower Bound, Upper Bound
Let (L,⪯) be a poset, and a,b∈L. Then c∈L is a lower bound of a and b if c⪯a and c⪯b. Also, d∈L is an upper bound of a and b if a⪯d and b⪯d.
In most of the posets that will interest us, every pair of elements have both upper and lower bounds, though there are posets for which this is not true.
Definition 12.1.3: Greatest Lower Bound
Let (L,⪯) be a poset. If a,b∈L, then ℓ∈L is a greatest lower bound of a and b if and only if
- ℓ⪯a
- ℓ⪯b
- If ℓ′∈L such that ℓ′⪯a and ℓ′⪯b, then ℓ′⪯ℓ.
The last condition in the definition of Greatest Lower Bound says that if ℓ′ is also a lower bound, then ℓ is “greater” in relation to ⪯ than ℓ′. The definition of a least upper bound is a mirror image of a greatest lower bound:
Definition 12.1.4: Least Upper Bound
Let (L,⪯) be a poset. If a,b∈L, then u∈L is a least upper bound of a and b if and only if
- a⪯u
- b⪯u
- If u′∈L such that if a⪯u′ and b⪯u′, then u⪯u′.
Notice that the two definitions above refer to “...a greatest lower bound” and “a least upper bound.” Any time you define an object like these you need to have an open mind as to whether more than one such object can exist. In fact, we now can prove that there can't be two greatest lower bounds or two least upper bounds.
Theorem 12.1.1: Uniqueness of Least Upper and Greatest Lower Bounds
Let (L,⪯) be a poset, and a,b∈L. If a greatest lower bound of a and b exists, then it is unique. The same is true of a least upper bound, if it exists.
- Proof
-
Let ℓ and ℓ′ be greatest lower bounds of a and b. We will prove that ℓ=ℓ′.
- ℓ a greatest lower bound of a and b ⇒ ℓ is a lower bound of a and b.
- ℓ′ a greatest lower bound of a and b and ℓ a lower bound of a and b ⇒ℓ⪯ℓ′, by the definition of greatest lower bound.
- ℓ′ a greatest lower bound of a and b ⇒ℓ′ is a lower bound of a and b.
- ℓ a greatest lower bound of a and b and ℓ′ a lower bound of a and b. ⇒ℓ′⪯ℓ by the definition of greatest lower bound.
- ℓ⪯ℓ′ and ℓ′⪯ℓ⇒ℓ=ℓ′ by the antisymmetry property of a partial ordering.
The proof of the second statement in the theorem is almost identical to the first and is left to the reader.
Definition 12.1.5: Greatest Element, Least Element
Let (L,⪯) be a poset. M∈L is called the greatest (maximum) element of L if, for all a∈L, a⪯M. In addition, m∈L is called the least (minimum) element of L if for all a∈L, m⪯a. The greatest and least elements, when they exist, are frequently denoted by 11 and 00 respectively.
Example 12.1.2: Bounds on the Divisors of 105
Consider the partial ordering “divides” on L={1,3,5,7,15,21,35,105}. Then (L,∣) is a poset. To determine the least upper bound of 3 and 7, we look for all u∈L, such that 3|u and 7|u. Certainly, both u=21 and u=105 satisfy these conditions and no other element of L does. Next, since 21|105, 21 is the least upper bound of 3 and 7. Similarly, the least upper bound of 3 and 5 is 15. The greatest element of L is 105 since a|105 for all a∈L. To find the greatest lower bound of 15 and 35, we first consider all elements g of L such that g∣15. They are 1, 3, 5, and 15. The elements for which g∣35 are 1, 5, 7, and 35. From these two lists, we see that ℓ=5 and ℓ=1 satisfy the required conditions. But since 1|5, the greatest lower bound is 5. The least element of L is 1 since 1|a for all a∈L.
Definition 12.1.6: The Set of Divisors of an Integer
For any positive integer n, the divisors of n is the set of integers that divide evenly into n. We denote this set Dn.
For example, the set L of Example 12.1.2 is D105.
Example 12.1.3: The Power Set of a Three Element Set
Consider the poset (P(A),⊆), where A={1,2,3}. The greatest lower bound of {1,2} and {1,3} is ℓ={1}. For any other element ℓ′ which is a subset of {a,b} and {a,c} (there is only one; what is it?), ℓ′⊆ℓ. The least element of P(A) is ∅ and the greatest element is A={a,b,c}. The Hasse diagram of this poset is shown in Figure 12.1.1.
The previous examples and definitions indicate that the least upper bound and greatest lower bound are defined in terms of the partial ordering of the given poset. It is not yet clear whether all posets have the property such every pair of elements always has both a least upper bound and greatest lower bound. Indeed, this is not the case (see Exercise 12.1.1).
Exercises
Consider the poset (D30,∣), where D30={1,2,3,5,6,10,15,30}.
- Find all lower bounds of 10 and 15.
- Find the greatest lower bound of 10 and 15.
- Find all upper bounds of 10 and 15.
- Determine the least upper bound of 10 and 15.
- Draw the Hasse diagram for D30 with respect to ∣. Compare this Hasse diagram with that of Example 12.1.3. Note that the two diagrams are structurally the same.
- Answer
-
- 1, 5
- 5
- 30
- 30
- See the Sage cell below with the default input displaying a Hasse diagram for D12.
Exercise 12.1.2
List the elements of the sets D8, D50, and D1001. For each set, draw the Hasse diagram for “divides.”
Figure 12.1.2 contains Hasse diagrams of posets.
- Determine the least upper bound and greatest lower bound of all pairs of elements when they exist. Indicate those pairs that do not have a least upper bound (or a greatest lower bound ).
- Find the least and greatest elements when they exist.
- Answer
-
- Solution for Hasse diagram (b):
- ∨a1a2a3a4a5a1a1a2a3a4a5a2a2a2a4a4a5a3a3a4a3a4a5a4a4a4a4a4a5a5a5a5a5a5a5∧a1a2a3a4a5a1a1a1a1a1a1a2a1a2a1a2a2a3a1a1a3a3a3a4a1a2a3a4a4a5a1a2a3a4a5
a1 is the least element and a5 is the greatest element.
- ∨a1a2a3a4a5a1a1a2a3a4a5a2a2a2a4a4a5a3a3a4a3a4a5a4a4a4a4a4a5a5a5a5a5a5a5∧a1a2a3a4a5a1a1a1a1a1a1a2a1a2a1a2a2a3a1a1a3a3a3a4a1a2a3a4a4a5a1a2a3a4a5
- Partial solution for Hasse diagram (f):
- lub(a2,a3) and lub(a4,a5) do not exist.
- No greatest element exists, but a1 is the least element.
- Solution for Hasse diagram (b):
Exercise 12.1.4
For the poset (N,≤), what are the greatest lower bound and least upper bound of two elements a and b? Are there least and/or greatest elements?
Exercise 12.1.5
- Prove the second part of Theorem 12.1.1, the least upper bound of two elements in a poset is unique, it one exists.
- Prove that if a poset L has a least element, then that element is unique.
- Answer
-
If 0 and 0′ are distinct least elements, then
0≤0′ since 0 is a least element0′≤0 since 0′ is a least element}⇒0=0′ by antisymmetry, a contradiction
Exercise 12.1.6
We naturally order the numbers in Am={1,2,...,m} with “less than or equal to,” which is a partial ordering. We define an ordering, ⪯ on the elements of Am×An by
(a,b)⪯(a′,b′)⇔a≤a′ and b≤b′
- Prove that ⪯ is a partial ordering on Am×An.
- Draw the ordering diagrams for ⪯ on A2×A2, A2×A3, and A3×A3.
- In general, how does one determine the least upper bound and greatest lower bound of two elements of Am×An, (a,b) and (a′,b′)?
- Are there least and/or greatest elements in Am×An?
Exercise 12.1.7
Let P0 be the set of all subsets T of S={1,2,…,9} such that the sum of the elements in T is even. (Note that the empty set ∅ will be included as an element of P0.) For instance, {2,3,6,7} is in P0 because 2+3+6+7 is even, but {1,3,5,6} is not in P0 because 1+3+5+6 is odd. Consider the poset (P0,⊆). Let A={1,2,3,6} and B={2,3,6,7} be elements of P0.
- Explain why A∩B is not element of the poset.
- Use the definitions of the italicized terms and the given partial ordering to complete the following statements:
- R∈P0 is an upper bound of A and B if \rule{3cm}{0.01cm}
- R∈P0 is the least element of P0 if \rule{3cm}{0.01cm}
- Find three different upper bounds of A and B.
- Find the least upper bound of A and B. If it doesn't exist, explain why not.
- Answer
-
- The sum of elements in A∩B={2,3,6} is odd and disqualifies the set from being an element of the poset.
- Use the definitions of the italicized terms and the given partial ordering to complete the following statements:
- …A⊆R and B⊆R
- … for all A∈P0, R⊆A
- Any set that contains the union of A∪B={1,2,3,6,7} but also contains 3 or 5, but not both will be an upper bound. You can create several by including on not including 4 or 8.
- The least upper bound doesn't exist. Notice that the union of A and B isn't in P0. One of the two sets {1,2,3,5,6,7} and {1,2,3,6,7,9} is contained within every upper bound of A and B but neither is contained within the other.