[Agda] question about a form of irrelevance elimination
Andrew Pitts
Andrew.Pitts at cl.cam.ac.uk
Tue Jul 14 15:11:07 CEST 2015
On 14 July 2015 at 13:46, Martin Escardo <m.escardo at cs.bham.ac.uk> wrote:
> I am a bit nervous about the computational consistency of this
> postulate. I think this may imply excluded middle (but I am not sure).
If true, that would be annoying, but interesting.
Thanks to all who posted replies to my question. Let me try to explain
why I asked the original question.
Stimulated by some work of one of my Masters students (see
<http://www.cl.cam.ac.uk/~amp12/index.html#choudhury>), I have been
thinking about an Agda development of nominal set theory which starts
with a decidable type of atoms that is infinite in the sense that for
every list of atoms there merely exists an atom not in the list. So I
need to use propositional reflection. I can hack that into Agda
following Dan Licata and Guillaume Brunerie's tricks in Agda-HoTT. But
as far as I know that forces me to construct proofs about
propositional reflection using its eliminator, which is tedious.
Whereas proofs using irrelevant truncation can make use of
pattern-matching and are rather nice. However, the theory of nominal
sets (when it comes to the Freshness Theorem and properties of name
abstraction) require unique-choice: if for every x : A I know there
merely exists a unique y : B with some property, I need to be able to
extract a function A -> B witnessing that. I can't see how one can do
that for irrelevant truncation without extra postulates. Am I wrong?
Andy
More information about the Agda
mailing list