梅德韦杰夫格与穆奇尼克格的一阶理论

### 梅德韦杰夫格与穆奇尼克格的一阶理论 #### 1. 引言 在可计算性理论约简性的研究中，一个主要问题是相应度结构的一阶理论有多复杂。可计算性理论约简性通常是数集或数论函数上的预序关系。若 ≤r 是函数上的约简性（即预序关系），对于函数 f 和 g，f ≤r g 通常有算术定义。所以，若 (P, ≤r) 是对应 ≤r 的度结构，关于偏序集 (P, ≤r) 的一阶陈述可转化为二阶算术陈述，允许对函数进行量化。这通常能得出 Th(P, ≤r) ≤1 Th2(N)。 例如，对于图灵度 DT = (DT, ≤T)，由上述内容可直接推出 Th(DT) ≤1 Th2(N)。而辛普森的经典结果表明 Th2(N) ≤m Th(DT)，这意味着图灵度 DT = (DT, ≤T) 的一阶理论与二阶算术 Th2(N) 一样复杂，即它们是可计算同构的。 梅德韦杰夫约简性是一种有趣但研究较少的可计算性理论约简性。它是定义在函数集上的预序关系，因此表达关于相应度结构（即有界分配格，称为梅德韦杰夫格）的一阶陈述需要对函数集进行量化。这表明要找到梅德韦杰夫格一阶理论复杂度的上界，需转向三阶算术。本文将证明梅德韦杰夫格及其非一致版本（穆奇尼克格）的一阶理论实际上与三阶算术是可计算同构的。 #### 2. 基础知识 - **质量问题与梅德韦杰夫约简**：质量问题是 NN 的子集。在质量问题上可定义预序关系 A ≤M B，若存在图灵泛函 Ψ，使得对于所有 f ∈ B，Ψ(f) 是全函数且 Ψ(f) ∈ A。关系 ≤M 诱导出质量问题上的等价关系 A ≡M B。A 的等价类记为 degM(A)，称为 A 的梅德韦杰夫度。所有梅德韦杰夫度的集合记为 M，按 degM(A) ≤M degM(B) 当且仅当 A ≤M B 进行偏序排列。存在最小的梅德韦杰夫度 0（包含可计算函数的质量问题的度）和最大的度 1（空质量问题的度）。 - **穆奇尼克格**：穆奇尼克格 Mw = (Mw, ≤w) 是梅德韦杰夫格的非一致版本。其约简关系定义为 A ≤w B ⇔ (∀g ∈ B)(∃f ∈ A)[f ≤T g]，其中 ≤T 表示图灵约简。同样，≤w 生成质量问题上的等价关系 ≡w，A 的等价类称为 A 的穆奇尼克度，记为 degw(A)。上述质量问题上的运算使 Mw 成为一个格 Mw = (Mw, ∨, ∧, 0w, 1w)，其中 0w 是包含可计算函数的质量问题的穆奇尼克度，1w = degw(∅)。 - **图灵度的嵌入**：图灵度可以嵌入到 M 和 Mw 中。映射 i(degT (A)) = degM({cA}) 和 iw(degT (A)) = degw({cA}) 分别是 (DT, ≤T) 到 (M, ≤M) 和 (Mw, ≤w) 的定义良好的嵌入，且它们保持最小元素和并运算。因此，我们常将图灵度与 i 或 iw 的值域等同起来。 - **图灵度的一阶可定义性**：图灵度在 (M, ≤M) 和 (Mw, ≤w) 中都可以通过公式 ϕ(u) =def ∃v [u < v ∧ ∀w [u < w → v ≤ w]] 进行一阶定义。 - **梅德韦杰夫格与穆奇尼克格的非初等等价性**