To prove equisatisfiability, we prove something stronger (*): Let s be a signature. Let P be a sentence over s in prenex normal form (possibly with free variables). Let skolem(P) be its skolemization. Let f1,...,fk be the new fucntion constants (may be 0-ary) added in skolemization. Let s' be the signature s augmented with f1,...,fk. Then there exists a mapping G from intrepretations over s' to interpretations over s and a mapping H from interpretations over s to interpretations over s' such that 1. for every interpretation M' over s', G(M) agrees with M over s. 2. for every interpretation M over s, H(M) agrees with M over s. 3. for every interpretation M' over s', for every variable assignment v, if (M',v |= skolem(P)) then (G(M'),v |= P). 4. for every interpretation M over s, for every variable assignment v, if (M,v |= P) then (H(M),v |= skolem(P)). [We do this because induction does not quite go through with the weaker induction hypothesis.] Base Case: Let P be a quantifier-free sentence (possibly with free variables). skolem(P) is exactly P, so (*) holds for P. Induction hypothesis: Assume that for any sentence in prenex normal form, with at most n >= 0 quantifiers, (*) holds. Induction step: Let P be a sentence in prenex normal form with at most n quantifiers. Case 1: show (*) holds for Ax.P. By IH, (*) holds for P. Let G,H be functions as required by (*). Claim: G,H also serves as the function showing (*) holds for Ax.P Requirement 1 and 2 hold because G,H are unchanged. Requirement 3: skolem(Ax.P) is exactly Ax.skolem(P). For every M, for every variable assignment v over the free variables of Ax.P, If M,v |= skolem(Ax.P) then [by definition of skolem()] M,v |= Ax.skolem(P) then [by semantics of universal quantifier and the fact that v does not map x] M,v |= skolem(P) then [by (*) property of G for P] G(M),v |= P then [by semantics of universal quantifier and the fact that v does not map x] G(M),v |= Ax.P For every M, for every variable assignment v over the free variables of Ax.P, If M,v |= Ax.P then [by semantics of universal quantifier and the fact that v does not map x] M,v |= P then [by (*) property of H for P] H(M),v |= skolem(P) then [by semantics of universal quantifier and the fact that v does not map x] H(M),v |= Ax.skolem(P) then [by definition of skolem()] H(M),v |= skolem(Ax.P) then Case 2: show (*) holds for Ex.P By IH, (*) holds for P. Let G,H be the functions as required by (*). Let FV be the free variables of Ex.P, skolem(Ex.P) is skolem(P)[x<-f(FV)], where f is a new function constant (possibly zero-ary). Define G' as follows: G'(M) = G(M*), where M* is exactly M except the interpretation of f is removed. Define H' as follows: Let FV be the free variables of Ex.P. For every M and every variable assignment v over FV such that M,v |= Ex.P, there exists a member obj_v of the universe of M such that (M,v union {x<--obj_v} |= P. Define M' by augmenting H(M) with the interpretation of f as mapping each v(FV) to obj_v. Let H' map M to M'. Claim: G',H' serves as the function showing (*) holds for Ex.P Requirements 1 and 2 clearly hold. Requirement 3: For any interpretation M and any variable assignment v over the free variables of skolem(Ex.P): If M,v |= skolem(Ex.P), then M,v |= skolem(Ex.skolem(P)) by definition of skolem(). Then M*,v |= Ex.skolem(P) because M(f)(v(FV)) is such an x (M* is exactly M except the interpretation of f is removed). Let v' = v union {x <-- M(f)(v(FV))}. Then M*,v' |= skolem(P). Then G(M*),v' |= P by IH. Finally, G'(M),v |= Ex.P. Requirement 4: For any interpretation M and any variable assignment v over the free variables of Ex.P: If M,v |= Ex.P. Then there exists obj in the universe of M s.t. , letting v' = v union {x<-- obj}, M,v' |= P. Then H(M),v'|= skolem(P) by IH. Then H(M),v|= Ex.skolem(P). Then H'(M),v |= skolem(Ex.skolem(P)) by definition of H'. Finally, H'(M),v |= skolem(Ex.P) by definition of skolem().