Why are mathematical proofs so hard?

Question

I am an electrical engineer and trying to make a transition into machine learning. I read in multiple articles that I have to learn data structures and algorithms, before this I have to learn about mathematical proofs. I started studying it on my own using the material available on MIT's OCW, while I did grasp the concepts of induction and well ordering etc..

I've been struggling with the exercises for a very long time and it's really frustrating. I can easily deal with any type of proofs that I saw before (e.g. once I saw the proof of a recurrence question I became pretty good at proving them). My problems start when I face an unusual question. I feel like I am memorizing the proofs rather than learn how to prove.

Is there any way (or any resources) that can improve my proving skills in a way that whenever I see an unusual question (like the checkers tiles and chess tiles type of questions) I don't have to stare at them for 2 hours before giving up?

Answer 1

I feel like i am memorizing the proofs rather than learn how to prove

You can't learn "how to prove". "Proving" is not a mechanical process, but rather a creative one where you have to invent a new technique to solve a given problem. A professional mathematician could spend their entire life attempting to prove a given statement and never succeed.

I can easily deal with any type of proofs that i saw before ( eg. once i saw the proof of a recurrence question i became pretty good at prooving them). My problems start when i face an unusual question.

That is normal. Any mathematics "proofs" course isn't designed to teach you how to take an arbitrary problem you've never seen before and be able to solve it (since nobody, not even the best mathematics professors can do that). Rather, your learning goals are

1. Learn how to "read" proofs and judge their correctness

2. Learn how to "write" down a proof in the right mathematical language

3. Learn about known proof "techniques" and how to apply them

If you are working on a new, unknown problem, it is normal that you might not be able to solve it. However, knowing and having memorized other proof techniques may help you. Often proofs involve combining a new idea with existing known proof techniques. The more, and the more varied the proofs you already know are, the better your chance of being able to solve the given problem.

You are on the right track. You should simply keep studying proof techniques. The exercises you are doing are good. Don't worry if you get stuck. As you get more experienced and your "toolbox" of techniques grows, you will be able to solve exercises that are less "alike" the previous ones you have seen.

Answer 2

As other authors have mentioned, partly because proofs are inherently hard, but also partly because of the cold fact that proofs are not written for the purpose of teaching, even in most textbooks. Rather, most proofs are written out of a kind of obligation, as a sort of run-away argument; not presenting proofs at all is considered unacceptable, but writing them in exhausting details would burn the author out as well as endanger the reader getting lost in the woods. Hence, most proofs are succinct on purpose, leaving a lot of dots solely for the reader to connect themselves. While some people find this a helpful exercise, many readers like you and me find it making mathematics unnecessarily challenging. This is also why classroom pedagogy in a university setting is indispensable for professional mathematic learning as the tools of dialogue can fill in the blank of textbook proofs.

Answer 3

I can certainly recommend the book of G. Polya's, How to Solve It. It is a standard classic, not to be missed. There is a newer book How to Read and Do Proofs: An Introduction to Mathematical Thought Processes by Daniel Solow that may be more accessible.

In any event doing proofs is entirely Unnatural for humans. It is a discipline that requires careful thought we do not normally use. We are used to making many assumptions to get through our days and our lives. If we had to justify the first of them we could not get out of bed. A mathematical proof strips away the assumptions and lives on only what you can show clearly and unambiguously.

I had the similar trouble with problems over trigonometric identities. Trying to get from the start to the finish is easy when there is a known, learned method. Identities may require multiple steps in unknown directions without much sense of direction. Proofs are a bit easier since the logical methods are fairly limited and known (if you read the books). Keep at it.

Answer 4

I like Tom's answer: there's no magic bullet but you just need to continue doing exercises and gradually you will develop a better intuition and know how to attack a problem.

As for resources, you might like G. Polya's book How to Solve It. Looks like the Wikipedia article gives a nice and somewhat detailed overview. Basically, the book will offer you a strategy or methods for dealing with mathematical statements and their proofs.

Answer 5

Why are mathematical proofs so hard?... I have to learn data structures and algorithms,

