12

Can anyone recommend a textbook for an introduction-to-proofs bridge course that discusses the rules for "proving and using" (aka "introduction and elimination") each connective and quantifier, as in type theory or natural deduction? All the books I've looked at so far either explain the connectives using truth tables, or don't explain them specifically at all. They often discuss some of the rules (like "direct proof" = implies-intro and "proof by cases" = or-intro and "constructive proof" = exists-intro), but usually just in a list of "proof methods" without an organizing structure.

(To clarify, I'm not looking for a textbook in formal logic. I know that some people use textbooks in formal logic for bridge courses, but I don't think that would be appropriate for my students. I want a textbook which introduces students to the idea of proof, to basic concepts in mathematics like induction, divisibility, and sets, and to other aspects of mathematics like mathematical writing and exploration / proof search. There are lots of such textbooks, but I haven't found one yet that organizes the proof rules by their governing connectives as above.)

Mike Shulman
  • 6,560
  • 21
  • 53
  • 2
    Have you looked at How to Prove It by Daniel Velleman? I bought the book my senior year of high-school and I believe it introduced me to advanced math pretty well. An entire chapter is devoted to proof strategies and different kinds of proofs. – Andrey Kaipov Nov 23 '14 at 04:42
  • @AndreyKaipov no, I hadn't yet, thanks! His chapter 3 is pretty much exactly what I wanted. If you post that as an answer, I'll accept it. – Mike Shulman Nov 25 '14 at 23:34
  • I've written a text that addresses your needs, I believe; however, it's not available (yet) publicly. How can I share it with you (and others who may be interested)? – Brendan W. Sullivan Dec 02 '14 at 05:18
  • @brendansullivan07, if you only want to share it with me, my email address is on my web site; you can send me an attachment or point me to a private URL, dropbox folder, etc. I can't think of any way to share it with others who may be interested yet keep it non-public other than inviting any such person to contact you directly. – Mike Shulman Dec 02 '14 at 07:21
  • 1
    @MikeShulman I am writing course notes for a discrete math textbook now, and I may eventually assemble them into a book. If you are interested, take a look at

    https://drive.google.com/file/d/10-diAOsR8aC2sIhRqxFzl0WsDDAvC6hx/view

    and let me know what you think. Constructive criticism is welcome.

     – Steven Gubkin Feb 21 '21 at 16:12
  • @StevenGubkin Not bad! Minor point: you use F for both "Superman is fast" and absurdity, which might be a bit confusing. Less minor point: I think a very common way to prove a disjunction $p\vee q$ is to first use some other disjunction and then prove $p$ in one branch of the case split and $q$ in another branch. So I would disagree that most of the time we prove a disjunction with the converse-disjunctive-syllogism. – Mike Shulman Feb 21 '21 at 21:11
  • @MikeShulman Good point on both counts! I will update the document to include your observation about case analysis. – Steven Gubkin Feb 21 '21 at 23:44
  • @MikeShulman I also thought you might enjoy the bit about "weaseling out" of rules for proving that statements are false. I think I read a paper of yours some time back about linear logic which needed such rules. – Steven Gubkin Feb 21 '21 at 23:51
  • 1
    @StevenGubkin I wouldn't really use the phrase "weasel out", but I won't object to it either. I would say that $p\to \bot$ is really just the definition of $\neg p$. My paper about linear logic involves notions of "refutation" that are dual to "justification" when discussing semantics, but the rules of proof don't involve separate notions of "proving false" and "proving true". – Mike Shulman Feb 22 '21 at 00:23
  • Does this answer your question? How to teach Proofs –  Dec 28 '21 at 05:49

1 Answers1

8

The book How to Prove It by Daniel Velleman has an entire chapter devoted to the different types of proofs and the strategies on how to approach each one. It's actually the first book my university uses in its "Intro to Advanced Math" course. Even though the book's language tends to be fairly casual and conversational, it does a great job of introducing true mathematics!

Andrey Kaipov
  • 236
  • 1
  • 4
  • +1. Had DJV as a professor for a couple of classes; he is an excellent teacher, and his other writing (book on philosophy of mathematics, and pretty much all of his papers as found through google scholar) is exceptional. – Benjamin Dickman Nov 27 '14 at 04:46
  • Bonus points for including 0 as a natural number. (-: – Mike Shulman Nov 27 '14 at 10:11