산술적 위계 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Arithmetic_hierarchy.svg|섬네일|right|300px|산술적 위계와 몇 복잡도 종류에 따른 집합 분류]]
[[수리 논리학]]에서 '''산술적 위계'''({{llang|en|arithmetical hierarchy}}) 또는 '''[[클레이니]]-[[안제이 모스토프스키|모스토프스키]] 위계'''(Kleene hierarchy)란, 그것을 정의하는 식의 복잡도에 근거하여 집합들을 분류한 위계이다. 그러한 분류가 가능한 집합을 '''산술적'''(arithmetical)이라 한다.

[[재귀 이론]], [[기술적 집합론]], [[페아노 산술]] 연구 등에 있어서 중요한 개념이다.

== 식의 산술적 위계 ==
산술 위계에서는 1차 산술인 [[페아노 산술]]의 언어 속의 식들을 분류한다. 이는 0을 포함한 자연수 n에 대하여 <math>\Sigma^0_n</math> 및 <math>\Pi^0_n</math> 로 표기된다. (여기서 이 식들이 집합 변수를 포함하지 않는다는 점을 표시하기 위해 그리스 문자는 가는 폰트의 lightface로 쓰여진다.)

식 <math>\phi</math> 가 한정 양화사(bounded quantifiers)만을 포함하는 논리식과 동치라면, <math>\phi</math>는 위계 <math>\Sigma^0_0</math> 과 <math>\Pi^0_0</math> 로 분류된다.

이제 위계 <math>\Sigma^0_n</math> 과 <math>\Pi^0_n</math> 은 각 자연수 n에 대하여 다음과 같이 귀납적으로 정의된다:
*<math>\psi</math> 가 <math>\Pi^0_n</math> 일 때, <math>\exists n_1 \exists n_2\cdots \exists n_k \psi</math> 와 같은 형식의 논리식과 동치인 식 <math>\phi</math>는 위계 <math>\Sigma^0_{n+1}</math> 에 분류된다.
*<math>\psi</math> 가 <math>\Sigma^0_n</math> 일 때, <math>\forall n_1 \forall n_2\cdots \forall n_k  \psi</math> 와 같은 형식의 논리식과 동치인 식 <math>\phi</math>는 위계 <math>\Pi^0_{n+1}</math> 에 분류된다.

곧, <math>\Sigma^0_n</math> 의 식은 몇 개의 존재 양화자에서 시작하여 존재 양화자와 전체 양화자가 <math>n-1</math> 번 번갈아가면서 나오는 논리식과 동치이다.(물론 1번에 1개씩 나온다는 의미가 아니다) 비슷하게, <math>\Pi^0_n</math> 의 논리식은 몇 개의 전체 양화자에서 시작하여 또 양화자들이 번갈아 나오는 식과 동치이다.

모든 식은 [[프리넥스 표준형]]의 식과 동치이므로, 집합 양화자가 없는 모든 식은 반드시 적어도 어느 하나의 위계로 분류된다. 또 어느 논리식에든지 무의미한(중복적인) 양화자들을 덧붙일 수 있으므로, 어떤 식이 <math>\Sigma^0_n</math> 또는 <math>\Pi^0_n</math>로 분류된다면 n보다 큰 모든 m에 대하여 <math>\Sigma^0_m</math> 과 <math>\Pi^0_m</math> 으로도 분류될 수 있다. 따라서 가장 중요한 분류는 최소의 ''n''에 해당하는 위계로, 다른 분류는 여기에 따라서 결정되는 것이다.

== 자연수 집합의 산술 위계 ==
위의 정의를 가지고 자연수의 집합도 마찬가지로 그 집합을 정의하는 (즉, 그 집합의 원소에 대해서만 식이 참이 되는) 논리식의 산술 위계에 따라 분류할 수 있다.

== 같이 보기 ==
* [[계산 가능성 이론]]
* [[페아노 산술]]
* [[점류]]

== 참고 문헌 ==
* [https://web.archive.org/web/20190419120954/http://www.csc.villanova.edu/~japaridz/ G.Japaridze], "The logic of the arithmetical hierarchy", Annals of Pure and Applied Logic '''66''' (1994), pp.89-112.
* {{서적 인용| author=Moschovakis, Yiannis N. | title=Descriptive Set Theory | publisher=North Holland | date=1980 |id=ISBN 0-444-70199-0}}
* {{서적 인용| author=Rogers, H. | title= Theory of recursive functions and effective computability| url=https://archive.org/details/theoryofrecursiv00roge |publisher=McGraw-Hill | date=1967}}

{{토막글|수학}}

[[분류:계층]]
[[분류:수리논리학]]
[[분류:계산 가능성 이론]]
[[분류:복잡도 종류]]