如何理解算术层次结构中 $\Pi_k$ 的定义

Question

正在阅读有关可计算性理论的文本，并根据文本，在每个级别 $k$ 在算术层次结构中，我们有两个集合， $\Sigma_k$ 和 $\Pi_k$, ， 在哪里 $\Pi_k$ 定义为：

$$ \Pi_k=co-\Sigma_k $$

所以说对于 $k=0$, ，我们有可判定集类并且 $\Sigma_0=\Pi_0$, ，并且对于 $k=1$, ， 我们有 $\Sigma_1$ 作为可计算可枚举（c.e.）集合的类和 $\Pi_1$ 作为不可计算可枚举集的类（不是 c.e.）......

让 $L(M_e)$ 表示图灵机识别的语言 $M_e$ 与哥德尔数 $e$. 。我遇到了以下语言 $E$, ， 在哪里：

$$E=\{e|L(M_e)=\Sigma^*\}$$

IE。 $E$ 是所有图灵机代码的语言 $e$ 是可计算可枚举的。通过对角化论证，可以证明 $E$ 不是 c.e.这意味着：

$$ E \in \Pi_1 $$

然而，如果 $E \in \Pi_1$, ， 代表着 $E = co-A$, ， 对于一些 $A \in \Sigma_1$, ，使用上面语句中的定义...然而，补 $E$ 是：

$$ \overline{E}=\overline{\{e|L(M_e)=\Sigma^*\}} $$

这（我猜）意味着 $\上划线{E}$ 是所有图灵机的语言 $e$ 这样在某些输入上， $e$ 发散...然而，事实证明 $\overline{E} \equiv_m K^{2}$, ， IE。 $\overline{E} \equiv_m K^K$, ，因此，如果给定两个集合 $A$ 和 $B$, ， 我们有 $A \equiv_m B$ 当且仅当 $A \leq_m B$ 和 $B \leq_m A$, ， 和 $\leq_m$ 指的是多对一的减少：

$$ \overline{E} \equiv_m K^K \in \Sigma_2 $$

鉴于 $\Sigma_2 eq \Sigma_1$, ，看起来像这样 $\上划线{E}$ 不是可计算可枚举的...但这不是与定义相矛盾吗 $\Pi_1$ 其中指出 a not c.e 的补集。设置为 c.e.？

我认为我对定义的理解遗漏了一些东西......

Answer 1

为了 $k$ 甚至，一种语言 $L$ 是在 $\Pi_k$ 如果存在递归谓词 $R$ 这样$$ x in L\Longleftrightarrow （对于所有 y_1 （存在 y_2 ）\cdots （对于所有 y_{k-1} （存在 y_k ）, R(x,y_1,\ldots,y_k) $$量词之间交替 $\forall$ 和 $\存在$.

什么时候 $k$ 很奇怪，相同的定义有效，但最后一个量词是 $\forall$: $$ x in L\Longleftrightarrow （所有 y_1 \exists y_2 \cdots \exists y_{k-1} （所有 y_k \, R(x,y_1,\ldots,y_k) $$

例如，所有全图灵机的语言是 $\Pi_2$ 自从$$ x \in \mathsf{TOT} \Longleftrightarrow \forall y \exists z \, ext{"Machine $x$ halts on input $y$ within $z$ steps"} $$

班上 $\Sigma_k$ 以同样的方式定义，第一个量词是 $\存在$ 而不是 $\forall$.

如果你补充一种语言 $\Sigma_k$ 你得到一个 $\Pi_k$, ，反之亦然。这是由于量词的德摩根定律，以及递归谓词的否定也是递归的事实。

例如，语言 非-图灵机总数为 $\Sigma_2$ 自从$$ x \in \mathsf{NTOT} \Longleftrightarrow x otin \mathsf{TOT} \Longleftrightarrow \exists y \forall z \, ext{"Machine $x$ doesn't halt on input $y$ within $z$ steps"} $$