域理论中的自然不动点定理

258理论计算机科学电子笔记45（2001）网址：http://www.elsevier.nl/locate/entcs/volume45.html11页Domain理论凯耶·马丁牛津大学计算机实验室Wolfson Building，Parks Road，Oxford OX1 3QDhttp://web.comlab.ox.ac.uk/oucl/work/keye.martin摘要我们揭示了新的成果的基础上的测量，保证存在唯一的不动点，不需要最大。此外，我们建立了最小不动点总是μ拓扑中的吸引子，然后在分析中探索这些发现的后果特别地，得到了Banach不动点定理在紧度量空间[3]上的一个推广1介绍Domain理论中的标准不动点定理指出，dcpoD上的Scott连续映射f：D→D具有最小元素f的最小不动点点由fix（f）：=。n≥0fn（n）.这可能是域理论中最重要的结果，它在处理递归语义方面的有效性，以及它的推理自然地扩展到范畴层次来解释为什么像D[D→D]这样的方程可以求解的事实。可以说，它的缺点之一是它只适用于连续的映射，因为现在有更一般的不动点定理可用[5]。然而，在连续映射的上下文中，唯一似乎合理的批评是它的规范不动点并不像它们可能的那样规范。毕竟，有一件事比最小固定点更令人满意：唯一的固定点。利用最初在[6]中引入的思想，我们建立了Domain理论中的自然不动点定理，它们保证了唯一的吸引不动点的存在在接下来的三节中，我们讨论域，内容和不变性。这些都是以后需要的初步想法。然后我们在域上引入压缩，并证明了关于它们的不动点定理，这让人想起了分析中的Banach定理。事实上，这个新结果有巴拿赫定理作为其后果之一。2000年1月，出版社dbyElsevierScienceB。 V. 在CC BY-NC-ND许可下开放访问。马丁259⊆↑{∈}∈最后，在具有最小元的整环的情况下，我们知道最小不动点在μ拓扑中总是吸引的，并且关于压缩的结果对于更大更自然的一类非扩张映射也成立。由于后者，可以得到紧度量空间上Banach不动点定理[3]2背景偏序集是一个偏序集[1]。定义2.1设（P，±）是一个偏序集。P的最小元素满足对所有x的±x，当它存在时。一 个非空子集S ∈ P是有向的，如 果 （x，y∈S）（z∈S）x，y±z。 一个subset的super emu。SP是它的所有上界中最小的，只要它存在。这是写DCPO是一个偏序集，其中每个有向子集都有一个上确界。定义2.2对于dcpoD的子集X，S. 一↑X：={y ∈ D：（<$x ∈ X）x ± y} &↓X：={y ∈ D：（<$x ∈ X）y ±x}。对于元素x∈X，我们记为↑x=↑{x}和↓x=↓{x}。dcpoD中的极大元的集合是max D ={x ∈ D：↑ x ={x}}。根据Hausdor极大性，每个dcpo至少有一个极大元素。定义2.3dcpoD的子集U是Scott开的，如果(i) U是一个上集合：x∈Ux±y∈U，并且(ii) U是不可达的有向上确界：对于每个有向S D，。S∈ U <$S<$U/=<$。D上所有Scott开集的集合σD称为Scott拓扑。命题2.4dcpo之间的映射f：D→E(i) f是单调的：x ± y <$f（x）± f（y）。(ii) f保持有向上确界：对于每个有向SD，。。f（ S）=f（S）.定义;定义第二条. 在dcpo（D，±）中，一个xi的所有有向子集S∈D，x±S<$（S∈S）a±s. 设↓x={a∈D：ax}。 dcpoD是连续的，如果对所有x∈D，↓x是有上确界x的定向的。集合x = y D：x y对于xD形成了连续dcpo D上Scott拓扑的基础。最后，我们采用本文中“域”的以下定义定义2.6一个Domain是一个连续的dcpo D使得对所有x，y∈D，存在z∈D且z±x，y。马丁260⊥→ →∞→。例如，具有最少元素的连续dcpo是当前意义上的域。3内容本节和下一节中的思想在[6]中有令人尴尬的细节。 设[0，∞）∞是序为x±y惠y≤ x的非负实的整环.定义3.1连续dcpoD上的Scott连续映射μ：D→[0，∞）n诱导X附近的Scott拓扑<$D，如果对所有x∈X和所有序列xnX，limµxn =µxn→∞。xn=x，这个上确界是有向的 我们把它记为μ→ σX。也就是说，如果我们观察到一个近似序列（xn）计算x，它实际上确实计算了x。映射μ测量X中对象的信息内容。 出于这个原因，我们有时会说μ测量X。定义3.2测量是一个Scott连续映射μ：D→ [0，∞）μ，它测量集合ker μ={x∈ D：μx = 0}。这个想法的本质是，通过测量环境传递给我们的信息可以被认为是真实的。下面是这个原则的一个例子。命题3.3设μ：D→ [0，∞）是具有μ→σD的测量。然后(i) 对所有x∈D，μx = 0 <$x∈ max D。(ii) 对所有的x，y ∈ D，x ± y &μx = μy μ x = y。(iii) 一个单调映射f：DD是Scott连续的，i µf：D[0，）是Scott连续的。测量的最初动机之一是希望证明有用的不动点定理。一般来说，“有用”的意思是容易应用于非单调映射的定理，或者比斯科特不动点定理更能说明单调映射的结果。这是第一个发现后一种类型的例子[6]。定理3.4设f：D D是域D上的单调映射，其度量为μ，且有常数c1，使得（x）μf（x）≤ c·μx。如果存在一个点x∈D，其中x±f（x），则xx=n≥0fn（x）∈maxD⇒马丁261→→→∈是f在D上的唯一不动点。此外，x是两种不同意义上的吸引子：(i) 对所有的x∈kerμ，在kerμ上的Scott拓扑中fn（x）→x∈ k(ii) 对于所有的x ±x，n≥0 fn（x）=x≠ 0，这个上确界是D上的Scott拓扑这个定理的唯一问题是它需要不动点极大值。很快我们将发现一些新的结果，这些结果似乎用一种更优雅的方法克服了这个困难。4不变性所有衡量一个领域的方法都有一个共同的目标。定义4.1连续dcpo D上的μ拓扑以所有形式为↑x <$<$y的集合为基，其中x，y ∈ D。 它表示为µD。斯科特拓扑的一个不令人满意的方面是它的弱极限概念。理想情况下，人们希望任何在斯科特拓扑中有极限的序列都有一个上确界。但事实远非如此。 例如，在一个具有最少元素的连续dcpo上，所有序列都收敛于dcpo。引理4.2（Martin [6]）设D是连续dcpo。然后(i) 序列（xn）收敛到μ拓扑中的一个点x，它收敛于对Scott拓扑中的x和（？n）xk± x，对所有k ≥ n.(ii) 如果xn x在µ拓扑中，则存在最小整数n，使得。xk= x.k≥n(iii) 如果（xn）是一个序列，其中xn±x，则在μ拓扑i中xn→xxn→x在Scott拓扑中。简而言之，µlimits是具有计算意义的Scott limits命题4.3连续dcpo之间的单调映射f：DE是它是Scott continuous。那么，这一切与信息内容有什么关系呢？给定测量值μ σD，考虑元素ε-接近xD，对于ε > 0，给定通过µε（x）：={y ∈ D：y ± x &|µx − µy|<ε}。无论我们使用哪种测量方法，这些集合始终是µtopology. 事实上，正是这个属性定义了域上的内容定理4.4（Martin [6]）对于Scott连续映射μ：D→[0，∞）μ，μ→σDi<${με（x）：x∈D&ε> 0}是D上μ拓扑的基。马丁262→→ →∞→这一认识不仅提高了我们对µ拓扑的理解，还使我们能够更有效地利用测量。引理4.5设（D，μ）是一个连续的dcpo，度量为μ →σD。(i) 如果（xn）是一个序列，其中xn±x，则xnxin theµ topology i µlimn→∞ µxn= µx。(ii) 一个单调映射f：D D是Scott连续的i ∈µf：D[0， ）∈µ连续。请注意，斯科特拓扑总是可以从µ拓扑恢复为σD={↑U：U∈µD}。5收缩不动点在本节中，（D，µ）是一个度量为µ→ σD的域。定义5.1设f是（D，μ）上的单调自映射。如果存在一个常数c，x±y<$µf（x）−µf（y）≤c·（µx−µy），对所有x，y ∈ D，则f是压缩的，<如果c ≤ 1，则f是非扩张的.命题5.2收缩是斯科特连续的。证据首先，μf是μ连续的。 根据定理4.4，D上的μ拓扑首先是可数的，因此我们可以用序列来验证这个断言。设xn→x在D上的μ拓扑中。然后我们可以假设xn±x。因此0≤µf（xn）−µf（x）≤c·（µxn−µx）这意味limµf（xn）=µf（x）n→∞因为µxnµx。故f是连续的。根据引理4.5（ii），f是Scott连续的。✷最后一个命题不需要压缩：同样的证明适用于任何c≥0的值。这是我们的下一个结果，需要c<1。定理5.3设f是（D，μ）上的压缩。如果有一个点x±f（x），然后fix（f）：=。n≥0fn（x）是f在D上的唯一不动点。证据 通过Prop。5.2，f是Scott连续的，所以很明显fix（f）是f的不动点。马丁263。→±/±n设x=f（x）和y=f（y）是f的两个不动点。通过我们对D的假设，存在一个元素z∈D，其中z±x，y。 然后fn（z）±x=fn（x），对于所有n ≥ 1。 通过归纳，我们有µfn（z）−µfn（x）=µfn（z）−µx≤cn·（µz−µx），对于所有n≥1。则μfn（z）→μx，因此fn（z）=xn≥0因为μ→σD。同样的道理也适用于y。✷事实上，仔细检查最后一个定理的证明表明，唯一不动点是μ拓扑中的吸引子定义5.4空间X上的连续映射f：X X的不动点p= f（p）称为吸引子，如果在p周围存在开集U，使得fn（x）→p对于所有的x∈ U。我们也把p称为吸引力。有吸引力的不动点的例子很容易找到：在双曲迭代函数系统的分析中，它们有时被称为分形，或者在数值分析中的迭代方法的研究中，如牛顿推论5.5设f是（D，μ）上的压缩。 如果afix（f），则。fn（a）= fix（f），n≥0这个上确界是μ拓扑中的极限。也就是说，fix（f）是µ拓扑中的吸引子。证据这个主张在前面的定理中是隐含成立的。对于吸引子位，令U=↓fix（f）。这是一个较低的集合，因此是开放的。✷因此，从fix（f）的任何近似a开始，迭代fn（a）收敛到fix（f），即使a f（a）。此外，我们可以很好地估计需要多少次迭代才能实现fix（f）的ε-近似。命题5.6设f是（D，μ）上的压缩，具有唯一不动点fix（f）. 对于任何x ± fix（f）和ε> 0，n>log（µx−µfix（f））−logεlog（1/c）对于任何整数n≥ 0，提供x/= fix（f）。⇒ |µf（x）−µ fix（f）|ε<，证据 如果c = 0，则f是常数，并且该陈述平凡地成立，采用log（1/0）= log ∞ = ∞的约定。设0<为<1。马丁264⇒·−≤·±→∞对于整数n≥0，我们有n n n|=µf（x）−µfix（f）≤c |= µf (x) − µ fix(f) ≤c因此，在本发明中，·（µx − µ fix（f））。n>log（µx−µfix（f））−logε cn（µx µfix（f））<ε，log（1/c）这证明了他的说法✷当然，为了使估计有用，我们必须知道fix（f）的度量。一个容易计算的例子是如果µf（x）c µx。 则μ fix（f）= 0。令人惊讶的是，这个条件等于说f是kerμ上连续映射对D的扩张。命题5.7对于（D，μ）上的收缩f，其中kerμ = maxD，以下等价：(i) 映射f保持极大元。(ii) 对所有x∈D，μf（x）≤c·μx。在任何一种情况下，fix（f）∈ max D。证据 设f具有收缩常数c。(i) （ii）：设x∈D. 通过D的有向完备性，存在元素y∈ ↑x<$maxD。然后µf（x）−µf（y）=µf（x）≤c·（µx−µy）=c·µx成立，因为µf（y）= 0 by（i）。(ii) n（i）：设x ∈ max D. 则μx = 0，所以0 ≤ μf（x）≤c·μx = 0。因此，在本发明中，f（x）∈ ker µ = max D.✷事实上，完备度量空间上的每一个压缩都可以表示为上述类型的整环上的一个压缩。例5.8设f：X→X是完备度量空间X上的一个压缩，Lipschitz常数为 0。令人高兴的是，对于这样的地图，我们可以证明最后的结果，假设只有一个测量。定理6.3设（D，μ）是一个具有度量μ和最小元素μ的连续dcpo。 如果f：D → D是Scott连续映射，其中μf（x）<μx，x >0，则fix（f）：=。n≥0fn（n）∈maxD是f在D上的唯一不动点。此外，如果f（ker µ）ker µ，则（f∈ k∈k）fn（x）→fix（f），在ker μ上的相对Scott拓扑中。马丁267∈⊆证据 如果μ fix（f）> 0，则μ fix（f）= μf（fix（f））<μ fix（f）。因此，μ fix（f）= 0，这意味着fix（f）ker μ max D。但如果一个最小不动点是极大的，它必须是唯一的。马丁268∈→±→为了证明fix（f）是ker μ上的相对Scott拓扑中的吸引子，让U D是fix（f）周围的Scott开集。 然后有K使得n≥K<$fn（n）∈U这意味n≥Kfn（x）∈Ukerµ因为fn（k）±fn（x）和f（kerµ） kerµ。因此，在ker µ上的相对Scott拓扑中，对于任何初始猜测x∈ ker µ，f n（x）→ fix（f）。✷这与定理3.4推广到具有最少元素的域上的更大类映射的结果相同。此外，在后两个结果中，定理6.1都暗示了fix（f）是D上μ拓扑中的吸引子。现在说说为什么这一切都很重要。7应用又到了十六岁的时候了。设f：[0，π/2] [0，π/2]为f（x）= sin x。众所周知，从任意点x [0，π/2]开始，依次应用f，会产生一个迭代序列（f n（x）），它神奇地趋向于零。为什么？为什么？乍一看，人们会想到巴拿赫定理，它解释了收缩的这种行为。然而，经过仔细检查，我们发现正弦波的情况更有趣。 因为fJ（0）=1，f（x）= sinx不是[0，π/ 2]上的压缩，因此Banach定理是不适用因 但领域理论是。例7.1设D=[0，π/ 2]π是定义域，x±y惠y≤x自然测量µx = x。函数f（x）= sinx是D上的单调自映射.根据中值定理，如果x±y和xi=y，则存在c∈（y，x）使得µf（x）− µf（y）= f（x）− f（y）= f J（c）（x-y）=（cos c）（µx −µy）。因此，µf（x）−µf（y）<µx−µy，因为0 cosc 1。<那么定理6.2意味着f有唯一的不动点，由下式给出：。fix（f）= fn（π/2）.n≥0然而，f（0）= 0，所以我们必须有fix（f）= 0，通过唯一性。有趣的是。根据定理6.1，fix（f）是一个吸引子，µ拓扑。因此，对于任何x fix（f），fn（x）fix（f）在µtopology中。但是D上的μ拓扑中的收敛意味着欧几里得拓扑中的收敛。因此，对于所有x∈[0，π/2]，fn（x）→ 0。事实上，上一个例子中的推理可以扩展到任何紧致度量空间，因为它们都可以被建模为测量的核[4]。马丁269→¯→→{∈}命题7.2（[3]）设f：X X是紧度量空间（X，d）上的函数，使得d（fx，fy）0，要么μf（x）= 0<μx，要么x的紧性产生不同的点a，b∈x，使得µf<$（x）=d（fa，fb）1且为奇数），我们可以对元素f±g写出：µφ（f）−µφ（g）=Σf（n−2）= 012n+1−Σg（n−2）=12n+1Σ=f（ n）= 0112n+3−Σg（ n）= 112n+3=4（µf − µg）。根据定理5.3，φ有唯一的不动点。显然，这个不动点不是极大的：它在集合{2k +1：k >1}上未定义。8想法很高兴看到基于度量的语义方法被基于定理5.3的结果的方法所取代。特别是在CSP模型上。试图获得估计的精神。5.6对于非扩张性地图来说也是一个有趣的问题。如果能弄清楚信息导数[6]（一个域上的地图相对于测量的导数）在这方面是否有用，那就太好了。9确认特别感谢Ulrich Kohlenbach让作者意识到[3]。引用[1] S. Abramsky和A.俊作。域理论In S. Abramsky，D. M. 加贝T. S. E. Maibaum，编辑，计算机科学逻辑手册，卷。三.牛津大学出版社，1994年。[2] A. Edalat和R. 赫克曼 度量的一个计算模型 空间.理论计算机科学193（1998）53[3] M.艾德斯坦关于压缩映象下的不动点与周期点。伦敦数学学会杂志37（1962）74[4] K.马丁计算模型的非经典技术。Topology Proceedings，vol. 24，1999.[5] K.马丁领域理论中的测量过程。 第27届自动机、语言和程序设计国际学术讨论会论文集（ICALP），计算机科学讲义，第一卷. 1853年，Springer-Verlag出版社，2000年。[6] K.马丁计算的基础。博士论文，杜兰大学数学系，2000年。