With that intuition it's simply a matter of slogging through a proof textbook like Velleman's "How to Prove It" until you have the confidence to work through the texts that truly interest you. If you don't feel like a clueless fool you're not trying hard enough. Confusion and self-doubt are sure signs you're finally learning something.
For me, a proof is essentially transforming one formular into another one until someone who understands math says "yes, now you have proven it!"
For me, any step is as good as the others.
I wish, I could understand what's happening.
Algebra was like solving a puzzle where you randomly move pieces around to try to get them in order. There didn't seem to be any real principles involved. Just a set of rules to memorize.
But I didn't understand proofs with either.
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.
Here's what happens if you try to prove that 2+2=4 with a computer program that refuses to skip any steps (granted, it's treating them as complex numbers with zero imaginary parts):
http://us.metamath.org/mpeuni/mmset.html#trivia
Math is just a matter of transforming one thing into another using the operations allowed by the system starting from the ground truths stipulated by the system
I can’t help but shake the feeling that if it takes this many steps to prove 2+2=4 then you’ve done something wrong in the design of your formalism.
Yeah, this is why
A human proof would probably not generally go beyond something like:
2+2=4
1+1+1+1 = 1+1+1+1 // Substitute the definitions of 2 (1+1) and 4 (1+1+1+1)
S(S(0)) + S(S(0)) = S(S(S(S(0))))
and that is non-trivial. (But it's not 26,000 steps either.)
For example, in Metamath[0] (which was mentioned in another comment), there are just two inference rules. First is modus ponens[1], which says "if A is true, and if A being true implies that B is true, then B is true". Second is the rule of generalization[2], which says "if A is unconditionally true, then for all x A is true". If you start with the axiomatic statements of classical logic + set theory, pretty much all of mathematics can be inferred just by repeatedly applying these two rules to derive more true statements.
The hard part is developing a good feel for what's possible within this system and what's not, so that you can start skipping large numbers of steps too. As someone who's self-learning this stuff I've personally found exploring Metamath very helpful for this, because I find it helpful to break things down to the foundations when I'm not sure about a bit of reasoning, and Metamath is good at breaking things down to the foundations. But to each their own. Regardless, if you haven't already done so, I'd recommend learning classical logic if you want to understand proofs.
[0] http://us.metamath.org/mpeuni/mmset.html
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"?
CS is quite math-intensive on its own but it kind of assumes a certain level of math maturity.
Any particular recommendations?
Instead of listing other books I would suggest the following learning scheme of a programmer trying to deepen their math:
1. No need to go beyond basics. Any uni-level introductory math course is already more advanced than 99.99% uses you might have.
2. Know your basics well. Get 2-3 classic books. Work through the one you like most, but still read through the rest.
3. Practical book size limit - 200-250 pages. Math material is hard, 200 pages of good math is months and months and months and mo...
4. Setup a learning/reading routine.
Disclaimer: I didn't fully work through this game, I never studied at ICL and I can't vouch for its effectiveness, I simply heard about it and thought it was interesting and relevant to your question.
(Here's also a talk by the professor about his rationale for using Lean: https://youtu.be/Dp-mQ3HxgDE).
It's a good thing then that this framing is rather unlike the intuitionistic mathematics actually suggested.
I have to wonder if highschool math would make more sense to some students if (a) and (b) were taught together.
I might even cut polynomials entirely to make room for the new stuff and do informal calculus earlier.
Math is ultimately about bridging the gap between fuzzy warm intuition and and cold artificial rigor. Focusing on either in isolation defeats the purpose.
For anyone that struggled with pure math because memorizing seemed less "big brained" than informal proofs, computers making thing concrete let alone gamified can help immensely.
I learned a lot from working through An Infinite Descent into Pure Mathematics by Clive Newstead. It's designed to get someone with minimal math background started with the basics of pure math. Becoming comfortable with proofs happens along the way.
Lately, I have also really enjoyed 99 Variations on a Proof by Philip Ording, which is not a textbook. Rather it is an Exercises in Style type book that explores many different ways to express a mathematical proof of the same simple fact. Some of the proofs are whimsical, and others offer genuine insight. If you're looking for something lighter than a textbook that is still interesting and somewhat useful, this book is more approachable.
https://www.amazon.com/99-Variations-Proof-Philip-Ording/dp/...
Thank you, I really enjoyed this so far. Probably going to read one per day or so and then think about it.
The best one right now is Proofs: A Long Form Textbooks by Jay Cummings. I wholeheartedly recommend it. And this is exactly the one you are looking for.
It is fully intended to teach learners how to write proofs, and not to impress one's peers or get citations.
I loved the book.
I picked it up because although I had a decent curriculum-based Maths education as a Physics undergrad and wrote many proofs, these proofs were always learned in a domain-dependent way. I was clueless about writing a new proof in a new domain.
This book filled a large hole in my life.
And I recommend it.
One other book that is good and should be read if you want to rigorously study Calculus from ground up, and it also teaches you a decent amount of Analysis, too. It's Spivak's Calculus. It's one of the best Math books ever written.
https://www.amazon.com/Proofs-Long-Form-Mathematics-Textbook...
I have not read this particularly entry from him, but I have his analysis book. He is a wonderful author, and I really like his "long-form" style that presents things in a much more illustrative (often literally) style.
There's also a book called Creative Mathematics by H.S. Wall. It is intended for high school students, and I think of all the books that claim this, this one probably hits the mark. He starts you off slow and steady. Instead of proving simple logical things, Wall basically walks you through calculus with differentiation and integration and up to differential geometry. One shouldn't be discouraged because the calculus presented is simplified. It is a very enjoyable book.
"Geared to preparing students to make the transition from solving problems to proving theorems, this text teaches them the techniques needed to read and write proofs. The book begins with the basic concepts of logic and set theory, to familiarize students with the language of mathematics and how it is interpreted. These concepts are used as the basis for a step-by-step breakdown of the most important techniques used in constructing proofs. To help students construct their own proofs, this new edition contains over 200 new exercises, selected solutions, and an introduction to Proof Designer software. No background beyond standard high school mathematics is assumed. "
The problem is that, from what I can infer from your description, you don't have the fundamental skills necessary to self-tech effectively. You could try using some of the resources mentioned by other commenters, but chances are this process will much more tedious than if you had a mentor, and you'll probably come to believe various incorrect things that you'll have to unlearn later. Real-time feedback and correction would be more effective.
Also, I disagree with some of the advice given here. (Suggesting resources on Coq and ZFC to someone asking how exponents work? Really?) Tread carefully, and prefer the recommendations of people who have experience teaching high school students and undergraduates.
> OP, you should try to get someone to work with you.
Those both sound like great suggestions to me.
When I was a linguistics major in college, around 1976, I started wondering about pure mathematics—it seemed a lot more interesting than high-school calculus, which had snuffed out my previous interest in math—so I took an introductory class in abstract algebra. It was the first math class I had taken that was oriented around proofs rather than calculation, and I had trouble at first understanding what proofs were and how I was supposed to come up with them.
I went to see the professor during his office hours to ask for advice, and he told me something like this: “A proof is basically a story you tell to other mathematicians.” It took a while for the meaning of his advice to sink in, but it did eventually, especially after I took a couple of seminar-style classes in which the students worked on proofs together.
Looking back now, I would summarize what I learned then as follows: A proof is a story you tell to other intelligent, knowledgeable people to convince them that the theorem is true. As with all story-telling, you have to adjust what you say and how you say it depending on your audience and on their knowledge and expectations. If you are new to mathematical proofs, then you need to work with other people for a while to learn how mathematicians use proofs to tell stories to each other.
we can try your example
we want to show that (a^b)^c = a^bc
let's work on the LHS
by the definition of an exponent, we know that a^b is just a * a * ... * a b times, so we can rewrite it as:
(a_0 * a_1 * ... * a_b)^c
by the same definition, we can multiply the quantity inside the parenthesis by itself c times:
(a_0 * a_1...a_b)_0 * (a_0 * a_1 * ... * a_b)_1 * ... * (a_0 * a_1 * ... * a_b)_c
now, use the fact that a^m * a^n = a^(m+n) to consolidate the parenthesis, since each factor has an exponent of 1 we can use simple counting:
(a^b)_0 * (a^b)_1 * ... * (a^b)_c
Repeat the previous step c times, we end up with
a^(b_0 + b_1 + ... + b_c)
which of course is just
a^(bc)
therefore (a^b)^c = a^(bc)
Let A->B be the set of functions from A to B. Then it has b^a elements.
Let AxB the set of couples with the first element in A and the second on B. Then it has ab elements.
So to prove that (a^b)^c = a^(cb) you have to prove that there is a bijection between C->(B->A) and (CxB)->A.
Ever heard of currying and uncurrying?
(BTW, I didn't really use the hypothesis that the sets are finite, the proof is also valid for transfinites if you care about those)
One solution to this problem is to learn from a book purely on proofs, as Velleman suggests. It seems to me, however, that given your background and your wish for an 'exceedingly gentle introduction', this method might not be the best for you.
While I agree with the view that the attachment between geometry and proofs is detrimental to students' learning of both topics, I would like to make the argument that in a case like yours, learning proofs through geometry is actually a great place to start.
Proofs are not traditionally linked to geometry without reason; in school, geometry is the closest thing you get to "real" mathematical thinking. Since you are already familiar with geometry, revisiting it, this time through a lens focused on proofs, would be an effective way to bridge the gap between traditional school mathematics and proof-based thinking.
At this point, it comes down to finding the right geometry book. I highly recommend Introduction to Geometry by Richard Rusczyk: https://artofproblemsolving.com/store/book/intro-geometry. While it is designed for the advanced high school student seeking to learn geometry in a different way than what is taught in school, it just so happens that this makes it a great book for your purpose as well.
Having already learned geometry, you will be able to focus more exclusively on the proof aspect of the book. Take a look at some of the excerpts listed in the link above to see if the style of the book suits what you are looking for. After learning geometric proofs, you will then be able to easily extend the same ideas to proofs in other subjects.
1) An introduction to logic through pictures, basically Venn diagrams with explanation. This is a point of view on propositional calculus.
2) A brief presentation of the rules of the logic of "simple type theory" at a raw beginner's level.
3) A number of completely rigorous simple proofs, some in pure logic, and some about real numbers, starting from the classic "complete ordered field" axioms that define the behavior of real numbers. The proofs are all done by computer from the ground up using the logic and axioms (with a handful of gaps). The proofs are all available for reading online, down to any level of detail, interactively, and at the reader's discretion.
4) A web-based tool that lets you build and edit your own proofs.
User feedback on the site is very welcome, and I will answer questions also as far as I am able.
I highly encourage you to submit it to HN as a "Show HN: ..." (instead of being buried in a comment) and solicit feedback. Projects like this deserve more and better recognition.
I have submitted to "Show HN" at https://news.ycombinator.com/item?id=31927224.
Your input (and potential upvote) would be much appreciated.
Maybe resubmit as a link with a title something like "Show HN: Simple Proof System for Beginners" (look at previous "Show HN" posts) and add the text which will show up as a comment.
We used it in our intro proofs class in undergrad and it will get you from basic logic to introductory analysis.
With proofs, I also think there are three layers:
1. How do I draw logical conclusions from premises. This is the most straightforward part.
2. What are some of the clever tricks mathematicians use for doing this (e.g. constructing non-intuitive counterexamples, finding equivalences between two seemingly incompatible things, etc). This requires reading other proofs, and is slower, but can be very fun if you like math and find clever proofs beautiful.
3. Finding the right English words and phrases to capture the logic you have in mind (the language used in proofs is not normal English, and it has its own idiosyncrasies and conventions. Like other mathematical notation, it's often specific to particular fields of math and sometimes to a specific author). This also requires reading proofs, I think, and is also where one benefits the most from formal instruction ("how do I say X in my proof?") but I think you can get there on your own with some persistence. It's not Klingon either—proofs are supposed to be readable—but it's a bit like code, maybe, or legalese. If you just try to write nice prose, other mathematicians may find it confusing or non-rigorous.
It can be good to separate the three. Specifically, when learning a new field of math, the proofs sometimes don't feel rigorous to me right away, but once I get used to the the basics and the linguistic conventions, I'm more able to fill in the holes in my head
the most complicated proofs i ever dabbled in were things like proofs of convergence for algorithms, but i encountered various types of proofs in several intro courses: computability and theory of computation, discrete math, introduction to higher math and then some upper div cs courses in ai/ml.
what you say here rings absolutely true to me. as someone coming in with a long time background in coding and computers, i always found myself wanting to apply the same unambiguousness and precision that one uses to express computations in a programming language in mathematical proofs. this was a huge stumbling block for me! proofs are written in shorthand (!) by humans for other humans who have the same base knowledge, obvious things are omitted. once you have that knowledge it makes sense, but before that it seems like giant leaps are being taken without a rigorous line of reasoning between them.
to answer op's question: "an introduction to mathematical reasoning" by peter eccles was helpful for me. it's basically an expanded version of what you'll find at the start of many intro cs/math courses. another option, if sets, number theory and such are confusing to you is the computability angle (cs theory, computation). personally i found this material a lot easier to reason about which then imputed confidence, which is really the magic ingredient for good proofs.
Here is some help with Baby Rudin:
He wants to get to the Riemann integral, that is, the simplest version of ordinary integration in first calculus. Then for a little more, he also wants to do the Stieltjes extension of the Riemann integral.
So, he wants to integrate a function of one real variable -- he wants to keep it simple and elementary.
For this he wants to state carefully the properties of the function he wants to assume and use. Again, he goes for the simple stuff:
First he integrates the function f only over an interval, e.g., [0,1] or in general [a,b] for real numbers a and b with a < b (maybe a <= b, I save the effort of checking my copy). So, the interval is of finite length, b - a. Integrating over the whole real line from minus infinity to infinity is more difficult and left for later (and is much better done with the Lebesgue integral, see below). Also the interval is closed, that is, includes the two end points a and b.
Second, he wants the function f to be continuous on that closed interval.
So, he needs to define continuous. And what is magic about the closed interval [a,b] is that it is compact. So, he wants to define compact.
Then with continuous and compact, he shows that the function is not just continuous but also uniformly continuous, and that is the crucial, central, key property of function f that makes defining the Riemann integral easy, showing that the integral exists, and establishing its basic properties.
So, Rudin takes you off on a little side journey to understand closed, continuous, compact, and uniformly continuous. Also, with the real numbers, he uses the completeness property -- the rationals are not complete and won't work; he needs the reals! It's good to know this. Completeness also generalizes, e.g., is a key property in Hilbert space and Banach space.
Now he wants to give you a little more for your money, effort, time, etc.: These concepts of completeness, closed, continuous, compact, and uniformly continuous generalize, that is, are principles as in the title of his book. So, really he is attacking, i.e., defining and developing, the simplest integral of freshman (or high school) calculus with more general concepts, closed, continuous, compact, uniformly continuous, and completeness.
And while his function f has only one real variable, he generalizes a little, takes a positive integer n and the set of real numbers R, and considers the Euclidean n-space R^n. Then he proves that in R^n, a set is compact if and only if it is both closed and bounded. Darned good to know! And the proof is not difficult and worth understanding. I used this result in a paper I published on some really tricky aspects of the Kuhn-Tucker conditions. My department got all impressed, and that eased my path to my Ph.D.
Compact: (A) Every infinite subset has a limit point. (B) Every open cover has a finite subcover. Compact via (A) and (B) is so nice that it is almost as well behaved as only finitely many points and generalizes enormously.
A real valued, continuous function with a compact domain is forced to be quite nicely behaved -- in particular to make the Riemann integral easy to develop.
Then the uniformly continuous says that if we pick a fine partition on the X-axis (the domain of function f), then the resulting partition we get on the Y-axis (the range of function f) is also fine -- so, as we make the partition fine on the X-axis, we can be sure the partition on the Y-axis will be as fine as we please which means that, with completeness, the finite Riemann sums converge and our Riemann integral is defined.
So, completeness, closed, bounded, compact, continuous, uniformly continuous -- not very difficult and worth understanding.
Then he moves on and does the basics of infinite sequences and series, enough to define logs, exponents, and the trig functions.
Rudin is especially good with Fourier theory, and there in Baby Rudin gives a solid treatment of Fourier series. Good to know. Of course, first see the connections with organ, flute, and violin music.
Last I checked he did do the inverse and implicit function theorems -- central in Lagrange multipliers and differential geometry.
And he showed that more generally the Riemann integral exists if and only if the function is continuous everywhere except on a set of measure zero -- so he touches on measure theory.
Somewhere you should see a good proof of Leibniz's Rule (differentiation under the integral sign).
Now that you see the Riemann integral, Lebesgue's approach is better: Lebesgue partitions on the Y-axis. Turns out, for handling pathological cases, that works out a lot better. It also generalizes nicely and, in particular, is a great foundation for probability theory. That is, expectation in probability is just a Lebesgue integral. Very nice.
Rudin's development of the Lebesgue integral in his Real and Complex Analysis is very nice. Royden's treatment is a little easier to read. Read them both. And there Rudin also has very nice chapters on the Fourier transform, Banach space, and Hilbert space. Read those three chapters and apparently be for all your career nicely ahead of nearly everyone in physics, chemistry, and engineering. E.g., see how the Heisenberg uncertainty principle, whatever it is in the natural world, is really just a simple result in Fourier theory.
If you still want a gentle introduction to proofs but would prefer if the author uses a more serious tone like traditional textbooks, I recommend Proof and the Art of Mathematics by Joel Hamkins. https://www.amazon.com/dp/0262539799
All of the math is proof-based, so we start with books that teach just that: proof writing, basic logic and set theory. Then you can branch out and learn what you like. Each person goes at their own pacing.
One thing is that you will have to put a lot of effort into learning yourself; there is no silver bullet, regardless of whether you know proofs or not.
If you want to join, you can PM u/CheapViolin on Reddit.
The most basic subject to understand mathematical proofs is Euclidean geometry. There you will learn the basics of proofs and what it means to prove something.
Let’s look at x/a = b/c. You want to show that this equation has the same exact solution set as xc = ab. In order to prove this rigorously you’ll need to prove things about associativity. You’ll also need to prove that a unit isn’t a zero divisor in the real numbers. What we see is that to prove seemingly simple statements requires some machinery and to understand the necessity of this machinery requires mathematical maturity.
But maybe you don’t want to rigorously prove the above. Maybe you just want to understand why it is plausible that this is true. For that, pick up a beginning algebra book and actually read what it says and try to understand it. This is hard to do on your own.
Here’s a plausible explanation for why x/a = b/c has the same solution set as xc=ab. Note that a and c must be nonzero because we can’t divide by zero (this requires proof!). We note that
(x/a) times a
Is the same thing as x times (1/a times a). This is due to associativity. A nonzero number times it’s reciprocal is 1. And 1 times anything is itself. So x/a times a simplifies to x.
So,starting with
x/a = b/c
I can multiply both sides by a. I can do this since a is invertible and multiplying by an invertible element preserves equality (requires proof!). So what I get, after simplifying, is
x = (b/c) times a
I can rearrange things (by associativity) to write this as
x = (ab)/c
Now multiply both sides by c to get (I skipped a step by multiplying and simplifying at the same time)
xc = ab.
Good luck!
Broadening your field of view will also help a lot. Some introductory abstract algebra (groups, rings, vector spaces) would be a solid next step in my opinion, because there you will have sets of axioms and lots of proofs and you will learn about properties such as commutativity, associativity, inverses and identities in a more abstract and general way.
What you want is a book that combines an introduction to logic with a bunch of different proofs from different areas of math, such as set axioms, relations, functions, sequences, construction of real numbers, etc. There are many books like this, here is one that includes all of that plus a little number theory and algebra towards the end: http://libgen.rs/book/index.php?md5=7E4D97D2F58B91D052595E68...
https://www.cs.virginia.edu/~asb/teaching/cs202-spring05/sli...
So you want to prove that this multiplying both sides is valid?
This is something that is very close to the fundamental axioms of arithmetic (Peano axioms).
To prove it you have to show that the basic rules like associative and distributive property will derive ab = ac from b = c.
x(yz) = (xy)z # associative law
x(y + z) = xy + zy # distributive law
HOw can we use this? If we have b = c
Suppose we already have a proof which allows us to add to both sides: we can add -c: b - c = 0
One way we could do that is proof by contradiction. Assume ab ≠ ac and show that it must be that b ≠ c, without ever relying on multiplying both sides. (Which would be begging the question: assuming that which you're trying to prove; you must never assume the truth of the rule you're trying to prove.)For instance:
ab - ac ≠ 0 # subtract ac from both sides
a(b - c) ≠ 0 # distributive law
a ≠ 0 AND (b - c) ≠ 0 # Follows from 0x = 0
b - c ≠ 0 # right branch of AND above
b ≠ c # add c
Thus if we assume that b = c, yet ab ≠ ac, we arrive at a contradiction: b ≠ c. Something has to give if we want to keep b = c, namely it must be that ab = ac.We relied on some existing rules, like being able to add the same quantity to both sides, but we didn't multiply both sides of the inequality by the same factor; we relied on inferring something by using the distributive property to rearrange the difference of products ab - ac into a product form a(b - c). If a product XY is nonzero, Y must be nonzer, and so must X; if either is zero, then it falls victim to the 0x = 0 rule: zero times anything is zero.
The process of writing will hopefully help you:
- build awareness of when your arguments are not airtight or when you make false assumptions
- modularize your thinking
- become more fluent with logical "vocabulary"
As for books, my personal favorites were Problem Solving Strategies (Engel) and Art and Craft of Problem Solving (Zeitz). They're both really approachable, have plenty of examples, and will give you a different perspective on what math can be about.Take a square that has a equal parts, with x parts shaded. It represents x/a.
You can split up the whole square in a different way but keep the same area. This square has c equal parts, with b parts shaded. It represents b/c.
You can represent the work by multiplication and division, too.
Take, for example, 6/12. Divide both numerator and denominator by 3. You get the equivalent fraction 2/4.
The area does not change. Hope it makes sense.
It will take time so go at your own pace and enjoy yourself!
You'll learn something much more rigorous and concrete.
At the college level you sometimes find a division between "Pure Mathematics" courses and "Applied Mathematics" courses. Doing proofs is the name of the game in pure math classes. In applied math, while proofs are used as needed, the emphasis is on gaining intuition about how math works when it relates to the physical world. I found that approach more satisfying and rewarding. Proofs are neither the only way nor necessarily the best way for everyone to "grasp the underlying principles."
There can be great beauty in proofs - I'm not knocking them - but their are other routes to advancing your mathematics knowledge that still avoid the trap of rote memorization.
That's actually kind of hard. Not because the proof is hard, surprisingly, but because you need a rigid notion of what exactly you're trying to prove. That's the hard part. The closer you get to the basics, the deeper the rabbit hole goes. You end up with axiomatizing the algebra, mathematical logic, formal proofs and different formal models...
So _maybe_ start with something less abstract. Some problems which do not involve either algebra or geometry so you can develop intuition for what is a proof and how to see holes in a one. Afterwards, you can try adding more and more rigidity to the things you're familiar with.
If you keep doing this, you'll build up a whole library of examples and counter-examples for various statements and you'll get a feeling of how you can approach any problem (of similar difficulty).
Start with any Real analysis I and Algebra I book, and try to understand every part of it - don't skim chapters, just work at your own pace. Your pace will improve over time, that's guaranteed.
And keep doing the same thing - work out the proofs, exercises, examples and counter-examples. Re-read old ones, etc.
A lot of math knowledge is really perfect or near-perfect understanding of the basic principles.
* Doing Mathematics: An Introduction to Proofs and Problem-Solving by Steven Galovich.
The above is an expansion of the first couple of chapters of his previous book;
* Introduction to Mathematical Structures by Steven Galovich.
Reference:
1) https://mathoverflow.net/questions/62629/textbook-recommenda...
2) https://math.stackexchange.com/questions/10209/resources-boo...
In fact, the natural answer to “how do I learn to prove” or “how do I understand mathematical notation” is that you do it by learning mathematics. In mathematics, it’s important, for example, to see how things are connected, and that’s what proofs help with. Without this mathematics turns into a largely useless collection of facts - useless because an isolated fact or a formula can rarely be used as is.
If you're missing some fundamental knowledge of algebra or other high school level math, you should refresh that. You can do so through Khan Academy (https://www.khanacademy.org/math/).
The proof course I took mostly started with examples from number theory to allow students to focus on the mechanics of writing proofs. The course seems to have replaced the book I used (Mathematical Proofs: A Transition to Advanced Mathematics Book by Albert D. Polimeni, Gary Chartrand, and Ping Zhang) with this freely accessible book https://www.people.vcu.edu/~rhammack/BookOfProof/Main.pdf. This course was a prereq to the analysis, algebra, and other proof based upper level courses in math.
The most important thing is to work the examples in the chapters and solve the exercises in the back of the book. You can usually find lecture notes, problem sets, and assignment solutions on the web these days. If you're having problems with material, someone else probably has, so there is a good chance your question has been asked on Reddit or other math specific forums.
If you're more interested in math applied to computer science, then you can look for a book on discrete math. The only discrete math book I'm familiar with doesn't really make it explicit that you're learning proof techniques the way the above books do, so I can't really recommend it as a first book for self-study.
The sequence of topics covered for a course from Book of Proof by Hammack: - Sets and basic definitions: 1.1 - Logic: 2.1, 2.2, 2.3 - Proofs: 4.1, 4.2, 4.3, 4.4, 4.5 - Logic: 2.4, 2.5, 2.6 - Contrapositive Proof: 5.1, 5.2, 5.3 - Logic: 2.7, 2.8, 2.10 - Proving non-conditional statements: 7.1, 7.2, 7.3, 7.4 - Disproof: 9.1, 9.2, 9.3 - Mathematical Induction: 10.1 and 10.3 - Sets: 1.3, 1.4, 1.5, 1.6, 1.7 - Proofs involving sets: 8.1, 8.2, 8.3 - Sets: 1.2 - Relations: 11.1, 11.2, 11.3, 11.4, 11.5 - Functions: Chapter 12 - Proof by contradiction: Chapter 6 - Cardinality: Chapter 14
https://www.people.vcu.edu/~rhammack/BookOfProof/
It’s important to get feedback on your proofs, so it’s worth learning to use Lyx which is a LaTeX editor - once you know some LaTeX, you can post questions on math.stackexchange.com and people are usually glad to help
Journey into Mathematics: An Introduction to Proofs (Dover Books on Mathematics) https://a.co/d/csM8jRd
I seem to remember that by design it didn't require any advanced maths to get started constructing proofs. Good luck!
Good luck!
https://softwarefoundations.cis.upenn.edu/
Not only will you learn how to prove software correct, you will also get a deep understanding of what mathematics really is.
Lots of people are introduced to it in their linear algebra class which is a terrible way to learn it. You want a book like "Proofs and Fundamentals" by Ethan Bloch.
Multiply both sides by a
xa/a = ba/c; a ≠ 0
Simplify
x = ba/c; a ≠ 0
Master precalculus, with emphasis on conceptual understanding and computation. It's the base.
You may want to read There’s more to mathematics than rigour and proofs by Terry Tao.
https://terrytao.wordpress.com/career-advice/theres-more-to-...
Is the formatting wrong on this? Because this isn't an identity.
For
x/a = b/c
implying xc = ab
that is part of the properties of the real number system. The properties also hold for the complex numbers and some somewhat goofy number systems, e.g., integers modulo a prime number. Since the properties hold for the reals, they also hold for subsets of the reals such as the rationals, integers, and natural numbers.Here is how that goes: Thousands of years ago people could check with just simple examples that
x/a = b/c
implies xc = ab
Soooo, thousands of years ago, maybe being less picky, critical, and skeptical than now, people just believed such properties.Then ballpark the late 19th century, along came efforts to be more careful. The approach was, we will just DEFINE some things that look like the real numbers and then from the definitions prove as theorems the properties that hold. So, in short, bluntly, the reason
x/a = b/c
implies xc = ab
for the real numbers is that we have DEFINED the real numbers so that what we get looks like the numbers people did work with 1000+ years ago and also have, from some proofs, the properties they observed we want to prove can hold.In the proofs, a favorite tool is mathematical induction. So, suppose A is a non empty set. Suppose 1 is an element of A. Suppose for each n in A n + 1 is also in A. Then A it follows that A must contain the set of natural numbers (or this is the DEFINITION of the set of natural numbers).
To apply this tool, suppose B is a set, 1 is an element of B, and for each n in B n + 1 is also in B. Then, sure, A is a subset of B, and whatever property we used to define B, that property must also hold for all the elements of A, that is, all the natural numbers.
Thus mathematical induction proofs are also standard tools in proving correctness of iterative schemes in computer software.
The careful definition of the various number systems and proofs of their properties is standard material in a college math course in abstract algebra.
The course I took used
R. E. Johnson, A First Course in Abstract Algebra.
Might also consider texts by I. Herstein or S. Lang. But there are no doubt still more.
To jump just ahead, the main properties of the number systems that get proved in such texts are
identities:
0 + a = a
1a = a
inverses: a + (-a) = 0
for a not 0 there exists a unique inverse of a, 1/a, and a(1/a) = 1
associative: a + (b + c) = (a + b) + c
a(bc) = (ab)c
commutative: a + b = b + a
ab = ba
distributive: a(b + c) = ab + ac
So, define a field -- the leading examples are the rational, real, and complex numbers. But there is also the integers modulo a prime.Then with a field can define a vector space, inner products, norms, metrics, topologies, and continuous functions.
Then can define linear functions and how to represent them with matrix algebra. Then can show that matrix algebra has identities, sometimes inverses, and has associative operations. Addition is commutative but multiplication usually is not. But multiplication is distributive over addition.
Now we are into the linear algebra part of a course in abstract algebra. There can learn about principle components and dimensionality reduction, IQ testing, etc. maybe useful in some AI approaches. Can learn about convexity, linear programming, Lagrangian relaxation, group representations, error correcting coding, and get a start on Hilbert space.
The standards of precision in proofs is especially high.
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.