Ask HN: How to learn mathematical proofs from scratch?

I love, love, love Velleman's book.

I worked through it after uni years, and after working for a few years. It changed my perspective on proofs and math completely!

It showed how the language of logic combined set theory form a very small and comprehensible foundation for most of math.

After reading it and a few introductory-level books on number theory, calculus and combinatorics, most of CS proofs started feeling... cute.

Did I say I love "How to prove it"?

I could "use" linear algrbra in programming and I never understood analysis.

But I didn't understand proofs with either.

Step 1. Read the textbook called "ForallX". Step 2. I don't know what step 2 should be. Perhaps step 1 will be enough.

Surprised nobody has mentioned https://pimbook.org/

Jeremy Kun is a mathematician and programmer who has worked at Google and also maintains a blog at https://jeremykun.com/ (though he's writing another book more than he's blogging atm).

This does a fantastic job of teaching how you read proofs, which is otherwise a very frustrating exercise for the non-mathematician. Mathematicians, he explains, write for other mathematicians rather than students, so even rigorous proofs are full of implicit assumptions and handwaves that are deeply confusing to those outside the discipline. Kun elucidates how mathematicians think and communicate, from obscure but important typographical symbols to how conceptual formation proceeds very differently from algorithmic execution - emphasizing mathematicians' goal of understanding why mathematical objects behave a certain way as distinct from observation of how they do it. He goes back and forth between picking mathematical entities and showing how they can end up as code, and looking at code that 'just works' and backtracking to explore what makes the underlying math optimal.

It's language-agnostic and takes a slow measured approach, delving into different areas of math (calculus, linear algebra, etc) in each chapter and taking time to situate the examples in their historical and developmental context (this is foundational, that derives from the application of technique in one field to a problem in another). It's not a quick or easy read and I tend to work through a section and then set it aside while I let the insights germinate and change how I work (which is why I haven't finished it yet). But it is an enjoyable read: Kun is an engaging writer, provides useful bibliographic suggestions in context, points out blind alleys or short cuts that might not be worth taking, and reassures with stories of his own and famous mathematicians' frustrations and mistakes, so that when you inevitably run into difficulties you don't feel demoralized or stupid. The annotated bibliography in the endnotes is worth the price of admission alone.

I was in a similar position to you of being kinda good at and enjoying math but not having a good theoretical foundation, so it would be easy to get sidetracked into problems of calculation or notation and lose sight of which techniques to reach for or appreciate how a superficially complex-looking thing is simple but being expressed very tersely.

Other books I found worth reading over the years:

Euclid's Elements, because you can't be too good at geometry and the proofs are so concise you can treat them as warm-up exercises

Hofstadter's Godel, Escher, Bach: An Eternal Golden Braid, which uses humor, poetry, art, music, philosophy as mnemonic digressions to explore one very advanced mathematical proof (Godel's incompleteness theorem) and a lot of foundational computer science concepts.

Lancelot Hogben's Mathematics for the Million, an old-fashioned (1936) work aimed at the under- or reluctantly-educated person who wants to catch up. Much more about developing the skills to do math with pencil and paper (and perhaps a slide rule) than your original question of how to write proofs (not mentioned at all until page 60), but useful because it explores how and why different fields of math originated in practical need. If you can put up with his verbose style (and assumption that you will be working the examples by hand), he begins with the very basic questions of how to count and measure things and works (slowly) towards the demontrating things in the context where they matters - for example, theorems of spherical geometry are proven as solutions to the acute problems of ocean navigation.

Proving things is basically a graph search problem. You start from some givens, and you try to transform those givens into the desired theorem. Each transformation is an edge in the graph, leading you to another vertex.

What makes one person better than another at proving things? The same things that make e.g. one chess engine better than another:

1. They have a better heuristic about which paths to explore.

2. They are simply faster at executing the search.

3. They know of more “edges” in the graph: intermediate lemmas that they can apply to arrive at the theorem faster. (This doesn’t apply to most chess engines.)

Getting better at proving things requires exercising these muscles.

This is also why (IMO) it’s important to have basic data structures and algorithms memorized. The faster your recall of these algorithms, and the more algorithms you know, the more likely it is you can solve hard algorithmic problems on the job should that be necessary.