12.3 同态与同构
本章目录 · 1 节
本章导读
【同构的直观意义】模3加法Z₃={0,1,2}与A={0,2,4}上的模6加法,通过f(0)=0、f(1)=2、f(2)=4一一对应。两张表把元素统一换名后完全相同。
【定义12.3.1】同类型系统V₁=⟨A,○⟩、V₂=⟨B,*⟩,若f:A→B满足 (所有x,y∈A),称同态。必须既是函数,又保持指定运算;不是任意两个同类型系统之间的函数都为同态。
同态若单射称单同态,若满射称满同态,若双射称同构,记V₁≅V₂。同构的逆映射也保持运算,所以它表示结构一致,只是元素名称不同。f:A→A为自同态;双射自同态称自同构,单自同态、满自同态分别强调相应的映射性质。
【同态像与保持性质】f(A)对*封闭,因为f(x)*f(y)=f(x○y)仍在像内。交换、结合、幂等等恒等式从V₁传到f(A),但不能在f不满射时推及B的全部元素。两个指定二元运算须分别保持;一元运算u须满足f(u(x))=u′(f(x));指定常数c须满足f(c)=c′。
若单位元e₁未显式列入签名,同态至少使f(e₁)成为像f(A)的单位元;f满射时才必然是整个B的单位元。零元同理。若运算结合且e被保留,可逆元素的像可逆,。不是满射又未指定保单位时,不能直接把像内单位元与目标单位元等同。例如从单元素单位系统映到⟨{0,1},普通乘法⟩的常值0映射保持乘法,却将源单位元映成0而非目标单位元1。
通常消去律不一定被满同态像保留。例:非负整数加法的消去半群通过f(0)=0、f(n)=1(n>0)满同态到{0,1}上的max,因为f(m+n)=max(f(m),f(n));但max(1,0)=max(1,1),0≠1,目标不消去。恒等式的保持结论不能扩大到这类带蕴含的性质。
【例12.3.1】(1)f:Z→Zₙ,f(x)=x mod n,n≥1,是满同态:,且每个剩余类都由其代表元命中。n=1时目标只有0,映射仍成立。
(2)f:R→R*,f(x)=eˣ,是单同态,因为eˣ⁺ʸ=eˣeʸ,且指数函数严格递增。像为正实数,不包含任何负数,所以不是到R*的满射;若目标改为正实数乘法系统,它才是同构。
(3)对任意整数a,fₐ:Z→Z,fₐ(x)=ax,是加法自同态。a=0为零同态;a=±1为自同构;|a|≥2为单而不满的自同态,像为aZ。证明保持加法只需展开a(x+y)=ax+ay。(例完)
【例12.3.2】Zₙ模加法恰有n个自同态,分别是 ,0≤p<n。它们保持模加法;p不同则fₚ(1)不同(n≥2)。反之任意自同态满足f(0)=0,由x是x个1的模和可得f(x)=xf(1) mod n,完全由f(1)决定,所以没有更多。n=1时单元素集合上恰有唯一自映射,另行验证即可,不能把不在Z₁中的1当作输入。
进一步,fₚ为自同构当且仅当gcd(p,n)=1(n≥2);若gcd>1则会把不同元素合并,若互素则由模逆元给出逆映射。这也说明“自同态”不自动是自同构。(例完)
【例12.3.3】进程代数:售货机与顾客。进程代数用动作、选择、并行、限制等算子描述并发通信。输入动作a、输出动作ā互补,相互同步时产生内部动作τ。动作前缀α.P表示先执行一个动作α,再按进程P运行。
为避免将“动作前缀”误当成任意两个进程的普通顺序乘法,采用明确的多类签名:对每个固定动作α,α.是“进程→进程”的一元算子;+和|是两个进程到进程的二元算子;0是停止进程常数;对固定名字集合L,限制算子P\L是一元算子;递归常量可描述持续服务。标准CCS常用递归定义,并还可包含重命名;加入!P时是允许复制的版本,不应把某一简化语法列成所有CCS唯一的六个算子。
用递归写售货机与反复购买咖啡的顾客:
M接收硬币后才可提供咖啡或茶;C投入硬币后等待咖啡。令L={coin,coffee,tea},闭合系统(M|C)\L首先在coin上同步,成为 ,再在coffee上同步恢复(M|C)\L。两步都是τ;此顾客没有tea的互补输入,限制下不能单独完成tea分支。
若沿用原书的复制版本,定义 、,!P可展开为P|!P。第一次同步后,一个会话进入饮品选择,同时仍保留复制服务;第二次同步完成该会话。它允许并发多次会话,并不与只维护单个顺序会话的递归写法在所有并发情形下自动相同。复制符号作用范围须用括号写清,不能漏掉动作上划线或把两个进程直接拼接而不写|。
【算子与等价】0表示不再执行动作;+表示选择其中一个分支;|表示并行及可能的互补同步;限制屏蔽该名字的对外独立动作而保留内部同步。动作前缀优先于并行、并行优先于选择,限制和复制的范围以括号明确标出,不靠不完整的优先级说明猜测。
在强互模拟等价(用∼表示)下,、、;并行也有 、、。这些是行为等价,不是未经约定的原始字符串完全相等。互模拟要求一边的每一步都能由另一边匹配,继而比较后继状态,可用来验证实现与规范行为一致;这里讨论的是行为保持,不等于自动保证耗时、吞吐量等全部性能指标。
补充核验资料:UNSW《Modelling Concurrent Systems》课程讲义 https://cgi.cse.unsw.edu.au/~rvg/6752/notes.html ;École Polytechnique/CSE 520的CCS讲义 https://www.lix.polytechnique.fr/~catuscia/teaching/cg520/01Fall/lecture_notes/L16and17and18.html 。复制版本可参考Hirschkoff与Pous的原始研究 https://arxiv.org/abs/0810.2061 ,用于区分动作前缀、并行、限制和复制的含义。(例完)
