 Solution

Use a lower type bound to widen the element type only in the new value:

class ISet[+T](contents: List[T]) {
  private val data: List[T] = contents

  def add[U >: T](x: U): ISet[U] =
    new ISet[U](x :: data)

  def delete(): (T, ISet[T]) = data match {
    case x :: xs => (x, new ISet[T](xs))
    case Nil => throw new NoSuchElementException("ISet.delete")
  }
}

The list is immutable and neither method changes this instance. A new wider value cannot be accepted directly as the old narrow T; instead add[U >: T] returns a fresh ISet[U]. The original ISet[T] retains its element guarantee, and deletion returns both its old head and a fresh bag for the tail. This covariant persistent multiset safely shares unchanged list tails and preserves duplicate multiplicities. The historical name ISet does not require silently changing the question's bag semantics into duplicate-removing set semantics.^[ref]