News for hackers. Stuff that matters.
Re:'Equals' Has More Than One Meaning in Math by auggierose on Tuesday June 18, 2024 @09:24AM (#40717579)
It is a different story in Lean though, because Lean, as most other logics based on type systems, doesn't have subtypes. So all you have are coercions. That's actually a bad thing.
Re:'Equals' Has More Than One Meaning in Math by staunton on Wednesday June 19, 2024 @03:00AM (#40725597)
What do you mean by "subtype"? Lean defines a thing calles `Subtype`, members of which are constructed from a value and a property.
Re:'Equals' Has More Than One Meaning in Math by auggierose on Wednesday June 19, 2024 @03:06AM (#40725640)
That might be called Subtype, but is a disjoint type containing different values than the original type. If S is a subtype of T, and x : S, then also x : T.
Re:'Equals' Has More Than One Meaning in Math by singularity2001 on Wednesday June 19, 2024 @04:19AM (#40726055)
why would you say that this is a bad thing
Re:'Equals' Has More Than One Meaning in Math by auggierose on Wednesday June 19, 2024 @06:32AM (#40726883)
Because coercions are just a work-around, and more machinery hidden from you, but still there causing problems (like types). If you are coming from C++, then yes, Lean coercions are a step up. If you are coming from mathematics, then Lean coercions are just a cumbersome work-around.
Re:'Equals' Has More Than One Meaning in Math by lupire on Wednesday June 19, 2024 @07:44AM (#40727320)
Cumbersome compared to what? Ignoring the issue entirely?
Re:'Equals' Has More Than One Meaning in Math by auggierose on Wednesday June 19, 2024 @08:17AM (#40727547)
Cumbersome compared to just having ℕ ⊂ ℤ, instead of having a coercion c from ℕ to ℤ, with complicated algorithms of where to insert c automatically, and then hiding the result from you, because otherwise you would see with your own eyes what a mess you are in.
Re:'Equals' Has More Than One Meaning in Math by markusde on Wednesday June 19, 2024 @10:37AM (#40728728)
But with coercions you do have {↑n | n ∈ ℕ} ⊂ ℤ, which is the subtype that you really want!

The issue is that not all properties of subsets can be lifted to supersets. As an example from analysis, you can coerce the reals ℝ to the extended reals ℝ∞, but you lose some of your rewrite rules because you need to choose how to define edge cases like (∞ - ∞) in ℝ∞. Making these choices is common in mathematics (at least in analysis) and in pencil and paper proofs it's usually just handwaved away.

Using subtypes, a proof checker would have to be explicitly given which ambient superset you're going to rewrite something like ((a : ℝ) - (b : ℝ)) in... this is more or less the same as using coercions to distinguish between ℝ and {↑r | r ∈ ℝ} ⊂ ℝ∞ except with subsets type inference is way harder.

I'll admit that coercions are annoying, but subsets don't let you get around it: here there's an essential step up in complexity between sloppy pencil and paper proofs and verified code. Personally, I'm really interested in seeing how much of mathematical handwaving can be rigorously automated away. There's a lot of cool work in this area by I don't think the FM community has a definitive answer for it yet.

Re:'Equals' Has More Than One Meaning in Math by auggierose on Wednesday June 19, 2024 @12:23PM (#40729730)
Let's be clear, I am not arguing for subtypes. Subtypes are a mess, that is why no type system supports them. I am arguing against any types at all. So type inference being harder is not a problem, because there won't be any type inference. I know, that is a tough pill to swallow, type inference is like a hard drug for computer scientists.

Subsets or subcollections, on the other hand, are fine. Of course you will have proof obligations, but that is not a problem, and automation can take care of most of this (note that automation is much more flexibel than hardcoded type inference).

Re:'Equals' Has More Than One Meaning in Math by markusde on Wednesday June 19, 2024 @01:16PM (#40730252)
Fair enough, I haven't used many proof assistants without dependent types, and I probably should.