数学论文（无限时间图灵机） (7-2)

我们首先简要介绍博雷尔等价关系的研究。这个这门学科的名称有点用词不当--实际上是研究的主要对象是标准Borel空间上的任意等价关系，即配备有完全可分度量空间的Borel结构。在应用程序中，我们想到等价关系表示来自的某个其他领域的分类问题数学例如，由于域为N的任何群都是由其乘法函数决定的，因此研究可数群的分类问题相当于×N的一个子空间上的同构等价关系。对于更多示例，请参见[ST11]的第1.2节。

Borel等价关系理论围绕以下关键概念展开复杂性如果E，F是标准Borel空间X，Y上的等价关系，则如下〔FS89〕和〔HK96〕我们说E是Borel可约为F，写成E≤BF，当存在Borel函数f:X→ Y使得

(1)x E x′⇐⇒ f（x）Ff（x′）。

Borel可约性度量等价关系的复杂性，而不是作为对的集合，而是分类问题。也就是说，如果E是Borel可约为F，那么的分类X到E的元素并不比Y到F的元素的分类难。

现在，Borel等价关系的经典且非常成功的研究包括两大努力。首先，人们希望绘制出众多之间的关系充分理解和自然发生的等价关系。其次，给一个现实生活分类问题应该通过将其与制定基准关系。

关于归约函数（在这种情况下，它们是Borel）的一些可定义条件是必需的事实上，如果没有任何这样的限制，还原性总是可以确定的仅凭基数。然而，也有通过不变量进行自然分类的情况其不能通过Borel归约函数来计算。例如，它是∆∼1.2.，而不是Borel计算可数扭阿贝尔群的经典Ulm不变量。一可能会倾向于形成∆的理论∼1.2.可还原性，但事实证明这个概念也是慷慨的事实上，正如我们将在下面的定理11中看到的，它可能包含大多数等价性关系合并为一个琐碎的复杂性类。

我们将在这里考虑可在无限时间内计算的约化函数图灵机（参见[CH11]以获得更完整的阐述）。因此，对于R上的任何两个等价关系E，F，我们说E是无限时间可计算可约为F，写E≤cF，如果存在无限时间可计算函数F（自由允许实参数）满足等式（1）。类似地，我们说E最终可约为F，写成E≤eF，如果存在满足等式（1）的最终可计算函数f。请注意由于所有不可数的标准Borel空间都是Borel同构的，我们不失去一般性通过限制我们与域R的等价关系。

当然，通过第1节中的评论（并再次强调我们允许参数），无限时间可计算的约简包括所有的Borel约简。

因此，我们的理论将扩展经典理论。相反，许多不可约性E6≤BF的经典证明依赖于测度、范畴或强迫等方法。因此，他们经常“过冲”，并表明不存在从E到F的减少，即Lebesgue可测量，Baire可测量，或绝对∆∼1.2.（下面讨论）。

由于无限时间可计算的和最终可计算的函数享有这三个函数在这些性质中，在每种情况下，都可以得出E≰cF，甚至E≰eF，以及因此，当我们从≤B层次转移到≤c和≤e层次时，不会有太多的“塌陷”层次结构。

可约性的无限时间概念与绝对∆的概念密切相关∼1.2.可还原性，Hjorth等人在文献中对此进行了讨论。回想一下子集A⊆R被认为是绝对∆∼1.2.

如果它由等价∑定义∼1.2.和π∼1.2.公式其在每个强制延伸中保持相等。函数f:R→ 据说R是绝对∆∼1.2.　

如果它由等价∑定义∼1.2.和π∼1.2.公式其在每个强制延伸中保持相等。函数f:R→ 据说R是绝对∆∼1.2.

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。