2010/06/29

Set-theoretic inductive types

中午有人問到 structural induction 是不是一條 axiom,Max 的答案最為全面:系統外我們自然認為 induction 對,至於在系統內的話,first-order logic 必須要設成 axiom (scheme?),到 FLOLAC '08 講的 second-order propositional logic(對應 polymorphic lambda-calculus)就可以用 Church encoding 表示自然數,從而自然地有 induction principle。我想的則是在型式系統的邊界處:在一般的數學架構下我們怎麼促成 induction?Category theory 用 initial F-algebra 弄得很漂亮,set theory 的話可以用 monotonic functions on sets + Knaster-Tarski Theorem 處理,都是把 inductive datatypes 定義得能夠做 induction。以下記錄第二種做法備查,因為我在回憶這種做法時有卡了一下 XD。

先在一個夠大的宇集裡隨便挑一個 constant z 和一個 injective "label" function s。(這句話有辦法說得更好嗎?或許用 axiom of infinity?)(不用假設 0 不在 s 的 range 裡面。直覺上,假設 0 = s (s 0') 而 0' 是我們心目中真正的零,那麼我們定出來的自然數集就是從二開始算。)在集合上定義一個 function f S := { 0 } ∪ { s x | x ∈ S } ,f 在 set inclusion 下是 monotonic,意思是 X ⊆ Y 時有 f X ⊆ f Y。根據 Knaster-Tarski Theorem,f 有 least fixed-point N,它也會是所有滿足 f X ⊆ X 的 set X 裡面最小的 — 若 X 滿足前式,則一定有 N ⊆ X。現在我們就把 N 當作自然數。假設我們有個性質 P x 要證明對 N 的所有元素成立,定義 X := { x | P x },如果我們能夠證明 f X ⊆ X,即

  f X ⊆ X
⇔   { definition of f }
  { 0 } ∪ { s x | x ∈ X } ⊆ X
⇔   { since A ∪ B ⊆ C ⇔ A ⊆ C ∧ B ⊆ C }
  0 ∈ X ∧ (x ∈ X ⇒ s x ∈ X)
那麼我們就有 N ⊆ X,即 x ∈ N ⇒ x ∈ X,後件再用 P 改寫一下,就是 x ∈ N ⇒ P x。因此藉著如此定義 N,我們就免費得到 N 上的 induction principle 了。

--
寫這篇的時候也會卡,而且每次 monotonic 的意思都會想錯 XD。然後上面引的 axiom of infinity 裡面就有提只用到 set-theoretic axioms 的自然數建構法了 XD。

Labels:

2009/12/30

地基

我先前應該提過,有位學弟想考台大資工所,正在讀線性代數。今天他看今年的線性代數題目,第一題是假設實數方陣 A 滿足 A^2 - A + I = 0,求 A + 2I 的反矩陣。我試了一下,最後想到 x^2 - x + 1 類似 A 滿足的 minimal polynomial,用 simple extension 的想法(精確地說,是「u algebraic 時 F[u] 與 F(u) 同構」的證明裡面用輾轉相除法構造反元素的部份)就解出來了 ─ 所以和矩陣代數或線性代數沒什麼直接關係。(其實我很懷疑前提的 A 真的存在,但 Mathematica 幫我算了一個 2*2 的 case 出來。)雖然我必須說我不喜歡這份題目的味道,但批評題目不是我的重點。我想說的是我順路去看數學所的考古題,發現我還是忘了不少東西,尤其是高等微積分。雖說這些畢竟不是我專門的東西,可以只留個印象就好,但得小心不要連專門的東西都弄不熟呀。

--
連 Eisenstein's criterion 都記不全了…(其實我一直沒弄懂 p-th cyclotomic polynomial 怎麼用 Eisenstein's criterion 證明是 irreducible in Z[x] XD。)

Labels:

2009/08/30

Inversion

