Live data from Hacker News

Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

nature.com

121–130 of 140 posts

Re: Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

#121

Earlier quoted context omitted.

If not an asterisk, they’ll just have less impact. A proof generates a fact. The best facts and proofs are useful in that they help other things. You work becomes useful for my work, which may become useful for others.

It's still just as useful. The fact that's proven is what helps other proofs. A computer assisted proof is just as correct or helpful, it just may be more complicated of a proof initially. Given time said proof can be simplified but having the proof in the first place allows you to move away from assumptions into proofs or alternatively even open new doors that weren't known to exist. Keep in mind that these computer…

The best proofs are good explanations as well as just being correct. If you don’t understand the theorem and the proof as well, you’re less likely to use it.

Re: Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

#122
post #104

Earlier quoted context omitted.

Automated proofs aren't remotely comparable to Mochizuki's abc stuff. Automated proofs just handle a lot of complicated case by case checking that humans could in principle do, it's just too much work, like counting to a trillion. Automated proof systems are incapable of the brilliant but unreliable intuitive leaps that mathematicians can make. Mochizuki's stuff is simply a hypercomplicated pile of nonsense unintelli…

> Automated proof systems are incapable of the brilliant but unreliable intuitive leaps that mathematicians can make. I would add current automated proof systems. IMHO we are just at the beginning that mathematicians realize the usefulness of technology, which was basically neglected ever since.

It will be very interesting to see what happens! A common theme in mathematics is that the proofs are the (relatively) easy part, while knowing what to prove is hard. Still, I'm sure mathematicians will welcome greater automation of the "easy" part. If machines ever do more than drudge work, there will also be the challenge of making the machine-generated proofs intelligible to humans, similar to the interpretability issues around machine learning models today.

Re: Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

#123
post #49

Earlier quoted context omitted.

It's worth noting that GPT-f already gets a big performance boost from pretraining on Arxiv etc ( https://arxiv.org/pdf/2009.03393.pdf#page=7 ) despite those sources containing next to no Metamath or anything that looks like a raw Metamath proof, just regular natural language & LaTeX discussing math...

How well does text extraction from a PDF work? I almost never try it but thought there were random spaces in the output and such things.

It's worth noting that for most papers, arXiv provides the LaTeX source for download, which is presumably what they trained on.

Re: Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

#124
post #63

Earlier quoted context omitted.

This is missing the point. Modern mathematics textbooks, especially undergratuate ones, are written with set theoretic foundations. It requires a lot of effort to reformulate all of mathematics into equivalent formulations. That makes it harder to get buy-in from many working mathematicians, and it also makes the subject less approachable for, say, undergraduates.

Not quite. You're conflating two things: using set theory to talk about sets (what undergraduate math textbooks do) and using set theory to talk about everything (what ZFC foundations does).

In 99% of algebra textbooks you'll see a definition like "if G is a group and H is a subset of G, then we call H a subgroup if it is a group under the same operation." Then, the next thing you see is probably the theorem that "H is a subgroup of G if and only if it is a subset of G and gh^{-1} € H for all g, h € H". That's clearly using the language of set theory to talk about groups.

I mean, my argument is not that type theory or anything is unsuitable for doing maths. It's that it is different from how most people do maths. In my particular case, I am such an undergraduate who has actually tried to do some group theory in Coq and found it annoying to pull it off—not in the least because I figured out there were multiple equivalent ways of e.g. defining what is a group and/or subgroup and I had no idea which one was more natural or useful; you can work with injective homomorphisms, as someone else suggested, but you can also work with predicates so that you define a subgroup as all elements of some type that satisfy that predicate. Moreover, the fact that Coq includes several different types of "truth" (basically, Bool vs. Prop), which is undoubtedly well-reasoned, requires some adjustment, too.

Again, I'm not saying that this is a failure of tools such as Coq (although, they should really make documentation more discoverable and understandable). My sole argument was that you can't currently take any mathematician not particularly interested in logic or proof theory, especially not an undergraduate student, and expect them to encode simple proofs that they understand in Coq without a lot of assistance. If these tools are to be the future of (some part of) mathematics, they will have to become more accessible one way or another.

