[Agda] Are there unicorns in Agda?

Martin Escardo m.escardo at cs.bham.ac.uk
Fri Nov 11 10:29:12 CET 2011


Ok, that would count as a nice syntactical answer. (I am still 
interested in knowing what happens in the models.)

But what is precisely your answer? For example, although there may not 
be non-constant maps F:Set->X with X:Set, there certainly are 
non-constant maps F':Set->Set. What is the precise formulation of 
parametricity for ML type theory with a chain of universes, at least 
specialized to these small examples, that allows to see the absence of 
unicorns? (I explicitly said that the universes under consideration 
don't have eliminators.)

Martin

On 11/11/11 05:53, Dan Doel wrote:
> On Thu, Nov 10, 2011 at 5:13 PM, Martin Escardo<m.escardo at cs.bham.ac.uk>  wrote:
>> My question is, can one replace the final postulate by an actual
>> construction of a unicorn? (So that the resulting Agda code makes sense in
>> ML type theory.) More generally, are there non-constant maps F : Set → X
>> where X : Set? This more general question is not formulated in the Agda file
>> below, but it could.
>
> The answer should be no. Set is expected to have parametricity
> theorems similar to those in System F and the like. The free theorem
> for F : Set ->  X---for any particular X : Set---is:
>
>      forall A B : Set. F A = F B
>
> The same should be true for ML universes that don't have
> induction-recursion style eliminators (although whether they do
> depends on who you ask, I guess).
>
> -- Dan


More information about the Agda mailing list