這週複習到 Stoy 那段經典的「為何 computable functions 必須是 continuous lattices 上的 continuous functions」論證。我一直覺得這一段實在美不勝收,「計算」的精髓(或許可以引聰明的話「有涯飛躍無涯」?)從這種角度來看顯得清晰許多。我在 Trek Begins 裡面提到我原本對 Turing machines 的 finiteness 感到不舒服,但後來發現我們處理的 infinity 都是 finitely representable,Stoy 的論證對這個轉念應該有不小的幫助。

其實我要講的是 continuity 定義裡面的主客關係。第一次看到這種「主客對調」現象當然是在大一微積分裡極限的 epsilon-delta 定式。直覺上,若一個函數 f(x) 在 a 點連續,我們會講「當 x 趨近 a 時 f(x) 趨近於 f(a)」,此時自變數 x 是主,應變數 f(x) 是客。但現代微積分告訴我們主客關係不該這麼定,我們應當讓 |f(x) - f(a)| 取得主動,從這個差值回頭去找合適的 x。這種看法在拓樸上泛化成 open sets 的語言,我們說 f : X -> Y 是連續函數的意思是:Y 裡面任意的 open set V 經由 f^{-1} 拉回 X 裡面,f^{-1}(V) 仍然是 open set。主客關係完整地保留下來了。最後回到 Stoy,p.117 說

[T]he characteristic property of continuous functions [is] that every finite piece of information in the result is produced from some finite piece of information in the argument.

單純從數學來看,同樣的主客關係出現在這裡並不意外,因為 Stoy 提到 complete lattices 上的 continuous functions 只是 topological spaces 的特例。但如果從計算的觀點來看就滿有意思了,主客關係的對調似乎比極限的情況更順理成章一些。寫到這裡又覺得,可能是我已經習慣這種主客關係,所以很順理成章地認為順理成章吧 XD。

發現主客關係應該對調的那群人真是太厲害了…

--
拖稿好幾天,累積好幾個主題,現在得慢慢還債啦 XD。

Labels: ,

2009/08/25

One-point compactification and Discourse on Method

近幾天看到兩項讓我在辦公室內微微驚呼出聲的東西。首先是拓樸上的 one-point compactification,本來應該上星期就寫,但一直被別的主題擠掉。One-point compactification 顧名思義,一個只是 locally compact 的 Hausdorff space 只要補上一個點然後簡單地拓樸化,這個新的 space 就變成 compact 了!不僅如此,所有只多一個點的 compactification 全部都是 homeomorphic,所以 one-point compactification 是 unique up to homeomorphism!這麼單純卻又有這麼好的性質,可惜當時旁邊沒有人可以分享我的驚喜 XD。相較之下,號稱點集拓樸第一個 non-trivial 的命題 Urysohn's lemma 以及其後的 Urysohn's metrisation theorem 就真的是 non-trivial,我因此還看不出那個 metric 到底是怎麼變出來的。

另外也讀完 Descartes 的《Discourse on Method》第一部份。這根本就是 Descartes 的學思歷程嘛!一路讀下來,我覺得我的思路實在和 Descartes 很接近,而且根源應該不是因為讀 Meditations(雖然讀 Meditations 對往後的發展一定有影響)。看到 Part One 最後,Descartes 說

[...] I gradually extricated myself from many errors powerful enough to darken our natural intelligence, and incapacitate us in great measure from listening to reason. But after I had been occupied several years in thus studying the book of the world, and in essaying to gather some experience, I at length resolved to make myself an object of study, and to employ all the powers of my mind in choosing the paths I ought to follow [...]
我看到這最後一段不微微驚呼出聲也不行了。還是引 Descartes 的話:
I was aware [...] that the perusal of all excellent books is, as it were, to interview with the noblest men of past ages, who have written them, and even a studied interview, in which are discovered to us only their choicest thoughts[.]
與志同道合的古人神遊確實相當令人滿足啊!

--
不過 Descartes 要講的重點是讀太多別人的東西不好 XD。

Labels: ,

2009/08/18

被誰卡住

昨天最後就是被下面這個 "partial converse to the uniform limit theorem" 卡住,今天早上不讓它苟延殘喘,直接做掉了。

其實是滿典型的分析學證明,只能說練習不夠吧 XD。

