是否可以在具有简单不一致公理的构造微积分上提取 Sigma 的第二个元素？

Question

seems to be impossible 提取构造微积分中 Sigma 的第二个元素。此外，似乎没有已知的简单方法可以在不失去一致性的情况下通过相关消去扩展构造微积分。因此，如何利用一个简单的 但不一致的 公理（例如 Type : Type 或不受限制的递归，例如 μ）来提取 Sigma 的第二个元素？

也就是说，给定以下 Sigma 构造函数：

Sigma =
  λ A : *
  λ B : A -> *
  λ a : A
  λ b : B
  λ Data : *
  λ Sigma :
    ∀ fst : A
    ∀ snd : B fst
    Data
  Sigma a b

在等同于构造微积分的语言中，除了 Type : Type 或其他一些简单的不一致公理外，是否有可能实现一个函数，给定诸如 Sigma Nat (\x -> Nat) 3 6 之类的项，提取第二个值，6?

Answer 1

在 Martin-Löf 类型理论或构造微积分等类型理论的背景下，"inconsistency" 我们通常指的是 逻辑不一致 ：能够导出 forall T : Type, T 类型的项 contra。在这种情况下，任何其他类型 T 都会有人居住：对其应用 contra 就足够了。

不幸的是，在大多数类型理论中，有人居住并没有告诉我们任何关于可转换性或定义相等性的信息，因为没有类型表示两个术语 x 和 y 是可转换的。这表示无法推导出项

fst : Sigma A B -> A
snd : forall s : Sigma A B, B (fst s)

这样 fst (Sigma _ _ x y) 简化为 x 和 snd (Sigma _ _ x y) 通过诉诸逻辑矛盾简化为 y。（我有点滥用符号，对构造函数和类型都使用 Sigma。）但是，您可以使用 contra 来假设 fst 和 snd 的存在并断言相应的方程命题.

成立

在普通 CoC 中，如果存在

类型的项，我们说两个项 x1 和 x2 在命题上相等

forall T, T x1 -> T x2

（这有时被称为莱布尼茨等式：如果每个谓词都满足第一个谓词，则两个谓词相等。）为 snd 陈述一个相似点有点复杂，因为 snd (Sigma _ _ x y)和y的类型不同（前者是B (fst (Sigma _ _ x y))类型，后者是B x类型）。我们可以通过同时断言 fst 和 snd 的简化引理来解决这个问题：

forall (T : forall x : A, B x -> Type),
  T (fst (Sigma _ _ x y)) (snd (Sigma _ _ x y)) -> 
  T x y

编辑

关于您的评论：由于可转换性通常不能用类型来表达，我们需要修改其在类型论中的定义，以具有具有第一和第二投影的真正 sigma 类型——比简单地假设更精细的操作某些公理成立。有一些系统允许这样做，例如 Dedukti，Inria 开发的证明检查器。

是否可以在具有简单不一致公理的构造微积分上提取 Sigma 的第二个元素？

Is it possible to extract the second element of Sigma on the calculus of constructions with simple inconsistent axioms?

haskell

functional-programming

coq

agda

idris

编辑