A Proof is a Winning Strategy for a Game. Finding a proof for a statement with several nesting levels of quantifiers can be very confusing. It is my experience that this confusion is the main cognitive barrier for students trying to write proofs. We will try to fease this problem by reducing the problem of proving a statement to the problem of winning a two player game, which we call the "proof game." There are two players, the prover and the disprover. A proof of a statement consists of a winning strategy for the prover, where the role of the disprover is played by the adversary. Sometimes we need to prove that a statement is false, in which case, we must find a winning strategy for the disprover, where the role of the prover is played by the adversary. The game consists of a finite number of moves. At each step, either the prover or the disprover must make some choice, subject to some rules. There are also rules which determine the winner. If the prover can win no matter what the disprover does, then the statement is true. If the disprover can win no matter what the prover does, then the statement is false. Normally, the game is set up so that someone has to win. We now look at an example out of an elementary calculus textbook. Let f be the function defined by f(x) = x^2, and we need to prove that f is continuous at 1, that is, that lim_{x -> 1}f(x) = f(1). The standard way of expressing this statement is as follows: (forany eps > 0)(forsome del > 0)(forany x)((|x-1| < del) => (|x^2-1| < eps)) We now put this in game form. Here is the protocol. All variables are real. 1. The disprover chooses eps > 0. 2. The prover chooses del > 0. 3. The disprover chooses x. 4. If not (|x-1| < del), then the prover wins. Otherwise, continue. 5. If (|x^2-1| < eps)), the prover wins, otherwise the disprover wins. A proof of the theorem consists of a winning strategy for the prover. Since the prover makes only one choice, in step 2, all we need to show is that he can win by making the right choice of del in this step. In step 2, the prover picks del to be eps/3 or 1, whichever is smaller. Since eps > 0, we are guaranteed that del > 0, as required. Now, we show that the prover wins with this choice. If |x-1| >= del, the prover wins. If |x-1| < del, Using the triangle inequality, |x+1| <= |x-1| + 2 < del + 2 <= 3. Then |x^2-1| = |x+1|*|x-1| < 3*del <= eps, and we are done.