10 ms·

Basics of Proofs (2017) [pdf]

145 points by waldarbeiter 3y ago

tromp 3y ago
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. [1] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
tigerlily 3y ago
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... ;)
- constantcrying 3y ago
  Ironically when rigorous proofs were invented by the greeks, Euclids "proof by picture" was no less rigorous than modern formal logic.
- tmhn2 3y ago
  And another fun and powerful technique is "proof by intimidation" (https://en.wikipedia.org/wiki/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.
cubefox 3y ago
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.
- hiatus 3y ago
  > When I was first introduced to mathematical proofs, I was perplexed by how fuzzy and intuition-based the notion of proof was. This was precisely my issue when studying proofs in school. Do you have any suggestions for resources to get started down the right path?
  - cubefox 3y ago
    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.
    - yep31 3y ago
      >some introductory logic class like forall x from openlogicproject?
      - cubefox 3y ago
        Yes! It looks like a great introduction. Perhaps even better than the Lean course mentioned above. Here is the link: https://forallx.openlogicproject.org/ https://forallx.openlogicproject.org/
  - vkazanov 3y ago
    "How to prove it" is the best book you can find
    - layer8 3y ago
      How do you prove that?
      - vkazanov 3y ago
        With an intuitive explanation!
herodotus 3y ago
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.
- constantcrying 3y ago
  >which we all dutifully copied into our notebooks. Very uninspiring. I had 5 years of that, a very enjoyable time.
- WoahNoun 3y ago
  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.
Solvency 3y ago
It's intriguing to me that someone who made it to Stanford might only just be getting exposed to the basics of proofs like this?
- cubefox 3y ago
  Affirmative action and many related criteria mean that students aren't just admitted by considerations of ability.
- mbg721 3y ago
  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."
- sukilot 3y ago
  [dead]
btilly 3y ago
I still prefer the explanation that I prepared when I was teaching at Dartmouth College. https://docs.google.com/document/d/1_uwl3WDZk_BxNOUL7W0FiPMMxdmi7w4OoP4prUcIs2s/edit?usp=sharing 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."
- nohaydeprobleme 3y ago
  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.
- mjw1007 3y ago
  Maybe it's worth one more section near "Any Ideas On Why It Is True?", something like: 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?
getpost 3y ago
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. [0]https://www.amazon.com/Proof-Art-Mathematics-Examples-Extensions/dp/026254220X/ https://www.amazon.com/Proof-Art-Mathematics-Examples-Extens... [1] https://twitter.com/paulg/status/1662065331727155202 https://twitter.com/paulg/status/1662065331727155202
YeGoblynQueenne 3y ago
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?
- constantcrying 3y ago
  >Is this something that HN does on purpose? No, the HN algorithm is extremely simple and does not consider syntactic similarities of the titles.
  - Solvency 3y ago
    I've noticed similar themed posts appearing in clusters constantly on HN. It's way too commonplace to be coincidental.
    - constantcrying 3y ago
      No it is coincidental. Look at the algorithm yourself.
      - Solvency 3y ago
        It doesn't mean it's the algorithm, it means users could be tactically posting to ride a wave of similar interest. That's all.
        constantcrying 3y ago
        Yes, you are right. Potentially the effect is partly due to that after seeing the first post a user stumbles over something related and decides to post that as well.
a1o 3y ago
For some reason I thought it would be about Coq or other similar structured proof assistant language.

145 points by waldarbeiter 3y ago

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. [1] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...

tigerlily 3y ago

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... ;)

constantcrying 3y ago
Ironically when rigorous proofs were invented by the greeks, Euclids "proof by picture" was no less rigorous than modern formal logic.
tmhn2 3y ago
And another fun and powerful technique is "proof by intimidation" (https://en.wikipedia.org/wiki/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.

cubefox 3y ago

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.

hiatus 3y ago
> When I was first introduced to mathematical proofs, I was perplexed by how fuzzy and intuition-based the notion of proof was. This was precisely my issue when studying proofs in school. Do you have any suggestions for resources to get started down the right path?
- cubefox 3y ago
  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.
  - yep31 3y ago
    >some introductory logic class like forall x from openlogicproject?
    - cubefox 3y ago
      Yes! It looks like a great introduction. Perhaps even better than the Lean course mentioned above. Here is the link: https://forallx.openlogicproject.org/ https://forallx.openlogicproject.org/
- vkazanov 3y ago
  "How to prove it" is the best book you can find
  - layer8 3y ago
    How do you prove that?
    - vkazanov 3y ago
      With an intuitive explanation!

herodotus 3y ago

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.

constantcrying 3y ago
>which we all dutifully copied into our notebooks. Very uninspiring. I had 5 years of that, a very enjoyable time.
WoahNoun 3y ago
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.

Solvency 3y ago

It's intriguing to me that someone who made it to Stanford might only just be getting exposed to the basics of proofs like this?

cubefox 3y ago
Affirmative action and many related criteria mean that students aren't just admitted by considerations of ability.
mbg721 3y ago
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."
sukilot 3y ago
[dead]

btilly 3y ago

I still prefer the explanation that I prepared when I was teaching at Dartmouth College. https://docs.google.com/document/d/1_uwl3WDZk_BxNOUL7W0FiPMMxdmi7w4OoP4prUcIs2s/edit?usp=sharing 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."

nohaydeprobleme 3y ago
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.
mjw1007 3y ago
Maybe it's worth one more section near "Any Ideas On Why It Is True?", something like: 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?

getpost 3y ago

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. [0]https://www.amazon.com/Proof-Art-Mathematics-Examples-Extensions/dp/026254220X/ https://www.amazon.com/Proof-Art-Mathematics-Examples-Extens... [1] https://twitter.com/paulg/status/1662065331727155202 https://twitter.com/paulg/status/1662065331727155202

YeGoblynQueenne 3y ago

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?

constantcrying 3y ago
>Is this something that HN does on purpose? No, the HN algorithm is extremely simple and does not consider syntactic similarities of the titles.
- Solvency 3y ago
  I've noticed similar themed posts appearing in clusters constantly on HN. It's way too commonplace to be coincidental.
  - constantcrying 3y ago
    No it is coincidental. Look at the algorithm yourself.
    - Solvency 3y ago
      It doesn't mean it's the algorithm, it means users could be tactically posting to ride a wave of similar interest. That's all.
      - constantcrying 3y ago
        Yes, you are right. Potentially the effect is partly due to that after seeing the first post a user stumbles over something related and decides to post that as well.

a1o 3y ago

For some reason I thought it would be about Coq or other similar structured proof assistant language.