산술적 위계

3. 자연수 집합의 산술 위계

페아노 공리계의 언어에서, 자연수 집합 ''X''는 해당 집합의 원소에 대해서만 참이 되는 논리식 ''φ''에 의해 정의될 수 있다. 이때, ''X''의 원소는 정확히 ''φ''를 만족하는 숫자들이다. 이러한 방식으로 일차 산술에서 정의 가능한 자연수 집합 ''X''는 $\backslash Sigma^0\_n$, $\backslash Pi^0\_n$, $\backslash Delta^0\_n$ 형태로 분류된다.

• $\backslash Sigma^0\_n$ 분류: ''X''가 $\backslash Sigma^0\_n$ 공식으로 정의될 경우, ''X''는 $\backslash Sigma^0\_n$으로 분류된다.
• $\backslash Pi^0\_n$ 분류: ''X''가 $\backslash Pi^0\_n$ 공식으로 정의될 경우, ''X''는 $\backslash Pi^0\_n$으로 분류된다.
• $\backslash Delta^0\_n$ 분류: ''X''가 $\backslash Sigma^0\_n$ 공식과 $\backslash Pi^0\_n$ 공식 모두로 정의될 경우, ''X''는 $\backslash Delta^0\_n$으로 분류된다.

4. 칸토어 공간과 베어 공간의 부분 집합의 산술적 위계

칸토어 공간은 0과 1의 무한 수열 전체 집합이며, $2^\{\backslash omega\}$로 표기된다. 베어 공간은 자연수의 무한 수열 전체 집합이며, $\backslash omega^\{\backslash omega\}$ 또는 $\backslash mathcal\{N\}$으로 표기된다. 칸토어 공간의 원소는 자연수의 집합과 동일시될 수 있으며, 베어 공간의 원소는 자연수에서 자연수로의 함수와 동일시될 수 있다.

칸토어 공간의 부분 집합은 $\backslash Sigma^0\_n$ 공식으로 정의될 수 있는 경우 $\backslash Sigma^0\_n$ 분류를 할당받는다. 집합은 $\backslash Pi^0\_n$ 공식으로 정의될 수 있는 경우 $\backslash Pi^0\_n$ 분류를 할당받는다. 집합이 $\backslash Sigma^0\_n$과 $\backslash Pi^0\_n$ 모두인 경우, 추가로 $\backslash Delta^0\_n$ 분류가 부여된다. 예를 들어, 모두 0이 아닌 무한 이진 문자열의 집합(또는 자연수의 모든 비어 있는 집합) $O\backslash subseteq\; 2^\{\backslash omega\}$는 $O=\backslash \{\; X\backslash in\; 2^\backslash omega\; |\; \backslash exists\; n\; (X(n)=1)\; \backslash \}$이므로, $\backslash Sigma^0\_1$ 공식으로 정의되므로 $\backslash Sigma^0\_1$ 집합이다.

베어 공간의 부분 집합을 산술적 위계에서 분류하는 방법은 두 가지가 있다.

• 베어 공간의 부분 집합은 $\backslash omega$에서 $\backslash omega$로의 각 함수를 그래프의 특성 함수로 변환하는 맵 아래에서 칸토어 공간의 해당 부분 집합을 갖는다. 베어 공간의 부분 집합은 해당 칸토어 공간의 부분 집합이 동일한 분류를 갖는 경우에만 $\backslash Sigma^0\_n$, $\backslash Pi^0\_n$ 또는 $\backslash Delta^0\_n$ 분류를 받는다.
• 베어 공간에 대한 산술적 위계의 동등한 정의는 2차 산술의 함수적 버전을 사용하여 공식의 산술적 위계를 정의함으로써 제공된다. 그런 다음 칸토어 공간의 부분 집합에 대한 산술적 위계는 베어 공간의 위계로부터 정의될 수 있다. 이 대체 정의는 첫 번째 정의와 정확히 동일한 분류를 제공한다.

5. 상대화 산술적 위계

집합 ''X''가 집합 ''Y''에 대해 재귀적이라는 것을 정의할 수 있는 것처럼, ''X''의 계산이 오라클로 ''Y''를 참조하도록 허용함으로써 이 개념을 전체 산술적 위계로 확장할 수 있다. ''X''가 ''Y'' 내에서 산술적이라는 것은 ''X''가 어떤 자연수 ''n''에 대해 $\backslash Sigma^\{0,Y\}\_n$ 또는 $\backslash Pi^\{0,Y\}\_n$에 속한다는 것이다.

자연수의 집합 ''Y''를 고정하고 페아노 산술의 언어에 ''Y''의 원소인지 여부에 대한 술어를 추가한다. ''X''가 확장된 언어에서 $\backslash Sigma^0\_n$ 공식으로 정의되면 $\backslash Sigma^\{0,Y\}\_n$에 속한다고 말한다. 즉, ''X''는 ''Y''의 원소 여부에 대한 질문을 할 수 있는 $\backslash Sigma^\{0\}\_n$ 공식으로 정의되면 $\backslash Sigma^\{0,Y\}\_n$이다. 또는 $\backslash Sigma^\{0,Y\}\_n$ 집합을 ''Y''에서 재귀적인 집합으로 시작하여 이러한 집합의 합집합과 교집합을 최대 ''n''번 번갈아 가면서 만들 수 있는 집합으로 볼 수도 있다.

예를 들어, ''Y''를 자연수의 집합이라고 하자. ''X''를 ''Y''의 원소로 나누어지는 수의 집합이라고 하면 ''X''는 공식 $\backslash phi(n)=\backslash exists\; m\; \backslash exists\; t\; (Y(m)\backslash land\; m\backslash times\; t\; =\; n)$으로 정의되므로 ''X''는 $\backslash Sigma^\{0,Y\}\_1$에 속한다(실제로 두 양자를 ''n''으로 바운드할 수 있으므로 $\backslash Delta^\{0,Y\}\_0$에도 속한다).

