[Agda] Dependent injection without K?

Matthieu Sozeau matthieu.sozeau at gmail.com
Mon Feb 21 23:33:24 CET 2011


Le 21 févr. 2011 à 18:50, Brandon Moore a écrit :

> I am trying to prove something like fcinj in Coq. The code below compiles
> normally, but is rejected with the --without-K flag. Is this sort of goal
> provable without some sort of equality axiom?
> 
> data ℕ : Set where
>  Z : ℕ
>  S : ℕ → ℕ
> 
> data Fin : ℕ → Set where
>  fz : ∀{n} → Fin (S n)
>  fs : ∀{n} → Fin n → Fin (S n)
> 
> data FinCopy : ∀{n} → Fin n → Set where
>  FZ : ∀{n} → FinCopy (fz {n})
>  FS : ∀{n f} → FinCopy {n} f → FinCopy (fs f)
> 
> fcinj : ∀{n f} → FinCopy (fs {n} f) → FinCopy f
> fcinj (FS y) = y

Hi,

  It should be provable without K, as it is provable in Coq
without K. Something like the following should work:

fspred : forall {n} (f : fin n) -> Set
fspred fz = nat
fspred (fs f) = fincopy f

fsmatch : forall {n f} (fc : fincopy {n} f) -> fspred f
fsmatch FZ = Z
fsmatch (FS y) = y.

Then fcinj is just an instance of fsmatch.
-- Matthieu


More information about the Agda mailing list