specification
   using nat
   sorts Map('a, 'b);
   constants 
       ∅ : Map('a, 'b);
   
   functions 
       . [ . := . ] : Map('a, 'b) × 'a × 'b → Map('a, 'b);
       # . : Map('a, 'b) → Nat;
       . -- . : Map('a, 'b) × 'a → Map('a, 'b) prio 9 left;
   
   predicates 
       . ∈ . : 'a × Map('a, 'b);
       . ⊆ . : Map('a, 'b) × Map('a, 'b);
   
   variables 
       st : Map('a, 'b);
       st0 : Map('a, 'b);
       st1 : Map('a, 'b);
       st2 : Map('a, 'b);
       a : 'a;
       b : 'a;
       c : 'a;
       d : 'b;
   
   partial functions 
       . [ . ] : Map('a, 'b) × 'a → 'b with λ st, a. a ∈ st;
   
   
   induction 
      Map('a, 'b) generated by ∅, [ := ];
   
   axioms 
      Extension: st1 = st2 ↔ (∀ a. (a ∈ st1 ↔ a ∈ st2) ∧ st1[a] = st2[a]);
      used for: ls;
      
      In-empty: ¬ a ∈ ∅;
      used for: s, ls;
      
      In-insert: a ∈ st[b := d] ↔ a = b ∨ a ∈ st;
      used for: s, ls;
      
      At-same: (st[a := d])[a] = d;
      used for: s, ls;
      
      At-other: a ≠ b → (st[b := d])[a] = st[a];
      used for: s, ls;
      
      Subset: st1 ⊆ st2 ↔ (∀ a. a ∈ st1 → a ∈ st2 ∧ st1[a] = st2[a]);
      used for: ls;
      
      Size-empty: # ∅ = 0;
      used for: s, ls;
      
      Size-insert: ¬ a ∈ st → # st[a := d] = # st + 1;
      used for: s, ls;
      
      Del-empty: ∅ -- a = ∅;
      used for: s, ls;
      
      Del-rec-same: st[a := d] -- a = st -- a;
      used for: s, ls;
      
      Del-rec-other: a ≠ b → st[b := d] -- a = (st -- a)[b := d];
   
   
end specification