산술적 위계
수리 논리학에서 산술적 위계(영어: arithmetical hierarchy) 또는 클레이니-모스토프스키 위계(Kleene hierarchy)란, 그것을 정의하는 식의 복잡도에 근거하여 집합들을 분류한 위계이다. 그러한 분류가 가능한 집합을 산술적(arithmetical)이라 한다.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/53/Arithmetic_hierarchy.svg/300px-Arithmetic_hierarchy.svg.png)
식의 산술적 위계
편집산술 위계에서는 1차 산술인 페아노 산술의 언어 속의 식들을 분류한다. 이는 0을 포함한 자연수 n에 대하여 및 로 표기된다. (여기서 이 식들이 집합 변수를 포함하지 않는다는 점을 표시하기 위해 그리스 문자는 가는 폰트의 lightface로 쓰여진다.)
식 가 한정 양화사(bounded quantifiers)만을 포함하는 논리식과 동치라면, 는 위계 과 로 분류된다.
이제 위계 과 은 각 자연수 n에 대하여 다음과 같이 귀납적으로 정의된다:
- 가 일 때, 와 같은 형식의 논리식과 동치인 식 는 위계 에 분류된다.
- 가 일 때, 와 같은 형식의 논리식과 동치인 식 는 위계 에 분류된다.
곧, 의 식은 몇 개의 존재 양화자에서 시작하여 존재 양화자와 전체 양화자가 번 번갈아가면서 나오는 논리식과 동치이다.(물론 1번에 1개씩 나온다는 의미가 아니다) 비슷하게, 의 논리식은 몇 개의 전체 양화자에서 시작하여 또 양화자들이 번갈아 나오는 식과 동치이다.
모든 식은 프리넥스 표준형의 식과 동치이므로, 집합 양화자가 없는 모든 식은 반드시 적어도 어느 하나의 위계로 분류된다. 또 어느 논리식에든지 무의미한(중복적인) 양화자들을 덧붙일 수 있으므로, 어떤 식이 또는 로 분류된다면 n보다 큰 모든 m에 대하여 과 으로도 분류될 수 있다. 따라서 가장 중요한 분류는 최소의 n에 해당하는 위계로, 다른 분류는 여기에 따라서 결정되는 것이다.
자연수 집합의 산술 위계
편집위의 정의를 가지고 자연수의 집합도 마찬가지로 그 집합을 정의하는 (즉, 그 집합의 원소에 대해서만 식이 참이 되는) 논리식의 산술 위계에 따라 분류할 수 있다.
같이 보기
편집참고 문헌
편집- G.Japaridze, "The logic of the arithmetical hierarchy", Annals of Pure and Applied Logic 66 (1994), pp.89-112.
- Moschovakis, Yiannis N. (1980). 《Descriptive Set Theory》. North Holland. ISBN 0-444-70199-0.
- Rogers, H. (1967). 《Theory of recursive functions and effective computability》. McGraw-Hill.
이 글은 수학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |