[Agda] universe with extensional propositional equality?

Dan Licata drl at cs.cmu.edu
Wed Apr 8 02:48:20 CEST 2009


Hi everyone,

Suppose I define a little universe as follows:

  data Tp : Set where 
    bool : Tp
    _⊃_  : Tp -> Tp -> Tp

  <_> : Tp -> Set
  < bool >  = Bool
  < A ⊃ B > = < A > -> < B >

I'd like to define a notion of propositional equality that treats
functions extensionally, like this:

  Eq : {A : Tp} -> < A > -> < A > -> Set
  Eq {bool} True  True  = Unit
  Eq {bool} False False = Unit
  Eq {bool} True  False = Void
  Eq {bool} False True  = Void
  Eq {A ⊃ B} f g = (x y : < A >) -> Eq x y -> Eq (f x) (g y)
	  
However, I can't seem to prove that this notion of equality is
reflexive:

  refl : {A : Tp} -> (e : < A >) -> Eq e e

For functions, you need to show 

  refl {A ⊃ B} f = 
   (? : (x : < A >) (y : < A >) -> Eq x y -> Eq (f x) (f y))

i.e. that functions take equals to equals.  

My hunch is that all Agda functions in this little universe do take
equals to equals (e.g., OTT has reflexivity and substitutivity as
axioms---they're at least consistent).  

But can you prove them inside the system?  Or, if not, why not?

-Dan



More information about the Agda mailing list