Insuficientemente evaluados contexto en el interior `con` cláusula

Question

Estoy atascado en la siguiente prueba.

module Temp where

   open import Data.Empty
   open import Data.Fin hiding (compare)
   open import Data.Nat hiding (compare); open import Data.Nat.Properties
   open import Function
   open import Level
   open import Relation.Binary
   open import Relation.Binary.PropositionalEquality

Estoy trabajando con números naturales Γ interpretarse como contextos, a la de Bruijn índices, y el uso de elementos de Fin Γ como identificadores.(Para los fines de mi pregunta no se debe entender como estos contextos y los identificadores, pero se puede ayudar con la intuición.)

Un cambio de nombre de un contexto de morfismos:

   Ren : Rel ℕ Level.zero
   Ren Γ Γ′ = Fin Γ → Fin Γ′

Ahora me defina los siguientes dos operaciones simples.La primera, close-var, produce un cambio de nombre que elimina un nombre desde el contexto, la asignación a un nombre existente en el resto de contexto.La segunda, open-var, produce un cambio de nombre que hace a la inversa, la inserción de un nuevo nombre en el contexto en una ubicación en particular.Para localizar una inserción o eliminación punto en el contexto, se podría comparar en toℕ, como todavía no he groked cómo utilizar Data.Fin.compare.

   open StrictTotalOrder strictTotalOrder
   open DecTotalOrder decTotalOrder renaming (refl to ≤-refl; trans to ≤-trans)
   open import Data.Fin.Props using (bounded)

   close-var : ∀ {Γ} → Fin Γ → Fin (suc Γ) → Fin (suc Γ) → Fin Γ
   close-var _ y z with compare (toℕ y) (toℕ z)
   close-var _ _ zero | tri< () _ _
   close-var _ _ (suc z) | tri< _ _ _ = z
   close-var x _ _ | tri≈ _ _ _ = x
   close-var _ zero _ | tri> _ _ ()
   close-var _ (suc y) z | tri> _ _ z<suc-y = 
      fromℕ≤ (≤-trans z<suc-y (bounded y))

   open-var : ∀ {Γ} → Fin (suc Γ) → Fin Γ → Fin (suc Γ)
   open-var y z with compare (toℕ y) (toℕ z)
   ... | tri< _ _ _ = suc z
   ... | tri≈ _ _ _ = suc z
   ... | tri> _ _ _ = inject₁ z

El único no-trivial parte de estas definiciones es el último caso de close-var que tiene para coaccionar a partir de un contexto más grande a una más pequeña.

Fijo de argumentos, la renamings obtenidos a partir de close-var y open-var forma un isomorfismo (estoy bastante seguro).Sin embargo estoy atascado hacer sentido de los siguientes objetivos:

   close∘open≡id : ∀ {Γ} (x : Fin Γ) (y : Fin (suc Γ)) (z : Fin Γ) → 
                   (close-var x y ∘ open-var y) z ≡ z
   close∘open≡id _ y z with compare (toℕ y) (toℕ z)
   close∘open≡id _ y z | tri< _ _ _ with compare (toℕ y) (suc (toℕ z))
   close∘open≡id _ _ _ | tri< _ _ _ | tri< _ _ _ = refl
   close∘open≡id _ _ _ | tri< y<z _ _ | tri≈ y≮suc-z _ _ = 
      ⊥-elim (y≮suc-z (≤-step y<z))
   close∘open≡id _ _ _ | tri< y<z _ _ | tri> y≮suc-z _ _ = 
      ⊥-elim (y≮suc-z (≤-step y<z))
   close∘open≡id _ y z | tri≈ _ _ _ with compare (toℕ y) (suc (toℕ z))
   close∘open≡id _ _ _ | tri≈ _ _ _ | tri< _ _ _ = refl
   close∘open≡id _ _ _ | tri≈ _ y≡z _ | tri≈ y≮suc-z _ _ rewrite y≡z = 
      ⊥-elim (y≮suc-z ≤-refl)
   close∘open≡id _ _ _ | tri≈ _ y≡z _ | tri> y≮suc-z _ _ = {!!}
   close∘open≡id _ y z | tri> _ _ _ with compare (toℕ y) (toℕ (inject₁ z))
   close∘open≡id _ _ _ | tri> _ _ _ | tri< _ _ _ = {!!}
   close∘open≡id _ _ _ | tri> _ _ _ | tri≈ _ _ _ = {!!}
   close∘open≡id _ _ _ | tri> _ _ _ | tri> _ _ _ = {!!}

El primer caso debería ser imposible, pero me parece que no se puede utilizar y≡z y y≮suc-z para derivar una contradicción, como hice en el caso anterior.Creo que esto es debido a que el patrón en sí es absurdo, pero no sé cómo convencer a Agda de este.

Un segundo, y tal vez relacionados con el problema, es que no parece suficiente la reducción se ha producido de acuerdo con los cuatro objetivos restantes.Todos ellos contienen with patrones tales como tri< .a .¬b .¬c.Pero yo estaba esperando el anidados with cláusulas para permitir suficiente ejecución para eliminar estos.¿Qué estoy haciendo mal?

(Como una comprobación de validez, es fácil de comprobar:

   sub : ∀ {Γ} (x : Fin Γ) (y : Fin (suc Γ)) → Ren Γ Γ
   sub x y = close-var x y ∘ open-var y

   Γ : ℕ
   Γ = 5

   ρ : Ren Γ Γ
   ρ = sub (suc (zero)) (suc (suc (suc zero)))

   ex₁ : ρ zero ≡ zero
   ex₁ = refl

   ex₂ : ρ (suc zero) ≡ suc zero
   ex₂ = refl

   ex₃ : ρ (suc (suc (zero))) ≡ suc (suc zero)
   ex₃ = refl

   ex₄ : ρ (suc (suc (suc (zero)))) ≡ suc (suc (suc zero))
   ex₄ = refl

y así sucesivamente.)

Answer 1

Anidado with las cláusulas están bien.El problema es que en la definición de close-var, coinciden no sólo en el resultado de compare (toℕ y) (toℕ z), pero también en los argumentos y y z a sí mismos.Y, por supuesto, Agda no se puede reducir algo sin estar seguro de que la ecuación de la función a utilizar.

En el segundo agujero, close-var debe coincidencia de patrón en inject₁ z, pero no (y no pueden).Usted tiene que resumen más de que así y, a continuación, el patrón coincide suficiente para convencer a Agda que se puede elegir con seguridad una ecuación.

close∘open≡id x y z | tri> _ _ _
  with inject₁ z | compare (toℕ y) (toℕ (inject₁ z))
... | tri> _ _ _ | Fin.zero  | tri< () _ _
... | tri> _ _ _ | Fin.suc r | tri< _  _ _ = {!!}  -- goal is r ≡ z

---

Como para el primer hoyo - si el código de arriba no ayuda, acaba de demostrar un simple lema:

≡→≤ : {x y : ℕ} → x ≡ y → x ≤ y
≡→≤ refl = ≤-refl

Y a continuación, se puede derivar la contradicción a través de:

y≮suc-z (s≤s (≡→≤ y≡z))

(No he mirado en el StrictTotalOrder los registros, pero lo más probable es que este lema es que ya existe).