形式陈述
设 A 是类型,B 是在 x : A 下良构的类型族。依赖类型 公理库 依赖类型 Dependent type 类型表达式可依赖项值的类型系统构造。 中的 Σ-formation、引入规则分别为
Γ ⊢ A type Γ , x : A ⊢ B type Γ ⊢ Σ ( x : A ) . B type , Γ ⊢ a : A Γ ⊢ b : B [ a / x ] Γ ⊢ ( a , b ) : Σ ( x : A ) . B . 第二个分量的类型不是原样的 B ,而是由第一个分量决定的 B [ a / x ] 。依赖消去须允许结果类型观察整对。若
Γ , z : Σ ( x : A ) . B ⊢ C ( z ) type 且
Γ , x : A , y : B ⊢ d : C ( ( x , y ) ) , 便有 split ( p ; x , y . d ) : C ( p ) ;其计算规则为
split ( ( a , b ) ; x , y . d ) ≡ d [ a / x , b / y ] : C ( ( a , b ) ) . 常用投影由消去子定义:fst ( p ) : A ,而 snd ( p ) : B [ fst ( p ) / x ] 。注意第二个投影的类型提到了第一个投影。某些理论采纳 Σ-η,使 p ≡ ( fst ( p ) , snd ( p ) ) ;另一些只给出恒等类型中的路径。替换同样必须穿过绑定器:( Σ ( x : A ) . B ) [ σ ] 按定义成为 Σ ( x : A [ σ ] ) . B [ σ + ] 。
当 x 不自由出现于 B 时,Σ 类型退化为普通积类型 公理库 积类型 Product type 其值由两个分量组成并支持投影的类型。 A × B 。这说明积是常纤维边界,不可反向用普通二元组的固定字段类型覆盖一般 Σ。
直觉
Σ 值是一份“带标签的货物”:第一分量给出标签 a ,第二分量必须来自标签指定的货架 B ( a ) 。打开包裹之后,两者要一起进入后续推理;如果丢掉标签,货物所属的类型也随之失去依据。普通积的两个字段彼此独立,所以任一投影都有预先固定的类型;依赖对则让第二项的静态意义随着第一项改变。
在命题解释下,Σ ( x : A ) . B ( x ) 对应“存在 x : A 使 B ( x ) ”,一对 ( a , b ) 同时给出见证与证据。但这是Curry–Howard 对应 公理库 Curry–Howard 对应 Curry–Howard correspondence · Propositions as types 把命题对应为类型、证明对应为程序、证明化简对应为程序求值。 所揭示的规则关系,不是经典逻辑存在量词的全部语义。构造一个 Σ 居民必须交付可用见证;从被截断的“仅知存在”通常不能恢复该见证,经典选择原则也不是 Σ 规则免费附送的结论。
例子与边界
设 Vec ( A , n ) 是长度索引向量,则
PackedVec ( A ) = Σ ( n : N ) . Vec ( A , n ) 把长度和对应向量封装在一起。若 a 0 , a 1 : A ,可以构造
p = ( 2 , cons a 0 ( cons a 1 nil ) ) : PackedVec ( A ) . 由投影计算得到 fst ( p ) ≡ 2 ,同时
snd ( p ) : Vec ( A , fst ( p ) ) ≡ Vec ( A , 2 ) . 定义 packedLength ( p ) = fst ( p ) 时只需固定结果类型 N ;定义返回“该包中向量确实具有所报长度”的证据时,motive 必须依赖 p ,这正是依赖消去与普通 pair destructuring 的差别。
边界例子是试图构造 ( 2 , nil ) 。因为 nil : Vec ( A , 0 ) ,除非理论中已有 0 与 2 的适当相等证据并显式运输,否则第二个引入前提失败。反过来,从任意 p : Σ ( n : N ) . Vec ( A , n ) 取出向量后若擦除 n ,得到的只是某种存在封装,不能再把它无证明地当作长度 5 的向量。Σ 类型也不自动等同于面向对象的动态类型包;后者还涉及表示擦除、运行时标签与开放世界子类型。
推论与应用
依赖对是证明携带数据、带尺寸容器、编译器中“语法项连同其推导”、数据库中带模式见证记录的基础接口。一个类型检查器可以返回 Σ ( A : U ) . TermOf ( A ) ,使推断出的类型与核心项不可分离;解析器可以返回输入长度及精确消费该长度的结果。只要后续函数对包使用依赖消去,索引信息就继续约束计算,而不会在拆包时退化为注释。
Σ 还把逐点见证组合成总结构:从 g : Π ( x : A ) . Σ ( y : B ( x ) ) . R ( x , y ) 可逐点投影出 f ( x ) = fst ( g ( x ) ) ,并由 snd ( g ( x ) ) 得到 Π ( x : A ) . R ( x , f ( x ) ) 。这正是未截断 Σ 保留见证时的构造性选择;若前提只有 Π ( x : A ) . ‖ Σ ( y : B ( x ) ) . R ( x , y ) ‖ ,则不能仅凭 Σ 规则消去截断并提取 f ,更不能把结论扩张成任意经典存在命题的选择公理。
参考资料
Per Martin-Löf, Intuitionistic Type Theory , Bibliopolis, 1984,dependent pair formation、elimination 与 computation rules。
Bengt Nordström, Kent Petersson, and Jan M. Smith, Programming in Martin-Löf’s Type Theory , Oxford University Press, 1990,dependent products、sets 与程序封装。
The Univalent Foundations Program, Homotopy Type Theory: Univalent Foundations of Mathematics , Institute for Advanced Study, 2013,§1.6,dependent pair types。