Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

12.1: Posets Revisited

( \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:

  1. is reflexive: aaaL
  2. is antisymmetric: ab and abbaa,bL
  3. is transitive: ab and bcaca,b,cL

The set together with the relation (L,) is called a poset.

Example 12.1.1: Some Posets

We recall a few examples of posets:

  1. (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.”
  2. Let A={a,b}. Then (P(A),) is a poset.
  3. 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,bL. Then cL is a lower bound of a and b if ca and cb. Also, dL is an upper bound of a and b if ad and bd.

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,bL, 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,bL, then uL is a least upper bound of a and b if and only if

  • au
  • bu
  • If uL such that if au and bu, then uu.

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,bL. 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 =.

  1. a greatest lower bound of a and b is a lower bound of a and b.
  2. a greatest lower bound of a and b and a lower bound of a and b , by the definition of greatest lower bound.
  3. a greatest lower bound of a and b is a lower bound of a and b.
  4. a greatest lower bound of a and b and a lower bound of a and b. by the definition of greatest lower bound.
  5. 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. ML is called the greatest (maximum) element of L if, for all aL, aM. In addition, mL is called the least (minimum) element of L if for all aL, ma. 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 uL, 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 aL. To find the greatest lower bound of 15 and 35, we first consider all elements g of L such that g15. They are 1, 3, 5, and 15. The elements for which g35 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 aL.

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.

clipboard_efb317ddbe2333d243104deb5e3f2685b.pngFigure 12.1.1: Power Set of {1,2,3}

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

Exercise 12.1.1

Consider the poset (D30,), where D30={1,2,3,5,6,10,15,30}.

  1. Find all lower bounds of 10 and 15.
  2. Find the greatest lower bound of 10 and 15.
  3. Find all upper bounds of 10 and 15.
  4. Determine the least upper bound of 10 and 15.
  5. 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. 1, 5
  2. 5
  3. 30
  4. 30
  5. 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.”

Exercise 12.1.3

Figure 12.1.2 contains Hasse diagrams of posets.

  1. 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 ).
  2. Find the least and greatest elements when they exist.
clipboard_eb8b7405f328596daf193a870779085a2.pngFigure 12.1.2: Figure for Exercise 12.1.3
Answer
  • Solution for Hasse diagram (b):
    • a1a2a3a4a5a1a1a2a3a4a5a2a2a2a4a4a5a3a3a4a3a4a5a4a4a4a4a4a5a5a5a5a5a5a5a1a2a3a4a5a1a1a1a1a1a1a2a1a2a1a2a2a3a1a1a3a3a3a4a1a2a3a4a4a5a1a2a3a4a5
      a1 is the least element and a5 is the greatest element.
  • 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.

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

  1. Prove the second part of Theorem 12.1.1, the least upper bound of two elements in a poset is unique, it one exists.
  2. 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

00 since 0 is a least element00 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)aa and bb

  1. Prove that is a partial ordering on Am×An.
  2. Draw the ordering diagrams for on A2×A2, A2×A3, and A3×A3.
  3. 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)?
  4. 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.

  1. Explain why AB is not element of the poset.
  2. Use the definitions of the italicized terms and the given partial ordering to complete the following statements:
    1. RP0 is an upper bound of A and B if \rule{3cm}{0.01cm}
    2. RP0 is the least element of P0 if \rule{3cm}{0.01cm}
  3. Find three different upper bounds of A and B.
  4. Find the least upper bound of A and B. If it doesn't exist, explain why not.
Answer
  1. The sum of elements in AB={2,3,6} is odd and disqualifies the set from being an element of the poset.
  2. Use the definitions of the italicized terms and the given partial ordering to complete the following statements:
    1. AR and BR
    2.  for all AP0RA
  3. Any set that contains the union of AB={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.
  4. 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.

This page titled 12.1: Posets Revisited is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Al Doerr & Ken Levasseur via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?