« Home

Display map category 捕捉了類型論的什麼面向? [tt-BBGG]

要理解 Display map category 的定義(參考 Categorical Logic and Type Theory, Definition 10.4.1),我們需要理解它的動機跟捕捉問題的方式,因此我們要觀察一個個相繼式(我假設讀者已經熟練相繼式定義的類型論),並用範疇論(category theory)的語言重述。

在用相繼式描述類型論時,公式

ΓA type\Gamma \vdash A \text{ type}

表示 Γ\Gamma 可派生出類型 AA。對於所有 Γ\Gamma 可派生的類型,我們用 Ty(Γ)Ty(\Gamma) 表示,所以我們也會用 ATy(Γ)A \in Ty(\Gamma) 來表示上面的相繼式。Display map category 捕捉的第一件事就是 contexts 構成一個 category,我們用 C\mathcal{C} 記號表示這個範疇,並且我們要求 C\mathcal{C} 有 terminal object \diamond,用來表示空的 context。

context 的構造方式只有兩種:\diamond 是一個 context;context Γ\Gamma 加入一個類型 AA 得到的 ΓA\Gamma \triangleright A 還是 context。

因此 ΓAB\Gamma \triangleright A \triangleright B \triangleright \cdots 也常被稱為 telescope

在相繼式中如果我們寫

σ:Δ\sigma : \Delta

我們的意思是 Δ=T1Tk\Delta = \diamond \triangleright T_1 \triangleright \cdots \triangleright T_k,對於每一個 TiT_i,都能找到 σi:Ti\sigma_i : T_i,我們稱「σ\sigma 實現了 Δ\Delta」。

但上面那樣寫有問題,因為 σ\sigma 沒有憑依,因此正確的通用寫法是記錄成

Γσ:Δ\Gamma \vdash \sigma : \Delta

這表示 σ\sigma 參考 Γ\Gamma 中的變數,並實現了 Δ\Delta,這叫做一個替換。

對 type 套用替換 [local-0]

如果我們同時有 Γσ:Δ\Gamma \vdash \sigma : \DeltaΔA type\Delta \vdash A \text{ type},那我們可以對 AA 進行替換得到:

ΓA[σ] type\Gamma \vdash A[\sigma] \text{ type}

換句話說,我們用 σ\sigma 完成了一個逆變,記成 σ:Ty(Δ)Ty(Γ)\sigma^* : Ty(\Delta) \to Ty(\Gamma)

對 term 套用替換 [local-1]

用相繼式時

Γu:A\Gamma \vdash u : A

表示 uuΓ\Gamma 中有類型 AA,當然,這裡隱含的前提是 ATy(Γ)A \in Ty(\Gamma)

而替換同樣可以在 term uu 上作用:

Γσ:ΔΔu:AΓu[σ]:A[σ]\frac{ \Gamma \vdash \sigma : \Delta \quad \Delta \vdash u : A }{ \Gamma \vdash u[\sigma] : A[\sigma] }

對替換套用替換 [local-2]

但我們也知道替換 σ\sigma 也能看成一個 term,所以同樣可以對它套用替換!

Γσ:ΓΓγ:ΓΓγ[σ]:Γ\frac{ \Gamma \vdash \sigma : \Gamma' \quad \Gamma' \vdash \gamma : \Gamma'' }{ \Gamma \vdash \gamma[\sigma] : \Gamma'' }

這說明了替換可以結合!我們經常記成 γσ\gamma \circ \sigma

而很明顯的,對於所有 Γ=T1Tk\Gamma = \diamond \triangleright T_1 \triangleright \cdots \triangleright T_k 有一個「引用變數 Γi\Gamma_i 來實現 TiT_i 的不變替換 idΓid_\Gamma」,所以我們想把每個替換 σ\sigma 視為 C\mathcal{C} 中的 morphism σ:ΓΔ\sigma : \Gamma \to \Delta。這裡需要證明幾件事

  1. 對於給定的 Γ,Δ\Gamma, \Delta,可能的 ΓΔ\Gamma \to \Delta 的 collection 是一個集合。由於所有替換都涉及對 Γ\Gamma 的引用(或是有限多的類型生成規則)並做出一個有限構造,所以可以用歸納的方式比較,這讓證明是唯一的,因此這些替換是 set
  2. f:ΓΔf : \Gamma \to \Delta 來說有 fidΓ=f=idΔff \circ id_\Gamma = f = id_\Delta \circ f。根據定義就知道了
  3. 替換要有 associative f(gh)=(fg)hf \circ (g \circ h) = (f \circ g) \circ h。這個不好證明,就我所知都是對規則進行 induction 得到(參考 Substitution Without Copy and Paste 的 §4.3)

