[Agda] Unification of function types

Vilhelm Sjöberg vilhelm at cis.upenn.edu
Fri Sep 20 20:51:08 CEST 2013

On 2013-09-20 06:14, Jesper Cockx wrote:
> From a more theoretical perspective, it seems to me quite 
> unproblematic to add a rule that A1 = A2 and B1 = B2 whenever (x : A1) 
> -> B1 = (x : A2) -> B2.
What do you propose to do about the bound variable x in B1?

One idea is to say that for any (a:A1), we should be able to conclude
{a/x}B1 = {a/x}B2.
But now the injectivity rule is really an injectivity axiom scheme which 
can be instantiated for arbitrary a:s, and it seems hard to use such a 
rule in a terminating algorithm (as we would want for definitional 
equality). For example, any equation scheme
∀ x y z. (a = b)
could be expressed by an assumption
((x y z:A) -> a) = ((x y z:A) -> b)
and deciding equality in a theory with arbitrary axioms is undecidable.

I was just thinking about this problem in another context, so ideas or 
literature pointers would be welcome. :)


More information about the Agda mailing list