# Introduction to proofs, CSI Math 505, Spring 2017

I shall be teaching a new course Introduction to Proofs at the CUNY College of Staten Island this semester. The course is intended for aspiring mathematics students who are learning—perhaps for the first time in a serious way—how to write mathematical proofs. I think of it as a kind of mathematical coming-of-age course, for students on the cusp, maturing into mathematicians, who aspire to communicate mathematical truths to other mathematicians in the currency of mathematics, which is: proof.

I hope to help them learn how a mathematician makes an argument in order to establish a mathematical truth.

I have written a new book specifically for the course, Proof and the art of mathematical reasoning, which I hope will be available before too long. The text will be suitable for any kind of introduction-to-proofs or transition-to-proofs course at the undergraduate level, with a variety of elementary proofs from a broad swath of mathematical topics. I shall post some excerpts later, to give you an idea of the nature of the book, but for now let me simply list the current table of contents. The book begins in chapter one with the proof that $\sqrt{2}$ is irrational. The epilogue contains a variety of logic puzzles in epistemic logic.

Preface 5
A note to the instructor 11
Chapter 1. Begin with a classic 13
Chapter 2. Multiple proofs 21
Chapter 3. Number theory and the primes 27
Chapter 4. Mathematical Induction 37
Chapter 5. Discrete mathematics and finite combinatorics 45
Chapter 6. Pick’s theorem: a case study in Pólya’s advice 57
Chapter 7. Visual proofs 67
Chapter 8. Geometry and lattice-point regular polygons 77
Chapter 9. Relations 85
Chapter 10. Graph theory 95
Chapter 11. Order theory 105
Chapter 12. Theory of games 111
Chapter 13. Set theory 129
Chapter 14. Real analysis 139
Epilogue 153
Bibliography 171

## 13 thoughts on “Introduction to proofs, CSI Math 505, Spring 2017”

1. The 505 course number is because this is a new course. It will eventually receive a 200-level course number and fit into our curriculum somewhere after the calculus sequence and before or concurrent with abstract alebra or linear algebra.

2. Robert Solovay on said:

Is a draft of your book available online?

• No, it’s not yet available. I’ve been hard at work on it (using it as a form of procrastination from all my other duties), and will complete it during the spring semester, while teaching from it in this course.

3. Yes, I would be very keen to see this! Strangely I found it one of the biggest hurdles to get over when I started mathematical logic: What exactly are the constraints on a satisfactory proof (in a given context)? To be honest, I think this question is still pretty philosophically perplexing, though people seem to be able to recognise a good proof when they see one.

• I’m glad to hear it! I also find many philosophically interesting or even perplexing issues surrounding the concept of proof, such as the differences between a pure-existence proof and an explicit construction, the nature of proof generally, but also in such simple matters as vacuous truth and proof by contradiction. Naturally, I try to bring out many of these more philosophical issues when they arise in my book. Mainly, I want to give the students a variety of solid examples of different kinds of mathematical proof, using elementary arguments, but which prove theorems that seem substantial. So in the course we are going to cover some number theory, finite combinatorics and discrete math, graph theory, such as the main theorems on Euler circuits, Euler paths and the Euler characteristic for connected planar graphs, but also game theory, including specific games like Nim but also game trees generally and the fundamental theorem of finite games. We’ll also cover some topics in relational logic and order theory, along with set theory, building to Cantor’s theorem on the uncountability of the reals. Probably the chapter on real analysis is the most mathematically sophisticated, since it includes the Heine-Borel theorem, the Bolzano-Weierstrass theorem in the reals and the principle of continuous induction. The epilogue includes some fun topics in epistemic logic, including the two-generals problem, Cheryl’s birthday problem, the blue-eyed islanders problem and others.

4. Satyam Kumar on said:

I am sophomore student of undergraduate course at Indian Institute of Information Technology, Vododara and interested in fundamental foundations of mathematics. I am eagerly waiting for your book in this endevour. Will you also please make available video recordings of the lectures, if possible, which would be great to make sense of abstract concepts.

• I think my book will become available next year. My lectures are not currently being recorded, but I shall look into it.

5. Satyam Kumar on said:

Thanks sir. Can you please recommend one or two similar books suitable enough for self learning for buiding mathematical maturity.

• It would depend greatly on your level of knowledge and interests.

6. Satyam Kumar on said:

Sir, I am interested in category theory also but I do not find any suitable book treating category theory from grounds up but rigorously using logic and proofs at upper undergraduate level. I am in search of suitable book. I wish if you add a chapter on category theory also in your upcoming book,

7. Monica Selva on said:

Is the book already available? Where can it be got from? Thanks

• Sorry, it is not yet available. I’m troubled with many tasks…

• Monica Selva on said:

Sorry, I hope you can finish it soon. Thanks for your answer.