Arithmetical Hierarchy
정의 가능성과 계산 복잡성에 기초하여 자연수 집합을 분류한 것. 계산 가능성 이론과 수학 논리학의 기본 개념이기도 하다.
보다 구체적으로 설명하자면 계층 구조는 자연수의 모든 부분 집합을 수준으로 분할하며, 각 수준은 특정 논리적 복잡성의 공식을 사용하여 정의할 수 있는 집합을 나타낸다. 산술 계층이라고 하는 가장 낮은 수준은 1차 산술 공식을 사용하여 정의할 수 있는 집합을 포함하는 반면, 더 높은 수준은 정량자 및 기타 논리적 구조를 포함하는 점점 더 복잡한 공식에 해당한다.
정의 가능성과 계산 복잡성에 기초하여 자연수 집합을 분류한 것. 계산 가능성 이론과 수학 논리학의 기본 개념이기도 하다.
보다 구체적으로 설명하자면 계층 구조는 자연수의 모든 부분 집합을 수준으로 분할하며, 각 수준은 특정 논리적 복잡성의 공식을 사용하여 정의할 수 있는 집합을 나타낸다. 산술 계층이라고 하는 가장 낮은 수준은 1차 산술 공식을 사용하여 정의할 수 있는 집합을 포함하는 반면, 더 높은 수준은 정량자 및 기타 논리적 구조를 포함하는 점점 더 복잡한 공식에 해당한다.
