THE COPYING METHOD

Let phi((x) over bar) and psi((y) over bar) be quantifier-free formulas. It is a simple exercise to prove that the sentence for all(x) over bar phi double right arrow for all(y) over bar psi. is logically equivalent to the sentence there exists(x) over bar for all(y) over bar(phi(x) over bar) double right arrow psi(y) over bar)). Here, we generalize this simple fact, presenting various sentences that are logically equivalent to each sentence of the form (for all(x) over bar (1)phi(1)((x) over bar (1)) boolean AND ... for all(x) over bar (n)phi(n)((x) over bar (n))) double right arrow psi((y) over bar), where phi(1), ..., phi(n), psi are quantifier-free formulas. We prove the logical equivalence by the game method, which assigns each sentence psi and structure M (interpreting each symbol in psi) to a two-players game G(psi,M) (the players are there exists and for all) such that the sentence psi holds in M if and only if player there exists has a winning strategy in the game G(psi,M).