現在我們要進入 Display map 的部分

Definition. Display map [local-3]

對於 Γ\GammaATy(Γ)A \in Ty(\Gamma),我們有 πA:ΓAΓ\pi_A : \Gamma\triangleright A \to \Gamma,這叫做 display map。提醒一下這個相繼式是

Γ,AπA:Γ\Gamma, A \vdash \pi_A : \Gamma

考慮逆變,就得到

πA:Ty(Γ)Ty(ΓA)\pi_A^* : Ty(\Gamma) \to Ty(\Gamma \triangleright A)

唯一確定了一個類型,也就是說現在每個 type AA 都被一個某一些替換代表了。這也可以說其實我們在看 HomC(,Γ)Hom_\mathcal{C}(- , \Gamma) 這些 morphisms。

term 的表示 [local-4]

同理可以放到 term uu 上,對於

Γu:A\Gamma \vdash u : A

可以視為

Γ(idΓ,u):(Γ,A)\Gamma \vdash (id_\Gamma, u) : (\Gamma, A)

也就是說每一個 term uu 都可以看成替換

Γ(idΓ,u)ΓA\Gamma \xrightarrow{(id_\Gamma, u)} \Gamma \triangleright A

到這裡我們發現,這個模型很好的捕捉了 syntactic categorical 的觀點,把類型論的句法特性都保留了下來。前面說過每個替換都有逆變,現在我們要證明逆變是一個 functor:

Proposition. 逆變是 functor [local-6]

對於任何 σ:ΔΓ\sigma : \Delta \to \Gamma,我們把逆變看成 slice category 的函數 C/ΓC/Δ\mathcal{C} / \Gamma \to \mathcal{C} / \Delta,要檢查這是否是 functor,我們想要證明兩件事:保留 identity 且保留 composition。

Proof. [local-5]

套上 display maps 的規範,知道逆變會產出一個 pullback:

figure tex2116

這直接證明了 σσ(id)=σ\sigma \circ \sigma^*(id) = \sigma,所以 σ(id)=idΔ\sigma^*(id) = id_\Delta,表示 σ\sigma^* 保留了 identity。

要證明 composition,可以用 pullbacks 的結合知道如果 σ(f)σ(g)\sigma^*(f) \circ \sigma^*(g)σ(fg)\sigma^*(f \circ g) 的頂點 up to isomorphism 是同一個,因此這兩個 morphism 是一樣的,證明了也保留 composition。因此每個替換誘導出的逆變都是 functor。

既然 σ\sigma^* 是個 functor,那在 display map category 裡,我們可以用 σ\sigma^* 的 right adjoint 表示 product,而且加上 Beck-Chevalley 條件:存在一個 natural isomorphism,讓我們可以把 product 用替換推來推去而不會變成不同的東西。

weak sum 同理,只是變成 σ\sigma^* 的 left adjoint,同樣要有 Beck-Chevalley 條件保證 coproduct 可以被推來推去而不遺失。strong sum 則是把條件強化到 display maps 組合一定是 display map,這蘊含 weak sum 條件。

我們前面完全沒有提到 Γa=a:A\Gamma \vdash a = a : A 這種形式,而確實這是 display map categorical 方法的額外條件:weak equality 用 diagonal 的 left adjoint EqπAEq_{\pi_A} 表示,還是用 Beck-Chevalley 條件避免遺失。strong equality 規定 diagonal 是 display map,蘊含 weak equality。

對細節有興趣的讀者可以看 Paige Randall North 的 slide:Homotopical models of type theory

現在我們看到,display map category 除了捕捉 type theory 的 syntactic 特性,還可以用直觀的範疇論語言表述 type theory 的數種特徵,成功的讓我們用範疇論的觀點來檢視類型論。