산술적 위계

산술적 위계와 몇 복잡도 종류에 따른 집합 분류

수리 논리학에서 산술적 위계(영어: arithmetical hierarchy) 또는 클레이니-모스토프스키 위계(Kleene hierarchy)란, 그것을 정의하는 식의 복잡도에 근거하여 집합들을 분류한 위계이다. 그러한 분류가 가능한 집합을 산술적(arithmetical)이라 한다.

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

식의 산술적 위계

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

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

이제 위계 $\Sigma _{n}^{0}$ 과 $\Pi _{n}^{0}$ 은 각 자연수 n에 대하여 다음과 같이 귀납적으로 정의된다:

• $\psi$ 가 $\Pi _{n}^{0}$ 일 때, $\exists n_{1}\exists n_{2}\cdots \exists n_{k}\psi$ 와 같은 형식의 논리식과 동치인 식 $\phi$는 위계 $\Sigma _{n+1}^{0}$ 에 분류된다.
• $\psi$ 가 $\Sigma _{n}^{0}$ 일 때, $\forall n_{1}\forall n_{2}\cdots \forall n_{k}\psi$ 와 같은 형식의 논리식과 동치인 식 $\phi$는 위계 $\Pi _{n+1}^{0}$ 에 분류된다.

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

모든 식은 프리넥스 표준형의 식과 동치이므로, 집합 양화자가 없는 모든 식은 반드시 적어도 어느 하나의 위계로 분류된다. 또 어느 논리식에든지 무의미한(중복적인) 양화자들을 덧붙일 수 있으므로, 어떤 식이 $\Sigma _{n}^{0}$ 또는 $\Pi _{n}^{0}$로 분류된다면 n보다 큰 모든 m에 대하여 $\Sigma _{m}^{0}$ 과 $\Pi _{m}^{0}$ 으로도 분류될 수 있다. 따라서 가장 중요한 분류는 최소의 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.