3 ms·

They're generally published in symbols, which largely have a direct translation in to more formal methods, with the English being included to comment on the mot

They're generally published in symbols, which largely have a direct translation in to more formal methods, with the English being included to comment on the motivations, things which might not be formalized in the theory, etc. The primary purpose of mathematics papers is for distributing information between mathematicians in a form which it's easy for them to integrate in to reasoning about new theorems. To reason about new theorems, you really want as many ideas/concepts to be able to be present in the mathematician's head free of context (ie, with the structure represented, but ignoring the traditional intuition about what it is or used for, which English naming can bias towards). Part of the problem of Coq is that you'd have to formalize a lot of the metatheory in to something computable, and we've been struggling to find a good approach to that since the 40s/50s. We have a lot of trouble with trying to formalize the axioms in a way that you can compute results from them. (Axiom of choice + axiom of excluded middle can cause problems in Coq, for instance.) A secondary concern is that the translations from full sequences of axiomatic steps to constructs which are higher level (ie, built on the idea that some axiomatic steps must exist in this instance, but we haven't found them explicitly) can be really complicated, as well as much bulkier. A math paper is usually no more than tens of pages, while a computer proof of a theorem can run in to the thousands.

makmanalp 13y ago
Your reply is fascinating - the part about size difference and the difficulty in expressing certain things in theorem provers. About the size difference, I don't understand why it takes so much longer. What is so fundamentally different about Coq (or E or whatever) that it takes so much more space that just specifying it with mathematical notation? Is it because you have to start from scratch? Has no one created a "standard library of existing theorems / proofs" that one can depend on? Or is it because mathematical notation is just that much more expressive? So if verifying proofs is that difficult, what the heck are mathematicians doing when they read a paper? Not really actually verifying the proof? It's hard to believe that verification is one of those things that humans are just better at. (As opposed to, say, formulating new ideas, which is fundamentally difficult for computers) What is it that is so fundamentally difficult about verifying proofs formally, when a mathematician can just read a paper and call it done? If provable theorems are too hard, why don't we simply just start with a parseable mathematical notation standard? It's be pretty similar conceptually, but would be standardized. Surely that's not too difficult? That could still serve as the portion of the paper that is the "transmitting new findings formally" part, whereas the remaining part can be devoted to explanation.
- DerpDerpDerp 13y ago
  You seem to imply that mathematical notation should be standardized, but are omitting that even languages explicitly meant for computation are not. Why do you think mathematics should be more standardized than programming? (Actually, I'd argue it's already more standardized than programming, and you're arguing for some kind of extreme position.) Sorry, forgot to reply to part I had meant to: > Is it because you have to start from scratch? Has no one created a "standard library of existing theorems / proofs" that one can depend on? It's because we have essentially picked the parts of mathematics we're going to force to be true about half way up the stack. If the axioms don't permit those theories, then we'll do away with the axioms and pick a different set. (And perhaps explore why they failed to, and what is required in axioms to enable those theorems.) As I mentioned before, mathematics already has a good way to relate high level theorems and such to these mid-level structures, and you see it employed all the time. The problem is that many of these structures aren't easy to compute with, so we're essentially having to work backwards to find a set of formalities that we can both do mechanistically and support the theorems/propositions we'd like to be true. Mathematicians generally don't evaluate the truth of a new paper relative to the axioms, but relative to the already established results in a field. So you question about why libraries don't exist is essentially "Why have mathematicians not replicated hundreds or thousands of years of effort in to a format that's hard for them to personally use, but is good for these tools we've developed in the past couple decades?" Well, people are working on it, but it's going to take some time. And the moment you pick a slightly different set of axioms, you need to rebuild large portions of the library you allude to, even if the results are still true. (Derivations in terms of base steps are considerably longer than most mathematics proofs would be, which often omit some "standard" kinds of details. For an idea of what this is like, read portions of Principia Mathematica by Russell and Whitehead.)
  - makmanalp 13y ago
    Hey - thanks for actually replying and taking me seriously. This is as far as this discussion has ever gotten between me and someone who seems to know what they are doing. I'm actually learning a lot. > It's because we have essentially picked the parts of mathematics we're going to force to be true about half way up the stack. If the axioms don't permit those theories, then we'll do away with the axioms and pick a different set. Is this related to the famous incompleteness theory? If you hit a proof that you can't prove with this set of axioms, you just try another one? It blows my mind that you can just pick any set of axioms you like. It feels like there should be a set of core axioms that is the fundamental truth. Maybe it's time that I read G.E.B and the Principia. Any recommendations for these kinds of questions? > So you question about why libraries don't exist is essentially "Why have mathematicians not replicated hundreds or thousands of years of effort in to a format that's hard for them to personally use, but is good for these tools we've developed in the past couple decades?" Okay, so people are working on it. It seems like a miracle that the alternative of "we're doing it all in our heads" actually works: > Mathematicians generally don't evaluate the truth of a new paper relative to the axioms, but relative to the already established results in a field. This is what I'm taking about. What if - somewhere in the middle - there was a mistake? ... > Why do you think mathematics should be more standardized than programming? (Actually, I'd argue it's already more standardized than programming, and you're arguing for some kind of extreme position.) My main concern is - every year we get someone who thought they proved, for example, P != NP, only to find a few months and a billion man hours later that there is a minute error on page thirty-five where the author misunderstood and overlooked some very subtle thing. Wouldn't it me much more pleasant if this task was automated? Wouldn't it be amazing if we could use machine learning methods or tree search methods to formulate a proof mechanically? Or automatically eliminate proof steps to make them less complicated! Compiler-style optimization if you will. Wouldn't it be amazing if thousands of existing proofs could be analyzed statistically? Wouldn't it be great if we could machine-translate standardized proofs into regular ol' mathematical notation or whatever language we want? When we have the ability in the future, we can go back and verify them all en masse! Am I deluded in thinking any of this could be valuable? > You seem to imply that mathematical notation should be standardized, but are omitting that even languages explicitly meant for computation are not. Well, at least programming languages without standards have an implementation that is the official implementation! So arguably, they are more standardized. Anyway, thanks for replying, I haven't had such an interesting exchange on HN in a while. I'm eagerly awaiting your response (if you have the time)! edit: Also it seems like learning a standardized mathematical notation would be only marginally harder that learning to typeset regular mathematical notation in latex! Heck, you could have it compile down to latex. edit2: Another thought I had was, since mathematicians don't prove things all the way from the bottom axioms up, but from the closest accepted truth, couldn't we have verification systems do that instead? That seems a more easily reachable goal.
jk4930 13y ago
"a computer proof of a theorem can run in to the thousands." For those interested in a small example, look at http://us.metamath.org/mpegif/mmset.html#trivia http://us.metamath.org/mpegif/mmset.html#trivia

makmanalp 13y ago

Your reply is fascinating - the part about size difference and the difficulty in expressing certain things in theorem provers. About the size difference, I don't understand why it takes so much longer. What is so fundamentally different about Coq (or E or whatever) that it takes so much more space that just specifying it with mathematical notation? Is it because you have to start from scratch? Has no one created a "standard library of existing theorems / proofs" that one can depend on? Or is it because mathematical notation is just that much more expressive? So if verifying proofs is that difficult, what the heck are mathematicians doing when they read a paper? Not really actually verifying the proof? It's hard to believe that verification is one of those things that humans are just better at. (As opposed to, say, formulating new ideas, which is fundamentally difficult for computers) What is it that is so fundamentally difficult about verifying proofs formally, when a mathematician can just read a paper and call it done? If provable theorems are too hard, why don't we simply just start with a parseable mathematical notation standard? It's be pretty similar conceptually, but would be standardized. Surely that's not too difficult? That could still serve as the portion of the paper that is the "transmitting new findings formally" part, whereas the remaining part can be devoted to explanation.

DerpDerpDerp 13y ago
You seem to imply that mathematical notation should be standardized, but are omitting that even languages explicitly meant for computation are not. Why do you think mathematics should be more standardized than programming? (Actually, I'd argue it's already more standardized than programming, and you're arguing for some kind of extreme position.) Sorry, forgot to reply to part I had meant to: > Is it because you have to start from scratch? Has no one created a "standard library of existing theorems / proofs" that one can depend on? It's because we have essentially picked the parts of mathematics we're going to force to be true about half way up the stack. If the axioms don't permit those theories, then we'll do away with the axioms and pick a different set. (And perhaps explore why they failed to, and what is required in axioms to enable those theorems.) As I mentioned before, mathematics already has a good way to relate high level theorems and such to these mid-level structures, and you see it employed all the time. The problem is that many of these structures aren't easy to compute with, so we're essentially having to work backwards to find a set of formalities that we can both do mechanistically and support the theorems/propositions we'd like to be true. Mathematicians generally don't evaluate the truth of a new paper relative to the axioms, but relative to the already established results in a field. So you question about why libraries don't exist is essentially "Why have mathematicians not replicated hundreds or thousands of years of effort in to a format that's hard for them to personally use, but is good for these tools we've developed in the past couple decades?" Well, people are working on it, but it's going to take some time. And the moment you pick a slightly different set of axioms, you need to rebuild large portions of the library you allude to, even if the results are still true. (Derivations in terms of base steps are considerably longer than most mathematics proofs would be, which often omit some "standard" kinds of details. For an idea of what this is like, read portions of Principia Mathematica by Russell and Whitehead.)
- makmanalp 13y ago
  Hey - thanks for actually replying and taking me seriously. This is as far as this discussion has ever gotten between me and someone who seems to know what they are doing. I'm actually learning a lot. > It's because we have essentially picked the parts of mathematics we're going to force to be true about half way up the stack. If the axioms don't permit those theories, then we'll do away with the axioms and pick a different set. Is this related to the famous incompleteness theory? If you hit a proof that you can't prove with this set of axioms, you just try another one? It blows my mind that you can just pick any set of axioms you like. It feels like there should be a set of core axioms that is the fundamental truth. Maybe it's time that I read G.E.B and the Principia. Any recommendations for these kinds of questions? > So you question about why libraries don't exist is essentially "Why have mathematicians not replicated hundreds or thousands of years of effort in to a format that's hard for them to personally use, but is good for these tools we've developed in the past couple decades?" Okay, so people are working on it. It seems like a miracle that the alternative of "we're doing it all in our heads" actually works: > Mathematicians generally don't evaluate the truth of a new paper relative to the axioms, but relative to the already established results in a field. This is what I'm taking about. What if - somewhere in the middle - there was a mistake? ... > Why do you think mathematics should be more standardized than programming? (Actually, I'd argue it's already more standardized than programming, and you're arguing for some kind of extreme position.) My main concern is - every year we get someone who thought they proved, for example, P != NP, only to find a few months and a billion man hours later that there is a minute error on page thirty-five where the author misunderstood and overlooked some very subtle thing. Wouldn't it me much more pleasant if this task was automated? Wouldn't it be amazing if we could use machine learning methods or tree search methods to formulate a proof mechanically? Or automatically eliminate proof steps to make them less complicated! Compiler-style optimization if you will. Wouldn't it be amazing if thousands of existing proofs could be analyzed statistically? Wouldn't it be great if we could machine-translate standardized proofs into regular ol' mathematical notation or whatever language we want? When we have the ability in the future, we can go back and verify them all en masse! Am I deluded in thinking any of this could be valuable? > You seem to imply that mathematical notation should be standardized, but are omitting that even languages explicitly meant for computation are not. Well, at least programming languages without standards have an implementation that is the official implementation! So arguably, they are more standardized. Anyway, thanks for replying, I haven't had such an interesting exchange on HN in a while. I'm eagerly awaiting your response (if you have the time)! edit: Also it seems like learning a standardized mathematical notation would be only marginally harder that learning to typeset regular mathematical notation in latex! Heck, you could have it compile down to latex. edit2: Another thought I had was, since mathematicians don't prove things all the way from the bottom axioms up, but from the closest accepted truth, couldn't we have verification systems do that instead? That seems a more easily reachable goal.

jk4930 13y ago

"a computer proof of a theorem can run in to the thousands." For those interested in a small example, look at http://us.metamath.org/mpegif/mmset.html#trivia http://us.metamath.org/mpegif/mmset.html#trivia