Why isn't mutable a subtype of immutable, or vice versa?

If you pair mutability with exclusive access then you have handled the objection raised by the (some may say overly) strict definition of subtyping here and also the attempt to argue over the objection. No code which asks for an immutable instance will ever observe the mutability because the ask for an immutable reference is exclusive. Therefore, you could pass the mutable reference but so long as something holds onto that reference the mutability is no longer available to other code.

So mutability xor aliasing provides this strict subtyping relation. Of course, you also then need ways of loosening this by providing objects without such a contract and you enter the land of interior mutability, where again the mutable methods can be understood as a part of a subtype because a holder of the reference without mutable methods was explicitly told that there was no the guarantee that the object wouldn't change.

In other words, immutable != read only.

In C# ReadOnlyCollection<T> and ImmutableArray<T> are two completely different things for this exact reason.

Isn't NSMutableArray a subclass of NSArray in a few languages?

Yep, I wondered that for a few optimizations in Racket. It's harder than it looks, probably something about covariant or contravariant types, I gave up.

The fact that it requires so much explanation, indicates the level of degradation in the reasoning ability of the audience. A value of a subtype shall deliver all of the expectations of its super type, because it is wearing both the hats of super type and sub type.