A Programmer's Introduction to Mathematics
pimbook.org
pimbook.org
> "The distinction between the discrete and the continuous lies at the heart of mathematics. Discrete mathematics (arithmetic, algebra, combinatorics, graph theory, cryptography, logic) has a set of concepts, techniques, and application areas largely distinct from continuous mathematics (traditional geometry, calculus, most of functional analysis, differential equations, topology). The interaction between the two - for example in computer models of continuous systems such as fluid flow - is a central issue in the applicable mathematics of the last hundred years."
http://philsci-archive.pitt.edu/16561/1/Discrete%20and%20Con...
With respect to programming and mathematics, this line is worth thinking about: The problem is that the continuous is easier to imagine and prove results about, but the discrete is unavoidable when it comes to calculation.
Why would that be true? A cyclic group of order n, or even all of Z, seems to me easier to think about than the real numbers which employ philosophically tricky notions such as uncountable infinity, limits, convergence, etc. There are a lot of weird and counterintuitive results even in elementary analysis because of the way the real numbers work.
Of course, there's also discrete objects that are hard to reason about.
I also suspect that this is a fairly orthodox attitude among mathematicians - in "The two cultures of mathematics" (https://www.dpmms.cam.ac.uk/~wtg10/2cultures.pdf) Tim Gowers says with more authority than I could:
> the subjects that appeal to theory-builders are, at the moment, much more fashionable than the ones that appeal to problem-solvers.
This isn't precisely the discrete/continuous split, but it's mostly aligned and the article puts combinatorics is firmly in the latter category.
As an example showing that it is true, read https://math.stackexchange.com/a/362840/6708 explaining how it is possible that the real numbers are complete (all first order statements about them are either provably true or false) while the integers are famously incomplete (no set of axioms can prove everything about them).
ALL of the philosophically tricky notions that you list are only tricky when you mix in discrete notions like "integers" in your construction. And given that discrete mathematics gives us things like the Halting problem and incompleteness WITHOUT continuity being involved, shows that it is discrete mathematics that is harder.
> ALL of the philosophically tricky notions that you list are only tricky when you mix in discrete notions like "integers" in your construction.
That may be so, but people generally don't use RCF exclusively. Real analysis always looks at the real numbers as an extension of the natural numbers, you can't go anywhere without sequences and limits. So it seems disingenuous to say that continuous mathematics is easier just because RCF is complete.
> And given that discrete mathematics gives us things like the Halting problem and incompleteness WITHOUT continuity being involved, shows that it is discrete mathematics that is harder.
While this is true, it's also true that a purely additive theory of the natural numbers is complete and several other theories of discrete structures are too (for example, while group theory itself is not complete, it's certainly completable, unlike Peano Arithmetic).
Also, the halting problem and incompleteness aren't where weirdness ends. There's a whole other range of weirdness that happens only once you add in uncountable infinities, such as Skolem's paradox, the Banach-Tarski paradox or the undecidability of the continuum problem.
The Banach–Tarski paradox is an example of an unintuitive result of the LEM, a paradox that doesn't exist in constructive mathematics.
I don't have any experience with constructive set theory, so maybe I'm missing something.
Sure, Errett Bishop came along with https://www.amazon.com/Foundations-Constructive-Analysis-Err... and fixed that. But it is harder. And sure, as soon as you start looking at error bounds in numerical analysis, the classical shortcuts start to take work. But it is simply wrong to assert that the continuous REQUIRES the law of the excluded middle.
In fact every mathematician has been through the classical treatments of continuity in courses on real analysis and topology. Very few can say much that is sensible about constructivism.
https://www.youtube.com/watch?v=XqywV-wkKSE
'discrete mathematics : algebra :: continuous mathematics : coalgebra'.
It's like the missing half of math and programming. Power series? Coalgebra. Combinatorics? Coalgebra. Continuousness? Coalgebra. Bases? Coalgebra. Control flow? Coalgebra [1].
I have a discord https://discord.cofunctional.ai.
I'm working on a second book: Practical Math for Programmers. Some details at https://pmfpbook.org/
Every weekend I livetweet my notes and research on the new book over at j2kun@mathstodon.xyz, e.g., https://mathstodon.xyz/@j2kun/110283189611214753
Happy to entertain any ideas folks have for topics! Got a long backlog to go through, but there's always room for more.
Once the next book comes out, I’ll buy a couple of copies immediately! Looking forward to it!
I will be purchasing your first book sometime this week. I feel like I can finally make real progress in learning mathematics with ChatGPT as an aide.
Suffice to say. Love the book. Will it make you a fully fledged mathematician? Of course not. Can it teach more or better, sure, what not? But it’s a great introduction anyway and it may inspire many that otherwise might not be inspired. Mathematics is really fun if you’re not afraid to feel uncomfortable all the time. Luckily most good programmers probably have that same feeling all the time anyway. I can only hope for more books like this, I have some space reserved for them on one of my dusty shelves! Big thanks for the author to write this book!
It seems to be heavily focused on Algebra and arithmetic. My own recommendation would be to pick up Coq or Idris and use that to bridge programming, math and logic. In my experience this is the best way to leverage the knowledge. Understanding monads and category theory will immediately let you make better API designs, architecting larger applications, etc.
Also, won't learning two things at once be harder than learning each independently?
There's no quick fix in there though.
And when that is digested: https://www.cis.upenn.edu/~bcpierce/tapl/main.html
And I think the learning should be fun. It is much more like taking an adventure into these areas. Especially when it is not a part of a course. So learn everything at ones and write about it (this is an area that is serious in need of some good written blog articles) - Maybe that will also create some serendipitous moments :)
> Also, won't learning two things at once be harder than learning each independently?
kind of, yes. But it's kind of funny. Like, it can take a while to get your head wrapped around functional or object oriented programming. But once you get a sense of it, you can kind of puzzle out any of that style of code. Math is written in proofs. after you prove a + (b + c) = (a + b) + c a few times, you kinda get a sense of what to look for.
I'm not saying it's easy. I am saying it's not that different than becoming fluent in another style of programming. functional hello world is still just hello world. deeper, more complicated programs are hard no matter the language/style. Getting a handle on writing proofs has been personally rewarding. (I've been pretty casually studying over the last few weeks/months). I don't think it'll advance my career or anything, but it's neat.
Why even go into anything that requires "real" numbers when talking to programmers, if no real numbers can possibly exist in computers? You don't need "real" numbers for logic, nor for algebra, neither for combinatorics and many, many more useful areas of mathematics (from programming perspective). And yet the reader is required to take on faith some "math wizardry"...
Even if the author wanted so much to have polynomials, why not take polynomials with rational coefficients? -- A much easier to digest concept that requires no hand-waving and works just as good for the purposes of illustration?
Perhaps that was the intention there.
As for choosing polynomials in general as a starting point, a potential answer is maybe found in the text:
> Polynomials occur with stunning ubiquity across mathematics.
That is, beyond the concept of basic arithmetic that's surely already known, it's possibly a logical place to begin.
Floating point numbers with arbitrary precision are not the same thing as "real" numbers. They are still rational numbers. See, even you made this mistake, not surprisingly, this will confuse (or even worse, will give a false sense of understanding) to programmers reading such examples.
Arbitrary precision floating point numbers exist and are quite tangible, while, perhaps, not very common, and that is the concept that's easy to grasp. These behave like almost any other number you know: you can add them, multiply, take a natural logarithm of etc.
You cannot do any of those operations on "real" numbers in computers because of the way arithmetic operations work, you'd have to start with the least significant digit (to know if there's a carry), but there's no way to find out what the least significant digit is going to be.
As for the definition of reals - most programmers have a basic knowledge of reals and functions already, would working from first principles be any use for programming?
The "real" numbers taught in high-school or in college are, well, basically, a thinly veiled lie. They "work well" for students who substitute memorizing the page number of a proof of a theorem for actual understanding of a theorem, but they don't work well for mathematicians who would actually want a good theory justifying their existence.
Needless to say that nothing in computers work as a "real" number. Knowing this is important to understand that you work with, as you called them "approximations" and that those "approximations" will have pathological cases where the distinction will bite you.
Finally, it's completely unnecessary for the purpose the author is using them for to have "real" numbers. It works perfectly fine with a much simpler and straight-forward concept of rationals, which doesn't require any pretension and wink-wink fingers crossed explanations.
I specifically pointed this out because I remember how in my days of being a CS student the boneheaded practicum material made my blood boil because a professor would write nonsense like "let A[j] be an array of real numbers" in a... C program! And the same boneheaded professor, when told to correct that to "floating point" or "rational" would spit some more nonsense about "real" numbers.
https://softwarefoundations.cis.upenn.edu/
With the added bonus that you learn how to prove software correct.
And its standard reply: "It's actually bananas all the way down."
You can evaluate the validity of a proof by checking the truthfulness of every statement which was used to argue that the proof holds
Miniature example of a proof with relaxed rigor:
Proove that 3+0=3
Proof: The above statement is a direct consequence of the additive identity axiom which states that x+0=x, if x is a real number. So the only thing we need to check is if 3 is a real number, and we know that it is. The statement holds, end of proof
So to check the validity of this proof you could check if that axiom really exists and check if 3 is a real number, if some of those is false than the proof is invalid
Edit: Or imagine that you have a DB full of axioms, theorems, prooven statements which you can use to proove a given statement. Then you could proove something by just referencing those. Eg. in the example above lets say that the neutral identity axiom has id 3, and the fact that 3 is a real number has an id 103. Then I could just say since 3 and 103 3+0=3
* There is a finite set of logical rules. For example, one rule is that if A => B and B => C are true, then A => C is true.
* We start with a finite set of given facts.
* At each step, we state a new fact and note it is true by combining previous facts with a rule.
* At the end, we have the claim we started with.
Example: prove 14 is an even number.
1. If a number equals two times an integer, it is even (given fact).
2. 7 is an integer (given fact).
3. 14 = 2 times 7 (laws of multiplication).
4. 14 = 2 times an integer (combining (2) and (3)).
5. 14 is even (combining (1) and (4)).
At a more complex level, e.g. proofs by induction are often no more than programs with for loops.
What are your favorite Math and Programming books?
Any lists for favorite Math book that you put together?
Approachable and friendly writing style reminiscent of the "3 Blue 1 Brown" channel on Youtube.
Having done competitive programming also, I would not say that it made any difference for my mathematical perception.
Even using recursion is rarely a good idea as you loose control with your memory layout.
And using a language that supports the concept of proof by induction would surely leave you on the absolutely last place for competitive programming as most of the algorithms used use guarantees that are extremely difficult to reason about even with some of the most recent advances in formal methods.
I do see how combinatorics work with competitive programming, though. and to an extend also probability theory, though I never used any probabilistic algorithms myself.
Used recursion at tons of Codeforces / ICPC problems with some caching(commonly known as "dynamic programming")
Functional programming? NOT TODAY!
My expectation is always, teaching Maths without using any of Maths language (forget theorem, signature,...). Is this possible ? Yes.
Programmers use code, algorithm, data structure to run the code, and to understanding the theory, instead of understanding Maths language, which is most of the time, "hurt the brain"
You can replace any of Math definition with code.
Is this the point of "for programmers" ?
You often (but not always!) can replace a math definition with code—but either your code is sufficiently precise that it's just another way of phrasing the definition, or you're in the analogous situation to using a language defined by its implementation instead of a specification. And there's plenty of useful space for such languages—but they aren't formally specified languages. Math that isn't formally specified isn't math, in any sense that a mathematician would recognize—which is not to say that it can't be useful.
It is just not very good for the newcomer that needs to learn the implicit assumptions that are not written out.
You say it as if it was a good thing. It's not. APL, J, and K would reign supreme over all programming if brevity and conciseness were all that good for people actually understanding what the heck is happening.
Math notation is a peculiar, loosely defined, context-dependent, ambiguous syntax that requires a lot of memorization, a special keyboard when writing, and a lot of focus when reading. It only benefits people forced to write equations on blackboards all day long. I mean, I feel for them, it's a tough job, but I'm not going to be doing that.
> the effort to understand the terminology is basically zero
You say it as if it was a fact. I don't believe it's anything else than a gut feeling you have. It's trivial to find people for whom the effort needed to understand the terminology or syntax was too big of a barrier to entry. If you could show a proper, replicated study from scientists working on cognition and memory that proves this statement (zero-cost of alien terminology), it would be great. Otherwise, I see this as a gut feeling coupled with survivorship bias.
On the flip side, try reading all your programs in assembly.
Verbosity is nice up to a point. When I look at the math I did for physics, solving a problem could take 3 pages. If we go with the GGP's approach, it would take perhaps 15-20 pages. Almost everyone would grok it quicker with those 3 pages than trying to read a more verbose 15.
It's actually why some prefer functional programming. Which is easier to understand:
"Take these student papers, and split them into two groups based on whether the student's name begins in a vowel or not."
OR
"Create two groups. Call them vowels and consonants. Take the first paper. If it begins with a vowel, put it in the vowel group. Otherwise put it in the consonant group. Once done with that paper, repeat the steps with the next paper. Keep repeating till there are no papers left."
And I won't even bother describing how one would do it in C (have a counter variable, at the end of each iteration explicitly check for termination, etc).
The difference between math formalism and verbosity is analogous to the difference between the two descriptions above. At some point, more verbosity lets you see the fine details at the expense of the big picture.
> It's trivial to find people for whom the effort needed to understand the terminology or syntax was too big of a barrier to entry.
It's almost impossible to find someone who can do, say Griffiths level electromagnetics or quantum mechanics without that formalism. Your refrain pops up all the time on HN, but I have yet to see someone do even undergrad level physics in any of the alternatives suggested.
Yes, agreed. But so is brevity. Up to a point, it's good. Beyond that point, it's a needless burden that could be eliminated.
> It's almost impossible to find someone who can do, say Griffiths level electromagnetics or quantum mechanics without that formalism.
I'm not saying that the formalism is useless. I'm saying it's not zero-cost. I'm against handwaving away the difficulty of working with the specific syntax because "concepts!"
Again, show me that learning to use the notation is not a problem, objectively, and then we can talk. Otherwise, you're just saying that "you just have to learn it, I did it and it wasn't that hard". OK, but that's not a proof that it isn't hard or it isn't a barrier to entry that could be lowered.
It's always believable that the barrier can be lowered. However, consider that on the one hand, you have millions of people who are quite comfortable with the current notation. On the other hand, there is ... nothing.
As I said, show me the alternative notation where people are comfortable solving Griffith level EM/QM problems with it.
I've heard this complaint for years - particularly on HN. An insistence that a superior notation must exist, that decades of SW experience shows this level of brevity makes working in the field harder, etc. Yet no one has come up with an alternative where one can solve higher level physics problems with it while maintaining sanity.
The status quo is we have a widely used system working. The burden is on those who claim it can be better to come up with something better.
We need to agree to disagree: in my mind, it's on those who say it's the best it can be to show that it indeed, cannot be better. Because otherwise their insistence on not even looking for ways to make it better looks drastically different. If you can show me that math notation is as closely aligned with how cognition works as possible without sacrificing its usability - that's great, you're right, I concede. OTOH, if the only thing you say is that it worked for a long time, worked for you, and therefore you're not interested in doing anything for it to work better - that strikes me as simply elitist.
The other problem is that nobody who is not deeply involved with math cares enough to take a closer look. How many linguists, psychologists, cognitive scientists invested their time into researching ways of making math notation better? I bet even fewer than the ones who tried researching programming. On the other hand, mathematicians are simply not equipped with knowledge and skills required to objectively assess the notation they use (neither are programmers, BTW.)
Indeed. The issue is that neither I nor most people are claiming it to be the best. I explicitly pointed this out in another comment.
> OTOH, if the only thing you say is that it worked for a long time, worked for you, and therefore you're not interested in doing anything for it to work better - that strikes me as simply elitist.
How is that elitist? If it works for me, why should I spend time making it better for? What do I gain from it?
And this comment doesn't even make sense. Mathematicians invent notations for their own convenience all the time. There's no committee that says "Yes, this is the official accepted notation." A mathematician uses whatever notation works for him, and if others find it useful, they adopt it.
> The other problem is that nobody who is not deeply involved with math cares enough to take a closer look. How many linguists, psychologists, cognitive scientists invested their time into researching ways of making math notation better? I bet even fewer than the ones who tried researching programming. On the other hand, mathematicians are simply not equipped with knowledge and skills required to objectively assess the notation they use (neither are programmers, BTW.)
You're not wrong, but you're also not helping. This is basically saying "Look, someone should do this!" If you think it's worthwhile, go for it. The category of professionals you have mentioned (linguists, etc) - most of them do not see it to be worthwhile. Put yourself in their shoes. Are they really going to invest a lot of effort to unseat a notation that has evolved over so many centuries, and then fight a battle to convince people to use it? That may well be a career killer.
And where the two of us will have to disagree on: Any improvement, although may be great for newcomers and amateurs, will barely have any impact on the productivity of a professional mathematician. As people have repeatedly pointed out: Notation is amongst the least challenging part of math. Sure, it is a barrier to entry, but at best you're simply lowering the barrier to entry - it won't benefit people who are already good at mathematics. A better notation will not enable them to suddenly grasp concepts they couldn't. That's why mathematicians don't bother.
To be frank (and I say it in all seriousness), the English language has more problems than the mathematical one, and if we could fix those, it would have a much larger impact.
That's the point. This is what going all-in on formality looks like:
/-- If n is divisible by m then the set of divisors of m is a subset of the set of divisors of n
lemma divisors_subset_of_dvd {m : ℕ} (hzero : n ≠ 0) (h : m ∣ n) : divisors m ⊆ divisors n :=
finset.subset_iff.2 $ λ x hx, nat.mem_divisors.mpr (⟨(nat.mem_divisors.mp hx).1.trans h, hzero⟩)
Compare that to a handwritten proof:
Let x be a divisor of m. Then there exists some y such that m = x * y. n is divisible by m, so there exists some k such that n = m * k. Thus n = (x * y) * k = x * (y * k) and x is a divisor of n.
But the very first review shown that I was wrong. Very few people saw this as a good idea. Most wanted both formulas and code. Apparently, there is a certain "comfortable" level of math language in a math book readers do not wish to give up.
Well, yes and no. It's true that notation is a tool and not the actual object of interest (except when it's both), but some tools are much, much better for certain tasks than others.
Imagine, for instance, trying to teach someone about databases and having them demand that you translate everything into x86 assembly first, since that's what they're comfortable with. Once you get past the basics, this is the level of mismatch we're talking about.
But if notation mattered a lot then... there would not be that many different notations either. There would be one and only notation that works and no one would dare to divert from it.
Math notation is a cultural artifact with its own significance pretty much like SQL or x86 assembly language indeed.
The reason they don't write the paper in "normal english" is because that normal english would make the paper thousands of pages long with lawyer-speak listing everything they dont mean. It turns out there isn't a shortcut to learning it, and after a couple lonely evenings slowly translating you will eventually be able to skip over that part of notation when you see it. repeat for all the maths youre interested in and you will be good