24.3 递归高阶归纳类型

高阶归纳类型的递归实现

传统HIT的构造限制

传统高阶归纳类型(HIT)通过点构造子和路径构造子定义拓扑空间，但构造规则是外在给定的。递归理论提供了HIT的内在递归生成机制。

递归高阶归纳类型的定义

定义 24.3.1（递归高阶归纳类型） 递归HIT通过递归构造子定义：

data A^R : U^R where
  point-constructors^R : ... → A^R
  path-constructors^R : ... → (x =_{A^R}^R y)
  higher-path-constructors^R : ... → (p =_{x=y}^R q)
  ...
  recursive-constraint^R : 满足递归约束

递归圆周类型

递归$S^1$的定义：

data S¹^R : U^R where
  base^R : S¹^R
  loop^R : base^R =_{S¹^R}^R base^R
  
  recursive-constraint^R : 
    loop^R ∘^R loop^R = η^R(2; 0) · loop^R

递归圆周的递归原理： $$S^1{\text{-rec}}^{(R)}:\prod _{P:S^1\to {\mathcal{U}}^{(R)}}P({\text{base}}^{(R)})\to ({\text{transport}}^{(R)}(P,{\text{loop}}^{(R)},p)=p)\to \prod _{x:S^1}P(x)$$

递归winding number： $${\text{wind}}^{(R)}:S^1\to {\mathbb{Z}}^{(R)}$$ $${\text{wind}}^{(R)}({\text{base}}^{(R)}):=0^{(R)}$$ $$\text{ap}({\text{wind}}^{(R)},{\text{loop}}^{(R)})={\eta }^{(R)}(1;0)$$

递归高维球面

递归$S^n$的定义：

data Sⁿ^R : U^R where
  north^R : Sⁿ^R
  south^R : Sⁿ^R  
  meridian^R : (x : Sⁿ⁻¹^R) → north^R =_{Sⁿ^R}^R south^R
  
  recursive-constraint^R :
    meridian^R(x) ∘^R meridian^R(y) = 
    η^R(n; 0) · meridian^R(recursive-compose^R(x,y))

递归Hopf fibration： $${\text{Hopf}}^{(R)}:S^3{\to }^{(R)}{S}^2$$

通过递归四元数构造实现。

递归悬挂类型

递归悬挂的HIT定义：

data Susp^R (A : U^R) : U^R where
  north^R : Susp^R A
  south^R : Susp^R A
  meridian^R : A → (north^R =_{Susp^R A}^R south^R)
  
  recursive-constraint^R :
    ∀ a b : A, meridian^R(a) ∘^R meridian^R(b) = 
    η^R(|path|; 0) · meridian^R(recursive-join^R(a,b))

递归悬挂函子： $${\Sigma }^{(R)}:{\mathcal{U}}^{(R)}\to {\mathcal{U}}^{(R)}$$

递归悬挂的函子性： $${\Sigma }^{(R)}(f):{\Sigma }^{(R)}A{\to }^{(R)}{\Sigma }^{(R)}B$$

递归商类型

递归集合商： 对于递归等价关系$R:A\to A\to {\text{Prop}}^{(R)}$：

data A/R^R : U^R where
  class^R : A → A/R^R
  eq^R : ∀ a b : A, R(a,b) → class^R(a) =_{A/R^R}^R class^R(b)
  
  recursive-constraint^R : 
    eq^R 满足递归传递性和递归对称性

递归商的universal性质： $${\text{rec}}_{A/R}^{(R)}:\prod _{B:{\mathcal{U}}^{(R)}}(f:A\to B)\to (\prod _{a,b:A}R(a,b)\to f(a)=f(b))\to (A/R{\to }^{(R)}B)$$

递归pushout类型

递归pushout的HIT定义：

data Pushout^R {A B C : U^R} (f : A → B) (g : A → C) : U^R where
  inl^R : B → Pushout^R f g  
  inr^R : C → Pushout^R f g
  glue^R : ∀ a : A, inl^R(f(a)) =_{Pushout^R}^R inr^R(g(a))
  
  recursive-constraint^R :
    glue^R 满足递归自然性和递归结合性

递归van Kampen定理： $${\pi }_1^{(R)}({\text{Pushout}}^{(R)}(f,g)){\cong }^{(R)}{\pi }_1^{(R)}(B){\ast }_{{\pi }_1^{(R)}(A)}{\pi }_1^{(R)}(C)$$

