ads Posets Revisited

Section 13.1 Posets Revisited

We recall the definition a partially ordering:

Definition 13.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 \forall a \in L$
$⪯$ is antisymmetric: $a ⪯ b and a \neq b \Rightarrow b ⋠ a \forall a, b \in L$
$⪯$ is transitive: $a ⪯ b and b ⪯ c \Rightarrow a ⪯ c \forall a, b, c \in L$

🔗

The set together with the relation

(L, ⪯)

is called a poset.

Example 13.1.2. Some posets.

We recall a few examples of posets:

$(R, \leq)$ 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), \subseteq)$ 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 13.1.3. Lower Bound, Upper Bound.

🔗

Let

(L, ⪯)

be a poset, and

a, b \in L .

Then

c \in L

is a lower bound of

a

and

b

c ⪯ a

and

c ⪯ b .

Also,

d \in L

is an upper bound of

a

and

b

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 13.1.4. Greatest Lower Bound.

🔗

Let

(L, ⪯)

be a poset. If

a, b \in L,

then

ℓ \in L

is a greatest lower bound of

a

and

b

if and only if

$ℓ ⪯ a$
$ℓ ⪯ b$
If $ℓ^{'} \in 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 13.1.5. Least Upper Bound.

🔗

Let

(L, ⪯)

be a poset. If

a, b \in L,

then

u \in L

is a least upper bound of

a

and

b

if and only if

$a ⪯ u$
$b ⪯ u$
If $u^{'} \in 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 13.1.6. Uniqueness of Least Upper and Greatest Lower Bounds.

🔗

Let

(L, ⪯)

be a poset, and

a, b \in 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$ $\Rightarrow$ $ℓ$ is a lower bound of $a$ and $b .$
$ℓ^{'}$ a greatest lower bound of $a$ and $b$ and $ℓ$ a lower bound of $a$ and $b$ $\Rightarrow ℓ ⪯ ℓ^{'},$ by the definition of greatest lower bound.
$ℓ^{'}$ a greatest lower bound of $a$ and $b$ $\Rightarrow ℓ^{'}$ is a lower bound of $a$ and $b .$
$ℓ$ a greatest lower bound of $a$ and $b$ and $ℓ^{'}$ a lower bound of $a$ and $b .$ $\Rightarrow ℓ^{'} ⪯ ℓ$ by the definition of greatest lower bound.
$ℓ ⪯ ℓ^{'}$ and $ℓ^{'} ⪯ ℓ \Rightarrow ℓ = ℓ^{'}$ 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 13.1.7. Greatest Element, Least Element.

🔗

Let

(L, ⪯)

be a poset.

M \in L

is called the greatest (maximum) element of

L

if, for all

a \in L,

a ⪯ M .

In addition,

m \in L

is called the least (minimum) element of

L

if for all

a \in L,

m ⪯ a .

The greatest and least elements, when they exist, are frequently denoted by

1 1

and

0 0

respectively.

Example 13.1.8. 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 \in 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 \in L .

To find the greatest lower bound of 15 and 35, we first consider all elements

g

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 \in L .

🔗

Definition 13.1.9. 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

D_{n} .

🔗

For example, the set

L

of Example 13.1.8 is

D_{105} .

Example 13.1.10. The power set of a three element set.

Consider the poset

(P (A), \subseteq),

where

A = {1, 2, 3} .

The greatest lower bound of

{1, 2}

and

{1, 3}

ℓ = {1} .

For any other element

ℓ^{'}

which is a subset of

{1, 2}

and

{1, 3}

(there is only one; what is it?),

ℓ^{'} \subseteq ℓ .

The least element of

P (A)

\emptyset

and the greatest element is

A = {1, 2, 3} .

The Hasse diagram of this poset is shown in Figure 13.1.11.

described in detail following the image — Figure 13.1.11. 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 that every pair of elements always has both a least upper bound and greatest lower bound. Indeed, this is not the case (see Exercise 13.1.3).

🔗

Exercises Exercises

🔗

1.

🔗

Consider the poset

(D_{30}, ∣),

where

D_{30} = {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 $D_{30}$ with respect to $∣ .$ Compare this Hasse diagram with that of Example 13.1.10. 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 $D_{12} .$

xxxxxxxxxx
 
Posets.DivisorLattice(12).show()

🔗

2.

🔗

List the elements of the sets

D_{8},

D_{50},

and

D_{1001} .

For each set, draw the Hasse diagram for “divides.”

🔗

3.

🔗

Figure 13.1.12 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.

Section 13.1, Exercise 3 — Figure 13.1.12. Figure for Exercise 3

Answer.

Solution for Hasse diagram (b):
- $\begin{array}{cc} \begin{array}{cccccc} \lor & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ a_{1} & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ a_{2} & a_{2} & a_{2} & a_{4} & a_{4} & a_{5} \\ a_{3} & a_{3} & a_{4} & a_{3} & a_{4} & a_{5} \\ a_{4} & a_{4} & a_{4} & a_{4} & a_{4} & a_{5} \\ a_{5} & a_{5} & a_{5} & a_{5} & a_{5} & a_{5} \end{array} & \begin{array}{cccccc} \land & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ a_{1} & a_{1} & a_{1} & a_{1} & a_{1} & a_{1} \\ a_{2} & a_{1} & a_{2} & a_{1} & a_{2} & a_{2} \\ a_{3} & a_{1} & a_{1} & a_{3} & a_{3} & a_{3} \\ a_{4} & a_{1} & a_{2} & a_{3} & a_{4} & a_{4} \\ a_{5} & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \end{array} \end{array}$
  
  $a_{1}$ is the least element and $a_{5}$ is the greatest element.
Partial solution for Hasse diagram (f):
- $lub (a_{2}, a_{3})$ and $lub (a_{4}, a_{5})$ do not exist.
- No greatest element exists, but $a_{1}$ is the least element.

🔗

4.

🔗

For the poset

(N, \leq),

what are the greatest lower bound and least upper bound of two elements

a

and

b ?

Are there least and/or greatest elements?

🔗

5.

🔗

Prove the second part of Theorem 13.1.6, the least upper bound of two elements in a poset is unique, if one exists.
Prove that if a poset $L$ has a least element, then that element is unique.

Answer.

0

and

0^{'}

are distinct least elements, then

\begin{array}{cc} 0 \leq 0^{'} & since 0 is a least element \\ 0^{'} \leq 0 & since 0^{'} is a least element \end{array}} \Rightarrow 0 = 0^{'} by antisymmetry, a contradiction

🔗

6.

🔗

We naturally order the numbers in

A_{m} = {1, 2, . . ., m}

with “less than or equal to,” which is a partial ordering. We define an ordering,

⪯

on the elements of

A_{m} \times A_{n}

(a, b) ⪯ (a^{'}, b^{'}) \Leftrightarrow a \leq a^{'} and b \leq b^{'}

Prove that $⪯$ is a partial ordering on $A_{m} \times A_{n} .$
Draw the ordering diagrams for $⪯$ on $A_{2} \times A_{2},$ $A_{2} \times A_{3},$ and $A_{3} \times A_{3} .$
In general, how does one determine the least upper bound and greatest lower bound of two elements of $A_{m} \times A_{n},$ $(a, b)$ and $(a^{'}, b^{'}) ?$
Are there least and/or greatest elements in $A_{m} \times A_{n} ?$

🔗

7.

🔗

Let

P_{0}

be the set of all subsets

T

S = {1, 2, \dots, 9}

such that the sum of the elements in

T

is even. (Note that the empty set

\emptyset

will be included as an element of

P_{0} .

) For instance,

{2, 3, 6, 7}

is in

P_{0}

because

2 + 3 + 6 + 7

is even, but

{1, 3, 5, 6}

is not in

P_{0}

because

1 + 3 + 5 + 6

is odd. Consider the poset

(P_{0}, \subseteq) .

Let

A = {1, 2, 3, 6}

and

B = {2, 3, 6, 7}

be elements of

P_{0} .

Explain why $A \cap B$ is not element of the poset.
Use the definitions of the italicized terms and the given partial ordering to complete the following statements:
1. $R \in P_{0}$ is an upper bound of $A$ and $B$ if
2. $R \in P_{0}$ is the least element of $P_{0}$ if
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 \cap B = {2, 3, 6}$ is odd and disqualifies the set from being an element of the poset.
The following correctly complete the statements in this part.
1. $\dots A \subseteq R$ and $B \subseteq R$
2. $\dots$ for all $A \in P_{0},$ $R \subseteq A$
Any set that contains the union of $A \cup 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 $P_{0} .$ 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.

You have attempted 1 of 1 activities on this page.

Prev Top Next