Ironically (?), I found that it was much easier to use Coq to prove e.g. algorithms correct (especially if you've done functional programming before) because programming languages actually do use types (even if some of them only do so at runtime).

Re: Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

#125

Earlier quoted context omitted.

I am quite confident that the developers of lean consider it a feature (or at least, not a bug). Though I'm also not sure why they are building on a complex metatheory like CiC if they are willing to accept undecidable typechecking since you can simplify a lot of things if you give that up.

What simplifications do you have in mind? I think one of the reasons is that Lean's approximation of defeq still works well enough in practice. As mentioned by others, you never really run into the kind of counter examples that break theoretical properties, but instead into examples where checking defeq is inacceptably slow, which remains an issue even when defeq is decidable. From my understanding CiC is used becaus…

For example, if you are willing to accept undecidable typechecking, you can define inductive types in a much simpler theory (inductive types and dependent pattern matching are by far the most complex parts of CiC): https://homepage.cs.uiowa.edu/~astump/papers/from-realizabil... .

There are a few other examples but this is the one that immediately sprung to mind. The complexity of CiC is very much about decidable typechecking, it's not fundamental to writing a sound dependently typed proof assistant. And anyone who has actually worked on a kernel for CiC knows that while it is "minimal" compared to what people want to do with it, no efficient kernel is nearly as minimal as something like λP2 with dependent intersections.

Re: Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

#126

Earlier quoted context omitted.

Not quite. You're conflating two things: using set theory to talk about sets (what undergraduate math textbooks do) and using set theory to talk about everything (what ZFC foundations does).

In 99% of algebra textbooks you'll see a definition like "if G is a group and H is a subset of G, then we call H a subgroup if it is a group under the same operation." Then, the next thing you see is probably the theorem that "H is a subgroup of G if and only if it is a subset of G and gh^{-1} € H for all g, h € H". That's clearly using the language of set theory to talk about groups . I mean, my argument is not that…

> That's clearly using the language of set theory to talk about groups.

If you like the language of set theory, what's wrong with replacing "A ⊆ X" with "A : SubsetOf X" where SubsetOf X = X → Prop? This is what Lean does: https://leanprover-community.github.io/mathlib_docs/group_th...

> there were multiple equivalent ways of e.g. defining what is a group and/or subgroup

Don't you have that problem in any foundation?

> Moreover, the fact that Coq includes several different types of "truth"

You probably know this already, but you can collapse Prop to Bool by adding some classical axioms.

> My sole argument was that you can't currently take any mathematician not particularly interested in logic or proof theory, especially not an undergraduate student, and expect them to encode simple proofs that they understand in Coq without a lot of assistance.

True, but I don't think that's a goal of the Coq developers right now. I feel like Lean is the only project trying to make formal proofs of classical mathematics accessible to an undergraduate student.

Re: Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

#127

Earlier quoted context omitted.

What simplifications do you have in mind? I think one of the reasons is that Lean's approximation of defeq still works well enough in practice. As mentioned by others, you never really run into the kind of counter examples that break theoretical properties, but instead into examples where checking defeq is inacceptably slow, which remains an issue even when defeq is decidable. From my understanding CiC is used becaus…

For example, if you are willing to accept undecidable typechecking, you can define inductive types in a much simpler theory (inductive types and dependent pattern matching are by far the most complex parts of CiC): https://homepage.cs.uiowa.edu/~astump/papers/from-realizabil... . There are a few other examples but this is the one that immediately sprung to mind. The complexity of CiC is very much about decidable type…

How are the ergonomics of a proof assistant based on λP2? Lean does a lot of elaboration of metavariables and typeclass instances and such before handing things off for checking by the kernel -- I'm curious about whether λP2's undecidability is decidable enough, so to speak.

Re: Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

#128
post #127

Earlier quoted context omitted.

For example, if you are willing to accept undecidable typechecking, you can define inductive types in a much simpler theory (inductive types and dependent pattern matching are by far the most complex parts of CiC): https://homepage.cs.uiowa.edu/~astump/papers/from-realizabil... . There are a few other examples but this is the one that immediately sprung to mind. The complexity of CiC is very much about decidable type…

How are the ergonomics of a proof assistant based on λP2? Lean does a lot of elaboration of metavariables and typeclass instances and such before handing things off for checking by the kernel -- I'm curious about whether λP2's undecidability is decidable enough, so to speak.

That's currently an open research question, but the answer most likely is that the ergonomics could be made just as good, considering that elaboration of metavariables, typeclass instances, etc. already uses possibly-undecidable algorithms distinct from those used in the kernel in just about every proof assistant I'm familiar with (Lean included).

In terms of stuff that do go more or less directly through the kernel, some followup papers to the one I linked discuss how to translate inductive definitions etc. automatically into a form accepted by the simpler kernel, so I am even more confident that this would not present a problem.

Re: Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

#129

Earlier quoted context omitted.

You don't need subgroups, you just need injective homomorphisms.

That's a nice idea but it tends to fall flat when you can't actually construct an explicit function exhibiting the homomorphism in question (which does happen from time to time). A lot of equivalences in areas like group theory only hold classically.

Your concerns make sense in general, but I have hard time understanding them for would-be subgroups. I would think the "explicit function" would be the easy part. The hard pat is annoyance of finding a "syntactic" representation of the subgroup and proving it's a group (closed) in its own right.

In any event, Lean's reputation is that it goes the extra mile for "regular" mathematicians. It probably has something nicer for this just like it does for quotiented types.

Re: Mathematicians welcome computer-assisted proof in ‘grand unification’ theory

#130
post #127

Earlier quoted context omitted.

How are the ergonomics of a proof assistant based on λP2? Lean does a lot of elaboration of metavariables and typeclass instances and such before handing things off for checking by the kernel -- I'm curious about whether λP2's undecidability is decidable enough, so to speak.

That's currently an open research question, but the answer most likely is that the ergonomics could be made just as good, considering that elaboration of metavariables, typeclass instances, etc. already uses possibly-undecidable algorithms distinct from those used in the kernel in just about every proof assistant I'm familiar with (Lean included). In terms of stuff that do go more or less directly through the kernel,…

The fact remains though that Lean 3 worked well enough to do Scholze level mathematics. I never quite know what to make of people saying "if the designers had done it in some other way, it would have been better". Of course if someone comes along doing it another way, and then they go on to also achieve Scholze level mathematics, then I will be all ears.
Post reply on HN