型別論

型別論，數學、邏輯和電腦科學以下的一個分支，是研究不同型別系統及其表達形式的學科。某些型別系統適合用作數學基礎，取代數學家一般使用的集合論，其中最具影響力的有阿隆佐·邱奇的有型別λ演算和佩爾·馬丁-洛夫的直覺型別論。許多函式語言和工具都建立在型別論的基礎上，如Agda、Coq、Idris、Lean等等。型別論的核心概念是，每一條合乎語法規則的表示式的集合，它的定義純粹就是指定其所含的所有元素。在型別論中，這些結構的定義並不羅列屬於它的所有項，而是指定如何建構它的項的一套規則。集合論建基於一階邏輯，有「集合」和「命題」兩個主要概念。任何一套集合論公理和命題都是以一階邏輯的語言所表達。型別論則只有「型別」的概念，每一條邏輯命題都是一個型別。要證明任何一條命題，就需要建構屬於此型別的項，是為命題為型別原理。換言之，證明定理的過程只不過是建構符合指定數學結構的數學物件的過程的一個特例。概覽.型別論有許多種，底下更細分許多變體，本文只能以直覺型別論為例做基本的入門介紹，而不詳細羅列每一種變體。項與型別.在型別論中，每一個數學物件都有其所屬的型別。每次加入新的變數時，必須同時指定其所屬的型別。舉例說，「設"x"為自然數」可寫作formula_1讀作「項"x"的型別是formula_2」。這在形式上似乎和集合論中的formula_3無所差異，但後者是一階邏輯中具備真值的一條「命題」，而前者則是一個純粹的「斷言」，並不是一條有待證明的命題。型別建構規則.每一種型別論都指定了如何建構新型別的一套規則，透過這些規則所得出的式子都是合理的斷言，不須證明。以下歸納每一個新型別定義的組成部分：以上是型別論的基本規則，可理解為型別論的語法，它並不包含數學公理。這和集合論有所不同：除了一階邏輯本身的推理規則以外，集合論還加入了一組有關集合的公理。最基本的型別論不需公理即可當做邏輯和數學推理使用，但在有需要時，同樣也可以加上額外的公理。型別論中的公理是不透過建構規則而接納的斷言，因此有些公理會產生無法透過運算規則簡化的式子，從而影響該型別系統的可計算性。常見型別.以下列出幾種常見的基本型別，除了全類和函式型別以外，它們都是最後介紹的的特例。這些型別既可以表達數學結構，又可以表達命題。型別的項可以是某個數學結構的成員，也可以是某條命題的證明。這就是命題為型別原理。全類.型別論規定，在介紹新的符號時，必須馬上指定它的型別，如「設formula_5」。同樣，當我們說「設"A"為型別」的時候也一樣要指定"A"自己的型別。然而，"A"本身就已經是一個型別，那麼型別的型別是甚麼？型別論中有「全類」的概念，每個全類的項都是型別。由於全類本身也是一個型別，如果所有型別都屬於同一個全類的話，就不可避免產生。因此，型別論一般都會假設存在無限層全類，記作𝒰0, 𝒰1, 𝒰2，如此類推。每一層全類都是它上一層全類的項：𝒰"i" : 𝒰"i"+1。「設"A"為型別」的意思其實是「設"A" : 𝒰"i"」，其中層級"i"可以明確指定，但一般可以從前文後理推斷出來，所以下標往往省略不寫。同理，當我們說「對於所有型別"A"」，意思其實是「對於所有第"i"層全類下的型別"A"」。有些型別系統規定，𝒰"i"下的所有項也是𝒰"i"+1的項，這種累積性屬性對設計一個型別系統來說有利有弊，在此並不詳述。以上解釋的是羅素式全類。塔斯基式全類是另一種繞過悖論的方法，它主張每個"A" : 𝒰要經過一個明確的強制轉換函式才能成為一個型別El("A")。函式型別.型別論將函式視為一種基礎型別，而不像集合論一樣定義為笛卡爾積的符合某些規定的子集。每一個函式都屬於一個型別：假設"A", "B"為型別，可以建構函式型別"A" → "B"。要定義這一型別的某個項，共有兩種方法。第一種是直接定義：先給函式取名，例如"f"，然後對於任意項"a" : "A"，將"f"("a")定義為一條可能含有"a"並且型別為"B"的公式Φ。"f"的定義可以讀成「給我任何一個"a" : "A"，我都可以給你一個Φ : "B"」。另一種方法是λ抽象化，直接寫(λ ("a" : "A"), Φ) : "A" → "B"，避開給函式取名。從命題為型別原理的角度來看，函式可以用來表達邏輯蘊涵。假如"p", "q"分別是代表命題的型別，那麼"p" → "q"就代表了「當"p"為真，則"q"為真」這一命題。要證明此命題，對於"p"的每個項，須給出"q"的一個項。依賴型別.依賴函式型別，又稱Π型別，是普通函式型別的推廣，使得函式的到達域型別可以依賴於輸入值。對於任何型別"A"和一族型別"B" : "A" → 𝒰，都可以建構依賴型別formula_6要定義依賴型別的某個項，同樣有兩種方法。直接定義：取名"f"，對於任意項"a" : "A"，將"f"("a")定義為一條可能含有"a"並且型別為"B"("a")的公式Φ。λ抽象化：直接寫formula_7假如"A"是任意型別而"p" : "A" → 𝒰是一族代表命題的型別，那麼formula_8就代表了「對於所有"a" : "A"，"p"("a")為真」這一命題。空型別.空型別記作⊥或0，它沒有任何相應的建構式，也就是說，它沒有任何項。空型別的消去規則是，對於任何型別"A"，都有一個函式false_elim : ⊥ → "A"。根據命題為型別原理，空型別可以詮釋為「假」命題，它不存在任何證明。設"p"為代表命題的型別，則"p" → ⊥代表「非"p"」這一命題，記作¬"p"。假設⊥有一個項"h"，而"p"為任何代表命題的型別，那麼透過空型別的消去規則就可以得出false_elim "h" : "p"。這意味著無論甚麼命題都可以證明是真的，是為爆炸原理。單值型別.單值型別記作⊤或1，它只有一條建構式，因此只含唯一的單個項，記作「∗ : 1」。假如有一個函式"f" : 1 → "A"，則可以說"A"有一個項"f"(∗)，亦稱「"A"是有棲居物件的型別」。雙值型別.雙值型別記作formula_9或2，它有兩條構件式，因此有兩個項，記作「02, 12 : 2」。雙值型別就是函數語言程式設計中的布林，其兩個項可以分別理解為「如果假」和「如果真」兩個情況。函式"f" : 2 → "A"可以理解為「如果真，輸出"f"(12) : "A"，否則輸出"f"(02) : "A"」。積型別.積型別所表達的是有序對的概念。從兩個型別"A", "B"可以建構出它們的積型別"A" × "B"。它有一條建構式：從兩個項"a" : "A"和"b" : "B"可以建構出積型別的項("a", "b") : "A" × "B"。對應於每一個函式"g" : "A" → ("B" → "C")，都有一個函式"f" : "A" × "B" → "C"。積型別可以詮釋為邏輯與：假如型別"A", "B", "C"都是命題，則函式"f" : "A" × "B" → "C"可以理解為「假如同時有"A"的證明和"B"的證明，就可以用"f"得出"C"的證明」。更簡短地說，「"A"與"B"為真時，則"C"為真」。餘積型別.餘積型別所表達的是不交並的概念。從兩個型別"A", "B"可以建構出它們的餘積型別"A" + "B"。它有兩條建構式：從一個項"a" : "A"可以建構出inl("a") : "A" + "B"，從一個項"b" : "B"則可以建構出inr("b") : "A" + "B"。要建構函式"f" : "A" + "B" → "C"，須指定兩個函式"g"0 : "A" → "C"和"g"1 : "B" → "C"，使得"f"(inl("a"))定義為"g"0(a)，"f"(inr("b"))定義為"g"1(b)。餘積型別可以詮釋為邏輯或：假如型別"A", "B", "C"都是命題，則函式"f" : "A" + "B" → "C"可以理解為「假如有"A"的證明，或者有"B"的證明，只需其一就可以用"f"得出"C"的證明」。更簡短地說，「"A"或"B"為真時，則"C"為真」。上文介紹的雙值型別可視為餘積型別的特例，等同於1 + 1。依賴對型別.依賴對型別，又稱Σ型別，是積型別的推廣，使得每個項("a", "b")中的第二個物件"b"的型別可以依賴於"a"。對於任何型別"A"和一族型別"B" : "A" → 𝒰，可以建構依賴對型別formula_10它的項的格式是("a", "b")，其中"a" : "A"，而"b" : "B"("a")。假如"A"是任意型別而"p" : "A" → 𝒰是一族代表命題的型別，那麼formula_11就代表了「存在"a" : "A"使得"p"("a")為真」這一命題。值得注意的是，這種存在比經典數學中的存在更強，因為型別論要求我們明確提供見證"p"("a")為真的那個項"a"，而經典數學則無此要求。這意味著，最純粹的型別論表達的是一種構成主義數學。透過引入各種公理，如排中律和選擇公理，型別論仍然可以靈活地表達非構成主義的經典數學。自然數.型別論一般按照皮亞諾算術來定義自然數formula_2。它共有兩條建構式：任何自然數，要麼是0，要麼是某個自然數的後繼。一、二、三分別表達為formula_17、formula_18、formula_19，如此類推。要定義某個函式formula_20，須指定一個起始項"g"0 : "A"以及一個「下一步」函式formula_21，使得"f"(0)定義為"g"0，並且對於任何formula_5，formula_23定義為formula_24，也就是以0為起始點利用數學歸納法做一個遞迴性的定義。比如，以下是「奇偶」函式formula_25的定義：這裡我們也用到了雙值型別2的消去式。其他常見函式，例如「雙倍」函式formula_32以及加法formula_33等二元運算都有類似的定義。等同型別.型別論有至少三種可以理解為「等同」的概念。第一種是「符號等同」，又稱「從定義上等同」，例如用1定義為代替formula_17的符號，這記作formula_35。自然數一節中的「定義為」就屬於此種等同，也可以用:≡表示。這種等同是為了給符號賦予含義，但它本身不含任何額外的數學意義。第二種是「斷言等同」，即在展開兩個符號的定義，並用型別論建構規則運算以後，兩者的公式完全吻合，記作「"a" ≡ "b"」。例如，透過oddeven的定義，可做運算：formula_36若"a" ≡ "b"，則在任何式子中出現的"a"都可以直接替換為"b"。此種等同屬於斷言，並不是邏輯命題，而是重複應用型別論語法規則後所得的符號等同。在型別論中，不允許說「假設"a" ≡ 1」，因為在設符號formula_37的時候，如果還沒有給"n"賦予定義值，那就應該做定義「"a" :≡ 1」；反之如果"n"已經被賦予定義值，那就輪不到我們假設其數值。假如將型別論的規則視為某種代數系統，那麼斷言等同就正是該系統中的普通等同關係，類似於一個群的元素之間的等同。第三種是「命題等同」。有時，兩條公式就算在展開定義和運算之後，仍然不完全吻合，但它們具有相同的語義。舉例來說，對於所有formula_5，"n" + 1和1 + "n"這兩條公式無論如何運算都不會斷言等同，因為自然數加法的定義本身就區分先後順序。故此，我們不能寫「對於所有formula_5，"n" + 1 ≡ 1 + "n"」。然而，對於任何特定的自然數"n"，例如2，我們可以透過運算得出「2 + 1 ≡ 1 + 2」。這種從定義上不同但從含義上相同的現象，正正就是內涵和外延之分，邏輯學家戈特洛布·弗雷格稱之為之分。針對這第三種等同關係，型別論有一種意義重大的「等同型別」。對於任何兩條型別相同的公式"p", "q" : "A"，都有一個型別Id"A"("p", "q")，指的是「"p"等於"q"」這一命題。在不怕混淆的情況下，可以使用更熟悉的寫法「"p" ="A" "q"」，其中型別下標"A"往往可以省略。根據命題為型別原理，要證明此命題，就必須提供它的項。等同型別只有一條建構式：對於任何項"a" : "A"，可以建構refl"a" : "a" ="A" "a"，稱為「自反」。由於斷言等同的公式都可以隨意互換，所以只要有"a" ≡ "b"，那就自動有"a" ="A" "b"。要證明「對於所有formula_5，"n" + 1 = 1 + "n"」這一命題，就必須給出這樣的項：formula_41要建構這樣的項，須展開1和加號的定義，然後結合利用依賴型別、自然數和等同型別的建構和消去式。再舉一例，formula_42也是一條合乎語法的等同型別，但它所代表的是一條假命題，所以它不含任何項。歸納型別.歸納型別是定義新型別的一套規則，以上介紹的0、1、2、formula_2、"A" × "B"、"a" ="A" "b"等都是其特例。要定義一個歸納型別，必須列出它的建構式。每一條建構式不但可以直接輸出該型別的項，從而建構出無限大的數學結構。歸納型別代表了由它的建構式所自由生成的結構，也就是說，它的項正好都是從無開始，透過重複應用任一條建構式後所得的。本文不試圖詳列歸納型別的嚴格定義。舉例來說，我們可以用歸納型別來定義整數formula_45。它有兩條建構式：要建構某一個整數，須先指定用哪一條建構式，然後指定一個自然數。再以么半群為例，它只有一條比較長的建構式，為方便閱讀以文字寫出：要建構某一個么半群，只須提供這單一條建構式所規定的所有項。同倫型別論.同倫型別論是型別論底下一個活躍的研究範疇，它主張從同倫論的角度視每一個型別為的基礎之上研發出基於一價公理上的新數學基礎。基本概念.在這樣的框架下，型別的項可以想象成空間裡的點，而兩個項之間等同則可以想象成兩個點之間有一條路徑。假如型別"A"中有兩項等同"p" : "a" ="A" "b"，這可以理解為「"p"是始於"a"而終於"b"的路徑」。等同型別的對稱性意味著存在"p"−1 : "b" ="A" "a"，可以理解為「"p"−1是始於"b"且終於"a"的路徑」。當然，每個項都有自己的自反路徑refl"a" : "a" ="A" "a"，可以理解為停留在"a"上不動的路徑。利用等同型別的遞移關係，可以從"p" : "a" ="A" "b"和"q" : "b" ="A" "c"得出"p" ∘ "q" : "a" ="A" "c"。理解為路徑的話，路徑"p"和路徑"q"可以複合起來形成一條始於"a"而終於"c"的路徑"p" ∘ "q"。假如我們複合"p"和它的對稱，就會得出"p"−1 ∘ "p" : "a" ="A" "a"。不過，這一條路徑往"b"點跑了一個來回，並不完全等同refl"a"，儘管兩者都是同一條命題的證明。這體現了同倫型別論所強調的「證明相關性」。從拓撲空間的角度來看，由於"p"−1 ∘ "p"沿著同一條線來回跑，所以它可以連續「縮小」至原地不動的refl"a"，而不怕中途被某個「孔」勾住。這種路徑與路徑之間的連續變換稱為同倫，亦可視為始於"p"−1 ∘ "p"而終於refl"a"的一條二維路徑，記作"p"−1 ∘ "p" ="a" ="A" "a" refl"a".循同樣的規律，很自然地有二維路徑之間的三維路徑，三維路徑之間的四維路徑，等等。從抽象代數的角度來看，路徑之間的複合可以視為乘法，自反路徑refl"a"可以視為單位元，而任何路徑"p"的對稱"p"−1可以視為反元素。這類似於群的結構，但有兩點差異。第一，不是任何兩條路徑都可以複合，因為其中一條的終點必須是另一條的起點，意味著這只是一個廣群而不是群。第二，"p"−1 ∘ "p"只是和refl"a"同倫等價而不是完全等同，因而反元素只是在同倫意義上得到滿足，故此只能說是弱廣群。整體來說，這種具有無限層的型別結構形成弱。任何函式"f" : "A" → "B"都會將命題等同的兩個項對映至兩個命題等同的項，從範疇論的角度可以說型別論中的函式都是函子，而從拓撲學的角度則可以說每個函式都是連續的。拓撲學的纖維化和範疇論的等價等等概念同樣也有型別論的類比。一價公理.在拓撲學中，假如兩個空間是同倫等價的，那麼它們的許多拓撲性質也會是相同的。因為同倫這一概念在型別論中也有對應的「等價」概念，所以我們可以寫下「型別"A", "B" : 𝒰是等價的」這樣的命題，記作"A" ≃ "B"。在一般「非形式化」的數學推理當中，也就是不糾結於數學基礎細節的時候，數學家往往會濫用符號，隨意互換兩個等價但嚴格來說不完全等同的物件。例如，群論所研究的是同構意義上不同的群的性質，而拓撲學所研究的是同胚意義上不同的空間的性質。換言之，數學家一般並不在乎兩個等價結構之間定義上的細節差異。例如，實數到底是以戴德金分割還是柯西序列來表示並不重要，更重要的是它的抽象性質，特別是在與另一個等價結構互換以後仍然不變的性質。傳統的集合論把所有結構都以層層相疊的集合來表達，無法做這種符合的數學推理。型別論對型別的定義恰好遵循結構主義，但在「兩個等價的型別可以互換」這一問題上，我們只能對於每一對等價型別"A" ≃ "B"逐一證明。弗沃特斯基因此提出在純粹的型別論上加入一條新的公理，稱為一價公理：("A" =𝒰 "B") ≃ ("A" ≃ "B"),可以讀成「等同」等價於「等價」。一價公理推廣了同一個全類以下兩個型別之間的等同關係。它要求同倫型別論下的所有定義都不違背型別間的同倫等價。對於任何同倫等價"e" : "A" ≃ "B"和任何項"t" : "P"("A")，其中"P"("A")是利用"A"建構出的型別，都可得出一個對應的項"e"∗"t" : "P"("B")。以一價公理作為數學基礎，終於能夠對常用的數學推理手法做嚴謹的形式化表述。更高歸納型別.更高歸納型別是在同倫型別論的框架下對歸納型別的推廣。更高歸納型別的建構式不但可以像普通歸納型別一樣建構新的項。例如，我們可以定義拓撲學意義的圓formula_48，它有兩條建構式：這第二條建構式所建構的是有別於常值路徑formula_51的另一條路徑，為這一型別賦予了不平凡的拓撲結構。再舉一例，我們可以定義拓撲學意義的球面formula_52，它同樣有兩條建構式：儘管定義裡只有基點和一條二維路徑，但是可以證明formula_52還有一條非平凡的三維路徑，其起點和終點都是reflreflbase。這就是霍普夫纖維化，同時印證了，更高歸納型別的簡單定義也可以創造出複雜而不易預見的拓撲結構。廣義地來說，更高歸納型別的建構式可以建構任何更高維度的路徑。參閲.