My guess is you'll also want to learn about algorithms' space and time complexity, as quantified in big O notation. Time complexity, in particular, hints at why proofs are hard. If I promised you there is a proof of at most length $n$ of a given statement, how would you find it? In theory, you could go through all proofs of length $\le n$ until you find one, which would take exponential time, say $O(ne^{cn})$ (I've included a factor of $n$ for reading time). That's far too inefficient for our purposes, unless $n$ is very small. There might be a much better algorithm, but no-one's found a particularly efficient general one. That's why proving things remains a "creative" exercise, by which we mean "we don't know in pseudocode terms how such thinking works".

Is there any way (or any resources) that can improve my proving skills in a way that whenever I see an unusual question (like the checkers tiles and chess tiles type of questions) I don't have to stare at them for 2 hours before giving up?

You call such questions unusual, yet you know what examples to give. That's the crux of the issue right there. It's only "unusual" in your experience if you've not seen it (much). As other answers note, just keep learning more tools. Hopefully, you should then be able to tell which ones help with a problem. Judging by your choice of examples, the use of invariants in proofs is something you could work on. I don't know how good your big/small O notation is, but I'll mention that topic again because it's often useful to prove results, such as inequalities or anything dependent on them, e.g. limits (at least if you're meant to give an $\varepsilon$-$\delta$ proof).

Answer 6

Some proofs have to be cumbersome, others just are cumbersome even when they could be easier but the author didn't came up with a more elegant way to write it down. Coming up with a simple proof is even harder than understanding a proof and so are many proofs more complicated than they should be.

There is no general advice how to understand proofs (elegant or not). Some technique that you can try is to disprove the statement. Why does the proof work? What would happen when you leave out one of the preconditions for the proof?

Answer 7

If you're already pretty handy with programming, you might enjoy learning to use an interactive proof assistant like Coq or Lean. A proof assistant is a programming language with a very rich type system in which it's possible to express constructive logic. These kinds of languages largely operate on the notion that there's a direct analogy between programs and their types on the programming side, and between propositions and proofs on the math side. (This is called the Curry-Howard isomorphism.)

A really interesting project on these lines is the Natural Number Game. The game is part of a larger program by several professors at Imperial College of London to formalize all of undergraduate mathematics using the proof assistant Lean. At the start of the game, you're given just the Peano axioms of arithmetic: 0 is a natural number, the successor of a natural number is a natural number, and the successor of any natural number is not equal to itself. You're allowed to use the usual rules of predicate logic and induction. The object of the game is to come up with rigorous, formal proofs of the properties of addition, multiplication, and some basic number theory.

Proof assistants effectively gamify doing pure mathematics -- they remember the rules for you and they give you feedback practically in real time. If you're looking for a way to improve your skills at doing proofs through self-study, I think proof assistants are great tools. On top of that, they're also used in formal verification of computer programs, which is an interesting and employable specialization in its own right.

Answer 8

I've been struggling with the exercises for a very long time and it's really frustrating. I can easily deal with any type of proofs that I saw before (e.g. once I saw the proof of a recurrence question I became pretty good at proving them). My problems start when I face an unusual question. I feel like I am memorizing the proofs rather than learn how to prove.

So you do know how to read proofs, but you're finding these ones to be difficult. I think there are probably a few things that are relevant.

One is that differences between ability required by different mathematical textbooks is exponential, not linear. I have seen books titled "Introduction to X" that are much harder than books titled "Advanced Y". Authors have in mind different audiences, and the levels of difficulty are correspondingly different.

Second, it might just be that once you get more familiar with concepts and proofs in a particular area, they will become easier. As some of the other answers indicate, proofs often leave out steps that the author thinks would be obvious for their intended audience. None of us would expect a proof to point out that two plus two equals four. Some things that one reader finds completely mysterious are like $2+2=4$ for other readers. That doesn't mean that the book or article isn't for you, though. If you can work through the missing steps, you will get a deeper understanding of the subject, and after you do that a few times, what was difficult will become easier. (A proof in a book that's a little bit too hard is like an exercise.)

Third, I understand if you don't want to stare at a proof for two hours, but I think that during that period, you may be learning a lot. What you are doing during that time is thinking through different interpretations of the concepts and steps and possible ways to get from one step to another, and thinking about what assumptions the author had in mind. That is a learning process, and I think that doing that helps one understand other things more easily, later.

I do a lot of self-study in subjects that are unfamiliar to me. Sometimes I use two or three books for one subject, because what's left out in one book will be explained more clearly in the other. Sometimes I find that I have to go and read books on other subjects, because the author assumed that their readers would all have a certain background--and I don't have it. That doesn't necessarily mean I read the entire book on the other subject. Sometimes I just read enough so that I can understand the book I really want to understand. This is not a bad practice. I end up learning things that I wasn't interested in learning, but that turn out to be useful later.

(Maybe all of this seems obvious, but hopefully some comment here is helpful to someone.)

Answer 9

I am an electrical engineer as well as a mathematician by training. After completing my undergraduate in EE, I switched to maths and finally obtained a hard-earned doctorate in it. I won't say that I am a particularly bright kid. However I have always found mathematics easy and consequently boring. However, thanks to my dad, even at a very early age (about eight or nine) I knew that there is far more to maths than my school. So I endured it.

I also derived my self-esteem from being good at maths (yes, wrecks like me do exist). I probably still do.

Since I progressively did less and less maths, by the time I completed my high school, I was somewhat scared of it. My situation would be very much that same as yours in my first or second year of undergraduate, which was very bad for my self esteem. Then I begun my reeducation in maths - largely by self-study and also by way of audit courses, which I attended at the expense of my regular EE curriculum. EE, anyway, was a cake-walk for me. But mathematics proved a very hard nut to crack.

I continued my mathematics studies after college, enrolled into maths program and after a long, hard and frustrating struggle did complete my doctorate.

I don't know which area of maths you are looking at. But I will not suggest any online resources or guest lectures to get entry into maths. Such things only give you an illusion of understanding. You will have to pick up a book. You will have to pick up a pen. And you will have to start writing. And you too will learn the hard way, only the hard way. If you have someone to discuss things with, great! Else toil in obscurity.

To begin with, talk to someone to get the first couple of books suitable for you. Rest you can figure out yourself.

Answer 10

I can't believe no one else is mentioning this but you are probably overdoing it if you want to learn applied machine learning. You'd be better off brushing up on linear algebra, and basic computer science. There are some great specializations on coursera - specifically the Machine Learning and Mathematics for Machine Learning tracks (it says there is a cost but you can audit each of the courses individually for free - there are about 8 of them total between the two specializations); Andrew Ng's Deep Learning specialization (5 courses) is also fantastic. Then sign up for Kaggle and apply what you're learning. I understand personally wanting to know how to derive mathematical proofs with rigor but no one is paying you to do that in production. You're better off actually studying machine learning.

Answer 11

It sounds like your issue is that you lack experience with logical reasoning in general. The fact that you can prove similar theorems easily by adapting a proof that you have seen before, shows that you do not have a problem with understanding proofs. But I suspect you have never learnt first-order logic proper, which is a necessary ingredient in real mathematical reasoning. Once you learn a deductive system for FOL (for which I recommend Fitch-style), it actually becomes easy to deal with arbitrary areas of mathematics even if they are completely new. However, there is an upfront cost, which is roughly half the effort you need to put in to learn a new programming language. So I leave you to decide whether to try or not.

Independent of learning FOL, you also need a source for practice, and for that I recommend How to Prove It by Daniel Velleman. It does teach you a bit of logical reasoning, and it gives you plenty of neat and interesting things to prove.

Answer 12

Theoretically Proof Search is a rather high-complexity computational task.

For the case of Boolean propositions, it is coNP-complete, and therefore conjectured to not have algorithms that are faster than exponential in the size of the formula you want to prove.

For proof in Peano Arithmetic (and many stronger systems like standard set theory ZFC), it is undecidable. So there is no "algorithm" that one can learn and follow to find proofs.

Godel, in his famous letter to von Neumann, speculates about the possibility of an efficient algorithm that can be used to find proofs. Turns out he was kind of touching on the subject of P vs. NP.