Lawvere's fixed point theorem 的陳述與應用 [math-0005]

這篇文章試著介紹 Lawvere's fixed point theorem 的意義與應用

Theorem Lawvere's fixed point [math-0006]

DIAGONAL ARGUMENTS AND CARTESIAN CLOSED CATEGORIES

在一個 cartesian closed category 中,如果 A→ϕBAA \xrightarrow{\phi} B^A 是 point-surjective,則所有 B→fBB \xrightarrow{f} B 都存在不動點 1→sB1 \xrightarrow{s} B(滿足 f∘s=sf \circ s = s)。

Proof [local-0]

首先畫出交換圖

figure tex151599

其中 δ\delta 的定義是 c↦⟨c,c⟩c \mapsto \langle c, c \rangle,所以對 1→pA1 \xrightarrow{p} A 來說 δ∘p=⟨p,p⟩\delta \circ p = \langle p, p \rangle。沿著這個定義,我們知道 (ϕ×1A)∘δ∘p=ϕ∘⟨p,p⟩(\phi \times 1_A) \circ \delta \circ p = \phi\circ \langle p, p\rangle。根據 point-surjective 我們知道 ϕ∘p\phi \circ p 對每個 pp 來說都是唯一確定的。現在把往下方 BB 的 evev 也畫出,即可得出等式:

f∘ev∘ϕ∘⟨p,p⟩=ev∘ϕ∘⟨p,p⟩f \circ ev \circ \phi\circ \langle p, p\rangle = ev \circ \phi\circ \langle p, p\rangle

換句話說 B→fBB \xrightarrow{f} B 的不動點即是

ev∘ϕ∘⟨p,p⟩ev \circ \phi\circ \langle p, p\rangle

Example 應用到 lambda calculus [math-0007]

編碼的方式是找一個只有兩個物件 1,T1, T 的 category MM,讓 lambda calculus 的 terms 是 MM-morphisms,這些技巧在 Categorical semantic 領域內相當常見。

到這裡必須檢查 lambda calculus 確實存在 point-surjective,歡迎自行嘗試。

按此編碼後可以得到 ev∘ϕ∘⟨p,p⟩→encodeϕ(p)(p)ev \circ \phi\circ \langle p, p\rangle \xrightarrow{encode} \phi(p)(p)。套到等式上

f∘ev∘ϕ∘⟨p,p⟩=ev∘ϕ∘⟨p,p⟩f \circ ev \circ \phi\circ \langle p, p\rangle = ev \circ \phi\circ \langle p, p\rangle

可以得到以下編碼

f(ϕ(p)(p))=ϕ(p)(p)f(\phi(p)(p)) = \phi(p)(p)

把 ϕ(p)\phi(p) 改寫成 qq,於是等式可以寫成 q(p)=f(ϕ(p)(p))q(p) = f(\phi(p)(p)),而函數套用語法可以用 λ\lambda 退化,於是得到

q=λx.f(ϕ(x)(x))q = \lambda x. f(\phi(x)(x))
注意到 qq 的定義是非遞迴的,因此一定是可定義的。

計算即可發現確實 q(p)=ϕ(p)(p)=f(ϕ(p)(p))q(p) = \phi(p)(p) = f(\phi(p)(p))。因為所有的 λ\lambda-term 都屬於 TT,所以現在我們知道任何 lambda calculus 的函數都有不動點。

Example 應用到 Cantor's theorem [math-0008]

取 category of sets Sets\bold{Sets} 並令 B=2B = 2 就可以證明 Cantor's theorem。我們需要引理

Lemma no point-surjective morphism [math-0009]

If there exists B→fBB \xrightarrow{f} B such that f∘b≠bf \circ b \ne b for all 1→bB1 \xrightarrow{b} B, then there has no point-surjective morphism can exist for A→gBAA \xrightarrow{g} B^A.

This is a reversed version of Lawvere's fixed point, no need an extra proof.

Proof [local-0]

存在 2→not22 \xrightarrow{\text{not}} 2 令所有 1→b21 \xrightarrow{b} 2 都滿足 not∘b≠b\text{not} \circ b \ne b,所以對任何集合 AA 都不存在 A→2AA \to 2^A 的 point-surjective 函數,因此也不存在 A≅2AA \cong 2^A。

這個定理也可以用到 Gödel incompleteness、Tarski definability 等等問題上。論文 Substructural fixed-point theorems and the diagonal argument: theme and variations 更進一步的簡化了前置條件。