[Agda] Are there unicorns in Agda?

[Andreas Abel]

Hello Martin,

On 11/11/11 2:13 AM, Martin Escardo wrote:
> (The reason I am interested in (the non-existence of) unicorns is that,
> together with someone else, I am trying to find a topological model of
> type theory with a chain of universes, such as "Set i" in Agda. With
> just one universe, such models are known to exist. A unicorn would be a
> non-trivial definable clopen of the first universe "Set 0", before we
> know what the topological model is. The existence of unicorns one of the
> first natural questions regarding the topology of universes.)

The usual PER models for MLTT do not exclude unicorns.  However, the 
absence of unicorns is central for type-erasure.  I welcome your 
research which would give more precise models.

My own take on this question is that when you write

   F : Set -> Bool

then F is to be a shape-irrelevant function over Set.  This implies it 
cannot match on its result, only pass it along.  Using a size argument 
one can then infer that F is actually the constant function.  [There is 
no formal status to my argument (yet).]  This can be used by the 
extractor to optimize the program.

Cheers,
Andreas

-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Theoretical Computer Science, University of Munich
Oettingenstr. 67, D-80538 Munich, GERMANY

andreas.abel at ifi.lmu.de
http://www2.tcs.ifi.lmu.de/~abel/