Immutable subclass of a Set class
You are right it seems rather weird for an immutable object to provide setters, which will throw an exception no matter how you call it. I would use inheritance and two different interfaces in this situation.

Imagine the base set. I would argue the base class should be the immutable set, since the immutable set declares functionality which both classes should be able to use. An example could be:

interface ImmutableInterface {

    public function fetch($key);
    public function exists($key);

}

class ImmutableSet implements ImmutableInterface {

    protected $items = [];

    public function __construct(array $items)
    {
        $this-&gt;items = $items;
    }

    public function fetch($key)
    {
        return $this-&gt;items[$key];
    }

    public function exists($key)
    {
        return array_key_exists($key, $this-&gt;items);
    }

}


You now have a basic implementation. You make your set manipulatable you could write a new interface declaring methods for changing values inside your set. The new interface could be:

interface ChangeableInterface {

    public function add($key, $value);

}


You could then write a sub-class of your original immutable set and implement the new interface. Since the $items array was declared protected any sub-class also has access to it.

class ChangeableSet extends ImmutableSet implements ChangeableInterface {

    public function add($key, $value)
    {
        $this-&gt;items[$key] = $value;
    }

}


You can now type-hint against a specific required implementation by using the interfaces. You also have the opportunity to use other classes as long as they implement the specific interface.

You can think of this strategy as declaring the fewest amount of required methods for your class to work. If you want to add more functionality you write an interface declaring no more than the required methods for that functionality to work. You can even take this further. Imagine not all your changeable sets should be able to remove items again. This could be an interface:

interface RemoveableInterface {

    public function remove($key);

}


You would then write a new sub-class of either the ChangeableSet or ImmutableSet, depending on your requirements, and implement the new interface. You can now type-hint specifically against sets which are only able to remove items. This strategy can continue forever, but do be careful. This can also be too much. Too many sub-classes can become a hell to maintain. So try to keep the amount of interfaces low, while still maintaining your required flexibility and the method signatures they declare concise.

The interface/class names used in these examples are not set in stone. They are by purpose very descriptive, so you can always rename them. Also keep in mind  there are no error checking in the examples.

I hope this can help you, happy coding!