[Agda] Do you use postulates extensively?

Sergei Meshveliani mechvel at botik.ru
Thu Jan 17 14:13:46 CET 2019


On Wed, 2019-01-16 at 01:56 +0200, Apostolis Xekoukoulotakis wrote:
> Since now, I have spent days proving trivial mathematical propositions
> without knowing if the general theory/idea is correct.
> 
> 
> This, of course, means that the theory is developed while programming
> in Agda. It is not developed before using Agda.
> 
> 
> I am thinking of using postulates extensively and prove things on
> paper instead of doing it in Agda.
> It is less safe but much faster. Then check the validity of the main
> Idea with the use of the postulates. Only then try to prove some of
> the postulates that might be a bit tricky.
> 
> 
> At least for me, proofs that do not take part in the computation of a
> program can remain postulates.
> 
> 
> What is your strategy? Do you use postulates extensively? In my
> opinion this is important enough that it needs to be put in the
> documentation. I have wasted too much time proving trivial
> propositions and we do not have to do that.
> 


Usually I postulate simple lemmas of which I am sure that I can prove
them in Agda. I move fast to the final goal. If fail with this final
goal, then one can forget of those lemmas.
And if the goal is proved, I return to proving those lemmas in Agda.  
Formal proofs are difficult.

Still setting postulates is dangerous.
Consider the problem:
(given a prime number  p,  find any prime number  q  greater than  p.

Many people suggest:
     Method:
     let A = product [p' | prime p', p' <= p]
     in  1 + A 

and think that  1+A  is the needed prime.
I also thought this way, and postulated this, and continued.
Then, I returned to a formal proof for Method.
And discovered that I fail to prove it.
Then I discovered a counter-example:   2*3*5*...*13 + 1
-- something of this sort.
  
There were more simple cases when my postulate occurred wrong. 
 
Another example of using Agda proofs.
I "developed" a certain factorization theory for cancellative
commutative monoids, with definitions, and so on, because it looks as
trivial.
To make sure that I have not mistakes there, I proved all the lemmata in
Agda. Then I looked into the book of Jacobson, and observed there all my
definitions and lemmas. If there was not such a book, Agda could
essentially help.

And even without proofs, dependent types are important.
They provide an adequate programming language for representing algebraic
classes and domains. 

--
SM





More information about the Agda mailing list