산술 위계(Arithmetic Hierarchy)란 1차 산술 위의 명제들을 복잡도를 기준으로 나눈 위계를 말한다.
목차
1. 정의
산술 위계는 다음과 같이 귀납적으로 정의된다.
\Sigma^0_0과 \Phi^0_0은 유계 양화사 (bounded quantifier)만을 갖는 문장들의 집합이다.\phi가 \Sigma^0_n이면 \forall x_1\cdots\forall x_n \phi는 \Pi^0_{n+1}이다.\phi가 \Pi^0_n이면 \exists x_1\cdots\exists x_n \phi는 \Sigma^0_{n+1}이다.
이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.본 문서의 원본은
링크에서 확인할 수 있습니다.