--
KDX 這一兩天就會到家了吧!

Labels:

2009/05/11

最後高潮

本週陳榮凱老師出國,代數導論交由去年暑假才剛到數學系的林惠雯老師代課,「使命」應該是把 finite dimensional 的 fundamental theorem of Galois theory 證完吧。課上起來還滿 high 的,和 YouTube 上講 category theory 的老師相距不遠了 XD。果如相傳,Galois theory 基本定理一寫出來,芬芳氣味便透出黑板瀰漫整間教室,(finite) Galois extensions 和 Galois groups 漂亮無隙地被連接在一起。後面的應用精彩可期。程式也應該要有這種風味、這種強度的刻劃呀。

--
只能說 AoP 真的還在石器時代 XD。

Labels:

2009/04/24

第一篇 Structured Proof

向人推銷 Lamport 的 structured proof 自己卻不用的話很沒說服力,所以很自然地拿代數導論作業來練習,成果在此。簡單的一題就已經寫了 3/4 頁(在代數導論作業專用格式下),看來目標先設定成一次作業寫一題就好 XD。

--
今日飲食:… 欸,已經結束了啦 XD。

Labels:

2009/02/23

Componentwise

當我們有兩個 groups G 和 G',我們可以取它們的 direct product G × G',其上的操作是對每個分量個別運算。可以很直覺地想像,這樣的定義確實造就一個 group。

另一方面,任意的函數集 GA = (A → G)(其中 G 是一個 group)也可以擴充成一個 group ─ 只要定義 (f · g) x = f(x) · g(x) 即可。Martin-Löf 這時會跳出來說:A → G 其實是一堆 G 的 cartesian product,以 A 的元素當作 index。例如 ℕ → G 就相當於 G × G × G × ⋯,一個函數 f : ℕ → G 就相當於一個 countably infinite tuple (f(0), f(1), f(2), ...)。如此詮釋下,(f · g) x = f(x) · g(x) 的意義就很明顯:「f · g 的 x 分量」是「f 的 x 分量」乘上「g 的 x 分量」,其實就是推廣的 direct product。

--
和 accessibility 一樣,這裡丟掉 higher-order 的想法會更直覺簡單 XD。

Labels:

2008/11/04

代數導論作業

我把前幾次的代數導論作業放上網了,包括題目和我自己的答案。想練習的人可以參考 XD。

--
對於初學者應該是難易適中的題目 XD。

Labels:

2008/10/30

Least Fixed Point and Point-Set Topology

Rudin 第二章的 13 號練習題:"Construct a compact set of real numbers whose limit points form a countable set." 我的造法是從 T = { 1/(2^k) | k is a positive integer } 開始,把 T 的 closure 嵌在 [0, 1] 上當作「印章」,然後把印章均勻地縮成一半長度之後蓋在 [1/2, 1] 上面,再縮一半長度蓋在 [1/4, 1/2] 上面,如此下去。蓋了無窮多次之後,取最終集合的 closure 就是答案。(欸,我知道寫得這麼不正式其實沒什麼好處啦 XD。)可以證明這個答案確實是 bounded & closed 因而 compact(從實數完備性來的),而且所有 limit points 正好是 0 或 1/(2^k) 因而 countable。可是真的把這個 set 寫下來某種程度而言還是挺囉唆的,因此我試著把它寫成某個函數 f : P(R) -> P(R) 的 least fixed-point,希望可以從 f 的性質推得 least fixed-point 的性質。函數 f 很簡單:拿到一個集合之後以 0 點為中心把這個集合線性地縮寫 1/2 倍,接著把長 1/2 的印章蓋在 [1/2, 1] 上面。從 Kleene's theorem 可以很清楚地看到答案的建造過程。很可惜的是,除了 boundedness 以外我還不太能從 f 的性質推得我需要的性質,特別是 "the set of limit points is countable"。目前就先擱著 XD。

--
我一開始誤以為要取 greatest fixed-point(因為看起來有點 unfold 的味道),不過 gfp 其實是整個實數集。

Labels:

2008/09/19

論箭頭的單調與反單調性

