[Agda] Injectivity of Constructors?

Shin-Cheng Mu scm at iis.sinica.edu.tw
Tue Apr 1 04:03:56 CEST 2008


Hi,

Every once in a while I find myself needing a proof of, for
example, b ≡ b', while having only proved inj₂ b ≡ inj₂ b'.
Do you think should each data constructor defined in the
standard library come with a proposition that it is injective?

For inj₂, this will do:

   inj₂-injective : {A B : Set}{b b' : B} ->
        inj₂ {A}{B} b ≡ inj₂ b' -> b ≡ b'
   inj₂-injective ≡-refl = ≡-refl

I thought these propositions are easy but they turn out to
be not always trivial. In pair-injective below, for example:

   pair-injective : {A B : Set}{a a' : A}{b b' : B} ->
      _,_ {A}{\_ -> B} a b ≡ (a' , b') -> (a ≡ a') × (b ≡ b')
   pair-injective ≡-refl = (≡-refl , ≡-refl)

It is probably pointless to generalise the first explicit
argument to:

   _,_ {A}{B} a b ≡ (a' , b')  where B : A -> Set

because we would need a proof of a ≡ a' in the first place
to show that B a and B a' yield the same type.

sincerely,
Shin



More information about the Agda mailing list