通用性ω-双有限域的概率结构和测度证明：基于概率方法构建无限偏序与泛域的测度1

理论计算机科学电子笔记173（2007）103-119www.elsevier.com/locate/entcs几乎每个领域都是通用的曼弗雷德·德罗斯特和迪特里希·库斯克InstitutfurIinforormatikUniversitaütLeipzigGermany摘要我们赋予ω-双有限域的集合一个概率空间的结构，并且我们将证明在这个空间中所有泛域的集合具有测度1。 为此，我们提出了一种概率方法，将有限偏序扩展一个元素。迭代地应用这个过程，我们得到一个无限偏序。 我们证明，以概率1，这个无限偏序的cpo-完备化是泛齐性ω-双有限域。通过交替使用概率单点扩张和完备化过程，我们几乎必然地分别得到了泛的和齐次的ω-代数格、ω-Scott域和ω-双有限L-域.我们还证明了在射影拓扑中，泛齐性ω-双有限域的集合是剩余的（即，comeagre），我们提出了一个明确的数论建设这样的域。关键词：Domain Theory，Universal Homogeneous Domain，Probabilistic Systems，ConstructiveMathematics，Topological Models1介绍在编程语言的指称语义理论中，一些作者建立了特定类型的“通用”域的存在Scott[23]为所有的ω-代数格类提供了一个泛域，并证明了在这个域中的计算可以用收缩演算来处理。Plotkin [21]和Scott [24]给出了所有凝聚的、有界完备的ω-代数域类的泛域Gunter和Jung[15]以及Droste和Go？bel[7]提出了一种关于共形结构域或泛齐性结构域的系统。 让我们回想一下，一个域类C的域U被称为泛域，如果C的每个其他域可以嵌入（通过嵌入投影对）到U中，并且U是齐次的，如果U的两个有限子域之间的每个同构扩展到U的自同构;直观地，1电子邮件：droste@informatik.uni-leipzig.de2 电子邮件地址：kuske@informatik.uni-leipzig.de1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.02.030104M. Droste，D.Kuske/Electronic Notes in Theoretical Computer Science 173（2007）103均匀性意味着U具有最高可能的结构对称度这样的泛齐性域直到同构都是唯一的。有关各种通用域的进一步结果，请参见[16]，[17]，[15]，[6]，[9]和[10]。[20 ]第20段。在本文中，我们将提出一个概率结构的域，我们将表明，与概率1，它将产生一个普遍的齐次域。更具体地说，我们将对四类域实现这一点：ω-代数格，ω- Scott域（=有界完备ω-代数域），ω-双有限L-域和ω-双有限域。我们构造泛齐性ω-双有限域的过程如下。注意，任何定义域都是由它的紧元素子集的结构唯一确定的。由于这个集合是可数的，我们可以假设它是自然数的集合N（任何元素下面都有1）。 然后我们将决定N上的偏序为此，我们进行归纳。 假设我们已经得到了{1，.，n}，对n ∈ N. 为了将其扩展到集合{1，...，n + 1}，我们只需要指定n +1和i之间的顺序关系，对于每个元素i∈ {1，.，n}。我们将以随机的方式这样做，仅受一些自然的副条件的影响，我们留在我们给定的域类中，并且{1，.，n}成为{1，...，n + 1}。通过归纳，我们得到了N上的一个阶。 由于每个{1，. ，n}将是N上的阶的子域，我们可以将我们的过程视为阶的有限近似的构造对北冰洋西部N.我们的主要结果表明，它对一个域的完备化是一个泛齐次双有限域，概率为1。分别在所有ω-代数格类、所有ω-Scott域类中构造泛齐性域 对于所有的ω-双有限L-域，我们以完全相同的方式从{1，...，n}概率地在{1，...，n + 1}。 然而，在下一步中，我们构造一个完整的这个偏序集的格，斯科特域，分别。L-域，以确定性的方式。这个完备化是有限的，现在我们再次对它应用概率过程，将阶数再扩展一个元素。通过归纳，我们得到了N上的偏序，并证明了它的cpo-完备化分别以概率1是泛齐次代数格、Scott域和泛齐次代数格。L-结构域。事实上，我们的概率构造将取决于给定的参数序列。我们的结果表明，无论这些参数的选择，以概率1，我们得到相同的通用齐次域。我们将描述如何更精确地表达我们直观给出的结构，即。如何构造相应的概率空间。 我们对{1，…，n}到≤n+1阶，在{1，...，n +1}基本上描述了在给定≤n的情况下获得≤n+1的条件概率。因此，我们得到在一个自然的方式有限离散概率空间的投影系统，其极限是概率空间的构造偏序N。Scott [23]展示了如何构造嵌入或甚至同构于它们自己的函数空间的域;这样的域会产生弱可拓的（分别是）。扩展）模型的无类型λ演算，方法是至关重要的M. Droste，D.Kuske/Electronic Notes in Theoretical Computer Science 173（2007）103105用于构造域方程的解。作为我们的结果的直接后果，它遵循的四类域中的每一个，我们认为，所有这些域的集合嵌入自己的功能空间有措施1，而所有域的集合是同构的功能空间有措施0。在我们的第二个主要结果中，我们证明了四类ω-整环中的每一类都可以被赋予完备度量空间的结构。有一个拓扑概念，这样的空间的子集是“大”或包含“几乎所有”的空间。这是剩余的概念，即一个贫乏集合的补集。在描述了背景之后，我们证明了在四个相应的度量空间中，所有泛齐性域的子集都是剩余的，即，在这个拓扑学意义上是巨大的。最后，我们将提出一个简单的归纳数论构造的普遍齐次双有限域。因此，我们的构造是有效的，并且每个初始段{1，...，可以确定N中的n在n中的时间多项式。事实上，这是宇宙最简单的构造齐性ω-双有限域对泛结构的研究至少可以追溯到Cantor [5]，他证明了在可数线性序类中，链（Q，≤）是泛的。例如，（Q，≤）都是随机数。Frés′e[13]证明了所有可压缩无向图的类都包含一个泛齐次对象（唯一的直到它是一个形状）。Erdos和R′enny[11]给出了可数图的一个概率为1的泛齐次图，因此也称为随机图。这一惊人的结果激发了对此类图和有限模型理论中概率定律的进一步研究。文[8]给出了泛齐次可数偏序的一个概率构造更多的结果参见例如[2]。最近，在[10]中给出了泛齐次因果集的概率构造（这些是半序集，已被提出作为量子引力中离散时空的基本模型）。 目前的结果表明，在该地区，域理论的概率，因此直观上是2背景为了方便读者，我们首先总结一下我们的符号（大部分是标准的） 设（D，≤）是偏序集。 称一个非空子集A∈D是有向的，如果对任意a，b∈A，存在c∈A，且a≤c，b≤c。我们说（D，≤）是一个cpo，如果它有一个最小的元素，记为n，并且D的每个有向子集在D中有一个上确界。 一个元素x∈D是紧的，如果对于D的任何有向子集A，其中存在超A且x≤超A，则存在a∈A，其中x≤a。 D的所有紧元的集合记为D0. 则（D，≤）是代数的，如果对每个d∈D，集合{x∈D0：x≤d}是有向的且有上确界d.一个代数cpoD将被称为一个域。众所周知，106M. Droste，D.Kuske/Electronic Notes in Theoretical Computer Science 173（2007）10311任何整环（D，≤）都由它的紧元子集（D0，≤）的结构唯一确定（直到同构）.一个整环（D，≤）称为Scott整环（L-整环），如果D的每个上有界的非空子集A有D中的一个上确界（一个下确界）。因此，一个代数格可以被认为是一个包含最大元素的Scott域。我们用前缀ω−来表示一个整环的紧元素集合是可数的。设（D，≤）是一个偏序集。对于A<$D和x∈D，我们写A≤x来表示对于所有a∈A，a ≤ x。设mub（A）表示A在D中的极小上界集.称D的子集S在D中是有界完备的，记为SD，如果只要A∈S是有限子集，x∈D且A≤x，则存在s∈S使得A≤s≤x。则（D，≤）称为双有限，如果每个有限子集A<$D0包含在某个有限有界完备子集S<$D0中。设（P，≤），（Q，≤）是两个偏序集.一个函数f：P→Q是连续的，如果它保持P的有向子集的上确界。此外，f是一个mub-嵌入，如果对于P的任何有限子集A，我们有f（mub（A））= mub（f（A））。请注意，特别地，f是阶嵌入（即， a≤ bi <$f（a）≤ f（b），对任意a，b∈ P）;此外，若P ， Q 分 别 有 最 小 元 <$P ， <$Q ， 则 有 f （ <$P ） =<$Q （ letA=<$aandobservethatmub（<$） ={<$P}）. 通常，一个在上的非线性嵌入称为同构。现在，设f：P→Q，g：Q→P是连续的。则称（f，g）是从（P，≤）到（Q，≤）的嵌入投影对（EPP），若g<$f=idP且f<$g≤idQ.如果f是同构，则g=f−1，EPP也称为同构。我们将EPP（f，g）表示为ε。两种无害环境产品的组成（f、g）：（P≤）→（Q，≤），（h，k）：（Q，≤）→（R，≤）定义为（h<$f，g<$k），也是一个EPP。我们用ωBepp，ωBLepp，ωSepp，ωLatepp表示所有分别是ω-双有限域、ω-双有限L-域、ω-Scott域和ω-代数嵌入-投影对、多嵌入和有界完备子集密切相关，这是众所周知的（参见，例如，在一个实施例中，[9]）。命题2.1设（D1，≤），（D2，≤）是两个双有限域，f：D0→D2成为一个映射。则以下是等价的：(i) 存在一个EPP（f<$，g）f rom（D1，≤）into（D2，≤）满足f<$TD0=f.(ii) f是mub-嵌入，f（D0）≠ D0.1 2(iii) f是序嵌入，f（D0）D0.1 2设C是范畴ωBepp，ωBLepp，ωSepp或ωLatepp之一，且（U，≤）∈C.故（U，≤）称为• 在C中是泛的，如果对于每个domain（D，≤）∈C，存在一个EPP：（D，≤）→（U，≤）;• 齐次的，如果对任意有限整环（D，≤）∈C和EPP<$i：（D，≤）→（U，≤）（i= 1， 2），存在同构<$i：（U，≤）→（U，≤）使得<$i <$1=<$2。此外，我们说，（U0，≤）实现了所有的一点扩张的有限subdo，M. Droste，D.Kuske/Electronic Notes in Theoretical Computer Science 173（2007）103107nmains，如果对C中任意两个有限域（A，≤A）和（B，≤B），其中（A，≤A）（U0，≤），（A，≤A）（B，≤B）和B=A{y}，存在z∈U0使得idA<${（y，z）}：（B，≤B）→（U0，≤）是一个mub-嵌入;等价地，A<${z}（U0，≤）和idA<${（y，z）}：（B，≤B）→（A<${z}，≤）是一个同构.正如模型理论中所熟知的那样（cf. [14，4，18]），普适性和齐性的性质与单点扩张的实现密切相关;在我们的设置中，单点扩张的这种实现已经在[15，7，9]中使用，我们有以下有用和必要的特征。命题2.2（[9，Prop.2.2]）设（U，≤）∈ C，其中C是范畴之一ω B epp、ω BL epp、ω S epp或ω Lat epp。则以下是等价的：(i) （U，≤）在C中是泛齐次的.(ii) （U 0，≤）实现了有限子域的所有单点扩张。文[7]的主要结果如下定理2.3（[7]）每个范畴ω B epp，ω BL epp，ω S epp或ω Lat epp都包含一个泛齐次域。这个普遍的齐次域直到同构为止都是唯一的.为了证明这个结果，[7]证明了C中的有限域类具有合并性质。然后，从范畴论的一般化Fra se的theore m从modelthe or y得出结果，cf。 [7，Thm. 1.1]。3泛双有限域为了介绍我们的构造，我们简要回顾了泛齐次图的随机构造下面，结构（V，R）是一个图，如果V是一个非空集，并且R<$V×V是非自同构和对称的，即， 图是无环无定向的图的嵌入是一对一函数，既保持又尊重边缘关系。一个可数图U是泛图，如果任何可数图都可以嵌入到它里面; U是齐图，如果每个同构都不包含U的子图。Fra？s？e[13]证明了存在可数泛齐次图U，并且U在同构下是唯一的.现在，让我们描述这个图U的概率构造。作为基础集合，我们取自然数N选择所有2-子集的枚举Si={ai，bi}（i∈N）的N. 然后掷硬币决定ai和bi是否成为是否由边连接。由于这些选择是完全独立的，它们可以按照枚举、任何其他顺序甚至同时进行。然后，在任何情况下，概率为1，我们得到泛齐次图。为了更精确地表达这种启发式构造，我们描述了底层的probb ii l ityspace（cf.Er do ssandSpencer[12]，Cam eron[4]）。我们假设我们的图有N，自然数，作为基础集。让Ω ={R<$N×N|（N，R）是一个图}且Ω n={R <$A2| (An, R) is a graph}108M. Droste，D.Kuske/Electronic Notes in Theoretical Computer Science 173（2007）103nn其中An={1，2，.，n}（n∈N）.对于R∈ Ω n，设（R，n）<$={S∈Ω |SA2 = R}。设A表示Ω上由基集（R，n）n生成的σ-代数，其中R∈Ωn.−（n）则Ω上存在唯一的概率测度μ满足μ（（R，n））= 22对于任何R∈Ωn，如上所述。 上面的主要陈述说，集合{R∈ Ω|（N，R）是泛齐次图}在（Ω，A，μ）中测度为1.接下来，我们希望发展我们的双有限域的概率构造我们将再次首先进行实证研究，然后指出潜在概率空间的精确定义。注意任何定义域（D≤）在同构下由其紧元素子集（D0，≤）的结构唯一确定事实上，如果（D，≤）和（E，≤）是整环，并且f：（D0，≤）→（E0，≤）是同构，则f唯一地扩张到一个sonisorpismf<$：（D，≤）→（E，≤），其中f<$TD0=f。本文利用集合（D0，≤）的相应性质来刻划所有Domain（D，≤）类的性质. 我们将假设我们的无限域（D，≤）满足D0=N，并且它们以唯一和统一的方式定义（例如，通过CPO完成）其偏序集（N，≤）的紧元素。构造3.1我们固定某个离散概率分布ν：N→[0，1]，对于每个i∈N，有某个概率pi∈[0，1]。 我们描述了如何在An={1，2，.，n}概率地映射到有限偏序在An+1 ={1，2，...，n + 1}使得（An，≤n）（An+1，≤n+1）.为此，我们只需要确定n+1和i之间的顺序关系，对于每个i∈An。为了实现（An，≤n）（An+1，≤n+1），必须在（An，≤n）中有一个最大元素x，且x 0，对所有i ∈ N. 此外，对于每个i ∈ N，设p ∈（0，1）是某个概率Σ使得i∈Npi<∞。然后，在概率为1的情况下，构造3.2产生一个N上的偏序≤，其cpo-完备化是泛齐次双有限域证据通过Prop. 2.2，它表明，在概率为1的情况下，所得到的偏序（N，≤）实现了有限子域的所有单点扩张。注意，直到同构，只有可数多个这样的一点扩张（A≤A）（B，≤B），且A<$N。 因为无数事件的交集 概率为1的概率再次为1，因此可以考虑一个任意固定的一点扩张（A，≤A）（B，≤B），其中A{y}=B且（A，≤A）（Am，≤m），其中m∈N.我们证明了以概率1，存在n∈N使得fn+1=idA<${（y，n+ 1）}）：（B，≤B）→（An+1，≤n+1）是一个mub-嵌入.为此目的，考虑任何整数n∈{m，m+ 1，. ），则（n）为零。我们希望计算出构造概率的下限，≤n+1在An+1上使得fn+1是一个多嵌入。设x∈A是（A，≤）的最大元素，使得xBy.<在构造式3.1中，我们从An中选择这个元素x的概率至少是ν（x）>0。现在考虑关系R ={（n +1，a）|a∈A，y 0Σ由无穷乘积分析的一个标准结果可知，由于i∈Npi<∞。因此，在≤n+1的构造中，选择上述关系R的概率至少为{pa|a ∈ A，y 0，使得至少在概率r下，x和R的所有这些选择都是如上所述完成的，并且r仅取决于（A，≤A）和（B，≤B）（但不取决于n）。设R是这样构造的，设≤n+1是≤n<${（x，n+1）}<$R的自反传递闭包。证明了映射fn+1= idA<${（y，n+1）}：（B，≤B）→（A<${n+1}，≤n+1）是序同构.设a∈A.通过x的选择，（A，≤A）<$（An，≤n）的事实，以及≤n+1的定义，我们得到一个Byia≤Bx ia≤Ax ia≤nx iann+1n + 1。 如果yBa，我们通过构造有（n+ 1，a）∈R，因此n+ 1n+1a。相反地，设n+ 1n+1a.则存在aJ∈A，其中（n+ 1，aJ）∈R且aJ≤na。 因此，根据R的定义，我们有yBaJ，其中隐含yBa。因此fn+1是一个序同构.为了证明fn+1 是到（ An+1 ，≤n+1 ）中的一个多嵌入，还需要看到A{n+1}（An+1，≤n+1）。设S<$A<${n+1}且c∈An+1\S，其中S≤n+1c. 若n+1∈/S ，则nA（Am，≤m）（An，≤n）（An+1，≤n+1）im证明b∈A存在，其中S≤n+1b≤n+1c.现在假设n+1∈S。由于n +10，n∈Nνn（1）<∞.这与任何普遍的同质双有限性的情况形成鲜明domain（U，≤）. 在那里，对于任何a∈U0<，有一个z∈U0满足拉克<兹河 对于，考虑单点扩张（A，≤A）（B，≤B），其中A={A，a}，B ={A，y，a}和B<，y 0，对所有i ∈ N.此外，对于每个i∈N，令p ∈（0，1）是某个Σ概率使得i∈Npi<∞。然后，在概率为1的情况下，构造式4.4在N上产生一个偏序≤，CPO完备化是一个普适的、齐次的(a) ω-代数格，(b) ω-Scott域，(c) ω-双有限L-域。证据这个证明对所有这三个陈述都是类似的，并且实际上遵循定理3.3的证明路线。我们只做必要的改动。设（N，≤）为构造式4.4的任何结果。 那么有1 = k1k2k3<<<. 使得如果An={1，2，.，kn}则构造4.3的一个应用从（An，≤）产生（An+1，≤），并且AnAn+1（N，≤）。设（A，≤A）（B，≤B）是ω Lat epp（分别为ω S epp，ω BL epp）中的一点扩张，B=A{y}和（A，≤A）（Am，≤m），其中m∈N.正如定理3.3的证明，它表明这个单点扩张在（N，≤）中以概率1实现。在定理3.3的证明中，设n∈{m，m + 1，. }且考虑（An，≤n）。然后有一个固定的r >0，使得在概率至少为r的情况下，构造4.3的第一步（即，康-结构3.1）得到一个偏序集（An<${kn+1}，≤J），它通过mub-嵌入fn+1= idA<${（y，kn+ 1）}嵌入（B，≤ B）.则（An+1，≤n+1）是（An <${kn +1}，≤J）和（An，≤n）（An+1，≤n+1）的MacNeille完备化（分别是Dedekind完备化和L完备化）.根据引理4.2，映射fn+1也是（B，≤B）到（An+1，≤n）的多嵌入. 因此，同样概率至少为r，M. Droste，D.Kuske/Electronic Notes in Theoretical Computer Science 173（2007）103115构造式4.3给出了一个偏序集（An+1，≤n+1），它实现了单点扩张（A，≤A）（B，≤B）。其余的论证可以从定理3.3的证明中得到。Q为了指出上述定理背后的精确概率空间，我们可以类似于定理3.3的情况进行。我们画出了泛齐性ω-Scott域的情形。一个Scott偏序是N的某个初始段A上的偏序≤，使得存在1 = k1

下载后可阅读完整内容，剩余1页未读，立即下载