[Agda] conjectures in agda

Martin Escardo m.escardo at cs.bham.ac.uk
Thu Jan 7 01:10:22 CET 2010


Some of you have discussed how to compile agda proofs with missing 
parts. Some of you have suggested to use postulates, but this is 
inconvenient in several ways. For example, among other things, you have 
to explicitly type postulates, and one advantage of agda is the facility 
to infer types (often).

I've come across the following clean way of doing this. I define a 
module "Conjecture" (listed below after my signature), which defines a 
proof "conjecture" that proves everything (using "postulate", of course).

For example, suppose you need a lemma for the proof of a theorem:

   lemma : ... statement ...

Suppose everything else has been proved, using this lemma, but not the 
lemma itself. The you can write the following:

   lemma : ... statement ...
   lemma = conjecture

If your proof of the theorem is correct assuming the conjecture, your 
agda file will compile, and it won't otherwise.

Moreover, you can use this when there are several cases, e.g.

   lemma : ... statement ...
   lemma O = conjecture
   lemma (succ n) = another-lemma n (lemma n)

Additionally, there can be several conjectures in a proof, and your 
proof will compile with the conjectures regarded as hypotheses (giving 
an error, or accepting your proof from the conjectured hypotheses).

I thought you might find this useful. (I didn't take universe 
polymorphism into account.)

Martin
--
module Conjecture where
-- Use this module to be able to compile
-- proofs/programs with missing parts.

conjecture : {A : Set} → A
conjecture {A} = ! inhabitant-of-∅
  where data ∅ : Set where
        -- no elements in the empty set.
        ! : ∅ → A
        ! ()
        postulate inhabitant-of-∅ : ∅

-- End of message





More information about the Agda mailing list