산술 위계 (원본) (2)

[[분류:가져온 문서/오메가]]
산술 위계(Arithmetic Hierarchy)란 1차 산술 위의 명제들을 복잡도를 기준으로 나눈 위계를 말한다. 

== 정의 ==
산술 위계는 다음과 같이 귀납적으로 정의된다.

* [math(\Sigma^0_0)]과 [math(\Phi^0_0)]은 유계 양화사 (bounded quantifier)만을 갖는 문장들의 집합이다.
* [math(\phi)]가 [math(\Sigma^0_n)]이면 [math(\forall x_1\cdots\forall x_n \phi)]는 [math(\Pi^0_{n+1})]이다.
* [math(\phi)]가 [math(\Pi^0_n)]이면 [math(\exists x_1\cdots\exists x_n \phi)]는 [math(\Sigma^0_{n+1})]이다.

[Include(틀:가져옴,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]], L=[[https://archive.ph/96kNT|링크]])]