要理解 Display map category 的定義(參考 Categorical Logic and Type Theory, Definition 10.4.1),我們需要理解它的動機跟捕捉問題的方式,因此我們要觀察一個個相繼式(我假設讀者已經熟練相繼式定義的類型論),並用範疇論(category theory)的語言重述。
在用相繼式描述類型論時,公式
表示 可派生出類型 。對於所有 可派生的類型,我們用 表示,所以我們也會用 來表示上面的相繼式。Display map category 捕捉的第一件事就是 contexts 構成一個 category,我們用 記號表示這個範疇,並且我們要求 有 terminal object ,用來表示空的 context。
context 的構造方式只有兩種: 是一個 context;context 加入一個類型 得到的 還是 context。
因此 也常被稱為 telescope
在相繼式中如果我們寫
我們的意思是 ,對於每一個 ,都能找到 ,我們稱「 實現了 」。
但上面那樣寫有問題,因為 沒有憑依,因此正確的通用寫法是記錄成
這表示 參考 中的變數,並實現了 ,這叫做一個替換。
對 type 套用替換 [local-0]
對 type 套用替換 [local-0]
如果我們同時有 跟 ,那我們可以對 進行替換得到:
換句話說,我們用 完成了一個逆變,記成 。
對 term 套用替換 [local-1]
對 term 套用替換 [local-1]
用相繼式時
表示 在 中有類型 ,當然,這裡隱含的前提是 。
而替換同樣可以在 term 上作用:
對替換套用替換 [local-2]
對替換套用替換 [local-2]
但我們也知道替換 也能看成一個 term,所以同樣可以對它套用替換!
這說明了替換可以結合!我們經常記成 。
而很明顯的,對於所有 有一個「引用變數 來實現 的不變替換 」,所以我們想把每個替換 視為 中的 morphism 。這裡需要證明幾件事
- 對於給定的 ,可能的 的 collection 是一個集合。由於所有替換都涉及對 的引用(或是有限多的類型生成規則)並做出一個有限構造,所以可以用歸納的方式比較,這讓證明是唯一的,因此這些替換是 set
- 對 來說有 。根據定義就知道了
- 替換要有 associative 。這個不好證明,就我所知都是對規則進行 induction 得到(參考 Substitution Without Copy and Paste 的 §4.3)
現在我們要進入 Display map 的部分
Definition. Display map [local-3]
Definition. Display map [local-3]
對於 與 ,我們有 ,這叫做 display map。提醒一下這個相繼式是
考慮逆變,就得到
唯一確定了一個類型,也就是說現在每個 type 都被一個某一些替換代表了。這也可以說其實我們在看 這些 morphisms。
term 的表示 [local-4]
term 的表示 [local-4]
同理可以放到 term 上,對於
可以視為
也就是說每一個 term 都可以看成替換
到這裡我們發現,這個模型很好的捕捉了 syntactic categorical 的觀點,把類型論的句法特性都保留了下來。前面說過每個替換都有逆變,現在我們要證明逆變是一個 functor:
Proposition. 逆變是 functor [local-6]
Proposition. 逆變是 functor [local-6]
對於任何 ,我們把逆變看成 slice category 的函數 ,要檢查這是否是 functor,我們想要證明兩件事:保留 identity 且保留 composition。
Proof. [local-5]
Proof. [local-5]
套上 display maps 的規範,知道逆變會產出一個 pullback:
這直接證明了 ,所以 ,表示 保留了 identity。
要證明 composition,可以用 pullbacks 的結合知道如果 跟 的頂點 up to isomorphism 是同一個,因此這兩個 morphism 是一樣的,證明了也保留 composition。因此每個替換誘導出的逆變都是 functor。 □
既然 是個 functor,那在 display map category 裡,我們可以用 的 right adjoint 表示 product,而且加上 Beck-Chevalley 條件:存在一個 natural isomorphism,讓我們可以把 product 用替換推來推去而不會變成不同的東西。
weak sum 同理,只是變成 的 left adjoint,同樣要有 Beck-Chevalley 條件保證 coproduct 可以被推來推去而不遺失。strong sum 則是把條件強化到 display maps 組合一定是 display map,這蘊含 weak sum 條件。
我們前面完全沒有提到 這種形式,而確實這是 display map categorical 方法的額外條件:weak equality 用 diagonal 的 left adjoint 表示,還是用 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 的數種特徵,成功的讓我們用範疇論的觀點來檢視類型論。