2005年Wadge约化在理论计算机科学中的重要性：Baire和Cantor空间的行为

理论计算机科学电子笔记120（2005）159-171www.elsevier.com/locate/entcs关于Wadge Reduction-ExtendedAbstract的Victor L. Selivanov谢利瓦诺夫1，2俄罗斯科学俄罗斯新西伯利亚摘要Baire和Cantor空间中的Wadge约化在描述集合论中是非常重要的。我们考虑了代数有向完备偏序在拓扑上的对应物-空间中的Wadge约化事实证明，在许多空间的韦奇reductionaries行为不如在经典的情况下，但也存在有趣的例子，空间有一个更好的行为。关键词：有向完全偏序，维空间，收缩，Wadge约化，Borel集，差族。1介绍回想一下，如果A=f−1（B）对于某个连续函数f：ωω→ωω，则A<$ωω可以Wadge约化为B<$ω ω（符号为A≤WB）。用任意拓扑空间X代替Baire空间ωω，得到幂集P（X）上的预序≤W，称为X中的Wadge约化.Baire空间和Cantor空间2ω中的Wadge约化在描述集合论中非常重要，因为它包含许多有趣的层次，并且在Borel集上几乎是良序的（这意味着它是良基的，并且对于所有Borel集A和B，它保持A≤WB或B≤WA），参见[22，20，7]。1由DFG-RFBR联合赠款（项目436 RUS 113/638/0-1）提供部分支助。2电子邮件地址：vseliv@nspu.ru1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.06.042160V.L. Selivanov/Electronic Notes in Theoretical Computer Science 120（2005）159本文研究了任意空间中的Wadge约化，重点讨论了代数有向完备偏序的拓扑对应-关于域理论的一般信息，我们请读者参考[4，5]。我们将试图理解经典Wadge约化的哪些性质（或其较弱的版本）在其他空间中也成立。例如，在一个示例中，本文讨论了Wadge序的某些子结构在Wadge约化下几乎良序时的上确界（或上确界的弱形式），并考虑了Wadge约化与[14]中的层次的关系（也可参见早期的相关论文[18，19，11，12]）。我们还考虑以下推广的Wadge约化，这在某些情况下是有用的。设X是一个空间，S是一个非空集，SX是所有映射ν：X→S的集合。设≤是SX上的预序定义如下：μ≤ν，如果μ=νf，对于某个连续的f：X→X。映射的叠加态通常简称为νf。注意，预序（{0， 1}X;≤）自然同构于预序（P（X）;≤W）（同构用它们的特征函数来标识X的子集）。我们用字母X，Y，.来表示空间。. ，空间（点）的元素x，y，.(for空间的具体例子也可能使用特殊符号），有限p，q，. . ，空间的子集（点集）由A，B，. 和类的子集的空间（点类）由 A ， B ， .. . . 我 们 用 A 表 示 A∈X 的 补 集 ， 即 ： A=X\A 和 byco-A={A|A∈A}-点类A的对偶。在第二节中，我们对任意空间中的Wadge约化做了一些一般性的评论。在第3节中，我们建立了一些特定于空间的事实。在第4-7节中，我们更详细地讨论了与[9，10]密切相关的两个有趣的子类和一些具体的例子。我们在第8节结束时讨论了未来可能的工作。由于空间限制，我们省略了可能在本文[17]的完整版本中找到的证明。2一般性评论在这一节中，我们给出了拓扑空间中Wadge约化的一些一般概念和事实。我们从Wadge序上确界存在性的几个结果开始。首先，我们证明了许多空间的结构的Wadge度不是一个上半格。命题2.1设X是空间，使得X上的任何连续函数有一个固定的点。 则对于任何A∈ X，集合A，A在下V.L. Selivanov/Electronic Notes in Theoretical Computer Science 120（2005）159161→→→→αβ∩ααα1α11Wadge还原剂下一个结果给出了Wadge约化下上确界存在的充分条件。命题2.2（i）如果直和X<$X等价于拓扑空间范畴中的X，则任意两个元素μ，ν ∈ S X在（S X; ≤）中有上确界。（ii）如果无穷序列（X，X，. . ）等价于拓扑空间范畴中的X则任何序列ν0，ν1，.的元素在（SX; ≤）中有一个上确界。我们说一个连续函数c：X Y是一个拟收缩，如果对于任何连续函数f：Y Y，存在一个连续函数f∈：X X使得fc = cf∈。空间Y是空间X的拟收缩，如果存在拟收缩r：X→Y。回想一下，收缩是一个连续函数r：X→Y，使得存在一个连续函数s：Y→X（称为截面），其中rs=idY。请注意，节始终是一个嵌入。空间Y是一个空间X的收缩，如果存在收缩r：XY。任何收缩都是拟收缩（考虑f= sf r）。下一个命题将拟撤回和撤回与Wadge归约联系起来。命题2.3（i）如果c：X→Y是拟收缩映射，则映射ν<$c →νc是从（S Y; ≤）到（S X; ≤）的单调函数。（ii）如果r：X→Y是一个收缩，则ν→νr是（SY; ≤）的一个嵌入（S X; ≤）。推论2.4（i）如果c：X→Y是拟收缩映射，则映射A<$→c−1（A）是从（P（Y）; ≤W）到（P（X）; ≤W）的单调函数。（ii）如果r：X→Y是一个收缩，则A<$→r−1（A）是一个嵌入，（P（Y）; ≤W）转换为（P（X）; ≤W）。设ω1是第一个不可数序数，{ω0}α ω是BorelX中的层次结构（参见[14]）。 对于任意0<β ω1，令{Dα（ω0）}α ω表示超过100的差异层次结构。0上的差异层次结构简称为β1差阶，记为{ω −1}α< ω。 像往常一样，让-1表示这两个函数分别对应于<$−α1和<$−α1=<$−α1<$−α1，这两个函数也类似于博雷尔等级制度让我们把不同空间中的层次结构的相应层次命题2.5如果f：X→Y是连续函数，则映射A→f-1（A）尊重引入的层次的所有层次，即 A ∈ φ 0（Y）蕴涵f−1（A）∈ 0（X），其他水平也是如此。162V.L. Selivanov/Electronic Notes in Theoretical Computer Science 120（2005）159→→ββ2N≤2ββ提案2.6设s：XY，r：YX是连续函数的一个截缩对。(i) 如果s（X）是open，则映射A→s（A）是s的第一个水平s−α1，Dα（0），co-D α（ω 0）（α，β< ω1，β > 1）。(ii) 如果s（X）是<$−21，则第n个apA<$→s（A）是第s个水平s<$−1（n <ω），ω−α1（ω≤α<ω1）和Dα（ω0），co-Dα（ω0）（α，β<ω1， β>1）。3中文（简体）本文讨论了与代数有向完备偏序拓扑对应的n-空间中的Wadge约化让我们回顾一下[4]中的一些相关定义。 设X是T0-空间. 对于x，y∈X，设x≤y表示对所有开集U，x∈U蕴涵y∈U.设F（X）是X的有限个元素的集合，即元素p∈X，使得上锥Op={x|p≤x}是o pen。 若任意开集都是集合Op（p∈F（X））的并，则称空间X为空间-空间X. 如果（X; ≤）包含一个最小元素（通常记为X），则称X-空间X为X-0 -空间。一个X-空间X是完备的，如果任何没有最大元素的非空有向集S有一个上确界supS∈X，并且supS是S的一个极限点（注意supS/∈F（X），对于任何有限元素p≤supS，存在s∈S，p s）。如众所周知的，任何X-空间X都是正则可嵌入到完备的X-空间称为X的完备化。具有可数集F（X）的X-空间称为可数基的.本文的主要结果还假设X是完备的。结果与文献[1 - 4]的结果相比，具有一定的优越性。 如果A ∈A−α1\A−α1，则n维表示A是pp p ∈A−α1-集. 我们考虑这样的集合可以包含底部元素T还是顶部元素T（假设这些元素存在）的问题。建议3.1LetXea10-s pa ce. F或任何αω1，如果A是proper<$−α1则n/∈A。命题3.2设X是一个有顶元素T的X-空间。 针对任何数目n<ω且任意p ro per<$−n1-集A，T ∈Ai<$n是奇数.我们用几个关于Wadge约化的结果来结束本节。空间。命题3.3设X是一个完备的空间.对于任何数n ω，每个n−n1-集是Wadge可导的，它可导于从n−0\n−n1的每一个集合。下一个结果是上一个命题的直接推论V.L. Selivanov/Electronic Notes in Theoretical Computer Science 120（2005）159163定理3.4设X是一个具有任意有限长的无穷元链 的完备X-空间。(i) F或任何数bern <ω，p ro pern−n1-集类形成W边度。(ii) 对任意数n< ω，有G n

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