递归截断类型

递归n-截断： $$\Vert A{\Vert }_n^{(R)}:{\mathcal{U}}^{(R)}$$

是$A$的递归$n$-类型化：

data ‖A‖ₙ^R : U^R where
  |_|^R : A → ‖A‖ₙ^R
  hub^R : ∀ f : Sⁿ⁺¹^R → ‖A‖ₙ^R, ‖A‖ₙ^R
  spoke^R : ∀ f x, hub^R(f) =_{‖A‖ₙ^R}^R f(x)
  
  recursive-constraint^R : 满足递归截断性质

递归截断的universal性质： $$\Vert \cdot {\Vert }_n^{(R)}:{\mathcal{U}}^{(R)}\to n{\text{-Type}}^{(R)}$$

是左伴随函子。

递归实数类型

递归Cauchy实数： 基于递归Cauchy序列的HIT构造：

data ℝ^R : U^R where
  rat^R : ℚ^R → ℝ^R
  lim^R : (s : ℕ^R → ℚ^R) → isCauchy^R(s) → ℝ^R  
  eq^R : ∀ s t, cauchy-equiv^R(s,t) → lim^R(s) =_{ℝ^R}^R lim^R(t)
  
  recursive-constraint^R : 满足递归完备性

递归实数的性质：

• 递归完备性：每个Cauchy序列收敛
• 递归阿基米德性：$\forall x:{\mathbb{R}}^{(R)},\exists n:{\mathbb{N}}^{(R)},|x|<n$
• 递归连续性：基于递归ε-δ定义

递归集合论基础

递归集合的HIT实现：

data Set^R : U^R where
  ∅^R : Set^R
  singleton^R : Set^R → Set^R
  union^R : Set^R → Set^R → Set^R
  
  recursive-axioms^R : 满足递归ZF公理

递归ordinal： 通过递归良基关系定义： $${\text{Ord}}^{(R)}:=\{A:{\mathcal{U}}^{(R)}\mid {\text{isWellOrdered}}^{(R)}(A)\}$$

递归分类空间

递归Eilenberg-MacLane空间： $$K(G^{(R)},n):{\mathcal{U}}^{(R)}$$

满足： $${\pi }_k^{(R)}(K(G,n))=\{\begin{array}{ll}{G}^{(R)}& k=n\\ 1^{(R)}& k\ne n\end{array}$$

递归Brown表示定理： $$[X,K(G^{(R)},n){]}^{(R)}{\simeq }^{(R)}{H}^n(X;G^{(R)})$$

递归HIT的计算语义

递归计算规则

递归β-规则： HIT的递归器在点构造子上的计算： $${\text{rec}}^{(R)}(c,e,{\text{point}}^{(R)}){\equiv }^{(R)}c$$

递归β-path规则： 在路径构造子上的计算： $$\text{ap}({\text{rec}}^{(R)}(c,e),{\text{path}}^{(R)}){\equiv }^{(R)}e$$

递归同调计算

递归球面的同调： $$H_k^{(R)}(S^n)=\{\begin{array}{ll}{\mathbb{Z}}^{(R)}& k=0,n\\ 0^{(R)}& \text{otherwise}\end{array}$$

递归复投影空间： $$\mathbb{C}{P}^n=S^{2n+1}/S^1$$

的递归同调： $$H_{2k}^{(R)}(\mathbb{C}{P}^n)={\mathbb{Z}}^{(R)},0\le k\le n$$

递归cohomology理论

递归deRham cohomology： 基于递归微分形式的cohomology理论，连接第17章递归微分几何。

递归étale cohomology： 为递归代数几何提供上同调工具。

递归HIT的哲学深度

递归高阶归纳类型揭示了构造的递归本质：

• 构造不是人工操作：而是递归过程的自然表现
• 归纳不是逻辑技巧：而是递归生成的内在机制
• 高阶不是抽象层次：而是递归深度的自然展开

HIT的每个构造子都对应递归系统自我构造的一个方面，高阶路径对应递归自指的不同层次。

递归HIT的数学完备性

第24.3节完成了拓扑空间在类型论中的递归表示：

• 所有CW复形都有递归HIT表示
• 所有拓扑不变量都可以递归计算
• 所有同伦等价都有递归类型解释

这为数学提供了最自然、最统一的递归基础：所有数学对象都是递归类型，所有数学关系都是递归路径，所有数学证明都是递归构造。