Доказывая Агде, что мы говорим об одном и том же

Я пытаюсь доказать противоречие, но сталкиваюсь с проблемой, пытающейся доказать Agda, что тип домена сигмы, возвращаемый <>-wt-inv та же сигма, что и в предыдущем доказательстве. Я ожидаю, что доказательство uniq-типа должно помочь мне там, но я не могу соединить их вместе.

Я надеюсь, что комментарии в коде ниже дают достаточно контекста.

-- given a type for (f ⟨⟩), we can derive that f is a function type
-- and we can prove that the context yields σ 
⟨⟩-wt-inv : ∀ {n m f τ} {K : Ktx n m} → K ⊢ (f ⟨⟩) ∶ τ → 
            ∃ λ σ → K Δ↝ σ × K ⊢ f ∶ (σ ⇒ τ)
⟨⟩-wt-inv (_⟨_⟩ {τ = σ} K⊢f∶σ⇒τ KΔ↝σ) = σ , (KΔ↝σ , K⊢f∶σ⇒τ)

uniq-type : ∀ {n m} {K : Ktx n m} {t τ τ'} → K ⊢ t ∶ τ → K ⊢ t ∶ τ' → τ ≡ τ'

-- excerpt from the typeof decision procedure
typeof : ∀ {n m} (K : Ktx n m) t → Dec (HasType K t)
typeof (Γ , Δ) (f ⟨⟩)   with typeof (Γ , Δ) f
typeof (Γ , Δ) (f ⟨⟩) | yes (σ ⇒ τ , _)     with (Δ-resolve (Γ , Δ) σ)
typeof (Γ , Δ) (f ⟨⟩) | yes (σ ⇒ τ , f∶φ) | no KΔ↝̸σ = 
  -- I'm trying to derive a contraction based on the fact that we've proven that
  -- K Δ↝̸ σ, but assuming a type for (f ⟨⟩) will yield an instance of K Δ↝ σ' (see ⟨⟩-wt-inv)
  -- the problem is that I don't know how to make agda see that σ' ≡ σ
  -- such that the following typechecks.
  -- (while agda will now complain that the σ in the wt-inv is not the
     same one as used in the KΔ↝̸σ instance, which is sensible)
  -- I think I have to use the uniq-type prove on f somewhere...
  no $ KΔ↝̸σ ∘ proj₁ ∘ proj₂ ⟨⟩-wt-inv ∘ proj₂

Любая помощь приветствуется

1 ответ

Решение

Сайзан на канале #agda был достаточно любезен, чтобы указать мне правильное направление: используя функцию subst использовать доказательство равенства для "замены" σ на σ в доказательстве того, что мне нужно было получить экземпляр KΔ↝σ из KΔ↝σ':

typeof (Γ , Δ) (f ⟨⟩) | yes (σ ⇒ τ , f∶φ) | no KΔ↝̸σ = 
  no $ KΔ↝̸σ ∘ helper
    where
      helper : (HasType (Γ , Δ) (f ⟨⟩)) → (Γ , Δ) Δ↝ σ
      helper p with (⟨⟩-wt-inv ∘ proj₂) p
      helper p | (σ' , KΔ↝σ' , f∶φ') = subst (λ s → (Γ , Δ) Δ↝ s) σ'≡σ KΔ↝σ' 
        where
          σ'≡σ : σ' ≡ σ
          σ'≡σ = ≡⇒dom $ uniq-type f∶φ' f∶φ 
Другие вопросы по тегам