Least Upper Bound of $\{3,5\}$ in a Divisibility Poset

Consider the poset

$$P=\{3,5,9,15,24,45\}$$

ordered by divisibility, written as $(P,\mid)$. Thus, for $a,b\in P$,

$$a\leq b \quad \Longleftrightarrow \quad a\mid b.$$

The question asks for the least upper bound of $\{3,5\}$.

In a divisibility poset, an upper bound of $\{3,5\}$ must be divisible by both $3$ and $5$. The relevant candidates are $15$ and $45$. Since

$$15\mid 45,$$

the element $15$ is below $45$ in the poset and is therefore the least upper bound.

Hence,

$$\operatorname{lub}\{3,5\}=15.$$

Correct answer: (iii) $15$.

Footnotes

1. Answer these questions for the poset - Identifies $15$ and $45$ as the upper bounds of $\{3,5\}$ in the given poset. ↩

2. Answer these questions for the poset - Gives $15$ as the least upper bound of $\{3,5\}$. ↩

Core vocabulary

• Poset
• Divisibility order
• Upper bound
• Least upper bound
• Join

For the relation $\mid$:

$$a\leq b \iff a\mid b.$$

Therefore, “larger” in the poset does not necessarily mean numerically larger in the usual sense; it means “is a multiple of.” In this setting, the join of two integers, when it exists in the poset, is related to their least common multiple.

Footnotes

1. LCM & GCD - Explains the relationship between divisibility, greatest common divisors, and least common multiples. ↩

Direct verification

Check each candidate:

Thus, the set of upper bounds is

$$U(\{3,5\})=\{15,45\}.$$

Now compare these upper bounds using divisibility:

$$15\mid45.$$

Consequently, $15$ is the least element of the set of upper bounds under $\mid$.

Hasse-diagram reasoning

The relevant divisibility relationships are

$$3\mid9,\qquad 3\mid15,\qquad 3\mid24,\qquad 3\mid45,$$ $$5\mid15,\qquad 5\mid45,$$

and

$$15\mid45.$$

The Hasse diagram can be represented schematically as:

Only covering relations are normally displayed in a Hasse diagram; transitive relations such as $3\mid45$ are understood from the diagram.

Starting from both $3$ and $5$, the first common element reached above them is $15$. Although $45$ is also above both, it is not the least such element because $15\mid45$.

Footnotes

1. Posets and their Hasse diagrams - Defines upper bounds, least upper bounds, and Hasse diagrams. ↩

Why the other options are incorrect

Option (i): $3$

Although $3$ is one of the elements under consideration, it is not divisible by $5$:

$$5\nmid3.$$

Therefore, $3$ is not an upper bound of $\{3,5\}$.

Option (ii): $5$

Similarly, $5$ is not divisible by $3$:

$$3\nmid5.$$

Therefore, $5$ is not an upper bound.

Option (iii): $15$

Both divisibility conditions hold:

$$3\mid15,\qquad 5\mid15.$$

Thus, $15$ is an upper bound. It is also below every other upper bound, because the only other upper bound is $45$ and

$$15\mid45.$$

Therefore, $15$ is the least upper bound.

Option (iv): $45$

The element $45$ is an upper bound because

$$3\mid45,\qquad 5\mid45.$$

However, it is not the least upper bound, since $15$ is also an upper bound and

$$15\mid45.$$

General principle

For positive integers ordered by divisibility, a common upper bound of $a$ and $b$ is a common multiple of $a$ and $b$. If the least common multiple belongs to the selected poset, then

$$a\vee b=\operatorname{lcm}(a,b).$$

For this problem,

$$3=3^1,\qquad 5=5^1,$$

so

$$\operatorname{lcm}(3,5)=3\cdot5=15.$$

Because $15\in P$, the join exists in this poset and equals $15$.

The distinction between the ordinary least common multiple and the poset join is important: if $\operatorname{lcm}(a,b)$ were not in the given subset, one would need to inspect the available common multiples and determine whether a least one exists.

Footnotes

1. Greatest common divisor - Describes least common multiples as joins in divisibility-ordered structures. ↩