산술적 계층
Arithmetical hierarchy![]() |
수학 논리학에서, 산술적 위계, 또는 클린-모스토프스키 위계(수학자 스티븐 콜 클린과 안제이 모스토프스키 이후)는 어떤 집합을 정의하는 공식의 복잡성에 기초하여 분류한다.분류를 수신하는 집합을 산술적 집합이라고 합니다.
산술적 위계는 재귀 이론, 효과적인 기술 집합 이론, 그리고 페아노 산술과 같은 형식 이론의 연구에서 중요하다.
Tarski-Kuratowski 알고리즘을 사용하면 수식에 할당된 분류와 수식에 정의된 집합에 대한 상한을 쉽게 얻을 수 있습니다.
초산술 계층과 해석 계층은 추가적인 공식과 집합을 분류하기 위해 산술 계층을 확장합니다.
공식의 산술적 계층 구조
산술 계층은 1차 산술 언어로 된 공식에 분류를 할당합니다.분류는 자연수 n(0 포함)의 경우 0 \0}) 및 0(\})으로 표시됩니다.여기에 있는 그리스 문자는 라이트페이스 기호로, 수식에 설정된 파라미터가 포함되어 있지 않음을 나타냅니다.
{ \ 이 (가) 수량화되지 않은 수식과 논리적으로 동일한 경우, 0(\ \ _ { 및 (\ \_ { 이 (가)로 구분됩니다.수식이 경계화된 수식이 a로 대체될 수 있습니다.수량자(예를 들어 " ,"( x < 2, ( x)는 "( 에 합니다 \ ( 0 )\\ (1에는 한정 수량자를 지정할 도 있습니다.
분류 0 \n}^ 0(\ _은 다음 규칙을 사용하여 각 자연수 n에 대해 유도적으로 정의됩니다.
- }이) m m 2m \ \ 형식의 공식과 논리적으로 동일한 경우, 서 }는\ + _
- 이 (가)equival 2 { 형식의 공식과 논리적으로 동등한 경우 서 \ 0. _ n cation n + 0( \ \_ { + }^ )
_{은 일부 기존 수량자로 시작하여 n-1의 연속된 수량자와 범용 수량자 사이를 교대로 공식에 해당하며, 공식은 다음과 같습니다.몇 가지 범용 수량화 및 교대로 사용할 수 있습니다.
모든 1차 공식은 프리넥스 정규형을 가지기 때문에 모든 공식에는 적어도 하나의 분류가 할당됩니다.용장 수량자는 임의의 수식에 추가할 수 있으므로 수식이 _ 또는 0(\_{에 할당되면 r0(\ _ 및 0 R)에 할당됩니다> n마다 0} 입니다.따라서 수식에 할당된 유일한 관련 분류는 최소 n개의 분류이며, 다른 모든 분류는 수식에서 결정할 수 있다.
자연수 집합의 산술적 계층 구조
자연수의 집합 X는 X의 원소가 정확히 θ를 만족하는 숫자일 경우, Peano 산술 언어(기호 "0", 후속 함수 "S", 덧셈 "+", 곱셈 "×", 등식 "=")에서 공식 θ로 정의된다.즉, 모든 자연수 n에 대해
서 n _{\은 n{\에 하는 산술 언어의 숫자입니다. 집합은 Peano 산술 언어의 공식에 의해 정의된 경우 1차 산술에서 정의할 수 있습니다.
1차 산술로 정의할 수 있는 자연수의 각 세트 에는 \}^0 \0 및0(\ \}^0 의 분류가 할당됩니다. 서 은 n)입니다X가 _ 공식으로 정의 가능한 경우 X에는 _이 할당됩니다.X가 공식으로 정의 가능한 경우 가 할당됩니다.는 _과 _{ 이며 X X에는 추가 0 _이 할당됩니다.
0 \0}) 공식은 거의 의미가 없다는 점에 유의하십시오. 공식의 첫 번째 수량자는 존재 또는 보편입니다. 0 세트는 공식으로 정의되지 않고 0(\과 }^0예를 들어 홀수 n n의 집합은of ( 2 × k ( \ 2 \ k)}또는 ( × + 1 \ k ( n \ k + )로 정의할 수 있습니다
자연수 집합의 유한 데카르트 거듭제곱에 대한 산술적 위계질서를 정의하기 위해 병렬 정의가 사용됩니다.하나의 자유 변수를 갖는 공식 대신 k 자유 숫자 변수를 갖는 공식을 사용하여 자연수의 k-튜플 집합에 대한 산술적 위계를 정의합니다.이는 사실상 페어링 기능의 사용과 관련이 있습니다.
상대화 산술 계층
집합 X가 다른 집합 Y에 대해 재귀적인 것을 정의할 수 있는 것과 마찬가지로 X를 정의하는 계산에서 Y를 오라클로 참조할 수 있도록 함으로써 이 개념을 전체 산술 계층으로 확장하고 X가 0 _ \Sigma _이 되는 것을 정의할 수 있습니다. Y의 0 \0}), _ n , \ \ _ { n }^{ , 및 0 _ 이를 수행하려면 정수 Y 세트를 수정하고 Peano 산술어에 Y 멤버쉽의 술어를 추가합니다.다음으로 X가 0 _ 이 확장 언어로 0 _ 공식으로 정의되어 있는 경우.즉, X는 0(\ _이가) 0(\ _ 공식으로 정의되어 있는 경우 Y의 멤버십에 대한 질문을 할 수 있습니다. 0, _ Y의 집합에서 시작하여 이러한 집합의 합집합과 교집합을 최대 n회 반복하여 작성할 수 있는 집합으로 설정합니다.
예를 들어 Y를 정수 집합이라고 가정합니다.X를 Y의 원소로 나눌 수 있는 숫자의 집합이라고 하자.으로 X는 식 ( ) m ( ( ) m × ){ (n ) = \ \ t}에 의해 정의됩니다.그러면 X는 { \} _ {
산술적 환원성과 정도
산술적 환원성은 튜링 환원성과 초산술적 환원성 사이의 중간 개념이다.
집합이 Peano 산술 언어의 어떤 공식에 의해 정의된 경우 집합은 산술적(산술적 및 산술적으로 정의 가능)입니다.X가 _ _일 경우 X는 등가적으로 계산됩니다.집합 X는 집합 Y 내의 산술이며, 만약 X가 Y 내의 멤버쉽의 술어에 의해 확장된 Peano 산술의 언어로 어떤 식으로서 정의될 수 있다면 X A\ \ X \ 로 표기된다.마찬가지로 X가 0 \ \ _ { }^{ 0 Y \ display \ Sigma _ { n }의 경우 X는 Y로 산술됩니다. 또는 0 ,Y}}의 정수입니다. 의 동의어는 X는 Y로 산술적으로 환산할 수 있다
A ( \ \ { A })는 반사적이고 과도적이며, 따라서 에 의해 정의된A ( \ display \ _ {} )
는 동등 관계입니다.이 관계의 동등성 클래스는 산술도라고 불립니다.이 클래스는 아래에 부분적으로 정렬되어 있습니다.
칸토르와 베아르 공간의 부분 집합의 산술적 계층 구조
칸토어 공간은 2(\ 로 되며, Baire 공간은s(\로 표기되며 Baire 공간은 자연수의 모든 무한 시퀀스 집합입니다.칸토어 공간의 요소는 정수 집합과 정수에서 정수까지의 함수를 가진 베아르 공간의 요소로 식별할 수 있습니다.
2차 산술의 일반적인 공리화에서는 집합 양자화자가 칸토어 공간에 걸쳐 수량화하는 것으로 자연스럽게 볼 수 있는 집합 기반 언어를 사용한다.칸토어 공간의 서브셋에는 (\ \_{0}) 으로 정의할 수 있는 경우 분류 \n 0(\displaystyle \ _이 할당됩니다.is \ _ { }^ 공식으로 정의할 수 있는 경우 이 세트에는 0(\ \ { n0})이 할당됩니다.세트가 _과 _{인 경우 추가 (\ \{n}^이 됩니다. 예를 들어 O 2 \ 2 ^ \ set ren't all 0(또는 동등하게 비어 있지 않은 모든 정수 집합)입니다. { 2 2 2 n ( ( ) ) { O \ { \ 2 ^ { \ \ n ( ( n )1 } } we 、 O 、 、 0 0 0 0 0 0 hence hence 0 0 0 0 0 0 01 。
칸토어 공간의 요소(정수 집합과 관련)와 칸토어 공간의 하위 집합은 모두 산술적 계층 구조로 분류되지만, 이들은 동일한 계층이 아닙니다.사실 두 계층 간의 관계는 흥미롭고 단순하지 않다.예를 들어 칸토어 공간의 0{ \ _ { }^ 요소는 (일반적으로) 칸토어 공간의 { X 요소와 하지 않으므로{ { \ { X은 (는) {\ _ 공간의 집합입니다.그러나 많은 흥미로운 결과가 두 계층과 관련되어 있습니다.
Baire 공간의 서브셋을 산술적 계층으로 분류할 수 있는 방법은 두 가지가 있습니다.
- Baire 공간의 서브셋은 맵 아래에 대응하는 칸토어 공간의 서브셋을 가지며, 이 서브셋은 그래프의 특성 함수에 {\} ~ {\}의 각 함수를 취한다.Baire 공간의 서브셋에는 분류 1 \_{ 1_ 또는 하는 Cantor 공간의 서브셋이 동일한 경우에만 분류가 부여됩니다.
- 2차 산술의 함수 버전을 사용하여 공식의 분석 계층을 정의함으로써 Baire 공간에서의 분석 계층의 동등한 정의가 주어집니다. 그러면 칸토어 공간의 하위 집합에서의 분석 계층은 Baire 공간에서의 계층으로부터 정의될 수 있습니다.이 대체 정의는 첫 번째 정의와 정확히 동일한 분류를 제공합니다.
병렬 정의는 여러 자유 변수를 가진 공식을 사용하여 Baire 공간 또는 Cantor 공간의 유한 데카르트 거듭제곱에 대한 산술적 위계를 정의하기 위해 사용됩니다.산술적 위계질서는 모든 유효 폴란드 공간에서 정의할 수 있습니다. 이 정의는 칸토어 공간과 베아르 공간에 대해 특히 단순합니다. 왜냐하면 그것들은 일반적인 2차 산술 언어와 일치하기 때문입니다.
또한 일부 정수 집합을 기준으로 칸토어와 베아르 공간의 부분 집합의 산술적 계층 구조를 정의할 수도 있습니다.사실 굵은 글씨 0 _{n은 모든 정수 Y에 0 \n}^Y}의 조합일 뿐입니다.굵은 글씨 계층은 보렐 집합의 표준 계층일 뿐입니다.
확장 및 변형
각 원시 재귀 함수에 대해 함수 기호를 사용하여 확장된 언어를 사용하여 공식의 산술적 계층을 정의할 수 있습니다.1차 Peano산술에서 원시 재귀 함수를 사용하기 때문에 1차 산술에서는 일반적으로 일부 무한정 수량 집합이 필요하기 때문에 이 변동은 0 = 0 = δ 0 = 0 0 0 0= δ 0 0 = 0 δ 0 = δ 0 0 this 0 = this 0 this 0 this 0 this 0 {\ 0 {\ 0 \ 0 pi 0 pi 0 pi 0 = {\ 0 {\ 0 {\ 0 0 pi 0 0 pi 0 0 _은(는) 이 문서의 첫머리에 있는 정의에 따라 0 _에 있습니다.1 }^{0})이므로 계층 내 상위 클래스는 모두 영향을 받지 않습니다.
계층 구조의 보다 의미적인 변화는 자연수의 모든 최종 관계에서 정의될 수 있다. 다음 정의가 사용된다.모든 계산 가능한 관계는 0 0= 0 0 { \_ { }^0= \ _ { }^ = \ _ {} 으로 정의됩니다.분류 0\ \_ { }^ 및 n \ \ _ { }^ 은 다음 규칙에 따라 유도적으로 정의됩니다.
- R ( n, , l , , , m) { R ( { , , _ { , { { k )is n the the 、 \ \ { } { 。,},\1}}은(는 + { \}^{0 로 정의되어 있습니다
- R ( , , , 1 , , k) { R ( {1} , \ , _ { , \ m { k} ) is is 00 n {\ 、 { \ _ { n }^ 、∃ s s s s 、 、 1 l ) 。 \1},\ldots은 (는+ (\ \}^0로 정의되어 있습니다.
이 변동에 따라 일부 세트의 분류가 약간 변경됩니다.특히 0 0 = 0 0= 0 0= \ { = \ _ { } = \ Delta _ { ( ( ( ( ( (\ _ 1 \ style _ 。자연수, 베아르 공간, 칸토어 공간의 정수 관계를 포함하도록 확장할 수 있습니다.
표기법의 의미
공식의 산술 계층 표기법에는 다음 의미를 부가할 수 있습니다.
기호 n \ \_ { }^ 및 n \ \_ { }^의 n { n 은 공식에서 사용되는 범용 및 기존 번호 양자의 블록 교대 횟수를 나타냅니다.또한 가장 바깥쪽 블록은 _ 공식으로 존재하며 _ 공식으로 보편적이다.
기호 0\ \_ { }^ 、 n0 \ \ _ { }^0 、 0 \ \ { n } the 0 0 0 0 0 0 0 0 0 00 0 0 0 0 00 、 、 、 ified 0 0 0 0 0 0 0 0 0 0 0 0 00 0 being being being being 0 0 00 0 0 0 0 0 being being being being being being being being 0 0 0 being being유형 0 객체는 자연수이고 는 의 집합을 자연수에 매핑하는 함수입니다.자연수에서 자연수까지의 함수와 같은 상위 유형 객체에 대한 정량화는 분석 계층에서와 같이 0보다 큰 윗첨자로 설명됩니다.supercript 0은 숫자 위의 수량자를 나타내고, supercript 1은 숫자에서 숫자(타입 1 개체)까지의 함수에 대한 수량화를 나타내며, supercript 2는 type 1 개체를 가져와서 숫자를 반환하는 함수에 대한 수량화에 대응합니다.
예
- \ \ _ { }^{ 0 n k ( , ,k , \( , \ 으로 정의할 수 있는 숫자입니다.이것들은 정확하게 재귀적으로 열거할 수 있는 집합입니다.
- 전체 함수를 계산하는 튜링 기계의 색인인 자연수 집합은 2 {{ _입니다. 직관적으로, 모든m {\ m에 대해 "s s가 있는 경우에만 이 집합에 들어갑니다.{\s 단계 m {\ m에서 멈춥니다.완전한 증거는 앞의 문장에서 따옴표로 표시된 속성이 1 \ \_ { 공식으로 Peano 산술 언어로 정의 가능하다는 것을 보여줍니다.
- Baire 공간 또는 Cantor 공간의 모든 0 \ 서브셋은 공간 상의 일반 토폴로지로 오픈세트입니다더욱이 그러한 집합의 경우, 결합이 원래 집합인 기본 오픈 집합의 Gödel 수에 대한 계산 가능한 열거가 있다.이 때문에 0 \}) 세트는 사실상 오픈이라고 불리기도 합니다.마찬가지로 모든 0 \ 세트는 0 \0} 세트는 사실상 닫힘으로 불리기도 합니다.
- 칸토어 공간 또는 베아르 공간의 모든 산술적 부분 집합은 보렐 집합이다.라이트페이스 보렐 계층은 추가 보렐 집합을 포함하도록 산술 계층을 확장합니다.예를 들어 Cantor 또는 Baire 공간의 모든 0 \0}) 서브셋은 })입니다.또한, 각 열린 집합은 1 _이며 , 열린 집합의 Gödel 수 목록은 계산 가능한 열거를 가진다.(, n, ) { X , , ) \ displaystyle \ _ { } { } with with 、 m、 { , m } with with with 0 0 0 with with with with with with with with if 、 0 、 { \ _ { 0 는 자연수 범위로 설정된의 형식의 0\ _}^{ 세트의 교집합입니다.
- 0 0 0 display 0 0 = 0 \ \ _ { }^0 = \ _ { 0 }^0= \ _ { }^ can can can can can can can can can can can can can can can can can can can can can can can0 can can0 、 0 can can can can0 can0 can can can can can can0 ifiers0 can0 can0 can이에 대한 시간은 인수에서 다항식이다(예를 들어 (의 경우 n의 다항식 따라서 대응하는 결정 문제는 E에 포함된다(n은 비트수에서 지수함수이기 때문에).이것은 더 이상 0 0 = 0= 0 0 = \ { }^0= \ _ { }^의 대체 정의에서는 유지되지 않습니다. 이제 수량자는 원시 재귀 함수에 의해 결합될 수 있습니다.
- 대체 정의에서 0 = δ 0 {_{}=\ _}=\ _ 공식은 { 형식의 정수 집합에 합니다.재귀 함수 f.때문에 껑충 뛰어 기호의 정의에 전혀 없고 형식:원시 recursive f,∀ k<>n:f(k)에)0{\displaystyle \forall k<, n:f(k)=0}은 f로(0)모두 동일 f(1)+... f(n))0{\displaystyle f(0)+f(1)+...f(n)=0}, ∃ k<>n:f(k))0{\displaystyle \exists, n:f(k)=0 k<}+. 똑같다( 0) ( )f( ) { (0)= ; 값 재귀와 함께 이들 각각을 단일 원시 재귀 함수로 정의할 수 있습니다.
특성.
다음 특성은 자연수 집합의 산술적 계층과 칸토르 또는 베아르 공간의 부분 집합의 산술적 계층에 적용된다.
- 컬렉션 0 \n}^ 및 0({ _은 각각의 요소의 유한한 결합과 유한한 교집합 하에 닫혀 있다.
- 보수가 n인 경우에만 n \ style \ _ { }^{ 0is a is is is is is is a 0 \ \ { n }^ 이 됩니다.또, 양쪽이 모두 0 경우에만 n 0 \ style _ { n }^{ n } { n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a ah case의 보완도 0 _이 됩니다.
- 0 + \\ _ { }^{ }\ \ _ { + 및 0+ { style \ { }^0}^{ n。따라서 계층은 축소되지 않습니다.이것은 Post의 정리의 직접적인 결과이다.
- 포함 00 0 0 \ \ _ { }^{ 0} \ \ _ { 0 , n 0、 0 \ \ { n }^0}^{ 0 }\ \_ Sigma _ { 0 }^{ 0}^{ 0} } 0 0} 0 。 n 1입니다.
- 예를 들어 유니버설 튜링 머신 T의 경우 T가 m이 아닌n으로 정지하는 페어(n,의 집합은 하는 문제에 대한 오라클로 계산할 수 있음이지만 0δ 1 0 1 0 0 1 \ 0 에는 없습니다
- 0= 0= 0= 0∪ 0 = 0 0 ∪ 1 1 0 { \ \ _ { 0 0 = \ _ { 0 0 = \ _ { 00 = \ _ 0 0 ^0 ^이 기사에 제시된 정의에 따르면 포함은 엄격하지만, \ _인 ID는 위에서 제시된 정의의 변형 중 하나에 속합니다.
튜링 기계와의 관계
계산 가능한 집합
만약 S가 튜링 계산 가능한 집합이라면, S와 그 보완은 모두 재귀적으로 열거할 수 있다. (만약 T가 S의 입력에 대해 1을 주고 그 외의 경우, 우리는 전자에 대해서만 정지하고 후자에 대해서만 정지하는 튜링 기계를 만들 수 있다.)
Post의 정리에 따르면, S와 그 보어는 모두 0 _에 있습니다.즉, S는 0(\ _})과 0(\ \}^0 모두이므로 0 _입니다.
마찬가지로 0\ \ _ { }^{}의 모든 집합 S에 대해 S와 그 보완은 \ _ {이므로 (Post의 정리에 따라) 일부 튜링 머신1 T와 T에서2 각각 재귀적으로 열거할 수 있다.모든 숫자 n에 대해 정확히 이 중 하나가 멈춥니다.따라서 우리는 T와2 T를1 번갈아 가면서 튜링 기계 T를 구성할 수 있으며, 전자가 멈출 때 1을 멈추고 반환하거나 후자가 멈출 때 0을 반환할 수 있다.따라서 T는 n마다 정지하고 S에 있는지 여부를 반환하므로 S는 계산할 수 있습니다.
주요 결과 요약
튜링 계산 가능한 자연수 집합은 정확히 산술적 계층의 레벨 1 _}^{에 있는 집합입니다.재귀적으로 열거할 수 있는 세트는 레벨 _에 있는 세트입니다.
어떤 오라클 머신도 자신의 정지 문제를 해결할 수 없다(튜링의 증명의 변형이 적용됨). 0 , \ \_ { 의 정지 문제 oracle은 실제로는 0(\ _에 있습니다.
포스트의 정리는 자연수 집합의 산술적 위계질서와 튜링도 사이의 밀접한 관계를 확립한다.특히, 모든 n : 1에 대해 다음과 같은 사실을 확립한다.
- 세트 ( ){ ^ { ( ) } (빈 세트의 n번째 튜링 점프)는 n ( \ \ _ { }^{ )로 다원 완성됩니다.
- N ( ( ) \ \{ \ \ ^ { ( ) } 0 the complete complete1 complete in in in in1 in the n \ \_ { }^{ 。
- The set is Turing complete in .
다항식 계층은 관련된 숫자에 다항식 길이 경계가 배치되는 산술적 계층의 "실현 가능한 자원 경계" 버전이다.이는 산술적 계층의 0 \}^{인 자연수 세트를 보다 세밀하게 분류합니다.
다른 계층과의 관계
라이트페이스 | 굵은 글씨 | ||
---|---|---|---|
σ0 00 0 = π0 0 = δ (때로는 δ과0 1 동일) | σ0 00 0 = π0 0 = δ (정의되어 있는 경우) | ||
δ = 재귀적0 1 | δ = clopen(닫힘0 1) | ||
δ = 재귀 열거 가능0 1 | δ = 공칭 열거형0 1 | δ = G = 열림0 1 | δ = F = 닫힘0 1 |
Δ0 2 | Δ0 2 | ||
Σ0 2 | Π0 2 | δ0 2σ = F | δ0 2δ = G |
Δ0 3 | Δ0 3 | ||
Σ0 3 | Π0 3 | δ0 3δσ = G | δ0 3σδ = F |
⋮ | ⋮ | ||
σ0 <ω0 <ω = π0 <ω = δ1 0 = σ1 0 = π = met1 0 = 산술 | σ0 <ω0 <ω = π0 <ω = δ1 0 = σ1 0 = π1 0 = face = 굵은 글씨 산술 | ||
⋮ | ⋮ | ||
δ0 α(α 재귀) | δ0 α (α 계수 가능) | ||
Σ0 α | Π0 α | Σ0 α | Π0 α |
⋮ | ⋮ | ||
σ0 ωCK 10 ωCK 1 = π0 ωCK 1 = δ1 1 = δ = 초산술 | σ0 ω10 ω1 = π0 ω1 = δ1 1 = δ = B = Borel | ||
δ = 라이트페이스 분석1 1 | δ1 1 = 라이트페이스 코분석 | δ1 1 = A = 분석 | δ = CA = 공동분석1 1 |
Δ1 2 | Δ1 2 | ||
Σ1 2 | Π1 2 | σ1 2 = PCA | π1 2 = CPA |
Δ1 3 | Δ1 3 | ||
Σ1 3 | Π1 3 | σ1 3 = PCPCA | δ1 3 = CPCPCA |
⋮ | ⋮ | ||
σ1 <ω1 <ω = π1 <ω = δ2 0 = σ2 0 = π = tical = 분석2 0 | σ1 <ω1 <ω = π1 <ω = δ2 0 = σ2 0 = π = δ2 0 = P = 투사형 | ||
⋮ | ⋮ |
「 」를 참조해 주세요.
레퍼런스
- 를 클릭합니다Japaridze, Giorgie (1994), "The logic of arithmetical hierarchy", Annals of Pure and Applied Logic, 66 (2): 89–112, doi:10.1016/0168-0072(94)90063-9, Zbl 0804.03045.
- 를 클릭합니다Moschovakis, Yiannis N. (1980), Descriptive Set Theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North Holland, ISBN 0-444-70199-0, Zbl 0433.03025.
- 를 클릭합니다Nies, André (2009), Computability and randomness, Oxford Logic Guides, vol. 51, Oxford: Oxford University Press, ISBN 978-0-19-923076-1, Zbl 1169.03034.
- 를 클릭합니다Rogers, H., jr (1967), Theory of recursive functions and effective computability, Maidenhead: McGraw-Hill, Zbl 0183.01401.