第3章泛代數和代數數據類型(編輯修改稿)

　

【文章內容簡介】 – “ 最小模型 ” 是指它的理論包含的內容最少 等式、可靠性和完備性 最小模型完備性不一定成立 ， 考慮等式 E =def x = y [ x : a, y : a, z : b ] – 情況 1： a的載體只含一個元素 ， 則 E滿足 ， 此時 E1 =def x = y [ x : a, y : a ]成立 – 情況 2： b的載體為空 ， 則 E也 滿足 ， 此時 E2 =def z = w [ z : b, w : b ]成立 – E1和 E2都不是 E的語義蘊涵 – 不存在一個代數 ， 其理論正好就是由 E的等式推論組成的語法理論 等式、可靠性和完備性 同余 、 商和演繹完備性 ? 同余關系 ：等價關系加上同余性 ? 同余性：指函數保可證明的相等 性 ? 對單類代數 A = ?A, f1A, f2A,… ?， 同余關系是載體 A上的等價關系 ， 使得對每個 k 元函數 fA， 如果ai?bi(i=1,… , k)， 即 ai和 bi等價 ， 那么 f A(a1, … , ak ) ? fA (b1, … , bk )。 ? 對多類 ?代數 A = ??As?, I ?， 同余關系是一簇等價關系 ? ? ??s?, ?s ? As?As， 使得對每個 f : s1 ? … ? sk?s及變元序列 a1, … , ak和 b1, … , bk(其中 ai ?sibi ? Asi),有f A (a1, … , ak ) ?s f A (b1, … , bk ) 等式、可靠性和完備性 ? A模 ?的商的代數 A?? – 把 A中有關系的元素 a ? a? 壓縮成 A??的一個元素 ? 等價類 [a] [a]? ??a? ? As ? a ? a? ? ? ?商代數 A??定義： – (A??)s是由 As的所有等價類構成的集合 As??s ? ??a??s ? a ? As} – 函數 fA??由 A的函數 fA確定： 對適當載體的 a1,… , ak， f A?? ([a1], … , [ak]) = [f A (a1, … , ak)] 等式、可靠性和完備性 ? 上面定義有意義的條件是 f A?? ([a1], … , [ak])必須只依賴于 [a1], … , [ak]， 而不能依賴于所選的代表 a1, … , ak。 ? 例 單類別代數 ?N， 0， 1， ??上的同余關系“ 模 k等價 ” – 這個商代數是大家熟悉的整數模 k加結構 。 如果 k等于 5， 那么 ?3? ? ?4? ? ?2? 等式、可靠性和完備性 ? 如果 ?是 A的一個環境 ， ?是一個同余關系 ，那么 A??的環境 ?? 定義如下： ?? (x) = [?(x)]? ? 反過來 ， 對于 A??的環境 ??， 對應它的 A的環境 ?有多種選擇 ? 引理 令 ?是 ?代數 A 上的同余關系 ， 項M?Terms(?, ?)并且 ?是滿足 ?的環境 。 那么項 M在商代數 A?? 和環境 ??下的含義 (A??)〖 M〗 ??由下式決定 (A??)〖 M〗 ?? = ?A〖 M〗 ??? 等式、可靠性和完備性 ? 引理 令 E是一組 ?等式集合 ， 令 Terms(?, ?)是基調 ?上的項集 。 由 E的可證明性確定的關系?E,?是 Terms(?, ?)上的同余關系 ? 定理 （ 完備性 ） 如果 E M ? N??? ， 那么 E M ? N??? ? 完備性定理加上可靠性定理表明語法理論和語義理論相同 等式、可靠性和完備性 非空類別和最小模型性質 ? 類別 s非空：集合 Termss(?, ?)不是空集 ? 對應的載體肯定非空 ? 沒有 空載體 時 ， 可以增加推理規則 (nonempty) ? 定理 令 E是封閉于規則 （ nonempty） 的語法理論 ， 那么存在所有載體都非空的代數 A， 使得 E ? Th (A) ? 沒有空載體的代數有最小模型完備性 M = N ??, x : s? M = N ??? 同態和初始性 同態和同構 ? 將同態和同構的概念從單類代數推廣到多類代數 ? 同態是從一個代數到另一個代數的保結構的映射 （ 或叫做翻譯 ） ? 從 ?代數 A到 B的同態 h : A ? B – 一簇映射 h = {hs | s ? S }， 使得對 ?的每個函數符號 f : s1 ? … ? sk ? s， 有 hs (f A (a1, … , ak) ) = (f B (hs1a1, … , hskak) ) 同態和初始性 例 令 N = ?N, 0, 1, ? ?， 令 ?是模 k的等價關系 。 那么把 n?N映射到它的等價類 [n]?是從 N到 N??的一個同態 ， 因為 h (0) = 0N?? = [0]? h (n + m) = h (n) ?N?? h (m) = [n + m]? ? 任何代數到它商代數的同態都用這種方式定義 同態和初始性 例 含義函數是從項代數 T = Terms(?, ?)到任意代數 A的一個同態 h : T ? A。 如果 ?是 A的一個滿足 ?的環境 ， 該同態的定義是 h(M) = A〖 M〗 ? ? 這是一個同態 ， 因為 h (f M1 … Mk ) = A〖 f M1 … Mk〗 ? = f A(A〖 M1〗 ? … A〖 Mk〗 ?) = f A(h (M1 ) … h (Mk ) ) 同態和初始性 ? 引理 令 h : A ?B是任意同態 ， 并且 ?是滿足類別指派 ?的任意 A環境 。 那么對任何項 M? Terms(?, ?)， 有 h (A〖 M〗 ?) = B〖 M〗 ?h 當 M中不含變量時 ， h (A〖 M〗 ) =B〖 M〗 ? 證明 基于項的歸納 ? 引理 如果 h : A ?B和 k : B ? C都是 ?代數的同態 ， 那么合成 k ? h : A ? C也是 ?代數的同態 。 ( (k ? h)s = ks ? hs ) ? 同構 一個雙射的同態 , 寫成 A ? B 同態和初始性 初始代數 ? C是一類 ?代數并且 A?C， 若對每個 B?C， 存在唯一的同態 h : A ?B， 那么 A在 C中叫做 初始代數 – 初始代數是 “ 典型 ” 的 – 初始代數有盡可能少的非空載體 – 初始代數滿足盡可能少的閉等式 A B3 B2 B1 同態和初始性 ? 例 基調 ?0 – 類別 nat， – 函數符號 0 : nat和 S : nat ? nat。 – 令 C是所有 ?0代數構成的代數類 – 閉項代數 T ? Terms(?0, ?)是 C的初始代數 它的載體是所有閉項 0, S (0), … , S k(0), … 該代數的函數 S把 Sk(0)映射到 Sk?1(0) 該代數的元素少到能解釋所有的函數符號 該代數滿足項之間盡可能少的等式 同態和初始性 ? 引理 假定 h : A ?B和 k : B ?A都是同態 ， 并且 h ? k=IdB， k ? h =IdA。 那么 A和 B同構 ? 命題 如果 A和 B在代數類 C中都是初始代數 ，那么 A和 B是同構的 ? 命題 令 E是一組 ?等式 ， 并且令 A = Terms(?, ?)??E, ?是模可證明的相等性的代數 。 那么 ，A對 E來說是初始代數 – 由項代數和商的性質可知 ， 從 E可證明的等式在 A中都成立 – 還要證明從 A到任何滿足 E的代數有唯一的同態 同態和初始性 例 基調 ?1：類別 nat； 函數符號 0 : nat， S : nat ? nat和 ? : nat ? nat ? nat； 等式集合 E： x + 0 = x x + (Sy) = S (x + y) – Sk0 + Sl0 = Sk + l0 – 對任何閉項 M， 存在某個自然數 k， 使得 M = Sk0 – 等式 Sk0 = Sl0是不可證明的 ， 除非 k = l – 每個等價類正好包含一個形式為 Sk0的項 – 等價類和形式為 Sk0的項集間有一個雙射 – 載體看成由閉項 0, S0, … , Sk0, … 構成的集合 ， 函數 S映射Sk0 ? Sk＋ 10， ?映射 (Sk0, Sl0) ? Sk＋ l0， 得一個初始代數 – 這個初始代數和該基調的標準模型 （ 有后繼算子和加法的自然數 ） 同構 同態和初始性 ? 該規范的初始代數可以和其它有更多或較少元素的代數相對照 – 如果一個代數有更多元素的