OTT 中可证明的一致性
Provable coherence in OTT
我正在玩 observational type theory。
这里是π类型的等式（π是小写Π，即π A B是(x : A) -> B x的代码）相互定义强制：
π A₁ B₁ ≃ π A₂ B₂ = σ (A₂ ≃ A₁) λ P -> π _ λ x -> B₁ (coerce P x) ≃ B₂ x
和相应定义的函数相等（σ是小写Σ）：
_≅_ {A = π A₁ B₁} {π A₂ B₂} f₁ f₂ = σ (A₂ ≃ A₁) λ P -> π _ λ x -> f₁ (coerce P x) ≅ f₂ x
所以 "equal functions map equal inputs to equal outputs" 我们有 "equal functions map definitionally equal inputs to equal outputs".
在此设置中coherence
coerce : ∀ {α β} {A : Univ α} {B : Univ β} -> ⟦ A ≃ B ⟧ᵀ -> ⟦ A ⟧ᵀ -> ⟦ B ⟧ᵀ
coherence : ∀ {α β} {A : Univ α} {B : Univ β}
-> (P : ⟦ A ≃ B ⟧ᵀ) -> (x : ⟦ A ⟧ᵀ) -> ⟦ x ≅ coerce P x ⟧ᵀ
(Univ 0 是 Prop, Univ (suc α) 是 Type α)
是可以证明的。我唯一需要假设的是
postulate ≃-refl : ∀ {α} -> (A : Univ α) -> ⟦ A ≃ A ⟧ᵀ
但是我们可以调整等式来处理 A ≃ A 作为一个特殊情况（我认为，trustMe 需要一个朋友 _≟_ : ∀ {α} {A : Set α} (x y : A) -> Maybe (x ≡ y)）。
我们仍然需要假设一些东西来定义 subst 和其他东西。
我错过了什么吗？我们会失去任何无关紧要的东西吗？在函数相等的定义中提到类型相等似乎很可疑。通过将相等函数的输入限制为定义上相等，我们会损失很多吗？强归一化有什么好处 coherence 还是没关系，因为它在计算上无关紧要？
The code（我完全忽略了积极性、终止性和累积性问题）。
首先，感谢您询问有关观察类型理论的问题。其次，你在这里所做的 确实 似乎是连在一起的，尽管它与 Thorsten Altenkirch、Wouter Swierstra 和我把它们放在我们的故事版本中的地方不同。第三，连贯性是可推导的，这不足为奇（至少对我而言不是），让反身性成为唯一的假设。我们的 OTT 也是如此，当我们写那篇论文时，Wouter 在 Agda 1 中做了证明。证明无关紧要和生命的短暂意味着我没有将他的证明移植到 Agda 2。
如果您遗漏了什么，它就在您的评论中
We still need to postulate something to define subst and other stuff.
如果您有一些 P : X -> Set、一些 a, b : X 和一些 q : a = b，您希望在 P a -> P b 中获得一个函数。 "equal functions take equal inputs to equal outputs" 公式为您提供了 refl P : P = P，因此从 q，我们可以推断出 P a = P b。您的 "equal functions take a given input to equal outputs" 公式不允许您让 q 弥合从 a 到 b 的差距。
在 refl 和 subst 存在的情况下，"two equal inputs" 相当于 "one input used in two places"。在我看来，您已将工作转移到您需要获得 subst 的任何其他内容中。根据您对 coerce 的定义有多懒惰（以及 那 是您如何获得无关紧要的证明），您将只需要一个假设。
使用您的特定公式，您甚至可以摆脱 同质 值相等。如果您使用强制而不是等式来修复类型差距，您可能会为自己省去一些麻烦（并且可能会在函数相等性中摆脱域类型上的等式）。当然，在这种情况下，你需要考虑如何替换一致性声明。
我们非常努力地将强制转换排除在平等的定义之外，保留某种对称性，并将类型方程排除在价值方程之外，主要是为了一次性考虑更少。有趣的是，用 "a thing and its coercion" 替换 "two equal things".
至少可以使构造的某些部分变得更容易
我正在玩 observational type theory。
这里是π类型的等式（π是小写Π，即π A B是(x : A) -> B x的代码）相互定义强制：
π A₁ B₁ ≃ π A₂ B₂ = σ (A₂ ≃ A₁) λ P -> π _ λ x -> B₁ (coerce P x) ≃ B₂ x
和相应定义的函数相等（σ是小写Σ）：
_≅_ {A = π A₁ B₁} {π A₂ B₂} f₁ f₂ = σ (A₂ ≃ A₁) λ P -> π _ λ x -> f₁ (coerce P x) ≅ f₂ x
所以 "equal functions map equal inputs to equal outputs" 我们有 "equal functions map definitionally equal inputs to equal outputs".
在此设置中coherence
coerce : ∀ {α β} {A : Univ α} {B : Univ β} -> ⟦ A ≃ B ⟧ᵀ -> ⟦ A ⟧ᵀ -> ⟦ B ⟧ᵀ
coherence : ∀ {α β} {A : Univ α} {B : Univ β}
-> (P : ⟦ A ≃ B ⟧ᵀ) -> (x : ⟦ A ⟧ᵀ) -> ⟦ x ≅ coerce P x ⟧ᵀ
(Univ 0 是 Prop, Univ (suc α) 是 Type α)
是可以证明的。我唯一需要假设的是
postulate ≃-refl : ∀ {α} -> (A : Univ α) -> ⟦ A ≃ A ⟧ᵀ
但是我们可以调整等式来处理 A ≃ A 作为一个特殊情况（我认为，trustMe 需要一个朋友 _≟_ : ∀ {α} {A : Set α} (x y : A) -> Maybe (x ≡ y)）。
我们仍然需要假设一些东西来定义 subst 和其他东西。
我错过了什么吗？我们会失去任何无关紧要的东西吗？在函数相等的定义中提到类型相等似乎很可疑。通过将相等函数的输入限制为定义上相等，我们会损失很多吗？强归一化有什么好处 coherence 还是没关系，因为它在计算上无关紧要？
The code（我完全忽略了积极性、终止性和累积性问题）。
首先，感谢您询问有关观察类型理论的问题。其次，你在这里所做的 确实 似乎是连在一起的，尽管它与 Thorsten Altenkirch、Wouter Swierstra 和我把它们放在我们的故事版本中的地方不同。第三，连贯性是可推导的，这不足为奇（至少对我而言不是），让反身性成为唯一的假设。我们的 OTT 也是如此，当我们写那篇论文时，Wouter 在 Agda 1 中做了证明。证明无关紧要和生命的短暂意味着我没有将他的证明移植到 Agda 2。
如果您遗漏了什么，它就在您的评论中
We still need to postulate something to define
substand other stuff.
如果您有一些 P : X -> Set、一些 a, b : X 和一些 q : a = b，您希望在 P a -> P b 中获得一个函数。 "equal functions take equal inputs to equal outputs" 公式为您提供了 refl P : P = P，因此从 q，我们可以推断出 P a = P b。您的 "equal functions take a given input to equal outputs" 公式不允许您让 q 弥合从 a 到 b 的差距。
在 refl 和 subst 存在的情况下，"two equal inputs" 相当于 "one input used in two places"。在我看来，您已将工作转移到您需要获得 subst 的任何其他内容中。根据您对 coerce 的定义有多懒惰（以及 那 是您如何获得无关紧要的证明），您将只需要一个假设。
使用您的特定公式，您甚至可以摆脱 同质 值相等。如果您使用强制而不是等式来修复类型差距，您可能会为自己省去一些麻烦（并且可能会在函数相等性中摆脱域类型上的等式）。当然，在这种情况下，你需要考虑如何替换一致性声明。
我们非常努力地将强制转换排除在平等的定义之外，保留某种对称性，并将类型方程排除在价值方程之外，主要是为了一次性考虑更少。有趣的是，用 "a thing and its coercion" 替换 "two equal things".
至少可以使构造的某些部分变得更容易