What does valid method overriding mean?
The important sentence in the first quote is


  In case of overriding, if a method with the same name is declared in the superclass then it must have the same type.


So if you have 

class C1 { ... }
class C2 { ... }

class Cls {
    C1 foo(C2 x) { ... }
}


override(foo, Cls, (C2)-&gt;C1) holds but override(foo, Cls, (C2)-&gt;C2) doesn't; the subclass

class SubCls extends Cls {
    C2 foo(C2 x) { ... }
}


is illegal. In FJ, you can't have

class SubCls extends Cls {
    C2 foo() { ... }
}


either, unlike in Java.


  If mtype(m, D) = E→E0 implies C = E and C0 = E0, then override(m, D, C→C0 )


This is implicitly quantified "for all E and E0". If mtype(m, D) is undefined, then mtype(m, D) = E→E0 is always false, so it implies anything. If it's defined, then "mtype(m, D) = E→E0 implies C = E and C0 = E0" is equivalent to mtype(m, D) = C→C0.

So it ends up being the same as


  
    If mtype(m, D) = C→C0 or mtype(m, D) is undefined, then override(m, D, C→C0)
  


(unless I went wrong somewhere)