4 ms·
Formalizing 100 theorems in Coq
- anonlastname 8y agoI find it very interesting to see how experienced Coq programmers prove things. I have enough experience to know how deliberate there choices have to be.
- spaceman1331 8y agohttps://github.com/clarus/falso https://github.com/clarus/falso Coq has a terrible name and a reputation for asserting 1 = 2. These people do not know what they are doing. Do not trust them.
- anonlastname 8y agoThis bug only effects proofs that use types with more than 256 constructors. Also, it involves a command that is meant to optimize proofs so it isn't neccessary to ever use it. Personally, I still trust the implementation despite this edge case.
- anonfirstlasr 8y agoPerhaps this is funny, ironic or simply sarcastic. In any of these cases it’s an empty argument. If you want to criticise formal methods then you should rightly present a cogent argument, or simply stay quiet.
- archgoon 8y agoI believe this comment is meant to be a response to another post (https://news.ycombinator.com/item?id=18155410 https://news.ycombinator.com/item?id=18155410) who pointed out a flaw (now fixed) in Coq that allowed false theorems to be proved. Github link: https://github.com/clarus/falso https://github.com/clarus/falso
- archgoon 8y agoBrief proof that the sqrt of 2 is irrational. Suppose that sr2 is rational. Then it can be expressed as two integers with no common factors[0], p and q, as p/q. sr2 = p/q (1) Thus 2 = p^2/q^2 (2) 2q^2 = p^2 (3) So p^2 is divisible by 2. Since 2 is prime, and 2 divides p*p, it must also divide p. So p = 2p'. Plugging this back into (3) we have 2q^2 = 4p'^2 Which implies q^2 = 2p'^2 Which means that q is also divisible by 2. Which means both p and q are divisible by 2 which violates are orginal assumption [0] that p and q shared no common factors, which can be assumed for any rational number, which means that sr2 cannot be rational. Compare the above with: https://coq.inria.fr/distrib/8.2/contribs/QArithSternBrocot.sqrt2.html https://coq.inria.fr/distrib/8.2/contribs/QArithSternBrocot.... and you get an idea of the work that needs to be done to make proof assistants more ergonomic before wide adoption in mathematics. The benefit from ensuring no mistakes were made (I'm betting I messed up somewhere above; like not specifying that p and q are not zero) is dwarfed by the difficulty in expressing the core intuition and thus reusability of the proof.
- singularity2001 8y agoFunny I came to complain that the final version of this exact proof is not human readable any more: Theorem sqrt2_not_rational : forall p q : nat, q <> 0 -> p x p = 2 x (q x q) -> False. intros p q; generalize p; clear p; elim q using (well_founded_ind lt_wf). clear q; intros q Hrec p Hneq; generalize (neq_O_lt _ (sym_not_equal Hneq)); intros Hlt_O_q Heq. apply (Hrec (3 x q - 2 x p) (comparison4 _ _ Hlt_O_q Heq) (3 x p - 4 x q)). apply sym_not_equal; apply lt_neq; apply plus_lt_reg_l with (2 x p); rewrite <- plus_n_O; rewrite <- le_plus_minus; auto with x. apply new_equality; auto. Qed. This doesn't have to be. Maybe the author assumed that the audience knows the proof by heart. I don't, I know a proof but none including (3 * q - 2 * p). So longer names and comments please, ideally in a way understandable both by humans and machines. Or the goal was to 'get the proof done' with maximal brevity. Then please don't include it in the 'show off' page. In a future version of coq 'sqrt2_not_rational' might be spelled out "Theorem: sqare_root(2) not rational" PS: stupid HN removing unicode signs
- ekidd 8y ago> the final version of this exact proof is not human readable any more: In general, Coq proofs are meant to be read using tools, not as plain text. You start out with the theorem you want to prove, and you apply a rule to it. Then Coq shows two new things to prove. You apply a rule to each of these, and so on. Without seeing the list of active "proof goals" at each step, there's no way to guess what "apply sym_not_equal" means. But if you step through the proof line-by-line in the editor, then you can examine how each step updates your "proof goals". (I have an old blog post that shows what this looks like: http://www.randomhacks.net/2015/07/19/proving-sorted-lists-correct-using-coq-proof-assistent/ http://www.randomhacks.net/2015/07/19/proving-sorted-lists-c...) I admit, it can still be pretty arcane. But with the right tools and a bit of experience, it does get a lot easier. The real head-scratcher are advanced "proof tactics" like "auto", which automatically apply a long lists of possible transformations until they find an answer: Theorem basic_conj' : forall (A B : Prop), A -> B -> A /\ B. Proof. auto. Qed. This is the Coq version of "the proof is left as a exercise for the computer." It's pretty cool technology if you like math, well worth some time to puzzle it out. But expect to have to read some tutorials and think about them.
- joseraul 8y agoAll this may become much easier when we manage to merge proof assistants with automatic provers. Here is how you can prove the first theorem in Dafny. https://rise4fun.com/Dafny/GxplK https://rise4fun.com/Dafny/GxplK