News for hackers. Stuff that matters.
Re:Doing a math assignment with the Lean theorem prover by xvilka on Monday April 06, 2020 @10:06AM (#22793797)
The same can be done also with Coq[1], it is easy to learn[2], actively developed[3], and better documented[4]. You can also visit their discussion board[5]. Regarding the usual Lean vs Coq "war" and so-called "setoid hell" you can read a lengthy discussion on their GitHub[6].

[1] http://coq.inria.fr/

[2] https://learnxinyminutes.com/docs/coq/

[3] https://github.com/coq/coq

[4] https://softwarefoundations.cis.upenn.edu/

[5] https://coq.discourse.group/

[6] https://github.com/coq/coq/issues/10871

Re:Doing a math assignment with the Lean theorem prover by ahelwer on Monday April 06, 2020 @10:09AM (#22793813)
I tried learning Coq through the Software Foundations track a couple times and enjoyed what I did learn, but bounced off. If Coq made something similar to the Natural Number Game [0] I'd love to give it a go and see the differences!

[0] https://wwwf.imperial.ac.uk/~buzzard/xena/natural_number_gam...

Re:Doing a math assignment with the Lean theorem prover by ivanbakel on Monday April 06, 2020 @11:19AM (#22794496)
That final link is very insightful. Not to pick sides, but if Lean really doesn't have subject reduction when you use quotient types, that's a crazy property to drop (or lose accidentally).
Re:Doing a math assignment with the Lean theorem prover by ocfnash on Monday April 06, 2020 @12:12PM (#22794929)
I have a little experience of both Coq and Lean and have followed some of the discussion about Lean's handling of quotient types.

I have seen computer scientists emphasise to mathematicians that subject reduction should not be forfeit but I have yet to see a convincing argument/example for why not.

I don't suppose you can elaborate on why this may be / is so crazy, that someone with only a limited understanding of type theory might follow?

Re:Doing a math assignment with the Lean theorem prover by zozbot234 on Monday April 06, 2020 @12:27PM (#22795067)
Setoids are also very relevant in constructive math, for similar reasons. Quotient types/sets basically conflate cases where one can easily normalize the elements of some equivalent class vs. cases where this cannot be done effectively, and that's not a good approach at all.
Re:Doing a math assignment with the Lean theorem prover by kevinbuzzard on Monday April 06, 2020 @06:48PM (#22798639)
Lean's maths library development is essentially completely focussed on classical mathematics, which is why it has been so successful in drawing "working mathematicians" in. Such people do not care at all about the issues involving quotients, indeed quotients in Lean work just fine for them, and they don't care about constructibility either, because this is the prevailing culture in maths departments (although it is not, I am well aware, the prevailing culture in computer science departments). If you are interested in constructivism I would not recommend Lean. Many of the developments in mathlib are classical. That's why it's moving so quickly -- classical mathematics is much easier.
Re:Doing a math assignment with the Lean theorem prover by The_rationalist on Monday April 06, 2020 @12:18PM (#22794972)
What about coq vs z3 ? It seems they are the two most actively developed theorem provers/checkers
Re:Doing a math assignment with the Lean theorem prover by aweinstock on Monday April 06, 2020 @03:28PM (#22796958)
For a concrete example of how z3 differs from Coq, consider trying to prove that "for all integers x, there exists an integer y greater than x such that x divides y" (a subgoal of Euclid's theorem on there being infinitely many primes).

Here's a transcript of using the z3 python bindings to ask for a proof:

    $ python
    >>> import z3
    >>> x, y = z3.Ints('x y')
    >>> s = z3.Solver()
    >>> s.add(z3.Not(z3.ForAll([x], z3.Exists([y], z3.And(y >= x, y % x == 0)))))
    >>> s.check()
    unknown
z3 returns unknown (if it had returned "unsat", it would have been possible to extract a resolution-refutation proof), and there's not much that can be done with the unknown.

Here's a Coq interactive session that proves most of the cases (with one subproof left unsolved, it was taking me too long relative to the rest of the proof).

    $ coqtop
    Require Import NArith.
    Require Import Omega.

    Lemma x_le_fact : forall x, x <= fact x.
    induction x;.
    - simpl; omega.
    - simpl; admit. (* Proving `x <= fact x -> S x <= fact x + x * fact x` left unsolved here *)
    Admitted.

    Goal forall (x : nat), exists (y : nat), y >= x /\ Nat.modulo y x = 0.
    intros x; exists (fact x).
    split.
    - unfold ">=". apply x_le_fact.
    - induction x.
        + simpl; reflexivity.
        +
      (* goal here is `fact (S x) mod S x = 0` *)
      unfold fact; fold fact.
      (* goal here is `(S x * fact x) mod S x = 0` *)
      rewrite (Nat.mul_comm (S x) (fact x)).
      (* goal here is `(fact x * S x) mod S x = 0` *)
      apply (Nat.mod_mul (fact x) (S x)).
      discriminate.
    Qed.
Unlike z3, you need to manually tell Coq what the steps are, but it gives you feedback on which steps are correct, and what assumptions are available and what subgoals still remain at each step (I've included some of those as comments, running the proof through the interpreter shows more detail).
Re:Doing a math assignment with the Lean theorem prover by ahelwer on Monday April 06, 2020 @12:39PM (#22795187)
Z3 is very different from Coq and Lean. Coq and Lean are interactive theorem provers, while Z3 is a satisfiability modulo theories (SMT) solver which can do things like checking whether a logical formula is satisfiable or finding a solution for a system of constraints.
Re:Doing a math assignment with the Lean theorem prover by The_rationalist on Monday April 06, 2020 @02:11PM (#22796222)
Thanks! And what about agda and Idris?
Re:Doing a math assignment with the Lean theorem prover by aweinstock on Monday April 06, 2020 @03:33PM (#22796990)
Agda and Idris are the same sort of tool (total dependently typed languages/proof assistants/interactive theorem provers) as Lean and Coq.
Re:Doing a math assignment with the Lean theorem prover by umvi on Monday April 06, 2020 @11:44AM (#22794693)
Can someone explain why I would ever want to use Coq? Is it mainly for algorithm researchers?
Re:Doing a math assignment with the Lean theorem prover by agentultra on Monday April 06, 2020 @12:06PM (#22794884)
If you're a practicing programmer you may want to use a theorem prover like Coq or Lean for a couple of reasons:

1. You want to verify your algorithms, data structures, and properties are correct with regards to their specifications. For example: an OS micro-kernel, verified compiler, etc.

2. You want to derive some code with verified properties or deeply embed specifications. A lock-free and fair scheduler, an algorithm for sharing data that guarantees it doesn't leak private information, a real-time control system, etc. For an example of such a library see [0].

If you're a computer scientist you're probably more concerned with the first and proving more of your own theorems.

If you're a mathematician you're (probably) more interested in new theorems (I'm not a pure mathematician, I can only speculate from what I've heard Buzzard and other mathematicians say).

[0] https://hackage.haskell.org/package/containers-verified

Re:Doing a math assignment with the Lean theorem prover by logicchains on Monday April 06, 2020 @02:43AM (#22791391)
For people interested in using Lean, note that there's a community fork (https://github.com/leanprover-community/lean) of the last official Lean 3 release 3.4.2 (https://github.com/leanprover/lean). The fork is still under active maintenance, so might be a better place to start (the main development team have moved onto developing Lean 4.0 (https://github.com/leanprover/lean4), and it's not clear when that will be ready).
Re:Doing a math assignment with the Lean theorem prover by abjKT26nO8 on Monday April 06, 2020 @02:33AM (#22791352)
It's a bit ironic, but the author repeated the same error every time they wrote the formula involving sigma. What they wanted to write was $\sum_{0}^{n} k$. What they actually wrote ($\sum_{0}^{n} n$) is equal to $n \cdot (n+1)$ (without the division by 2).
Re:Doing a math assignment with the Lean theorem prover by mkl on Monday April 06, 2020 @06:55AM (#22792548)
Yes, though it's better to define k: $\sum_{k=0}^n k$.
Re:Doing a math assignment with the Lean theorem prover by ahelwer on Monday April 06, 2020 @10:07AM (#22793805)
lol oops, fixed thanks!
Re:Doing a math assignment with the Lean theorem prover by outlace on Sunday April 05, 2020 @11:15PM (#22790652)
I just started learning Lean today - what a coincidence. I have found learning lean difficult but gratifying. The post serves as further motivation.
Re:Doing a math assignment with the Lean theorem prover by dhosek on Sunday April 05, 2020 @10:52PM (#22790559)
It's a pity that the author's high school didn't use geometry as the means of introducing the concept of mathematical proof. The classical high school two-column proof is in many ways quite similar to the methods of Lean, albeit with a different structure.
Re:Doing a math assignment with the Lean theorem prover by Smaug123 on Monday April 06, 2020 @03:41AM (#22791620)
I greatly recommend Lockhart's Lament (https://www.maa.org/external_archive/devlin/LockhartsLament....) which says exactly the opposite.

I didn't personally undergo "two-column proof" education, and learned what the phrase means from Lockhart's Lament itself, but it sounds miserable; I say this as an MMath who specialised in set theory and logic, and who has been side-project formalising maths in Agda for the last two years.

Re:Doing a math assignment with the Lean theorem prover by JadeNB on Monday April 06, 2020 @05:53PM (#22798272)
> I didn't personally undergo "two-column proof" education, and learned what the phrase means from Lockhart's Lament itself, but it sounds miserable; I say this as an MMath who specialised in set theory and logic, and who has been side-project formalising maths in Agda for the last two years.

As a professional mathematician who did go through two-column proof, you're not the only one who finds them miserable. Personally, abstract algebra was what won me over to the beauty of proof (probably that old standby, the irrationality of sqrt(2), was the first); but everyone will find a different experience.

Re:Doing a math assignment with the Lean theorem prover by dhosek on Tuesday April 07, 2020 @11:46AM (#22804267)
Aesthetically, two-column proofs are miserable, but they have the advantage that the logic is very clearly laid out. There's no chance to hand-wave when every step of the proof needs to be explicitly justified.
Re:Doing a math assignment with the Lean theorem prover by 0az on Monday April 06, 2020 @11:02AM (#22794332)
I personally credit my own geometry education, as much as I disliked it, with giving me the tools I needed to succeed in Calculus. That Calculus final involved proving part two of the FTC. Fun times.

AP Calculus? It's much less helpful, in its computational focus.

Re:Doing a math assignment with the Lean theorem prover by lordnacho on Monday April 06, 2020 @03:01AM (#22791448)
Does Lean allow you to put in geometric proofs? Say someone draws some circles and some lines and wants to prove that some property of the intersection points is true, eg that are always on the same straight line?
Re:Doing a math assignment with the Lean theorem prover by h91wka on Monday April 06, 2020 @11:15AM (#22794456)
Quick search reveals that some people have encoded Euclid's axioms in Coq (Lean and Coq are based on roughly the same theory):

http://geocoq.github.io/GeoCoq/

Re:Doing a math assignment with the Lean theorem prover by aadams on Sunday April 05, 2020 @11:18PM (#22790661)
Will you provide links?
Re:Doing a math assignment with the Lean theorem prover by wwarner on Monday April 06, 2020 @10:00AM (#22793752)
This is really futuristic. Feels like it could be applied to model based design.
Re:Doing a math assignment with the Lean theorem prover by masteranza on Monday April 06, 2020 @02:51AM (#22791416)
The example the author provided is too trivial to convince me to use lean.
Re:Doing a math assignment with the Lean theorem prover by kevinbuzzard on Monday April 06, 2020 @11:27AM (#22794554)
[Here](https://arxiv.org/abs/1907.01449) is a Lean formalisation of a 2017 Annals of Mathematics paper.