如何證明 injectivity of type constructors

時間 2021-05-09 10:27:16

1樓:Anqur

這個問題好像少提供了一些 context, 咱是故意的= =, 隨便給個 context 讓它 hold 是可以的.

最近在看 Jon Sterling 寫的材料, 因為他, 包括 Coquand 老爺等一批人這幾年在 CTT 幹的事情, 其中的脈絡好像更清晰了:

Taichi Uemura 的型別論新 categorical/functorial semantics 去給 CTT 找 semantic model[1]

用 Artin gluing 搞事情

先證明 CTT 的 canonicity, 再搞 NbG (normalization by gluing), 實現 CTT 的 normalization 完全體 (正在進行)

這個結論在型別論的 initial model 很重要 (syntax 的元定理), 能完善型別檢查或 definitional equality 的完整性[3], 但 not preserved by homomorphisms (到 semantic 層次不 hold 了), 比如 @藥罐子千里冰封 給的反例.

2樓:藥罐子千里冰封

Type constructor 沒有 injectivity,題主這是試圖證明全世界的假命題啊。不過還是感謝題主整天提這些禁不起思考的問題,不然我哪來的發揮空間寫回答呢?我首先說明為啥 Type constructor 沒有 injectivity 再說明題主的那個特定的例子的問題。

題主提到了型別的相等性,那麼我先假定這是在 Univalent 的視角下看問題的。

只需乙個反例,`TyCon : (A : Type) → Empty`,這樣易證 `TyCon Nat = TyCon Unit`,但你能說 `Nat = Unit` 麼?

Cardinality 都不一樣。

兩個 Pi type 相等,當然需要 dependent path type,但並不能匯出兩個 domain 和 codomain 相等。參考 `Empty → A` 和 `A → Unit`,兩者各自有乙個 inhabitant,易證相等。

如果不考慮 Univalence 的存在,domain 相等或許是存在的,但是 domain 的 binding 可能 ∈ FV(codomain),導致你的相等型別變成了 dependent path type,於是你可以知道證明這倆東西相等需要某種意義上的外延性,which 我不太確定但我覺得在老型別論裡做不出來。

如何證明 3 05 ?

拓跋景帆 解A.由 sin x x 0 eeimg 1 可得 sin frac frac 2 eeimg 1 於是 4 sqrt eeimg 1 只需證 61 eeimg 1 兩邊平方得 3721 eeimg 1 即 再平方就是 得證.解B.由 sin x x 0 eeimg 1 可得 sin fr...

如何證明 1 1 4 1 9 1 16 1 25 6?

題主問題是Problems in Analytic Number Theory M.Ram Murty 習題5.5.5。放乙個有趣的小結論 這個二重和式可推廣成 比證明更重要的是怎麼去理解這個特殊的數!一種角度是Riemann 而這個和巧合就是 就是 function 的特殊值。 瑜書 前幾天思考另...

如何證明 1 1 1

袁傑 規定原點左邊1公尺,記作 1公尺,左邊2公尺,記作 2公尺,右邊1公尺,記作 1公尺,右邊2公尺,記作 2公尺,對於 1 1 現在這樣想,第乙個 1表示你每天向左走1公尺,第二個 1表示1天前,這就相當於問你現在在原點,而你每天向左走1公尺,1天前在哪個位置,很明顯你一天前在原點右邊1公尺處,...