# When can we say that a theorem has been proven?

I'm taking a Data Structures and Algorithms course for a CS program. The introductory material was all mathematics, mostly a series of formulas that we are to remember. I can work through the formulas without a problem. However, proving theorems is also a part of the material.

I've taken a fair amount of math classes but, somehow I never came to terms with proofs. I know that this question may be somewhat broad so, I'm willing to attempt to be specific if necessary.

Our book briefly explains proofs by induction, counterexample and contradiction. Regardless of the method, I don't know when the proof has been satisfied.

• You may want to do a bit of readings on "logic". – Willie Wong Apr 13 '11 at 17:45

## 1 Answer

"Proof" really refers to a spectrum of related concepts. At one end is the notion of a formal proof. A formal proof is a sequence of statements, each of which is either an axiom or is deduced from the previous statements by some deduction rule. This notion of proof depends on the axioms and deduction rules one uses. If you want to get comfortable with this kind of proof, it might not be a bad idea to study some propositional logic, where the axioms and deduction rules are relatively simple. To get a little closer to actual mathematics, the next step is predicate logic.

At the other end is the notion that mathematicians actually use in practice. Studying logic might lead you to believe that the notion of proof that mathematicians use is that of a formal proof in ZFC. However, many working mathematicians probably could not describe the axioms of ZFC when asked; in practice, this is not how mathematicians think. And for good reason: writing out formal proofs in ZFC is, for most people, a huge waste of time.

The notion of proof that mathematicians use in practice is a social construction: certain types of deductions and assumptions are socially acceptable as obvious, and one uses these to construct a socially acceptable proof. I say this not to argue that the proofs that mathematicians describe in practice are invalid but just to emphasize that what counts as a proof is a subtle question, and the answer depends on historical and cultural context. What counted as a proof for Euler is not the same as what counts as a proof now, for example.

In your case, I think the best thing you could do to get a handle on what a proof is in practice is to read the beginning (and more, if you want) of Sipser's Introduction to the Theory of Computation, which contains the clearest introduction to mathematics I have ever seen.

• Thank you, this explanation exceeds several years of classwork. – somehume Apr 13 '11 at 21:20