今天 meeting 的時候卡在這裡一陣子,整理一些詮釋方法。我們稱 "N -> P" 裡面 N 的位置為 negative position,P 的位置為 positive position。當 P 變強時 N -> P 會隨之變強,當 N 變強時 N -> P 反而會變弱。邏輯上可直覺解釋為「從同樣的前提能推得更強的結果,所以整個推論比較強」以及「需要更強的前提才能推得相同的結論,所以整個推論比較弱」。

畫張圖或許比較清楚。考慮集合 S = {x | P(x)},當 P 較弱時 S 比較大(例如取 P x = true),當 P 較強時 S 比較小(因為能達到較嚴苛要求的元素比較少)。令 P 和 Q 是任意的條件,那麼 P -> Q 是一個新的條件,對應以下的黃色部份:

因為不滿足 P -> Q 的元素只有那些「滿足 P 但不滿足 Q」的元素。若已知 Q -> Q',那代表 Q' 對應的集合是 Q 對應集合的 superset。請按上圖連結到 gif 動畫,就可看到 P -> Q' 所涵蓋的範圍會比 P -> Q 多出橘色那一塊,因此 Q 愈弱 P -> Q 也愈弱。類似地,若已知 P -> P',按下圖連結就可看到 P' -> Q 涵蓋的範圍比 P -> Q 少了慘綠色那一塊,因此 P 愈弱 P -> Q 反而愈強。

--
其實並不完全直覺 XD。

Labels:

2008/09/15

Simple Exercise

Prove that fº . R . f is an equivalence relation if R is. (f is, by convention, a total function.)

Proof. (i) Reflexivity:

id  ⊆  fº . f  ⊆  fº . id . f  ⊆  fº . R . f
(ii) Transitivity:
fº . R . f . fº . R . f  ⊆  fº . R . R . f  ⊆  fº . R . f
(iii) Symmetry:
(fº . R . f)º  =  fº . Rº . f  =  fº . R . f
□

Example: take f = signum and R the usual equality on real numbers.

--
I certainly like the way AoP treats relations. So concise!

Labels:

2008/05/01

碎碎念 Knaster-Tarski 定理

Knaster-Tarski 定理是 denotational semantics 上很關鍵的一個定理。因為我看它的證明常常會卡住,所以直接寫一篇極端囉唆版的證明擺在這裡備查,順便當通識推廣 XD。喜歡看一般精簡版證明的人可以看 Tarski 的論文。

既然是通識版,就從最基本的定義開始嘍。一個 partially ordered set (poset) 是一個集合 S 和其上的一個 partial order ≤。所謂 partial order 是一個 binary relation,滿足

  • reflexivity,即 x ≤ x for all x ∈ S;
  • transitivity,即當 x ≤ y 且 y ≤ z 時必有 x ≤ z;
  • antisymmetry,即當 x ≤ y 且 y ≤ x 時必有 x = y。
稱之為 "partial" 是因為在 partial order 下並非任兩個元素都能比較,例如集合的包含關係 ⊆。

我們今天的主角是一種特殊的 poset,稱為 complete lattice。這種 poset 的特異功能是:給定任意一個子集 T,都可以在 S 裡面找到

  • T 的最大下界(greatest lower bound),記為 inf T;
  • T 的最小上界(least upper bound),記為 sup T。
inf T 的定義是(對於任意 x ∈ S)"x ≤ inf T" if and only if "x ≤ y for all y ∈ T"。令左邊的 x = inf T,則左邊根據 ≤ 的 reflexivity 成立,於是右邊 "inf T ≤ y forall y ∈ T" 也成立 ─ 這就說明了 inf T 是 T 的下界。從右邊讀回來,如果有個 x 滿足右邊的條件,意思是 x 是 T 的下界,那麼左邊就告訴我們 x ≤ inf T ─ 意思就是 inf T 是所有下界之中最大的一個。sup T 的定義和 inf T 對偶:"sup T ≤ x" if and only if "y ≤ x for all y ∈ T",詮釋也是對偶的。

