算数阶层 Arithmetical hierarchy

（重定向自Kleene hierarchy）

算术阶层是递归论或可计算性理论中的概念，将自然数的子集按照定义它们的公式的复杂度分类。

设 $\phi(x)$ 为自然数的语言中的公式，定义 $\phi$ 为 $\Delta_0$ 公式当且仅当 $\phi$ 中的所有量词都是有界量词（即形如 $\exists n<t$ 或 $\forall n<t$ 的量词，其中 $t$ 为该语言中的项）。

定义 $\phi(x)$ 为 $\Sigma^0_1$ 公式当且仅当 $\phi(x):=\exists n\,\theta(n,x)$ ，其中 $\theta$ 为 $\Delta_0$ ；定义 $\phi$ 为 $\Pi^0_1$ 公式当且仅当 $\phi(x):=\forall n\,\theta(n,x)$ ，其中 $\theta$ 为 $\Delta_0$ 。

更进一步定义 $\phi(x)$ 为 $\Sigma^0_{n+1}$ 公式当且仅当 $\phi(x):=\exists n\,\theta(n,x)$ ，其中 $\theta$ 为 $\Pi^0_n$ 公式；定义 $\phi(x)$ 为 $\Pi^0_{n+1}$ 公式当且仅当 $\phi(x):=\forall n\,\theta(n,x)$ ，其中 $\theta$ 为 $\Sigma^0_n$ 公式。

设 $A\subseteq\mathbb{N}$ ；若存在 $\Sigma^0_n$ 公式定义 $A$ 则称 $A$ 为 $\Sigma^0_n$ 集合，若存在 $\Pi^0_n$ 公式定义 $A$ 则称 $A$ 为 $\Pi^0_n$ 公式。（若有公式 $\phi$ 与集合 $A$ ，使 $A=\{x\;\vert\;\mathbb{N}\vDash\phi(x)\}$ ，则称 $\phi$ 定义 $A$ 。）

单词	Kleene hierarchy
释义	Kleene hierarchy 中文百科算数阶层 Arithmetical hierarchy （重定向自Kleene hierarchy）算术阶层是递归论或可计算性理论中的概念，将自然数的子集按照定义它们的公式的复杂度分类。设 $\phi(x)$ 为自然数的语言中的公式，定义 $\phi$ 为 $\Delta_0$ 公式当且仅当 $\phi$ 中的所有量词都是有界量词（即形如 $\exists n<t$ 或 $\forall n<t$ 的量词，其中 $t$ 为该语言中的项）。定义 $\phi(x)$ 为 $\Sigma^0_1$ 公式当且仅当 $\phi(x):=\exists n\,\theta(n,x)$ ，其中 $\theta$ 为 $\Delta_0$ ；定义 $\phi$ 为 $\Pi^0_1$ 公式当且仅当 $\phi(x):=\forall n\,\theta(n,x)$ ，其中 $\theta$ 为 $\Delta_0$ 。更进一步定义 $\phi(x)$ 为 $\Sigma^0_{n+1}$ 公式当且仅当 $\phi(x):=\exists n\,\theta(n,x)$ ，其中 $\theta$ 为 $\Pi^0_n$ 公式；定义 $\phi(x)$ 为 $\Pi^0_{n+1}$ 公式当且仅当 $\phi(x):=\forall n\,\theta(n,x)$ ，其中 $\theta$ 为 $\Sigma^0_n$ 公式。设 $A\subseteq\mathbb{N}$ ；若存在 $\Sigma^0_n$ 公式定义 $A$ 则称 $A$ 为 $\Sigma^0_n$ 集合，若存在 $\Pi^0_n$ 公式定义 $A$ 则称 $A$ 为 $\Pi^0_n$ 公式。（若有公式 $\phi$ 与集合 $A$ ，使 $A=\{x\;\vert\;\mathbb{N}\vDash\phi(x)\}$ ，则称 $\phi$ 定义 $A$ 。）英语百科 Arithmetical hierarchy 算数阶层（重定向自Kleene hierarchy） In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical. The arithmetical hierarchy is important in recursion theory, effective descriptive set theory, and the study of formal theories such as Peano arithmetic.
随便看	inemendable的意思 in emergency的意思 in emergency cases的意思 inemia的意思 inemitie的意思 inemotivity的意思 in employment的意思 in empty的意思 inemulous的意思 Inemuri的意思 inenarrable的意思 inence的意思 inenchyma的意思 inenergetic的意思 in english的意思 inenition的意思 inenodable的意思 inent的意思 inenubilable的意思 inenucleable的意思 inenuclealble的意思 inenumerable的意思 ineo的意思 ineomplete bundle branch block的意思 in epitome的意思

Kleene hierarchy

算数阶层 Arithmetical hierarchy

Arithmetical hierarchy 算数阶层