泛代数和代数数据类型课件.PPTVIP

3.4 同态和初始性 例 含义函数是从项代数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 ) ) 3.4 同态和初始性 引理 令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 3.4 同态和初始性 3.4.2 初始代数 C是一类?代数并且A?C，若对每个B?C，存在唯一的同态h : A ?B，那么A在C中叫做初始代数 初始代数是“典型”的 初始代数有尽可能少的非空载体 初始代数满足尽可能少的闭等式 A B3 B2 B1 3.4 同态和初始性 例 基调?0 类别nat， 函数符号0 : nat和S : nat ? nat 令C是所有?0代数构成的代数类 闭项代数T ? Terms(?0, ?)是C的初始代数 它的载体是所有闭项0, S (0), …, Sk(0), … 该代数的函数S把Sk(0)映射到Sk?1(0) 该代数的元素少到能解释所有的函数符号 该代数满足项之间尽可能少的等式 3.4 同态和初始性 引理 假定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的代数有唯一的同态 3.4 同态和初始性 例 基调?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，得一个初始代数 这个初始代数和该基调的标准模型（有后继算子和加法的自然数） 同构 3.4 同态和初始性 该规范的初始代数可以和其它有更多或较少元素的代数相对照 如果一个代数有更多元素的话，那么这些多余的元素不能由项定义（有假货） 整数代数Z A = ?Anat, 0A, SA, +A? Anat = (?0? ? N) ? ({1} ? Z) 0A = ?0, 0? SA?i, n? = ?i, n +1? ?i, n? +A ?j, m? = ?max(i, j), n +m? 如果一个代数有较少元素的话，那么就有一些不能被证明为相等的项在该代数中被等同（出现混淆） 模k的自然数 3.4 同态和初始性 初始代数可能满足不能由E证明的额外的等式 例 上面的自然数基调例子中，初始代数满足等式 x + y = y + x 因为 E M = Sk0和E N = Sl0 蕴涵 E M + N = Sk+l0 = N + M 不满足交换性的代数 Anat是所有f : X ? X的函数的集合（X至少有两个元素） 0A是X上的恒等函数，SA是Anat上的恒等映射 +A是Anat上的函数合成 A = ? Anat ? 0A? SA ? +A ?满足E +A没有交换性，因为函数合成没有交换性 3.4 同态和初始性 基项、基代换、基实例（项、等式） 如果M ? N???是Termss(?, ?)的项之间的等式，并且S是一个?，?基代换，那么就把SM ? SN???称为M ? N???的基实例 命题 令E是一组?等式，并且A对E来说是初始代数。对任何?