没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记122(2005)247-296www.elsevier.com/locate/entcs在每一个抽象的石头对偶模型中,都有一个算术宇宙。保罗·泰勒1曼彻斯特大学计算机科学系摘要第一篇发表在Abstract Stone Duality上的论文表明,公开的离散对象(那些在内部允许有和=的对象)形成了一个pretopos,即一个具有有限极限、稳定的不相交的余积和稳定的等价关系的有效子的范畴。使用一个N-指标最小不动点公理,我们证明了这个全子范畴是一个算术论域,在任何显式上都有一个自由半格(“Kuratowski-有限子集的集合”)和一个自由幺半群(“列表的集合“)。离散对象 每个有限子集都由它的模态算子对(Q,n)表示,尽管与这些模态算子的紧密对应依赖于更强的斯科特连续性公理。拓扑学上,子集是紧的和开的,并且还涉及真开映射。在ASD的应用中,这可以消除列表,以支持延续传递解释。关键词:抽象石头对偶,pretopos,算术宇宙,自由半格,Kuratowski有限,列表,模态逻辑,powerdomains,真开映射。目录6.容许蕴涵模态2711.介绍2477.K作为函子2732.证明与自然数2528.列表,正面和反面2783.作为模态的2599.列表递归2824.固定点属性26310.自由半格2875.施工阶段26711.公开紧致子空间2901介绍在抽象Stone对偶中,空间X上的拓扑被视为具有λ-演算的指数型拓扑X,这已经给出了局部紧空间范畴的解释,无论是在一个1请仅通过电子邮件联系1571-0661 © 2005 Paul Taylor.由Elsevier B. V.在CC BY-NC-ND许可下开放获取。doi:10.1016/j.entcs.2004.06.059248P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247初等topos [H],以及映射N→ N恰好是可证全一般递归函数[G]的逻辑。注1.1ASD的一个重要特征是它的空间没有ASD是“空间”范畴S的直接公理化然而,当我们用离散这个词来表示存在一个内部的相等概念时,(=X):X×X→X(即对角线X<$X ×X是开的),我们实际上说的是公开离散,这意味着也存在一个“存在量化器”,X = X:X×注1.2在以这种迂回的方式假设了“集合”范畴的概念之后事实上,如果我们假设存在“底层集合”,即包含E <$→ S [ H ]的右伴随,则EGiraud的定理,以Grothendieck topos所承认的极限和(无限的)上极限为特征,提出了对集合范畴的“无限”方面的第一个范畴近似:一个预topos是一个具有有限极限、稳定不相交的上积和等长关系的稳定不相交性的范畴。 乔依和雷·乔依通过引入算术运算,以一种美学的风格来揭示哥德尔的不完备性理论:它们有足够的结构来形成同类的自由的内在事物。具体地说,算术论域是一个具有自由内部幺半群的预拓扑(列表X),自由内部算术论域可以通过生成元和关系得到实际上,这些结构只是为计算机科学家开设的第一年“离散数学”课程中所教授的内容我们将在以后的工作中(关于从E构造S的工作)论证幂集的其他替代物,即X的递归可判定子集和可判定子集的集合,是非离散空间λX和2X。如果X有一个底层集合,这将是X的通常幂集。注释1.3不幸的是,尽管有30年的历史,关于人工宇宙的知识仍然是通过口头传播的。关于它们的唯一参考(甚至可以获得)的论文是玛丽亚·艾米利亚·马耶蒂(Maria Emilia Maietti)的论文,她为m提供了一个Martin-Léof-styletypet theory[6]。她声称她P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247249算术宇宙的概念[7]比这里使用的更强。事实上,那些研究过算术宇宙的人知道在细节上存在一些分歧,但他们没有写任何论文,这对问题几乎没有然而,解决对数学中正确定义的怀疑的最好方法是证明它们与来自其他直觉的其他结构的等价性。在本文中,从ASD的模型构造算术宇宙和提出的逆将,我相信,不仅服务于这一目的,而且还提供了比Maietti的更有表现力的演算注1.4在ASD中,已知公开离散对象的全子范畴是一个pretopos [C],因此本文研究自由幺半群和自由半格(KX)。然而,请注意,作为一个存在性问题,这在我们通常关注的两种情况下是多余的:在经典模型(我们直觉的来源)中,E是一个topos,而在自由模型(我们计算的目标)中,E的每个对象都是N通过一个开放的部分等价关系的子商;在这两种情况下,列表都可以用众所周知的方式编码从拓扑学的观点来看,这篇论文也是不必要的,因为自由幺半群的存在可以合理地被认为是另一个公理,所以我们的结论仅仅是这个公理是多余的。然而,ASD通过具有独立的(技术上的)基本公理化,不依赖于预先存在的集合或空间类别,将自己与其他拓扑方法区分开来。我们的意图是将其用作计算的途径,因此即使我们已经抽象地知道它的存在,我们对KX的表示注1.5我们最常使用的两种半格结构是:的幂,并且证明它们是共同忠实的,实际上,KX是一个子空间,其中每个有限子集l由两个模态算子表示,[l] λφ。x∈ l. φ x和φlλφ。x∈l. φx。众所周知,模态逻辑与三个幂域有关,在其中一个幂域中,包含顺序与内在顺序一致,在另一个幂域中,它们是逆变的,而在第三个幂域中,包含既涉及内在顺序,也涉及其相反的顺序[4,9,10]。然而,我们只考虑(公开)离散空间的凸幂域。这种缺乏雄心的原因是,这篇论文构成了理论的“自举”的一部分250P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247ASD的:更多的可以做的使用整个事情,特别是[G];类似的结构,在一个Hausdor空间,如R被认为是在[I]。此外,我们用模态算子表示幂域的元素,而引用的作品则使用它们来生成其拓扑,依赖于自由半格的先验存在。注1.6我们将有限子集转化为高阶λ-项可能具有计算价值,就像其他连续传递风格的例子一样。局部紧空间的理论是在[G]中利用开紧子空间的基发展起来的,该论文最后给出了如何利用关系在计算上操纵连续函数(例如R→ R)的草图。不幸的是,至少当理论在那里表达时,这样的基必须用(无穷)格来索引,并且大量使用由公开离散对象生成的自由分配格。这可以通过自由半格来构造,其元素可以反过来表示为列表,但可能需要相当大的计算成本。另一方面,函数式程序员非常清楚,在很多情况下,(嵌套)列表提供了优秀的数据结构。为此,通过逻辑,特别是通过我们在第8因此,本文提供的是列表(传统上实现的)和数学同构结构之间的选择,该结构使用模态逻辑,λ-演算和连续传递来编码有限子集。需要进行实证研究,这种选择在特定的应用中。注1.7回到类型论,与Maietti关于算术论域的定义的分歧似乎涉及参数列表类型,这在本文中没有涉及。当然,这些都是需要的,但有一些方法可以获得它们,而不必首先开发一般的依赖空间。一个由另一个这样的对象所索引的公开离散对象的族,如在拓扑中,由任何映射δ:X→N给出,其中X[n]<$δ−1(n)。 (We称δ为然后列表X[n]由显示N+P→N给出,其中P)N列表XListδ) 列表N)的情况){|−}|vKNvP. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247251提供了非空列表和额外的项N的空列表。注1.8我们的结构和领域理论之间的另一个联系是它使用了领域理论的方法。具体地说,ASD演算提供了一个给定环境类型的子类型的引入,它由一个自同态E定义。在本文中,我们得到自同态作为一个更高类型的算子$的最小不动点要做到这一点,必须在[C]中添加一个不动点公理,以表明E是一个pretopos。为了构造KX和列表X,我们只需假设公理1.9Γ,n:N<$φn:<$UΓ,n:N<$φn≤φ(n+1):<$UΓ,F:<$U→ <$V <$F(<$n.φn)=φn。F(φn):φ V然而,为了得到我们期望[G]的所有拓扑结果,特别是为了证明满足模态律的每对算子(Q,Q)实际上对应于一个可列子集(第11节),需要更强的尽管它会使整个论文的概念简化,但在证明我们的主要结果之前,我们甚至无法陈述它,因为它涉及列表X或KX。公理1.10斯科特连续性公理是r,l:KX φ1:φUr,l1,l2:KXφl1φl2≤φl1+l2r,l:KX αl:rαnil=Tr,l1,l2:KXαl1+l2=αl1<$αl2F:F →α l(φ l)= φl。α l<$Fφ l.满足五个前提的族(αl,φl)称为有向图。在自由模型中,每一个公开的离散对象如KX是N的子商;在这种情况下,一般的斯科特连续性可以从上面的不动点公理导出。在其他模型中,例如经典模型,每个公开的离散对象X都需要一个斯科特连续性公理。注1.11这又把我们带回到ASD的一般模型的研究上(对于ASD,关于KX和ListX的存在性问题并不是微不足道的)。除了[2]不动点公理说F保持可数的有向连接,但在经典模型中也需要不可数的有向连接。例如,回想一下,在泛代数中,无限元理论κ的自由函子保持任意大小λ的图的κ-过滤余极限。我们公理的两个版本非常粗略地对应于这两个基数参数在经典情况下的作用。252P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247不在自由公理和经典公理的基础上,我们还可以用更多的类型、项或方程的形成方法来加强公理,从而得到其他的公理模型。例如, 一个终止的神谕会说对于非终止程序,代码的(已经可定义的)空间T<$是overt,表示一个新的wterm:T→。我们在第一段中所作的断言的真正意义取决于我们能证明哪些项是相等范畴的态射是一类根据一定逻辑可证明等价的项,而部分态射f:N~ N通过定义是全的,如果有一个证明,证明f:N~ N满足一定的方程[D]。由于素数和核[A,B]的定义依赖于方程,如果逻辑证明了更多的方程,那么它也定义了更多的项和(子)类型。什么是合法的证明(特别是两项相等的证明),这是我们在本文中必须比迄今为止在ASD文献中所做的更仔细地考虑的问题,因为这是我们对N上递归和归纳的第一次认真使用。这是下一节的主题。第3节给出了在第4- 6节中发展的K-X及其模态逻辑的构造的直观和符号第7节考虑K作为函子的性质。然而,KX作为自由半格的泛性质仅在第10节中得到证明,它是从我们在第8- 9节中构造的列表X的泛性质导出的第11节重新考虑了KX是有限幂集的意义2ASD中的证明和自然数在我们开始构造自由幺半群和半格之前,我们必须比以前的论文更仔细地考虑ASD的λ-演算的证明形式。然而,我们的目的是域理论的构造,而不是ASD的证明理论分析,因此我们不会给出完整的规则集。特别参见[B,§ 8]以获得{X}的λ演算的总结处理一元属性的。|要考虑的主要问题是N上的归纳法,重点是自然数对象的定义并不像通常给出的那样充分。众所周知,当我们工作在一个非笛卡尔闭的范畴中时,一个参数对象Γ必须显式地添加到定义中。类似地,当范畴不具有所有的均衡器时,必须明确地考虑等式假设。公理2.1ASD的λ演算由类型、项和方程组成。P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247253法院的判决称,• 类型,如0、1、N、X×Y、X × X和{X|E}形成良好,• 术语格式良好且具有特定类型,或• 等式在项之间成立。关于项和方程的这种判断是在某些上下文中作出的,即 假设它们的自由变量有特定的类型。然而,即使子类型的定义{X|E}涉及项E,我们坚持(作为理论目前制定),它是形成在空(全局)上下文中,即没有自由变量。甚至依赖类型理论的纯语法也是非常复杂的,并且在语义情形中变得更加复杂,在语义情形中我们必须选择一类显示映射[8,第八章]。当然,我们还必须执行语义计算,这是本文的主要任务显对象族和紧对象族分别被编码为开映射和真映射[C,§7]。因此,判决有四种形式► X型,Γ型 a:X,Γ, a=b:X和r► α≤β:X。最后一个问题来自于形式为<$U的类型上的格结构,其中(α≤β)表示α=(α<$β)或β=(α<$β)。这种秩序可以扩展到其他对象,但我们不需要它。在本文中,我们发现方程(和不等式)也需要作为假设。换句话说,上下文T可以包括项之间的等式和不等式,以及类型化变量的列表。任何可证明的判断都证明了从其假设到其结论的某个推理片段的有效性,因此,当我们想通过连接这些片段(即通过切割规则)来形成更大的论证时,所有被允许作为结论的断言形式也应该被允许作为假设。特别是,这是需要在N上的归纳,它内在化的连接过程。 (在Martin-Lofty理论中加入这样的命题会导致不可判定性[2,§3.2],但ASD演算无论如何都是图灵完备的。)公理2.2在相干逻辑中,类型为“n”的项可以被看作谓词:(a) T和t;(b) αβ和αβ,其中α,β:α;(c) φa,其中φ:φX和a:X;(d) (a=Xb),其中a,b:X,并且X是离散的(例如N但不是R或2N);(e) (a/=Xb),其中X是Hausdor型(例如N、R或2N);254P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247(f) Xφφx,其中φ:<$X,X是显型(N,R,2N);(g) Xφφ x,其中φ:<$X,X是紧类型(例如[0,1]<$R或2N但不是N)。我们将发现一个类型X具有所有四个性质(类型φ:<$X的项由λ-演算构成。像往常一样,引入λx、λx或λx将变量从上下文中释放出来,因此上下文中不包含x是自由的等式假设注2.3注意这个逻辑不包括蕴涵。事实上,每一项都是单调的,被认为是它的自由变量的函数。但是,允许严格限制的蕴涵形式,因为判断的假设和结论可以是α≤β:U的形式,所以判断可以是...,α≤β:α U,. ► γ≤δ:δV,这意味着(u。α u <$βu)(v. γ v <$δv)。当我们需要作出一个断言α是一个类型为T的项时,我们通常遵循数学习惯,只简单地说当然,作为假设的任何等式或不等式都可以直接用作“恒等式”或“公理”判断的结论,或者可以通过“切割”规则来解除。它们也被我们现在给出的逻辑规则所释放。公理2.4尽管我们不能定义一个αβ型项,但它的通常规则确实引入了一个不等式,既有直观的方式,也有明显经典的方式:Γ,α = T: β=T:Γ ► α≤β:Γ,α=α:γβ=α:γΓΓα≥β:γ直觉法则等价于欧几里得原理,F:,α:αFα =αFT,另一个规则是它的对偶格。对于α=T和β= π,记为α和<$βP. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247255..\..v (它们和单调性一起等价于Phoa原理,F:,α:Fα = FαFT.请注意,这些东西在直觉主义场所理论中是有效的[C,第5节]。欧几里德原理等价于(在单子假设的上下文中)说T:T分类了S中的某类单子,我们称之为开的,而它的对偶说T: T分类了闭包含。第一个原则的一个例子r,a=b:X c=d:YQΓ ► (a=Xb)≤(c=Yd):转向递归和归纳,我们必须重新考虑N在没有均衡器的范畴中的定义,例如局部紧空间。 另见[1]和[5,§II.4]。公理2.5递归方案引入任何类型X的项,依赖于n:N:Γ► z:XΓ,n:N,x:XΓ s(n,x):XΓ,n:N<$rec(n,z,s):X其意义由β-规则r = 0,z, s=z:Xr,n:Nrec(n + 1,z,s)= s.n,rec(n,z,s)这被称为在类型X上的递归,关键在于,随着递归方案被断言的类型的类的增长,逻辑的能力也会大大增加。相应的图形属性为Γ0)Γ×N(id×εcΓ×N...\中找到。rec ..... (id,rec).\\\s的X.. vΓ ×N ×X。如果这个类别是封闭的,那么这个图可以重写为N×XΓ代替X,对象Γ本身从顶行中移除\\\z256P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247.Σ这意味着参数可以通过λ-抽象嵌入到数据和新项中。如果像ASD中那样,范畴(有有限个乘积,但)不是完全封闭的,那么需要参数对象Γ公理2.6关于Γ,n:N<$a n,b n:X:Γ<$的方程归纳法 a0=b0:XΓ,n:N,an =bn:X<$an+1=bn+1:Xr,n:N an=bn:X请注意,这并没有说明an和bn本身是从哪里来的。如果它们是由X上相同的基和步长数据定义的,则上述递归方案中的η-规则或唯一性假设会使它们相等。然而,该方案比这更一般:术语an不需要直接从递归中产生,但可能是f rec(n,z,s)的形式,其中f是某个函数,而b n是某个无关的f J。rec(n,zJ,sJ)注2.7正像在一个Carnival闭范畴中带参数的推广是多余的一样,当范畴有均衡器时,方程归纳法也可以从N的一般普适性质导出:E≡ {(γ,n)|a n(γ)= b n(γ):X}))an)Γ× N)X.Bn基本情况说(id,0):Γ→ Γ× N因子通过E,而归纳步骤说id×succ限制于映射E→E。公理2.5提供了recE:Γ ×N →E。这是逆的包容,一个方程是由唯一性给出的,recN:Γ× N→ Γ× N另一个是由于E>Γ× N是单声道的。Q方程归纳法(以及它对不等式α n≤β n的等价形式)将用于命题4.4、4.12、5.9和7.10,我们将在命题9.7和10.11中推导出它对列表和有限子集的类似形式。它应该被表述为[A,备注2.5],因为它实际上在[A,引理8.9和9.6]和[B,引理8.14]中使用由于对[A,9.6]的证明是粗略的,并包含其他错误,我们在这里通过一个等式归纳的例子给出正确的版本P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247257它将N类型的递归转换为N类型的递归,作为引入描述过程的一部分(m。)到一个术语的外部。引理2.8n,z,λnJu. s(nJ,u)= m。 ρ(n,m),其中λm. m = z),σ(n,φ)λm。 J.φ mJ<$m = s(n,mJ)<$ρ(n,m)<$rec(n,n,σ)m.基本情况(在上下文中)是λm。ρ(0,m)<$λm。rec(0,λ,σ)m = λm。 古勒姆β规则λm。(m=z)定义= λm。(m=r 0)β规则归纳步骤,假设λmJ。ρ(n,mJ)= λmJ. (m=rn, j),λm。 ρ(n +1,m)<$λm。 rec(n +1,n,σ)m= λm。σ。n,rec(n,n,σ)β-规则=λm。 J. rec(n,n,σ)mj. m=s(n,mJ)<$defσλm。J.ρ(n,mJ)m=s(n,mJ)=λm。J. (mJ= rn)n. m=s(n,mJ)假设= λm。. m=s(n,rn)n个相等规则= λm。. m=r(n+1)β-规则因此,Γ,n:N <$λm。ρ(n,m)= λm。(m=rn):由公理2.6证明。Q备注2.9回想一下[B,第8节],引入焦点和承认项的规则具有等式前提。这就意味着,有这样的术语,只有在包含特定等式假设的特定上下文中才被定义。然而,请回顾前引书。对于任何项Γα:λ,存在另一个不涉及focus或admit的项Γα<$:λ ,其性质为Γα=α<$:λ。 (事实上,通过提高行政管理水平,我们获得了α′i。)Now,as它不包含任何内容或管理,在它的框架中没有使用任何量化的内容,并且在使用它们的内容中定义了内容。Q推论2.10在上下文范畴(可能涉及方程)和替换范畴中,“”是单射的。Q258P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247注2.11在一个不一定具有所有均衡器的范畴S中,如何解释这样的显而易见的方式是,对于S中的f1,f2:X→A和g1,g2:X→B,x:X,f1x = f2:A g1x=g2x:B意味着对S中的任意a:Γ →X, 若(f1·h)=(f2·h) ,则(g1·h)=(g2·h).限制λ-演算被形式上扩展为(抽象的)清醒性[A]和单子性[B]。对方程假设的这种解释可以用来做另一个类似的形式扩展。然而,这样一种扩展的结果将是对空间场所(相当于清醒空间--在传统意义上而不是[A]的意义上)的解释,而不是一般的解释。 这是因为测试对象Γ的一般性是虚假的:局部紧区域有足够的点(至少在经典上),因此这个公式只使用Γ的全局点来测试方程。场所和清醒空间的创造者(以及事实上的产品)并不相同[3,§II2.13]。注2.12其对象是具有方程的上下文的范畴具有有限乘积,但它不再具有最初激励ASD的指数(−)-这些仅在上下文的子范畴上定义,而没有方程这个问题是不可避免的,因为正如我们刚才指出的那样,这种假设已经被使用了,尽管是无意的。这意味着该理论真正捕捉的不是局部紧空间范畴本身,而是嵌入在locale或空间locale范畴中的范畴。然而,前进的方向不是重写以这种混合方式所做的工作,而是研究(实质上)更大的结构,包括均衡器和指数。对这种结构的初步研究,不仅涉及到整个locale范畴,而且还涉及到carbohydrate闭扩张,可以在[H]中找到。然而,这种结构不仅包含更一般的空间,而且还捕获了更强的方程(之间的含义)逻辑。这意味着,为了确定与算术宇宙的精确等价性(注1.3),所提出的逆构造可能属于类似于空间场所的范畴。但就本文的目的而言,等式假设只是管理证明的一种手段。P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)2472593作为模态算子在整个过程中,让X是一个公开的离散空间。它的典型值称为x、y等,其谓词为φ、φ等。我们将构造一个对象KX,然后证明它是X上的自由半格。虽然KX旨在成为X的Kuratowski有限子集的空间,但我们将使用列表表示法来表示它,写了l:KX为一个y值。 Sonil,{|x}|:KX表示emp ty,singleton subsets,+是union,x::l={|X|}+l.请注意,我们还使用{x}为λy。(x=Xy):X.我们实际上需要在KX和ListX之间来回切换,在基于+运算的“数学”幺半群概念和基于::的“计算机科学”概念之间来回切换注3.1KX将被构造为<$$>X× <$$>X的一个<$-分裂子空间.典型的值将被称为L=(N,P),其中字母代表必要性和可能性,因为中心思想是通过其模态算子[l]来表示子集l:KX,其中模态算子[l]也变化在列入名单方面,有消极的一面,也有积极的一面。 随着我们也将经常使用π<$λx。P{x}:X。注3.2如果我们已经有了KX和列表X,我们将定义[l] λφ。x∈ l. φ x和φlλφ。x∈l. φx,以及隶属谓词(x∈l)l.然后[nil] = λφ。不λφ = λφ。 ⊥π零 = λy。 ⊥[x::l] =φx<$[l]φx::lπx:: l = λy。(x=y)πly[l1+l2]= [l1][l2]l1+l2πl1+l2 =πl1<$πl2,我的天啊!|X|}]={|x}|λ=ηx=λφ。 φx和π{|x}|={x}。Also(l1 x ∈l1. y∈l2。(x = Xy)n [l1](λx. <$l2<${x})<$[l1]π2和(l1=l2)<$(l1<$l2)<$(l2<$l1),它们是类型1的值。最后,“Curried”操作Q φ <$λl. [l] φ和<$φ<$λl。在powerdomains上生成拓扑(注释1.5),但在这里不是很有用记法3.3由于我们想把KX构造为n的子空间,我们需要把这个记法推广到Ln(N,P):nnXn nx nn。对于模态符号本身,我们简单地使用[]和[]来表示乘积投影,因此QφL<$[L]φ<$260P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247Nφ和φL ≡ 公司简介 Pφ。 然后我们定义nil(T,):x::(N,P)<$(x::N,x::P)<$(λφ. Nφ<$φx,λφ。Pφ<$φx)(N1,P1)+(N2,P2)<$(N1<$N2,P1<$P2)(λφ. N1φ<$N2φ,λφ. P1φ(P2φ)x∈L<$$>L<${x}<$P{x}<$πxL1<$L2<$[L1](λx. <$L2<${x})<$N1(λx. P2{x})<$N1π2L1<$L2<$(L1<$L2)<$(L2<$L1)L=[L] 吴恩达L/= LTP T。显然+是一个结合的、交换的、幂等的二元运算,nil是它的一个单位,nil是L;我们将很快推导出+和L的其他代数性质。然而,请注意,对于P,它们表现为和≤,但对于N,它们就像这意味着它们并不是上的内在结构(就像≤、和在中一样),而是通过指定某些映射而强加给它的。在::符号中的/-歧义总是由上下文解决的,但是我们不应该冒险通过进一步重载重要的相等符号来混淆。显然,不是每一对(N,P)都将从有限子集中产生([l],定义3.4我们说对Γ(N,P):是模态的,如果N和P满足NT=TP=N(φ)=NφN P(φ)=PφP N(φ)≤NφPP(φ)≥PφNN(λx. P {x})= TPφ = φx。φ x <$P {x}。最后一个定律,它从π<$λx恢复P。P{x},意味着P保持,回想起有限性和斯科特连续性之间的经典联系,公理1.10提供了转换也许并不奇怪。 如果P是Scott连续的,并且保持λ和λ,那么它也保持λ,并且满足最后一个定律。从N的Scott连续性出发,定理11.7表明模态律恰好是Kuratowski有限子集。考虑到要检查的东西的数量,我们将省略对(N,P)是模态的大部分证明,推荐它们作为练习。注意,第六和第五定律通常需要欧几里得原理及其P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247261双分别。当周围空间是离 散 的 (例如,R ),第七定律被P(λx. N{x}),其中{x}<$(λy. xy)[I]。引理3.5模态算子满足弗罗贝纽斯定律及其对偶:φ:φ X,σ:φ X P(σφ)=σ Pφ和N(σφ)=σNφ。由Phoa原理(公理2.4)证明,因为P=且NT=T。Q引理3.6如果(N,P)是模态的,则P{x}<$Nφ≤φx。证明P{x}<$Nφ≤P({x}<$φ)好吧λy。(x=y)φy。 P {y}<$(x = y)<$φy=P{x}<$φx≤φxQ利用这些定律,我们已经可以恢复KX的代数结构。命题3.7可定义的有限子集产生模态对,因为(a) nil(T,)是模态的;(b) x:X{|x}|(λφ. φx,λφ。 φx)ismodal;(c) 如果Γ ► (N1,P1),(N2,P2)是模态的,(N1,P1)+(N2,P2)也是模态的.Q对交运算的类似研究提出了拓扑问题。命题3.8有一个最大模态(N,P)i <$X是紧的,在这种情况下N=<$X,P=<$X和π=T。证明假设所有的单例都有一个界λx。. {|X|} n(N,P)n = λx. [英|X|}](λy. P{y})= λx。P{x}= π。因此,如果(N,P)是最大的模态对,那么π=T。在这种情况下,P = λφ。你好πx<$φx = λφ。你好φx = φX。此外,x:X,φ:<$X <$ Nφ =NφP{x} =φx,太棒了!Xσ<$λx.σ≤φ i <$σ≤N(λx.σ)≤Nφ≤φx,这意味着,XEN,即N=<$X且X是紧的。262P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)24712现在N(λx. n(X{x})= N(λx. 很好x = y)= NT = T所以如果X是紧的则(N,P)<$(<$X,<$X). 这一对是模态的,因为,特别是你好 (φx <$$> x)≥ <$x。φ x φ(φy. x)≥(x. φ x)φ(φy. (y)你好 (φx <$$> x)≤ < $x。φ x φ(φy. x)≤(x. φ x)φ(φy. (y)Frobenius定律及其对偶Q命题3.9如果(=X)是可判定的(在这种情况下,我们说X是Haus-dor的,也是离散的),并且(N1,P1)和(N2,P2)是模态的,那么(N,P),其中Nφ= N。λx。φx<$N(λy. x/= y)Pφ = P1。λx。φx<$P2(λy. x = y)= 10x。P1{x}<$P2{x}<$φx,这是关于《圣经》的相遇。可决定性是必要的,因为,如果,|X|}和{|y}|当N=(x/=y)时,(x=Xy)是可判定的。可判定列表的交集也可以通过一个“过滤”程序来定义-Q模态律也足以保证,Kx的内部等式是由ε n提供的。命题3.10设Γ<$L1,L2:λ是模态的.则它们是等价的:(L1<$L2)= T<$L1<$$> ≤ <$L2<$<$π1≤ π2[L2]≤[L1]。由第八模态定律证明,P1≤P2i <$π1≤π2.记得(L1L2) [L1](λx. L2N1(λx. P2{x})<$N1π2。由第七模态定律,这由π1≤π2暗示,因为T=N1π1≤N1π2(L1<$L2),或由N2≤N1,因为T=N2π2≤N1π2<$(L1<$L2)。相反,从L1<$L2,我们依次推出:引理3.6Γ,N1π2 =T<$π1≤π2类似地Γ,N1π2=T<$P1≤P2第 八 模态 定 律Γ,N1π2=T,φ:<$X,N2φ=T <$π1≤π2≤φ单调性Γ,N1π2= T,φ:<$X,N2φ = T <$N1π1≤N1φ第 七模 态 律 Γ , N1π2= T , φ : <$X , N2φ = T <$T ≤N1φ公理2.4Γ,N1π2 =TP. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247263<$N2≤N1Q264P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247.Σ01.- 是的 Σ推论3.11在模态对中,提供内部相等关系,而是强加的偏序,强加的半格结构+是其连接。证明关系是自反的和传递的,因为[L]或[L]的等价条件是。我们有Γ<$ ( L1<$L2 ) <$ ( L1<$L2 ) <$ ( L2<$L1 ) =Ti<$Γ< $[L1]≥[L2] ,[L1]≤[L2],<$L1 <$≥<$L2<$且<$L1<$≤<$L2<$,这发生在<$Γ<$L1=L2:<$.至于和+的关系,(L1L1≤,[L1]≥[L2]EL2=L1L2,[L2] = [L1][L2]EL2=L1+L2Q命题3.12如果(N,P)是模态的,则(N,P)nil是可判定的:.(N,P)nil= Nand.(N,P)/πnilπ=PT=πx. x∈ L。从模态律出发,证明了NPT≥N(T)= NT = T和NPT≤P(T)= P=N.另一方面,根据定义,(N,P)nil = N,而PT = P(x。{x}x)={x}x。P{x}=10x。x∈L。Q推论3.13K0=1且K1=2。Proof=0×0==通过Phoa原理和约束NT=T,P=,NPT=,且N<$$>PT=T,则有(N,P)<$(T,<$)<$(N,P)<$(id,id)。Q虽然我们已经看到模态律描述了K-X的代数结构,但我们仍然必须证明它是(a) 一个π-分裂的子空间,因为模态定律只是定义了一个均衡器;(b) X上的自由半格,具有归纳和递归,以及(c) 这使得公理1.10中的量化器KX是合法的。我们将通过发展KX的另一个特征来做到这一点。4固定点属性由于本文的目的是定义Kuratowski有限子集的空间,我们必须从上一节的符号中删除它们。我们首先用存在性量化器的扩展来说明这一点,X:KX→到运算符E:→。P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247265备注4.1转换开关θ l变成θ nilx。 好吧 θ(x::l),我们有KXθθl = θnilx。好吧θ(x::l)=θ nilx。 X. λ 1。 θ(x::l)≡θnil 谢谢KX(S xθ)。因此,我们可以定义E为E = λ Θ 的最小不 动点。 Θ nil ∨你好 E(S x Θ),其中我们将Θ写为一个典型的值,类型为或上的谓词。请注意,解开这个不动点方程,我们就可以看到子集的列表表示,这些子集是我们在上一节中设法隐藏在半格结构后面的。符号4.2移位算子S:X×π→π定义为:S x Θ(N,P)<$Θ(x::N,x::P)<$Θ(λφ. Nφ<$φx,λφ。Pφ<$φx),异常运算符S:X×X→X,SxNφ<$N(λy. x = y <$φy)。注4.3类似地,为了证明嵌入i:KX>θ是可分的,我们还必须证明如何通过态射I:θKX→ θθ将任何谓词θ从KX扩展到θ。复合的EI·i被称为核(定义5.1),从它开始,[B]展示了如何将KX正式定义为的子空间。像E一样,E将由一个定点方程定义,其思想是,IθL 好吧(Ll。(Ll)θ([l],l).我们可以像以前一样扩展它,因为。(N,P)l=Nπl[l]πP:E Θ(N,P)= θ1。N π l<$[l] π P <$Θ([l],πl <$)=Nπnil<$[nil]πP<$Θnil谢谢好吧Nπ x::l<$[x::l] π P<$Θ([x::l],πx::l<$)=(NTθnil)谢谢 好吧 SxNπ l<$P {x}<$[l] π P<$S x Θ([l],<$l<$)=(N θ nil)x。P{x}<$E(S x Θ)(SxN,P).Q导致这个固定点方程的推理取决于列表的先验存在,所以我们必须再次从这个公式开始,作为我们 首先让我们回顾一下266P. Taylor/Electronic Notes in Theoretical Computer Science 122(2005)247点属性本身,它遵循公理1.9,但也使用方程归纳法(公理2.6)。命题4.4设A=<$U且Γ<$F:AA.然后是Γαn。F n:A满足Γ <$Fα = α。此外,如果Γ<$Fβ:A是一个预定点,即,Γ<$Fβ≤β,则Γ<$α ≤β。Q定义4.5设E∞和E∞为上述方程的最小不动点。在下一节中,我们将证明E∞是π上的核,也满足► E∞ ≤id且x:X,Θ:θ = 0, E∞(Sx Θ) ≤Sx($ E∞Θ),所以我们定义KX<${|E∞}。如果E∞容许:Γ,Θ:E∞ Θ L = Θ L,我们称Γ L:是可容许的。在第6节中,我们将证明所有可容许的L都是模态的,因此我们得到了前一节中所描述的代数结构引理4.6如果Θ ≤λL。则E∞Θ ≤σ。首先证明,E0Θ = Θnil≤σ.现在,如果E≤λ Θ.σ,那么E(S xΘ)≤σ,所以Φ
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- BottleJS快速入门:演示JavaScript依赖注入优势
- vConsole插件使用教程:输出与复制日志文件
- Node.js v12.7.0版本发布 - 适合高性能Web服务器与网络应用
- Android中实现图片的双指和双击缩放功能
- Anum Pinki英语至乌尔都语开源词典:23000词汇会话
- 三菱电机SLIMDIP智能功率模块在变频洗衣机的应用分析
- 用JavaScript实现的剪刀石头布游戏指南
- Node.js v12.22.1版发布 - 跨平台JavaScript环境新选择
- Infix修复发布:探索新的中缀处理方式
- 罕见疾病酶替代疗法药物非临床研究指导原则报告
- Node.js v10.20.0 版本发布,性能卓越的服务器端JavaScript
- hap-java-client:Java实现的HAP客户端库解析
- Shreyas Satish的GitHub博客自动化静态站点技术解析
- vtomole个人博客网站建设与维护经验分享
- MEAN.JS全栈解决方案:打造MongoDB、Express、AngularJS和Node.js应用
- 东南大学网络空间安全学院复试代码解析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功