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 / ii

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.

 Ancestors (12)

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version

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 / ii

Solution

 Ancestors (12)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)