I like how the move-only type problem comes down to increasing the flexibility of the hierarchy. A natural and intuitive evolutionary step, where an upcoming language feature merely acts as a means of further strengthening the motivation and justifying the source compatibility issue – an artificial factor – in a positive way, of course.
It's not easy to part with SetAlgebra and to some degree I prefer a simpler naming variant. On the other hand, IntensionalSet and ExtensionalSet are sensible namings that emphasize the absence or presence of init<S : Sequence>(_ sequence: S), isEmpty and other collection requirements. There is no hierarchy contradiction either: any extensional set can be intensionally defined, while the opposite is clearly false.
@Ben_Cohen, relative to Dictionary, Set probably has more important use cases when returning the new value is convenient, but I wonder if the proposal takes into account index validity over time. Will this be addressed by the index(of: Element) customization point?