= Solution
Store the <minimal elements> of the finite generating <set>. The represented <upper set> itself may be infinite; the code manipulates its finite basis.
``
class UpSet[T <: Ordered[T]](c: Set[T]) extends Ordered[UpSet[T]] {
private val basis: Set[T] = minimal(c)
def contains(x: T): Boolean = basis.exists(a => a <= x)
def intersection(that: UpSet[T]): UpSet[T] = {
val generators: Set[T] =
for (a <- basis; b <- that.basis) yield a.lub(b)
new UpSet[T](generators)
}
def <=(that: UpSet[T]): Boolean = basis.forall(a => that.contains(a))
def lub(that: UpSet[T]): UpSet[T] =
new UpSet[T](basis union that.basis)
}
``
The <abstraction function> and <representation invariant> are
$$
\boxed{\alpha(B)=\uparrow B=\{x:\exists b\in B,\ b\leq x\},\qquad B\text{ finite with no strictly comparable distinct values}.}
$$
Removing nonminimal generators preserves the upward closure: in a finite generating <set>, repeatedly descending below any discarded element must reach a retained <minimal element>. Thus the constructor represents exactly the required <finitely generated upper set>.
Membership follows directly from the <abstraction function>. For <intersection>, an element $x$ lies above some $a\in B$ and some $b\in C$ exactly when it lies above their <least upper bound>:
$$
(a\leq x\land b\leq x)\iff a\vee b\leq x.
$$
The forward implication is the defining leastness property; the reverse uses that $a\vee b$ is an <upper bound> and <transitivity>. Consequently
$$
\uparrow B\cap\uparrow C=\uparrow\{a\vee b:a\in B,b\in C\}.
$$
Recomputing <minimal elements> therefore yields a finite basis for the exact <intersection>.
For <subset> inclusion, it suffices that every generator of the left-hand <upper set> belongs to the right-hand <upper set>. Necessity holds because each generator belongs to its own closure by <reflexivity>. Sufficiency holds because the right-hand <set> is upward closed. Finally,
$$
\boxed{\uparrow B\subseteq\uparrow C\iff\forall b\in B,\ \exists c\in C,\ c\leq b,\qquad (\uparrow B)\vee(\uparrow C)=\uparrow(B\cup C).}
$$
Thus `lub` computes <union>, which is the <least upper bound> under <subset> inclusion. The empty basis represents the empty <set>; all four methods handle it without a special case. As in part (a), two distinct Scala objects may denote the same abstract ordered value. Retaining several equivalent representatives is harmless: they generate the same upward closure, and the strict-comparison test removes only genuinely nonminimal values.
Back to article page