一個重要特例是取 T = ∅,此時 "x ≤ y for all y ∈ ∅" 對於任意 x ∈ S 都成立(vacuously true),所以我們就有 x ≤ inf ∅ for all x ∈ S,亦即 inf ∅ 是 S 裡面的最大元素,我們記之為 max S。可以想像「最大下界」就是儘可能地往遞增的方向推進,直到被 T 中的元素擋下來為止。如果 T = ∅,這個推進過程便無法可擋,推著推著就推到最大元素了。相同道理,sup ∅ 就是 S 裡面的最小元素,我們記為 min S。所以 complete lattice 必有最大元素和最小元素。

最後介紹 monotonic function 和 fixed point。令 f 是一個定義在 poset (S, ≤) 上的 function。若 x ≤ y 時必有 f(x) ≤ f(y),我們就稱 f 是一個 monotonic (increasing) function,又稱 order-preserving function(因為把 f 套用到 ≤ 的兩邊,方向不會因此顛倒)。另外若有一點 p 滿足 p = f(p),則我們稱 p 為 f 的一個 fixed point(中譯為不動點、固定點,英文有時寫為 fixpoint)。

現在就讓 Knaster-Tarski 定理登場嘍!

定理(Knaster-Tarski)
令 φ 是定義域和值域都在 complete lattice (S, ≤) 上面的 monotonic function,P 是 φ 所有 fixed points 所形成的集合 { x | φ(x) = x }。那麼 (P, ≤) 也是一個 complete lattice。此外,令 P≤ = { x | φ(x) ≤ x } 和 P≥ = { x | φ(x) ≥ x },則 min P = min P≤、max P = max P≥。
剛剛提到 complete lattice 必有最大和最小元素,因此 Knaster-Tarski 定理的一個重要推論(corollary)就是「complete lattice 上的 monotonic function 必有最大和最小的 fixed point(兩者可能是同一個)」。這在 denotational semantics 上非常重要,可用來定義 recursive definitions(包括 induction 和 coinduction)的語意。(詳情在 FLOLAC '08 會談,5/22 就截止報名了喔!)事實上,這個推論可說是定理的核心 ─ 整個定理的證明就是從這個推論開始的。這是一個常見的情況:定理的完整證明奠基於其特例。

開始證明!根據 ≤ 的 reflexivity 和 antisymmetry,我們知道 P = P≤ ∩ P≥。用形狀比較特異的 Venn diagram 表示:

考慮 ℓ = inf P≤,即左邊藍色集合的最大下界。我們的目標是證明 ℓ 就在 P≤ 裡面,然後更進一步證明 ℓ也在 P 裡面。既然 ℓ 是 P≤ 的下界,它也是 P 的下界,而且因為它就在 P 裡面,所以它就是 P 的最小元素。「u = sup P≥ 是 P 的最大元素」可透過對偶的論證得到。

怎麼證明 ℓ 的確在 P≤ 裡面呢?證明 ℓ 滿足 P≤ 的「入團條件」φ(ℓ) ≤ ℓ 就行了。而正好 ℓ 是 P≤ 的「最大」下界,所以我們只要證明 φ(ℓ) 是 P≤ 的一個下界,就可以免費得到 φ(ℓ) ≤ ℓ!任取一點 x ∈ P≤。我們有 ℓ ≤ x 因為 ℓ 是 P≤ 的(最大)下界。然後因為 φ 是 monotonic function,我們就有 φ(ℓ) ≤ φ(x)。x 在 P≤ 裡面,所以 φ(x) ≤ x,於是就得到 φ(ℓ) ≤ x。最後因為當初 x 是任意取的,所以 φ(ℓ) ≤ x 對於所有 x ∈ P≤ 都成立,亦即 φ(ℓ) 是 P≤ 的一個下界。但 ℓ 是 P≤ 的「最大」下界,我們就得到入團條件 φ(ℓ) ≤ ℓ,因此 ℓ 在 P≤ 裡面。

我們已經成功把 ℓ 推進 P≤,現在我們得寸進尺,繼續把它推進 P 裡面。藉著 φ 的 monotonicity 和 ℓ 的入團條件 φ(ℓ) ≤ ℓ,我們可以得到 φ(φ(ℓ)) ≤ φ(ℓ),而這正是 φ(ℓ) 的入團條件,所以 φ(ℓ) ∈ P≤。不要忘記 ℓ 是 P≤ 的(最大)下界,因此 ℓ ≤ φ(ℓ)。根據 ≤ 的 antisymmetry,我們就有 φ(ℓ) = ℓ,那就代表 ℓ 在 P 裡面。根據一開始的論證,ℓ 就是 P 的最小元素。同理可推得 u 是 P 的最大元素。

至此我們已經證畢 Knaster-Tarski 定理的核心部份,即 P 有最小和最大元素(也就是 φ 的 least and greatest fixed point)。過程值得再簡述一遍:φ(ℓ) 靠著 ℓ 的最大下界身分努力成為 ℓ 的下界把 ℓ 推進 P≤,然後自己跟著進去,最後利用 ℓ 是一個下界的事實把 ℓ 推進 P 裡。不覺得 φ(ℓ) 真是勞苦功高嗎?XD

我們繼續證明 (P, ≤) 本身是個 complete lattice,即證明對於 P 的任意子集 A,都可以在 P 裡面找到 inf A 和 sup A。令 I = { x | x ≤ inf A } ⊆ S,這也是一個 complete lattice (*)。我們的目標是證明「φ 定義在 I 上的部份」φ' 的 greatest fixed point 就是 A 在 P 裡的最大下界,方法是對 I 和 φ' 套用 Knaster-Tarski 定理的核心部份,找到比 inf A 小的最大 fixed point,這就是 A 在 P 裡的最大下界。透過對偶的論證也可找到 A 在 P 裡的最小上界。

首先我們必須確定 φ' 的值域是 I,才能套用 Knaster-Tarski 定理的核心部份,得到 φ' 的 greatest fixed point。因為定義域是 I = { x | x ≤ inf A },所以 φ'(x) ≤ φ'(inf A)。我們只要證明 φ'(inf A) ≤ inf A,就能確定 φ' 的值都落在 I 裡面。要證明一點比最大下界小,最簡單的方法就是證明它是一個下界。任取一個 x ∈ A,因為 A 也是 fixed point(s) 的集合,所以 φ(x) = x。接著,inf A ≤ x 因為 inf A 是 A 的(最大)下界,套上 monotonic φ 之後得到 φ(inf A) ≤ φ(x) = x。x 任意,所以 φ(inf A) 是 A 的一個下界。又因為 inf A 是「最大」下界,因此 φ(inf A) = φ'(inf A) ≤ inf A。

現在 Knaster-Tarski 定理的核心部份所需要的條件已經全部滿足了:I 是個 complete lattice、φ' 是個從 I 映射到 I 的 function,因此我們知道 φ' 有 greatest fixed point,令它為 p。顯然 p 在 P 裡面,因為 p 也是 φ 的 fixed point。p 在 φ' 的定義域裡,故 p ≤ inf A ≤ x for all x ∈ A,即 p 是 A(在 P 裡)的一個下界。最後只要證明 p 是 A 在 P 裡的「最大」下界就結束了,而這很簡單:A 若有其他下界 q (≤ inf A),q 必為 φ' 的 fixed point 而一定有 q ≤ p,因為 p 是 φ' 的 greatest fixed point。透過對偶的論證也可以找到 A 在 P 裡的最小上界。至此我們終於把整個 Knaster-Tarski 定理證完了!    ∎

(*) 更一般地,任何 I = { x | a ≤ x ≤ b } ⊆ S 都是 complete lattice。任取 I 的子集 K,我們有 inf K ≤ b 因為 b 在 I 裡面。a 必為 K 的一個下界,所以根據 inf K 的「最大」性質,我們也有 a ≤ inf K。於是 a ≤ inf K ≤ b,因此 inf K 也在 I 裡面。同理,sup K 也在 I 裡面。

--
難怪沒人要寫這種證明… 下一步是試試看能不能從操作意義上了解它。

Labels: