Live data from Hacker News

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

nature.com

91–100 of 140 posts

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

#91
post #45

This is going to be an exciting area. I spent some time previously playing with Coq. It's very powerful, but even proving the simplest undergraduate maths statements (say, about group theory) can prove very challenging. I believe that part of this is that Coq uses different mathematical foundations than traditional mathematics, which mostly uses set theory (ZFC, although most people don't care about the specifics). S…

Here's the definition of a subgroup in Lean's mathlib: https://leanprover-community.github.io/mathlib_docs/group_th...

Given a group G, there is a type `subgroup G` of subgroups of G, and a subgroup is a structure consisting of a set of elements of G along with some proofs that it has the identity, it's closed under multiplication, and it's closed under taking inverses. Lean has a coercion facility using typeclasses, and there is a typeclass instance that will use the subgroup's set coerced to a type when the subgroup is used in a place that expects a type. This coerced type has a group typeclass instance, so a subgroup "is" a group.

The big complexity in all of this doesn't seem to be ZFC vs type theory, but rather how do you implement a mathematician's use of synecdoche and implicit coercions. Synecdoche is the figure of speech where you refer to a thing by its parts or vice versa -- for example, "let G be a group" and then using G as if it were a set, even though a group consists of a set, a binary operation on the set, a choice of identity element, and a few axioms that must hold. Mathlib uses typeclasses to implement the synecdoche -- a type is a group if there is a typeclass instance that provides the rest of the structure. As I understand it, Coq's Mathematical Components library uses structures and unification hints instead (though I've failed to understand how it works exactly), but I have heard that they can be very fiddly to get right.

I think you'd have to find solutions to these same problems no matter the foundations. At least with types, there's enough information lying around that, for example, group structures can be automatically synthesized by the typeclass resolution system in many common situations.

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

#92

For anyone frustrated that the article doesn’t say what specific part of math has the most to gain it’s here: “ The crucial point of condensed mathematics, according to Scholze and Clausen, is to redefine the concept of topology, one of the cornerstones of modern maths. A lot of the objects that mathematicians study have a topology — a type of structure that determines which of the object’s parts are close together a…

I know nothing about topology. If you have time, could you please explain this sentence?

"For example, any triangle is topologically equivalent to any other triangle — or even to a circle — but not to a straight line."

Is it because triangles and circles are "2D" and lines aren't?

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

#93

For anyone frustrated that the article doesn’t say what specific part of math has the most to gain it’s here: “ The crucial point of condensed mathematics, according to Scholze and Clausen, is to redefine the concept of topology, one of the cornerstones of modern maths. A lot of the objects that mathematicians study have a topology — a type of structure that determines which of the object’s parts are close together a…

I know nothing about topology. If you have time, could you please explain this sentence? "For example, any triangle is topologically equivalent to any other triangle — or even to a circle — but not to a straight line." Is it because triangles and circles are "2D" and lines aren't?

Crudely speaking, topologists consider spaces as if they're made of rubber - a mathematically perfect rubber that can be made infinitely thin or stretch to infinity. So, a circle can be made with an infinitely thin circular rubber ring, and you just pinch three points and stretch, and you get your triangle, in any shape.

But you can't get a straight line - to do that you need scissors to cut one point of a circle (to be precise, remove a single point) - and then you can stretch the remainder to infinity and now you have your line.

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

#94

For anyone frustrated that the article doesn’t say what specific part of math has the most to gain it’s here: “ The crucial point of condensed mathematics, according to Scholze and Clausen, is to redefine the concept of topology, one of the cornerstones of modern maths. A lot of the objects that mathematicians study have a topology — a type of structure that determines which of the object’s parts are close together a…

I know nothing about topology. If you have time, could you please explain this sentence? "For example, any triangle is topologically equivalent to any other triangle — or even to a circle — but not to a straight line." Is it because triangles and circles are "2D" and lines aren't?

No. Both are 1-d (lines).

It's because triangles are loops (closed) and straight lines aren't.

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

#95
post #13

Earlier quoted context omitted.

> You might be confused by the fact that Lean's definitional equality is not decidable, but that doesn't mean it isn't sound. Nobody has ever found a proof of `false` so far in Lean 3. You are right, my bad. Taking my words back on that. A bit more details from the Pierre-Marie Pédrot: > Lean does not escape this limitation, as it defines the equality type inductively as in Coq. Rather, in a mastermind PR campaign, t…

I haven't used quotients (or Lean), but I've certainly encountered subject reduction problems in Coq when using coinduction, so this sounds a tad hypocritical. It's certainly good to avoid breaking subject reduction even more though ;)

There's ongoing work[1] on fixing that. Also let's see how migrating setoids to cubical type theory might fix more issues for Coq. Will they follow the Arend[2] path? That remains to be seen.

[1] https://github.com/coq/coq/pull/10764

[2] https://arend-lang.github.io/about/arend-features

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

#96
post #45

This is going to be an exciting area. I spent some time previously playing with Coq. It's very powerful, but even proving the simplest undergraduate maths statements (say, about group theory) can prove very challenging. I believe that part of this is that Coq uses different mathematical foundations than traditional mathematics, which mostly uses set theory (ZFC, although most people don't care about the specifics). S…

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.

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

#97
post #13

Earlier quoted context omitted.

> You might be confused by the fact that Lean's definitional equality is not decidable, but that doesn't mean it isn't sound. Nobody has ever found a proof of `false` so far in Lean 3. You are right, my bad. Taking my words back on that. A bit more details from the Pierre-Marie Pédrot: > Lean does not escape this limitation, as it defines the equality type inductively as in Coq. Rather, in a mastermind PR campaign, t…

I haven't used quotients (or Lean), but I've certainly encountered subject reduction problems in Coq when using coinduction, so this sounds a tad hypocritical. It's certainly good to avoid breaking subject reduction even more though ;)

Pierre Pedrot has been very vocal in his belief that broken SR from coinductive types is a serious problem with Coq that needs to be fixed. This is quite different from introducing stuff that deliberately breaks it.

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

#98
post #86
post #60

Earlier quoted context omitted.

The jargon is a bit confusing sometimes. In Lean, "refl" does a whole lot more than prove x=x. It is of course available if you want to prove x=x, but the real power of "refl" is that it also proves x=y where x and y are definitionally equal. Or at least that's the idea; it turns out that lean's definitional equality relation is not decidable so sometimes it will fail to work even when x and y are defeq, and this is…

Thanks for the explanation. Is the defeq undecidability a bug of Lean that should be fixed in the future? Or is it an intentional design decision for it to function properly for other types of proofs?

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.

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

#99

Earlier quoted context omitted.

You can absolutely do constructive things in Lean, as long as you use neither the built-in "quot" type nor the three other axioms described in the docs, and then you get a system with all the desired properties I think

Some constructivists may also take offense with proof irrelevance (and the resulting loss of normalization [1] or its incompatibility with HoTT), which you can only really avoid by avoiding Prop. [1] https://arxiv.org/abs/1911.08174

There is also a problem of HoTT and equality reflection incompatibility[1].

[1] https://www2.mathematik.tu-darmstadt.de/~streicher/barc_corr...

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

#100
post #13

Earlier quoted context omitted.

The claim that Lean's core is not completely sound is FUD. Completely bogus. You might be confused by the fact that Lean's definitional equality is not decidable, but that doesn't mean it isn't sound. Nobody has ever found a proof of `false` so far in Lean 3. The choice for Lean is actually quite natural: (i) it has a large and coherent library of mathematics to build such a project upon. And (ii), it has a substanti…

> You might be confused by the fact that Lean's definitional equality is not decidable, but that doesn't mean it isn't sound. Nobody has ever found a proof of `false` so far in Lean 3. You are right, my bad. Taking my words back on that. A bit more details from the Pierre-Marie Pédrot: > Lean does not escape this limitation, as it defines the equality type inductively as in Coq. Rather, in a mastermind PR campaign, t…

[deleted]
Post reply on HN