幂等性是指一种操作或元素在首次应用后,重复应用不再产生变化的性质。对于函数 ,这意味着对每个 ,都有 。对于定义了乘法的元素 ,这意味着 。这两种表述密切相关:变换的复合本身就是一种乘法。
这一概念刻画了一步便达到最终状态的过程、具有投影作用的元素,以及重复输入或重复请求并无额外作用的操作。例子包括取实数的绝对值、将向量投影到子空间、取集合的闭包,以及为数据库字段赋予指定值。在计算领域,这里所说的相等,往往是指对系统状态产生的预期效果相同,而不是响应完全一致或执行历程完全相同。
这一术语源于十九世纪的代数学,尤其见于本杰明·皮尔斯关于线性结合代数的研究。如今,它将代数和几何中的结构问题与条件期望、逻辑运算、优化以及可靠软件的设计联系起来。其确切含义取决于重复的对象是什么,以及怎样的结果才算没有变化。
函数、不动点与收缩映射
自映射 满足以下条件时,称为幂等的:
其中, 表示函数复合。因此,它的任意正整数次迭代都等于原函数:
这里通常不包括零次迭代,因为零次迭代是恒等函数。幂等函数不一定使每个输入保持不变,但它会使自身能够产生的每个输出保持不变。
幂等函数的关键刻画是: 的像恰好就是它的不动点集:
若 ,则 。反过来,任意不动点 都属于像,因为 。因此,幂等函数将所有输入映入某个特定子集,并在该子集上起恒等映射的作用。实数上的绝对值函数就是一个例子:它的像是非负实数集,而每个非负实数都是它的不动点。同样,将向下取整函数视为实数上的实值函数时,它也使其像中的所有元素,即所有整数,保持不变。
这一描述给出了一种一般性的构造方法。选取子集 ,再选取一个函数 ,使其保持 中的每个元素不变。若 为包含映射,则 是幂等的,因为 。这样的映射 称为学术撤稿。当 非空时,幂等函数还确定了一个由其非空纤维构成的划分:每个纤维恰好包含一个不动点,作为该纤维选定的代表元。
幂等性不同于可逆性、周期性或迭代收敛性。若幂等函数是单射函数,则由等式 可得 ;若它是满射,也能得出相同结论。因此,唯一具有幂等性的双射自映射是恒等映射。相比之下,非恒等的对合映射满足 ,再次应用它会撤销自身的作用,而不是使第一次的输出保持不变。迭代算法可能趋近某个极限,却不具有幂等性:每一次有限次数的重复应用都会改变结果。幂等性描述的是应用一次后便精确地保持稳定,而不只是最终稳定或渐近稳定。
半群与重复乘法的代数
半群是配备了满足结合律的二元运算的集合。若半群中的元素 满足 ,则称其为幂等元。由结合律可知,对每个正整数 ,都有 。单位元总是幂等元,但幂等元未必是整个半群的单位元。例如,常值变换在复合运算下是幂等的,但它对其他变换并不起单位元的作用。在群中,单位元是唯一的幂等元:将 两边同乘 ,便得到 。
这一术语与本杰明·皮尔斯的《线性结合代数》有关。该著作于1870年宣讲,并于1881年在他去世后出版。皮尔斯用“幂等”指平方后保持不变的元素,同时用“幂零”指取足够高次幂后变为零的元素。这两类元素至今仍是抽象代数中的基本对象。幂等性体现了元素在乘法下的持续不变,而幂零性则体现了元素最终归零的性质。二者的相互作用有助于通过分解和表示来刻画代数。
每个非空有限半群都包含幂等元。要理解其中的原因,可以从一个元素 出发。由于半群中的元素只有有限个,它的幂最终必然重复:存在正整数 ,使得
选取 的一个正倍数 ,使 。指数 和 都位于周期部分,且二者之差是 的倍数,因此 。所以, 是幂等元。这一结果解释了为什么幂等元广泛出现于有限变换系统和有限状态计算的研究中。
每个元素都是幂等元的半群称为带。这一定义并不要求交换律成立。例如,运算 满足结合律和幂等律,但当集合中不止一个元素时,它并不满足交换律。可交换的带就是半格,它将半群乘法与序联系起来:定义
后,乘法就成为求最大下界的运算。因此,一个代数恒等式可以刻画一种序关系。
幂等元还能确定较大半群内部的局部单位元。若 ,则子集
是以 为单位元的幺半群,即使 本身没有全局单位元也是如此。有些半群的元素在整个半群中并不可逆,但其内部某些部分具有类似群的性质;这类局部结构有助于梳理这些半群的结构。这也是为什么幂等元应被视为结构性对象,而不仅仅是某个二次方程的孤立解。
环与布尔代数中的幂等元
在环(数学) 中,幂等元是满足 的元素 。在有单位元的环中, 和 都是幂等元。如果环没有零因子,那么等式
就必然推出 或 。因此,非平凡幂等元的存在表明环具有域或整环中不可能出现的结构。它们尤其有助于判断环及其上的模能否分解。
如果 是幂等元,那么 也是幂等元,并且
当 与 中的每个元素都可交换时,称其为中心幂等元。此时,
这两个分量环的单位元分别为 和 。反过来,两个非零环的直积具有非平凡中心幂等元 和 。因此,非平凡中心幂等元的存在,刻画了环可分解为非零含幺环的直积这一性质。
模算术提供了一个具体例子。在 中,剩余类 都是幂等元:
将其分解为模 和模 的算术,便能解释为何有这四种可能:在每个域分量中,幂等元只能是 或 。更一般地,如果正整数 有 个不同的素因子,那么 就有 个幂等元。每个素数幂分量都提供了在零与一之间独立选择的可能。
布尔环是每个元素都具有幂等性的环。这样的环必定具有特征二,并且是交换环。事实上,对 应用幂等性可得 ,再展开 ,便得到 ;在特征为二时,这意味着 。一个集合的幂集便是这样的例子:乘法是交集运算,加法是对称差运算,零元是空集,单位元是全集。
这一构造与布尔代数相对应。交集与并集运算满足幂等律
对于逻辑命题,相应的定律是 和 。然而,布尔环的加法并不具有幂等性:。这一区别很重要,因为同一组对象可以配备多种运算,而其中只有部分运算满足幂等律。
线性投影与矩阵结构
向量空间上的线性算子 在满足 时称为幂等算子。这类算子恰好就是线性投影,但不一定是正交投影。每个向量都可以分解为
其中 ,且 。这两个子空间的交集仅含零向量,因此有
反过来,每个分解 都唯一确定一个幂等线性映射,该映射使 中的向量保持不变,并将 中的向量映为零。因此,幂等算子同时刻画了保留的分量和舍弃的分量。
在有限维空间中,幂等矩阵在其所定义的域上可对角化。它的最小多项式整除
而这个多项式在任何域上都有两个互异的根。因此,它的所有特征值都属于 ,其中,特征值 对应的特征子空间就是它的像,特征值 对应的特征子空间就是它的核。在适当的基下,
在实数域或复数域上,这意味着迹等于秩。在正特征的域上,迹则是该整数所表示的相应域元素。
在内积空间中,正交投影还满足一个额外的对称性条件:,其中 是伴随算子。仅有幂等性并不能推出这一条件。例如,
对任意实数 都是幂等的,但只有在 时才是正交投影。当 非零时,它沿着一个不垂直于水平轴的方向投影到水平轴上。这类斜投影可能增大向量的长度,而正交投影的算子范数至多为一。
处理多个投影的相互作用时需要谨慎。如果 和 是可交换的幂等算子,那么
如果不可交换,它们的乘积就不一定幂等。交替向两个子空间作正交投影,可能收敛到向它们交集的投影,但仅作一次乘积运算通常还不能实现这一投影。这体现了精确的代数投影与迭代投影方法之间的区别。
数值计算还带来了另一层区别。在浮点运算中表示一个数学上幂等的矩阵时,它可能只满足 ,而不是严格相等。残差 衡量的是对幂等恒等式的偏离程度,而 衡量的是对自伴性的偏离程度。单独使用其中任何一个量,都无法全面描述数值计算的质量:尤其是斜投影,即使严格幂等,也可能由于其像与核的几何关系而对扰动高度敏感。
闭包、内部与序结构
幂等性广泛出现于偏序理论中,用来描述那些只需作用一次就能使指定条件完全满足的运算。在偏序集上,闭包算子是满足以下三个条件的映射 :
这三个条件分别是扩张性、单调性和幂等性。它们共同表明, 是大于或等于 的最小闭对象,其中“闭”指在 的作用下保持不变。仅有幂等性并不能保证这些序性质。
在拓扑学中,对子集取闭包是一个标准例子。若 是某个拓扑空间的子集,则其闭包 是包含它的最小闭集,并且
取内部则是序对偶的构造:它具有单调性、收缩性和幂等性。 的内部是包含于 的最大开集。这两种运算通常都不可逆,因为不同的子集可能具有相同的闭包或相同的内部。
其他闭包算子则来自生成过程。在向量空间中,对一个集合的线性包再次取线性包,结果不变。在群中,由一个集合生成的子群已经对群运算封闭。在逻辑中,只要后承关系按通常的闭包性质定义,一组前提的所有推论所组成的集合就是演绎封闭的。这些例子涉及不同的数学对象,却具有相同的机制:第一次作用就已纳入满足某个条件所需的一切,因此再次作用不会增加任何内容。
对于拓扑空间 ,其幂集上的闭包运算还具有以下性质:
这些性质与扩张性、幂等性一起构成库拉托夫斯基闭包公理。借助这些公理,可以从一个算子恢复出拓扑,而不必通过开集来指定拓扑。更一般的闭包算子不一定保持有限并,因此并非所有序理论中的闭包都来自某个拓扑。
幂等性也是格的交运算与并运算的基本性质:
这里重复的是操作数,而不是一元运算的输出。这一区别很重要:闭包算子在复合运算下具有幂等性,而交与并则是幂等的二元运算。此外,两个闭包算子的复合不一定是幂等算子。如果它们可交换,其复合仍是闭包算子;若不满足交换律,交替应用这两个算子可能需要经过多个阶段才能达到共同不动点。
条件期望与统计投影
在概率论中,条件期望是一种重要的幂等运算。设 为概率空间, 为一个子 -代数。对于可积随机变量 ,定义
所得结果已经是关于 可测的,因此再次以 为条件求期望,结果不变:
这些等式几乎必然成立;如果将几乎必然相等的随机变量视为同一等价类,那么这些等式就严格成立。
对于平方可积随机变量,条件期望在希尔伯特空间 中具有几何解释。关于 可测的平方可积随机变量构成一个闭线性子空间,而 就是到该子空间的正交投影。残差满足
其中 可以是任意关于 可测的平方可积随机变量。这一性质表明,条件期望是利用 所代表的信息能够得到的对 的最小二乘逼近。上述定义的条件期望在 中也存在,但此时不再具有希尔伯特空间中的正交投影解释。
对于嵌套的信息集 ,由塔式性质可得
先以较细的信息为条件求期望,再以较粗的信息为条件求期望,得到的就是基于较粗信息的条件期望。对于已经由较粗信息确定的变量,以较细信息为条件求期望不会改变它。令 ,便得到幂等性。对于两个不存在嵌套关系的信息集,其条件期望算子未必可交换,这与一般线性投影的情形类似。
在普通最小二乘法中,列满秩的设计矩阵 对应的拟合值矩阵为
它满足 和 。响应变量的拟合值为 ,使用同一设计矩阵对这些拟合值再次进行拟合,结果不会改变。残差生成矩阵 也是一个正交投影。如果设计矩阵的秩为 ,这两个投影的秩就分别为 和 ,从而将几何结构与回归的自由度联系起来。
并非所有统计平滑操作都具有幂等性。对于岭回归,平滑矩阵
在 时,沿设计矩阵的非零方向通常具有严格介于零与一之间的特征值。再次应用该矩阵,会进一步收缩这些分量。因此,投影与收缩之间的区别,可以直接表述为幂等线性算子与非幂等线性算子之间的区别。
范畴论中幂等态射的分裂
在范畴论中,幂等态射是满足下式的自同态 :
这将相应的函数方程抽象化,而不要求对象是集合,也不要求态射是通常意义上的函数。如果存在对象 及态射
使得
则称该幂等态射分裂。映射 是收缩映射, 是截面。它们在 上的复合将 投影到 的一个副本上。
在集合范畴中,每个幂等态射都可以通过其像分裂。对于向量空间、群、模和拓扑空间,只要为像赋予适当的继承结构,同样的结论也成立。对于向量空间,由此得到的收缩核也是直和项,因为核提供了一个补子空间。在其他范畴中,“收缩核”是更一般的概念,并不一定意味着存在同类的直和分解。
在任意范畴中,幂等态射并不一定分裂,因为所需的对象可能不存在。考虑一个只有一个对象的范畴,其自同态由整数构成,复合运算为整数乘法。自同态 是幂等的。如果它能够分裂,就必须存在整数 ,使得 且 ,这是不可能的。尽管乘法运算中存在幂等元,这个范畴却没有另一个对象可用于表示它的像。这说明,当仅用对象和态射来表述时,一种熟悉的逐元素构造为何可能失效。
若一个范畴中的每个幂等态射都分裂,就称该范畴是幂等完备的,或称为 Karoubi 范畴。每个范畴都有一个幂等完备化,也称为其 Karoubi 包络。它的对象是二元组 ,其中 是 的幂等自同态。从 到 的态射是满足下式的态射 :
上的恒等态射是 ,而不一定是 上原有的恒等态射。这一构造以形式化方式补入了使所有幂等态射分裂所需的像。
这套语言对于模尤其有用。一个有限生成模是投射模,当且仅当它是某个有限秩自由模的直和项。等价地,它同构于作用在该自由模上的某个幂等矩阵的像。因此,矩阵方程 成了具体描述抽象直和项的一种方式。幂等完备化以一种适用于多种代数情境的形式,表达了从自由对象到其收缩核的这一过渡。
幂等加法与优化
幂等半环是加法满足下式的半环:
与环不同,半环不要求存在加法逆元。这一点至关重要:在加法群中,等式 会推出 。因此,幂等加法支持这样一类代数系统:合并备选项时消除重复,而不是累加重复次数。
最大加半环是一个核心例子。其底集为
运算定义为
加法单位元为 ,乘法单位元则是通常的数 。约定 ,使加法单位元成为乘法的吸收元。加法具有幂等性,因为 ,但乘法通常不具有幂等性:。最小加半环则采用取最小值和普通加法,并以 为加法单位元。
这些运算可以用来表示图论中的路径问题。在最小加矩阵乘法中,
如果矩阵元素表示边的代价,那么乘积就会选出经过一个中间顶点的最低代价路线。矩阵的幂表示在边数给定的游走中所能达到的最小代价,而将这些幂适当组合,则可以处理更广泛的最短路径问题。同一个候选代价即使被重复列出,也不会改变最小值,这正是幂等加法在运算中的作用。负环需要单独处理,因为反复沿负环行进会使代价不断下降,从而不存在有限的最优值。
任何交换且幂等的加法都可以通过下式定义一个自然序:
对于最大加半环,这就是通常的数值顺序;对于最小加半环,则是相反的顺序。在这个诱导序中,加法给出的正是最小上界。这就在半环代数与数学优化的序理论表述之间建立了直接联系,其中包括通过取最小值或最大值来合并候选值的动态规划递推式。
这一更广泛的领域通常称为热带数学,不过这个术语涵盖了若干相关的约定和构造。热带多项式用取最小值或最大值代替普通加法,用加法代替乘法,从而得到分段线性函数。因此,其几何轨迹由多个仿射表达式并列取到最小值或最大值的条件来描述,而不是由普通多项式的零点来描述。由此可见,幂等性并不局限于将现有对象作投影的运算:对于以选择最佳备选项取代对所有备选项求和的系统,它也可以充当一条基本的算术法则。
重复请求与软件状态
在计算机科学中,如果重复执行某个操作对系统状态产生的预期效果与执行一次相同,通常就称该操作具有幂等性。若命令 引起状态变换 ,则其数学要求为
赋予一个固定值,例如将状态设为“已关闭”,可以满足这一等式;而递增计数器通常不能。这里的关键单位是包含参数在内的完整命令:两次赋予同一个值,与先后赋予两个不同的值并不相同。
这种基于状态的解释,并不要求执行过程中所有可观察到的方面都完全一致。重复执行删除操作时,第一次可能报告成功,之后则报告“未找到”,但资源最终处于相同状态。日志、监控计数器和响应时间戳也可能不同。因此,声称某个操作具有幂等性时,需要明确其适用范围:是应用程序预期的状态变换、整个数据库,还是所有外部可观察的事件。同一个操作,在一种解释下可能是幂等的,在另一种解释下则可能不是。
超文本传输协议使用幂等性对请求方法进行分类。按照 HTTP 语义,PUT 和 DELETE 是幂等的,包括 GET 和 HEAD 在内的安全方法也具有幂等性。这里关注的是多个相同请求在服务器端产生的预期效果,并不保证响应报文完全相同。POST 并未被定义为幂等方法,但应用程序可以将某个具体的 POST 操作设计为能够抑制重复操作。一个幂等的 DELETE 操作可以在首次执行时移除资源,而在后续执行时发现该资源已经不存在。
幂等性在分布式系统中十分重要,因为服务器执行请求后、响应到达之前,客户端可能失去连接。此时重试就可能重复产生效果。应用程序编程接口可以接受幂等键,即由客户端提供、与某一次逻辑操作关联的标识符。服务器可以将该键与操作结果一并存储,并在重试时复用该结果。正确地抑制重复操作需要协调机制:如果记录键与执行状态变更是分开进行的,就可能留下发生故障的时间窗口。请求载荷校验、保留期限,以及使用同一个键的并发请求,也都会影响这一保证。
相关系统会利用本身就具有幂等性的操作。向集合中添加同一个元素两次,得到的集合与只添加一次相同。在复制数据结构中,通过并运算合并状态,可以具备结合性、交换性和幂等性,从而允许消息重复送达或乱序送达,而不改变合并结果。这些代数性质是许多无冲突复制数据类型的核心,不过收敛性还取决于该结构的其他规则。
幂等性仍有别于确定性、事务原子性和恰好一次处理。确定性的递增操作执行两次,仍会递增两次;原子事务也可能提交两次;而重复抑制可以让多次执行看起来只发生了一次,却不能保证底层代码确实只运行过一次。它们所共享的数学判据更为有限:首次应用之后,重复应用不会再使所指定的状态或效果发生变化。