When I was first introduced to mathematical proofs, I was perplexed by how fuzzy and intuition-based the notion of proof was. A "convincing argument", really?! There is no knowing, as a novice, how detailed those "arguments" have to be, what parts you can simply assert without further justification. Usually the teachers themselves can't explain what the criteria for an "obvious" and "not obvious" step is, they just know it intuitively from experience. Writing proofs, then, is a lot like having to learn to ride a bike: Instructions are mostly unavailable or useless.
I later learned that there is indeed a precise way of learning proofs which doesn't rely on intuitions of what counts as a rigours inference step: Formal logic together with a natural deduction proof system. Natural deduction is a formal proof system which resembles actual ("natural") proofs in mathematics, unlike other proof systems.
In such a proof system, inference rules, like modus tollens or universal instantiation, are strictly defined. Only the given inference rules (and those which are provable from the given rules) may be used. Coming up with such proofs still requires creativity, there is no algorithm. But there is no ambiguity in what counts as a valid or invalid proof or inference step.
Of course, this is far too tedious for actual mathematical proofs, since every little step needs to be done explicitly, e.g. even applications of modus ponens (rule: "A, if A then B, therefore B"). Moreover, mathematicians rarely prove anything from axioms, they start from other statements which are considered more trivial. But I think it would be helpful for many people to first learn logic and deduction "the precise way", and then do actual mathematical proof where you can jump over more obvious parts.
But that's not how it is teached in mathematics or computer science. Students are thrown into the cold water, and only receive tips&tricks, but no rigorous introduction. Ironically, the one subject which often teaches formal logic as an early introductory class for undergraduates isn't mathematics, computer science, or physics, it's philosophy.
Whenever I have asked professors in the past how they first learned proofs the answer was always from doing Euclid in highschool which is no longer taught
Trees may be more elegant, but actual, informal proofs in mathematics are written sequentially. So I think trees defeat the purpose of "natural" deduction a bit. But that's complaining on a high level.)
I studied CS and electric engineering for 6-7 years total, and both degrees included some pretty math-intense courses, proofs and all. I remember how I really, really wanted an explanation of the underlying proof system but all I got was just more intuitive explanations, all of which felt out of place.
What is unusual is that I kept looking. "How to Prove It" was something I really wish I read ahead of calculus. It is only after this book it clicked for me, all of it. Having understood the rules of the game it became possible to play with math..! Which I still do from time to time.
I think that this material should be taught at high school. Bits of it even earlier.
Philosophy was the only field where I learned formal logic at all. I went into higher math, did some CS, and also got a law degree[1], and am now doing a Ph.D. in informatics, and still the only place I have really been exposed to formal logic was my undergrad degree in philosophy.
[1] It is amazing (or not, depending on your view of lawyers) that lawyers are basically not taught anything about making and proving formal arguments, at least in my experience.
> But I think it would be helpful for many people to first learn logic and deduction "the precise way", and then do actual mathematical proof where you can jump over more obvious parts.
Absolutely. And I can not imagine a mathematics degree which doesn't place formal logic front and center in the first semester.
When you are starting out you absolutely need to suffer through the rigourous formal arguments.
>Ironically, the one subject which often teaches formal logic as an early introductory class for undergraduates isn't mathematics, computer science, or physics, it's philosophy.
I can not believe that this is the case. Even engineering undergrads have to learn formal logic in their first semester.
> Even engineering undergrads have to learn formal logic in their first semester.
I got my engineering B.S. from a top 5 college in the US, and have known many people who have gone to similar schools. None of us have had to take a class that goes into first order logic or proof writing. I don't know what college you go to where that is a thing, but it would be exceedingly rare.
The lecture notes for some introductory logic class of an analytic philosophy department may be quite good, but unfortunately I can't recommend something specific for English.
> Moreover, mathematicians rarely prove anything from axioms, they start from other statements which are considered more trivial.
Not more trivial but from the ones already proved and those closer to the thing you are proving. There is no need to go back to the axioms if you know, and can reference, proof of step N-1, just go from there.
There is also this 'misconception' that mathematical theorems follow from the axioms. They do, of course, but the axioms were choosen just right to make things that were working to still work, with some weird consequences like axiom of choice
There are are a lot of "folk theorems" in mathematics, and things which are simply considered obvious or common knowledge relative to a conjecture in question, without anyone being able to actually cite a proof for that. Mathematical proof is really just for convincing other mathematicians, there is no need to prove things which are considered obvious.
Our discrete mathematics professor leaned heavy on proofs, but also introduced pop quizzes for proofs of algorithms and other mathematical constructs as an experiment that term which sent my anxiety ablaze. You either had the intuition for that particular problem or you didn’t. Studying would not help you that much. The success rate on the quizzes was very low surprising no one.
Classes like this were funny. I often found that people who just knew the answer immediately had a lot of difficulty doing proofs, and the people good at doing proofs usually didn't arrive at the solution very quickly or seem to have an intuitive understanding of the problem at first.
As someone who tutored a Formal Reasoning class for a top philosophy department, I don't think we should be teaching anyone logic. It's rigid, its made up, and it doesn't help much for most things. I think the way proofs are written in math is cool, and I think the fact that mathematicians are, in the end, aware that it is impossible to rigidly demonstrate anything is perfectly fine and it makes their proofs a lot easier to read and interpret. Formal logic should never be treated as first order or ever used as such, it will only hamper mathematics. I understand the need for a rigorous language to describe mathematics, I understand why people like it so much, and why it has found so much use. It is still not the groundwork (because there is none).
Would you agree to at least list some of the common natural deduction inference rules in an introductory class, and do a few exercises with them? Like, for propositional logic, modus ponens, modus tollens, contraposition, transitivity of the conditional, conditional proof, proof by contradiction, de Morgan's laws, distributive laws, etc, and some inference rules for quantified predicate logic?
I agree that full formal logic could be too much irrelevant information, but I think many experienced people underestimate how non-obvious the basic inference rules are to novices, and how confused people are about just being told to produce "convincing arguments". The important part is that the argument has to be truth preserving, unlike a "convincing argument" or "proof" an attorney might give in court. It is very hard to understand this difference if one has only a hazy idea of logic and deduction vs induction.
Isn't (classical) geometry basically about proving properties from a few theorems? I.e., logic, proof, and deduction.
A lot of people are exposed to Geometry in High School. It might not be universal, but it's pretty close. IIRC, Eucid's Elements was the second most read book, after the Bible. Many cities even have a street named after the guy.
I know, it's not the same as a formal logic course. But it's not that far off, either. There is some preparation in earlier years of schooling.
I like your analogy with riding a bike: If you want to ride a bike, what is more important, learning how to ACTUALLY DO IT, or to learn the physical and mechanical rules underlying it? Furthermore, technical knowledge will always be incomplete (and that applies also to logic in a very technical sense), while once you learnt how to ride a bike, your knowledge, in a way, is complete.
A lot of things can be learned simply by practice, without any theory, but many things at least benefit from learning it in a more principled way. That's not feasible for riding bikes, since this relies on the the motor cortex, which doesn't understand and benefit from explicit knowledge about the physics of bike movement. Writing proofs is more intellectual, it benefits from principled understanding.
I literally gave everyone that handout and told them, "To make sense of it, you're all going to do the next proof. I'll just prompt you." They thought this was impossible. But I told them to trust me and I began.
I went around the room. I asked one person what the next step in the flowchart was. I asked the next person to do it. I just wrote down what they said. Kept going until they had produced a complete proof of a result that, at the beginning, they did not know why it might be true.
The best comment I got from that class later was, "Proofs are easy. It is kind of like filling out a shopping list."
This is fantastic. Perhaps similarly, I personally found it much easier to complete math problem sets after I began to write out an explicit list of steps of what to do.
For example, I broke down problems with to-dos, such as:
1. Find the definition for what math_term_X means in a particular problem.
2. (For breaking down part of the problem): Figure out how to show that a particular object is lesser than or equal to another project.
3. Write down headings for each case I need to prove.
...and so on.
Writing down explicit steps was far more practically helpful to me, than my previous conception of problem-solving from the quote about how Feynman solves problems (that is: "Write down the problem, think real hard, write down the solution"). Some people may not need to write down steps, but I was personally able to learn a lot more with a specific, more verbalized approach.
It's very neat and helpful to have a flowchart suited to any general problem, which I'll try out in addition to my current approach of writing down a list of to-dos for solving specific problems. Thanks a lot for sharing.
Nice and concise! I just started Proof and the Art of Mathematics by JD Hamkins[0], based on pg's recommendation[1], "is a beautiful book in both senses. It's both beautifully written, but also physically beautiful, thanks to its many illustrations, which I was surprised to hear were made by the author himself." Chapter 4 on induction improved my attitude.
I found Johannes Riebel's thesis [1] an excellent introduction to the formalization of Zermelo Fraenkel-Set theory, complete with detailed examples of formal proofs.
I did my undergraduate degree at Wits University in Johannesburg. My Real Analysis course was SO boring. The lecturer basically wrote on the board:
Lemma: ......
Proof: ....
etc.
Theorem: Let epsilon < K, ....
Proof: ....
--QED--
which we all dutifully copied into our notebooks. Very uninspiring.
But when I got to the University of Waterloo for graduate studies, I had a real competitive advantage over my peers for the theory courses I took: I knew what a proof was, and how to do one.
I think the problem a lot of people have (even math majors) is expecting the lecture to be the first introduction to the topic. It's like taking a literature class and going to lecture without doing the reading. Reading (or even just skimming) the next section/chapter of the book before the lecture allows you to focus and ask questions on the parts of the material you didn't understand during the lecture. I very rarely wrote down full proofs in my notes during the lecture. I focused on the lecture itself and wrote down the pieces that I wanted to remember.
There's also "proof by picture", in which you can hastily attempt to prove or disprove something by drawing a suitable diagram in your exam booklet. You have to be darn sure of what you're doing though... ;)
And another fun and powerful technique is "proof by intimidation" (https://en.wikipedia.org/wiki/Proof_by_intimidation), in which you don't have to know what you're doing, but other people have to think you do.
Right now this article is at no. 10 on the front page, while no. 11 is "Book of Proof (2018)".
This is the third time I notice such a coincidence on HN. Is this something that HN does on purpose? Like, does the site match posts with similar titles on the front page to encourage discussion in both? Note that (at the time of writing) this article has 91 points and the other one 45, so the two articles are not ordered by upvote count.
Also, I need a catchy name for this phenomenon (just 'cause I want to name the folder where I keep screenshots documenting it, like). Suggestions?
Over the years I’ve noticed it too, the time lag between similar posts ranging from a few hours to a day or so. My simple explanation is that a person reading the original post either remembers a related nugget of Internet that they think people would also find interesting or else they find it while googling, inspired by the initial post.
The Book of Proof post was made 2 hours after this one, you wouldn't have been aware of it. It happens a lot. See a topic, and people post related things because it jogs a memory, they found it while digging deeper, or as a form of indirect response.
It makes some sense to have a leveling-of-expectations course for freshmen that both inflates their GPA and says "Okay, whatever you were told in high school, we expect you to use this."
Readit News
I later learned that there is indeed a precise way of learning proofs which doesn't rely on intuitions of what counts as a rigours inference step: Formal logic together with a natural deduction proof system. Natural deduction is a formal proof system which resembles actual ("natural") proofs in mathematics, unlike other proof systems.
In such a proof system, inference rules, like modus tollens or universal instantiation, are strictly defined. Only the given inference rules (and those which are provable from the given rules) may be used. Coming up with such proofs still requires creativity, there is no algorithm. But there is no ambiguity in what counts as a valid or invalid proof or inference step.
Of course, this is far too tedious for actual mathematical proofs, since every little step needs to be done explicitly, e.g. even applications of modus ponens (rule: "A, if A then B, therefore B"). Moreover, mathematicians rarely prove anything from axioms, they start from other statements which are considered more trivial. But I think it would be helpful for many people to first learn logic and deduction "the precise way", and then do actual mathematical proof where you can jump over more obvious parts.
But that's not how it is teached in mathematics or computer science. Students are thrown into the cold water, and only receive tips&tricks, but no rigorous introduction. Ironically, the one subject which often teaches formal logic as an early introductory class for undergraduates isn't mathematics, computer science, or physics, it's philosophy.
Whenever I have asked professors in the past how they first learned proofs the answer was always from doing Euclid in highschool which is no longer taught
(A small downside is, in my opinion, that is uses trees instead of a more classical sequential presentation in the style of Suppes and Kleene.
https://en.wikipedia.org/wiki/Natural_deduction#Different_pr...
Trees may be more elegant, but actual, informal proofs in mathematics are written sequentially. So I think trees defeat the purpose of "natural" deduction a bit. But that's complaining on a high level.)
What is unusual is that I kept looking. "How to Prove It" was something I really wish I read ahead of calculus. It is only after this book it clicked for me, all of it. Having understood the rules of the game it became possible to play with math..! Which I still do from time to time.
I think that this material should be taught at high school. Bits of it even earlier.
[1] It is amazing (or not, depending on your view of lawyers) that lawyers are basically not taught anything about making and proving formal arguments, at least in my experience.
Absolutely. And I can not imagine a mathematics degree which doesn't place formal logic front and center in the first semester. When you are starting out you absolutely need to suffer through the rigourous formal arguments.
>Ironically, the one subject which often teaches formal logic as an early introductory class for undergraduates isn't mathematics, computer science, or physics, it's philosophy.
I can not believe that this is the case. Even engineering undergrads have to learn formal logic in their first semester.
I got my engineering B.S. from a top 5 college in the US, and have known many people who have gone to similar schools. None of us have had to take a class that goes into first order logic or proof writing. I don't know what college you go to where that is a thing, but it would be exceedingly rare.
Geometry class in high school sometimes teaches some of it.
Computer science Binary logic teaches some of (De Morgan's laws)
Outside of New Math of the 1970s, it is a glaring omission from the curriculum.
Even enriched classes like Art of Problem Solving that put heavy emphasis on proofs, do not teach formal logic.
This was precisely my issue when studying proofs in school. Do you have any suggestions for resources to get started down the right path?
Not more trivial but from the ones already proved and those closer to the thing you are proving. There is no need to go back to the axioms if you know, and can reference, proof of step N-1, just go from there.
There is also this 'misconception' that mathematical theorems follow from the axioms. They do, of course, but the axioms were choosen just right to make things that were working to still work, with some weird consequences like axiom of choice
Some people are just wired differently.
I agree that full formal logic could be too much irrelevant information, but I think many experienced people underestimate how non-obvious the basic inference rules are to novices, and how confused people are about just being told to produce "convincing arguments". The important part is that the argument has to be truth preserving, unlike a "convincing argument" or "proof" an attorney might give in court. It is very hard to understand this difference if one has only a hazy idea of logic and deduction vs induction.
A lot of people are exposed to Geometry in High School. It might not be universal, but it's pretty close. IIRC, Eucid's Elements was the second most read book, after the Bible. Many cities even have a street named after the guy.
I know, it's not the same as a formal logic course. But it's not that far off, either. There is some preparation in earlier years of schooling.
https://docs.google.com/document/d/1_uwl3WDZk_BxNOUL7W0FiPMM...
I literally gave everyone that handout and told them, "To make sense of it, you're all going to do the next proof. I'll just prompt you." They thought this was impossible. But I told them to trust me and I began.
I went around the room. I asked one person what the next step in the flowchart was. I asked the next person to do it. I just wrote down what they said. Kept going until they had produced a complete proof of a result that, at the beginning, they did not know why it might be true.
The best comment I got from that class later was, "Proofs are easy. It is kind of like filling out a shopping list."
For example, I broke down problems with to-dos, such as:
1. Find the definition for what math_term_X means in a particular problem.
2. (For breaking down part of the problem): Figure out how to show that a particular object is lesser than or equal to another project.
3. Write down headings for each case I need to prove.
...and so on.
Writing down explicit steps was far more practically helpful to me, than my previous conception of problem-solving from the quote about how Feynman solves problems (that is: "Write down the problem, think real hard, write down the solution"). Some people may not need to write down steps, but I was personally able to learn a lot more with a specific, more verbalized approach.
It's very neat and helpful to have a flowchart suited to any general problem, which I'll try out in addition to my current approach of writing down a list of to-dos for solving specific problems. Thanks a lot for sharing.
Are you beginning to doubt whether it's true?
Try to think of a counterexample.
Is there something that keeps getting in the way of a counterexample working? Can you prove that that always happens?
:-)
[0]https://www.amazon.com/Proof-Art-Mathematics-Examples-Extens... [1] https://twitter.com/paulg/status/1662065331727155202
[1] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
Lemma: ......
Proof: ....
etc.
Theorem: Let epsilon < K, ....
Proof: ....
--QED--
which we all dutifully copied into our notebooks. Very uninspiring.
But when I got to the University of Waterloo for graduate studies, I had a real competitive advantage over my peers for the theory courses I took: I knew what a proof was, and how to do one.
I had 5 years of that, a very enjoyable time.
This is the third time I notice such a coincidence on HN. Is this something that HN does on purpose? Like, does the site match posts with similar titles on the front page to encourage discussion in both? Note that (at the time of writing) this article has 91 points and the other one 45, so the two articles are not ordered by upvote count.
Also, I need a catchy name for this phenomenon (just 'cause I want to name the folder where I keep screenshots documenting it, like). Suggestions?
No, the HN algorithm is extremely simple and does not consider syntactic similarities of the titles.
Dead Comment