证明用于子类型化、终止检查、`subst` 的反演引理
Proving inversion lemma for subtyping, termination checking, `subst`
我正在尝试证明 类型和编程语言 中的(第一部分)子类型引理。这是我目前所拥有的:
data Type : Set where
_=>_ : Type → Type → Type
Top : Type
data _<:_ : Type → Type → Set where
s-refl : {S : Type} → S <: S
s-trans : {S T U : Type} → S <: U → U <: T → S <: T
s-top : {S : Type} → S <: Top
s-arrow : {S₁ S₂ T₁ T₂ : Type} → T₁ <: S₁ → S₂ <: T₂ → S₁ => S₂ <: T₁ => T₂
lemma-inversion₁ : {S T₁ T₂ : Type}
→ S <: T₁ => T₂
→ ∃[ (S₁ × S₂) ∈ (Type & Type) ] ((S ≡ (S₁ => S₂)) & (T₁ <: S₁) & (S₂ <: T₂))
lemma-inversion₁ (s-refl {T₁ => T₂}) = (T₁ × T₂) , (refl × s-refl × s-refl)
lemma-inversion₁ (s-arrow {S₁} {S₂} T₁<:S₁ S₂<∶T₂) = (S₁ × S₂) , (refl × T₁<:S₁ × S₂<∶T₂)
lemma-inversion₁ (s-trans {S} S<:U U<:T₁=>T₂) with lemma-inversion₁ U<:T₁=>T₂
... | (U₁ × U₂) , (U≡U₁=>U₂ × T₁<:U₁ × U₂<:T₂) with lemma-inversion₁ (subst (S <:_) U≡U₁=>U₂ S<:U)
... | (S₁ × S₂) , (S≡S₁=>S₂ × U₂<:S₁ × S₂<:U₂) = (S₁ × S₂) , (S≡S₁=>S₂ × s-trans T₁<:U₁ U₂<:S₁ × s-trans S₂<:U₂ U₂<:T₂)
这对我来说是正确的,但我得到:
Termination checking failed for the following functions:
lemma-inversion₁
Problematic calls:
lemma-inversion₁ (s-trans S<:U U<:T₁=>T₂)
| lemma-inversion₁ U<:T₁=>T₂
lemma-inversion₁ U<:T₁=>T₂
lemma-inversion₁ (subst (_<:_ S) U≡U₁=>U₂ S<:U)
由于 subst
,Agda 似乎无法推断终止?那正确吗?有解决方法吗?
原来我需要在 refl
上进行模式匹配,如下所示:
... | (U₁ × U₂) , (refl × T₁<:U₁ × U₂<:T₂) with lemma-inversion₁ S<:U
这让 Agda 推断 U = U₁ => U₂
并且终止检查器很高兴。
我正在尝试证明 类型和编程语言 中的(第一部分)子类型引理。这是我目前所拥有的:
data Type : Set where
_=>_ : Type → Type → Type
Top : Type
data _<:_ : Type → Type → Set where
s-refl : {S : Type} → S <: S
s-trans : {S T U : Type} → S <: U → U <: T → S <: T
s-top : {S : Type} → S <: Top
s-arrow : {S₁ S₂ T₁ T₂ : Type} → T₁ <: S₁ → S₂ <: T₂ → S₁ => S₂ <: T₁ => T₂
lemma-inversion₁ : {S T₁ T₂ : Type}
→ S <: T₁ => T₂
→ ∃[ (S₁ × S₂) ∈ (Type & Type) ] ((S ≡ (S₁ => S₂)) & (T₁ <: S₁) & (S₂ <: T₂))
lemma-inversion₁ (s-refl {T₁ => T₂}) = (T₁ × T₂) , (refl × s-refl × s-refl)
lemma-inversion₁ (s-arrow {S₁} {S₂} T₁<:S₁ S₂<∶T₂) = (S₁ × S₂) , (refl × T₁<:S₁ × S₂<∶T₂)
lemma-inversion₁ (s-trans {S} S<:U U<:T₁=>T₂) with lemma-inversion₁ U<:T₁=>T₂
... | (U₁ × U₂) , (U≡U₁=>U₂ × T₁<:U₁ × U₂<:T₂) with lemma-inversion₁ (subst (S <:_) U≡U₁=>U₂ S<:U)
... | (S₁ × S₂) , (S≡S₁=>S₂ × U₂<:S₁ × S₂<:U₂) = (S₁ × S₂) , (S≡S₁=>S₂ × s-trans T₁<:U₁ U₂<:S₁ × s-trans S₂<:U₂ U₂<:T₂)
这对我来说是正确的,但我得到:
Termination checking failed for the following functions:
lemma-inversion₁
Problematic calls:
lemma-inversion₁ (s-trans S<:U U<:T₁=>T₂)
| lemma-inversion₁ U<:T₁=>T₂
lemma-inversion₁ U<:T₁=>T₂
lemma-inversion₁ (subst (_<:_ S) U≡U₁=>U₂ S<:U)
由于 subst
,Agda 似乎无法推断终止?那正确吗?有解决方法吗?
原来我需要在 refl
上进行模式匹配,如下所示:
... | (U₁ × U₂) , (refl × T₁<:U₁ × U₂<:T₂) with lemma-inversion₁ S<:U
这让 Agda 推断 U = U₁ => U₂
并且终止检查器很高兴。