(+)분류 : 가져온 문서/오메가
산술 위계(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}이다.
