Skip to content

依赖对类型

Dependent pair type · Sigma type · Σ-type

将索引与属于该索引纤维的见证共同封装,并以依赖拆对规则消费它们的 Σ 类型。

条目类型
定义

形式陈述

A 是类型,B 是在 x:A 下良构的类型族。依赖类型中的 Σ-formation、引入规则分别为

ΓAtypeΓ,x:ABtypeΓΣ(x:A).Btype,Γa:AΓb:B[a/x]Γ(a,b):Σ(x:A).B.

第二个分量的类型不是原样的 B,而是由第一个分量决定的 B[a/x]。依赖消去须允许结果类型观察整对。若

Γ,z:Σ(x:A).BC(z)type

Γ,x:A,y:Bd: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 时,Σ 类型退化为普通积类型 A×B。这说明积是常纤维边界,不可反向用普通二元组的固定字段类型覆盖一般 Σ。

直觉

Σ 值是一份“带标签的货物”:第一分量给出标签 a,第二分量必须来自标签指定的货架 B(a)。打开包裹之后,两者要一起进入后续推理;如果丢掉标签,货物所属的类型也随之失去依据。普通积的两个字段彼此独立,所以任一投影都有预先固定的类型;依赖对则让第二项的静态意义随着第一项改变。

在命题解释下,Σ(x:A).B(x) 对应“存在 x:A 使 B(x)”,一对 (a,b) 同时给出见证与证据。但这是Curry–Howard 对应所揭示的规则关系,不是经典逻辑存在量词的全部语义。构造一个 Σ 居民必须交付可用见证;从被截断的“仅知存在”通常不能恢复该见证,经典选择原则也不是 Σ 规则免费附送的结论。

例子与边界

Vec(A,n) 是长度索引向量,则

PackedVec(A)=Σ(n:N).Vec(A,n)

把长度和对应向量封装在一起。若 a0,a1:A,可以构造

p=(2,consa0(consa1nil)):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),除非理论中已有 02 的适当相等证据并显式运输,否则第二个引入前提失败。反过来,从任意 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。
关系图谱8 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组