Learning Proofs (for Computer Science)

Question

Harvard's math curriculum, for freshmen, is divided into 4 classes beyond the BC Calculus level, Math 21, 23, 25 and 55. Math 21 is your classic plug-and-chug multivariable calculus and linear algebra course. The rest of the courses teach multivariable calculus and linear algebra in the context of proofs, along with some real analysis. I decided to take Math 21 this semester (don't ask me why, it was a horrible decision and it is why I am writing this post).

Anyways, I now realize that I need to learn proofs in order to use them in higher-level computer science classes. Plus, I might have an interest in higher mathematics in concepts such as real analysis, probability theory, optimization, etc. How should I go about learning proofs, specifically in the context of discrete math, linear algebra, and real analysis, so that I can apply my knowledge to computer science and the higher-level math in which I might be interested?

Thanks for your advice in advance. This is my first question on Math Stack Exchange, and I'm curious to see what the community is like!

Answer 1

"I now realize that I need to learn proofs in order to use them in higher-level computer science classes." If this means you need to learn how better to organize and present proofs in mathematics you might well find How to Prove It: A Structured Approach by Daniel J. Velleman very useful indeed.

But even better is to work seriously at the maths courses you are doing. If you are having difficulty getting the hang of proof-cosntruction, look at more than one textbook covering the relevant topics. Work through two or three parallel chapters of a couple of books -- then go through the chapters covering the same material in a third book, but this time covering up the proofs, trying to produce your own, and compare yours with the book proofs. You need this sort of practice, practice, practice to get the hang of proof-writing.

Answer 2

Your question really resonated with me. I wish I could beam back in a time machine to give myself the following advice. Since I can't, I'll pass it along to you.

1. Become conscious of your own problem-solving processes. Read Polya's book How to Solve It carefully. Do all the exercises; this is very important. This is a book of great power hiding under great modesty: it presents itself as a trivial high-school algebra book. Nothing could be further from the truth; it's had a huge influence on Artificial Intelligence, for example. See the Wikipedia entry for a quick summary of what you'll get. After reading the book, try to observe your mind as you attempt to solve some problems. This brings a power of its own. If you can study Artificial Intelligence (AI), do. I know this sounds strange, but AI deals quite explicitly with these kinds of problems. Imagine trying to write a program to do proofs. How would you do it? Merely working on this problem, not necessarily succeeding, will help you with your own proofs.
2. Study logic. Work on proofs in propositional logic first. This gives you nice practice with proofs in and of themselves, but better yet gives you a firm intuitive grasp of what real rigor is like and when a proof is really a proof and when it's done or not. It gets rid of that queasy uncertain feeling one has had before exposure to logic. If you can over the long run take a class on mathematical logic, do so. Mathematical induction proofs before exposure to mathematical logic seem like magic or hand-waving hocus-pocus. Afterward, after seeing the induction axiom in all its rigorous glory, one knows exactly what is required for an induction proof and why it's needed.
3. Do examples. Everyone will tell you this and they're right. Finding the right mother lode of examples is tough. The best book I've ever seen for this by a long shot is Polya's book Mathematical Discovery. How To Solve It was just the warm-up, the first draft. Mathematical Discovery is the culmination. Try just the first two chapters. It's essential to try the problems! Polya is an amazing teacher; clearly these problems are the gems collected over a long lifetime. Just reading the chapter is liking eating a teaspoon of ice cream: merely a taste. Doing the problems is like eating the whole five-gallon drum of ice cream: much more filling and substantial, and when you absorb it as part of you, you've changed.

Finally, I want to echo Peter Smith's advice to study as many textbooks as you need to in order to get a clear explanation of the concept you want. I remember trying to understand a concept and getting something like 6 books from the library once, and only one of them did a decent job of explaining the concept. So lots of books is a good thing, not a bad thing.