[Agda] Without-K puzzle

Ulf Norell ulf.norell at gmail.com
Tue Jul 15 11:07:45 CEST 2014


I've been trying to define decidable equality on sigma types without K and
I run into
problems in the case where the first components are equal but the second
ones are
not. It boils down to solving the puzzle below, proving the contra-positive
of injectivity
of _,_ in the second argument. Any without-K wizard that can give me a hand
with this?

data ⊥ : Set where

¬_ : Set → Set
¬ A = A → ⊥

data Σ (A : Set) (B : A → Set) : Set where
  _,_ : (x : A) → B x → Σ A B

data Id (A : Set) (x : A) : A → Set where
  refl : Id A x x

elim-Id : {A : Set} (P : ∀ x y → Id A x y → Set) →
          (∀ x → P x x refl) →
          ∀ x y (p : Id A x y) → P x y p
elim-Id P r x .x refl = r x

puzzle : (A : Set) (B : A → Set) (x : A) (y z : B x) →
         ¬ Id (B x) y z → ¬ Id (Σ A B) (x , y) (x , z)
puzzle A B x y z neq eq = ?

/ Ulf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20140715/be8e5518/attachment-0001.html


More information about the Agda mailing list