Doing a math assignment with the Lean theorem prover

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?

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.

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

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.

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).

lol oops, fixed thanks!

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/

> 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.