When evaluating substitutability we only consider the attributes of a type that are salient to its instances' values. For example, if you have an Equatable class instance x, you need to treat ObjectIdentity(x) as non-salient to its value (unless all instances are being “uniqued” somehow).
If we declare that members is not salient to the value of a Set, the substitutability problem is solved. Given what you point out about member iteration being important to the implementation of many Set operations, it may be difficult to see members as non-salient, but that's because it carries both extremely salient information (which elements are in the set) and non-salient information (the order in which they are traversed). There's just no way to get the salient information out of the set without exposing the rest of it.