Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 3 / b

2, 3, 5

form the lower antichain; the nonprime elements

1, 4

form the upper antichain. In particular,

1

is not a prime number. Each lower element is below each upper element, and no third element can lie strictly between them. Therefore the six cover relations are $2, 3, 5 ≺ 1, 4$ , represented by the following Hasse diagram. Upward movement represents increasing order; crossing lines do not add elements.

Figure 1.
The six cover relations for the five-element partial order
. **Details**.

ii

 0  0

Solution

 0  0

Write

P

for the prime numbers in

A

and

C = A ∖ P

for its nonprime elements. Since

n \geq 4

, both antichains have at least two elements:

2, 3 \in P

and

1, 4 \in C

. Every element of

P

is below every element of

C

. We can classify a subset

S

by its intersection with these two levels of the two-level partial order.

If $S = \emptyset$ , every element of $A$ is an upper bound. There is no maximum, because $S$ has no elements, and no least upper bound, because the distinct elements $2, 3$ are incomparable minimal elements of $A$ .
If $S = {p}$ with $p \in P$ , its upper bounds are ${p} \cup C$ ; its maximum and least upper bound are both $p$ .
If $S \subseteq P$ has at least two elements, its upper bounds are exactly $C$ . There is no maximum in $S$ and no least upper bound, because $C$ has at least two incomparable elements.
If $S \cap C = {c}$ , its only upper bound is $c$ : no different element is above this nonprime element. Since every remaining element of $S$ is a prime number, $c$ belongs to $S$ and dominates all of it. Thus $c$ is both its maximum and its least upper bound.
If $S$ contains at least two elements of $C$ , these distinct nonprime elements have no common upper bound, and $S$ has neither a maximum nor a least upper bound.

Consequently an upper bound exists exactly when $∣ S \cap C ∣ \leq 1$ ; a maximum or least upper bound exists exactly when $∣ S \cap C ∣ = 1$ or $S$ is a singleton subset of $P$ . The exhaustive cases also justify why the last two existence criteria coincide here.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 3 / b

i

Solution

ii

Solution

 Ancestors (11)

 Discussion (0)

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 3 / b

i

Solution

ii

Solution

 Ancestors (11)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)