6. 산술 환원성과 차수

산술적 환원 가능성은 튜링 환원 가능성과 초산술적 환원 가능성 사이의 중간 개념이다. 페아노 산술 언어의 어떤 공식으로 정의되면 '''산술적'''(또는 '''산술적 정의 가능''')이라 한다.^[1] 어떤 자연수 ''n''에 대해 $\backslash Sigma^0\_n$ 또는 $\backslash Pi^0\_n$이면 ''X''는 산술적이다. 집합 ''X''가 집합 ''Y'' '''내에서 산술적'''이라는 것은 $X\; \backslash leq\_A\; Y$로 표시하며, ''X''가 ''Y''의 멤버십에 대한 술어를 확장한 페아노 산술 언어의 어떤 공식으로 정의될 수 있음을 의미한다. ''X''가 ''Y'' 내에서 산술적이라는 것은 ''X''가 어떤 자연수 ''n''에 대해 $\backslash Sigma^\{0,Y\}\_n$ 또는 $\backslash Pi^\{0,Y\}\_n$에 속한다는 것과 동등하다. $X\; \backslash leq\_A\; Y$의 동의어는 ''X''는 ''Y''로 '''산술적으로 환원 가능'''하다는 것이다.

$X\; \backslash leq\_A\; Y$ 관계는 반사 관계이며 추이 관계이므로, 다음 규칙으로 정의된 $\backslash equiv\_A$ 관계는 동치 관계이다.

:$X\; \backslash equiv\_A\; Y\; \backslash iff\; X\; \backslash leq\_A\; Y\; \backslash land\; Y\; \backslash leq\_A\; X$

이 관계의 동치류를 '''산술적 차수'''라고 부르며, $\backslash leq\_A$에 따라 부분 순서가 지정된다.

7. 튜링 기계와의 관계

포스트의 정리는 자연수 집합의 산술적 위계와 튜링 차수 사이의 밀접한 관계를 확립한다.^[1] 특히, 모든 ''n'' ≥ 1에 대해 다음이 성립한다.^[1]

• 집합 $\backslash emptyset^\{(n)\}$ (공집합의 ''n''번째 튜링 점프)은 $\backslash Sigma^0\_n$에서 many-one 완전하다.^[1]
• 집합 $\backslash mathbb\{N\}\; \backslash setminus\; \backslash emptyset^\{(n)\}$은 $\backslash Pi^0\_n$에서 many-one 완전하다.^[1]
• 집합 $\backslash emptyset^\{(n-1)\}$은 $\backslash Delta^0\_n$에서 튜링 완전하다.^[1]

8. 확장과 변형

원시 귀납적 함수 각각에 대한 함수 기호를 확장한 언어를 사용하여 공식의 산술적 위계를 정의하는 것이 가능하다.^[1] 이 변형은 $\backslash Sigma^0\_0=\backslash Pi^0\_0=\backslash Delta^0\_0$의 분류를 약간 변경하는데, 이는 일차 페아노 산술에서 원시 귀납적 함수를 사용하는 것은 일반적으로 무한한 존재량 기호를 필요로 하며, 따라서 이 정의에 따르면 $\backslash Sigma^0\_0$에 속하는 일부 집합은 이 문서의 시작 부분에서 주어진 정의에 따르면 엄격하게 $\backslash Sigma^0\_1$에 속하기 때문이다.^[1] 클래스 $\backslash Sigma^0\_1$ 및 따라서 계층 구조의 모든 상위 클래스는 영향을 받지 않는다.^[1]

계층 구조의 좀 더 의미론적인 변형은 자연수에 대한 모든 유한 관계에 대해 정의할 수 있으며, 다음 정의가 사용된다.^[1] 모든 계산 가능한 관계는 $\backslash Sigma^0\_0=\backslash Pi^0\_0=\backslash Delta^0\_0$로 정의된다.^[1] 분류 $\backslash Sigma^0\_n$ 및 $\backslash Pi^0\_n$은 다음과 같은 규칙으로 귀납적으로 정의된다.^[1]

• 관계 $R(n\_1,\backslash ldots,n\_l,m\_1,\backslash ldots,\; m\_k)\backslash ,$가 $\backslash Sigma^0\_n$이면, 관계 $S(n\_1,\backslash ldots,\; n\_l)\; =\; \backslash forall\; m\_1\backslash cdots\; \backslash forall\; m\_k\; R(n\_1,\backslash ldots,n\_l,m\_1,\backslash ldots,m\_k)$는 $\backslash Pi^0\_\{n+1\}$로 정의된다.
• 관계 $R(n\_1,\backslash ldots,n\_l,m\_1,\backslash ldots,\; m\_k)\backslash ,$가 $\backslash Pi^0\_n$이면, 관계 $S(n\_1,\backslash ldots,n\_l)\; =\; \backslash exists\; m\_1\backslash cdots\; \backslash exists\; m\_k\; R(n\_1,\backslash ldots,n\_l,m\_1,\backslash ldots,m\_k)$는 $\backslash Sigma^0\_\{n+1\}$로 정의된다.

9. 다른 위계와의 관계

다항 시간 위계는 산술적 위계의 "실현 가능한 자원 제한" 버전으로, 관련된 숫자에 다항식 길이 제한을 적용하거나, 이와 동등하게 관련된 튜링 머신에 다항식 시간 제한을 적용한다. 이는 산술적 위계의 $\backslash Delta^0\_1$ 수준에 있는 자연수 집합의 일부에 대한 더 세분화된 분류를 제공한다.