산술 집합

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "산술 집합" – 뉴스 · 신문 · 책 · 학자 · JSTOR(2011년 8월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

수학 논리학에서 산술 집합(또는 산술 집합)은 1차적 페아노 산술의 공식으로 정의할 수 있는 자연수 집합이다. 산술 집합은 산술 계층 구조로 분류된다.

이 정의는 괴델 숫자를 사용하여 집합의 요소를 나타내고 해당 괴델 숫자 집합이 산술적인 경우 A의 하위 집합을 산술적으로 선언함으로써 임의의 카운트 가능한 집합 A(예: 정수의 n-tules 집합, 합리적인 숫자의 집합, 일부 공식 언어의 공식 집합 등)로 확장할 수 있다.

$f{\displaystyle }$ ${\$$displaystyle$ $f$$:\$subseteq $\mathb {N} ^{k}\to \mathb {N}$ 함수 f {\$displaystyf}$의 그래프가 산술 집합인$$ 경우 산술적으로 정의할 수 있다고$$ 한다.

모든 더 작은 합리적 숫자의 집합이 산술적이라면 실수는 산술적 숫자라고 불린다. 복합수는 실제와 가상의 부분이 모두 산술적이라면 산술적 수라고 불린다.

형식 정의

자연수의 X 집합은 φ(n)이 산술의 표준모형에 포함되는 경우에만 각 숫자 n이 X에 있도록 페아노 산술 언어에 공식 φ(n)이 있으면 산술적으로 또는 산술적으로 정의할 수 있다. Similarly, a k-ary relation ${\displaystyle R(n_{1},\ldots ,n_{k})}$ is arithmetical if there is a formula ${\displaystyle \psi (n_{1},\ldots ,n_{k})}$ such that ${\displaystyle R(n_{1},\ldots ,n_{k})\iff \psi (n_{1$$}},\ldots ,n_{k}}$은(는) 자연$$ 숫자의 모든 k-tupple$({\displaystyle {n\mathrm{}}_{}}$ 1${\displaystyle }$,${\displaystyle }$… , ${\displaystyle {}_{}{k}_{}}$ )$${\$displaystyle(n_{1},\ldots ,n_{k})$을 보유한다$$.

자연수에 대한 정밀함수는 그 그래프가 산술적 이항 관계인 경우 산술함수라고 불린다.

A 집합은 B를 집합 매개변수로 하는 산술 공식으로 정의할 수 있는 경우 B 집합으로 산술적이라고 한다.

예

• 모든 소수점들의 집합은 산술적이다.
• 모든 반복적으로 열거된 집합은 산술적이다.
• 모든 계산 가능한 함수는 산술적으로 정의할 수 있다.
• Halting 문제를 인코딩하는 세트는 산술적이다.
• 차이틴의 상수 Ω은 산술적 실수다.
• 타르스키의 불변성 정리는 1차 산술의 진정한 공식 집합이 산술적으로 정의할 수 없다는 것을 보여준다.

특성.

• 산술 집합의 보수는 산술 집합이다.
• 산술 집합의 튜링 점프는 산술 집합이다.
• 산술 집합의 집합은 셀 수 있지만 산술 집합의 순서는 산술적으로 정의할 수 없다. 따라서 m이 n번째 산술 술어의 멤버인 경우에만 참인 산술식 φ(n,m)은 없다.

실제로 그러한 공식은 모든 유한 튜링 점프의 결정 문제를 기술할 수 있으며, 따라서 1차 산술적 계층구조에 속하지 않기 때문에 1차 산술에서 공식화할 수 없는^(ω) 0에 속한다.

• 실제 산술적 숫자의 집합은 셀 수 있고, 밀도가 높으며 순서가 이형적인 숫자의 집합이다.

암묵적 산술 집합

각 산술 집합에는 특정 숫자가 집합에 있는지 여부를 나타내는 산술 공식이 있다. 정의가능성의 대안 개념은 특정 숫자가 집합에 있는지 아닌 집합 자체가 일부 산술적 특성을 만족하는지 여부를 나타내는 공식을 허용한다.

자연수의 Y 집합은 Y를 매개변수로 사용할 수 있는 산술 공식으로 정의할 수 있는 경우 암묵적으로 산술적으로 또는 암묵적으로 산술적으로 정의할 수 있다. 즉, 자유수 변수가 없는 페아노 산술 언어에 공식$$ $\theta {\displaystyle (Z}$ )$${\$displaystyle \theta(Z)$가 있고, 새로운 집합 매개변수 Z가 있는 경우 멤버쉽 관계$\$ {\$displaystyle$ \in$$$}$을 설정하여 $Y$가${\displaystyle }$z (${\displaystyle Z}$) {\$displaystystyle \ta(Z)})$와 같은 고유한 집합 Z가 유지된다.

모든 산술 집합은 암묵적으로 산술적이다. X가 arithmet(n)에 의해 산술적으로 정의되는 경우, 산술 집합은 공식에 의해 암묵적으로 정의된다.

${\displaystyle \mathrm{\forall }n}$[ ${\displaystyle n}$ ${\displaystyle \in }$ ${\displaystyle Z}$ ${\displaystyle \iff \varphi }$ ( n${\displaystyle }$) ${\displaystyle ]}$ ${\displaystyle \forall n[n\in Z\Leftrightarrow \phi (n$

그러나 암묵적으로 모든 산술 집합이 산술적인 것은 아니다. 특히 1차 산술의 진실 집합은 암묵적으로 산술적이지만 산술적인 것은 아니다.

참고 항목

• 산술 계층 구조
• 계산 가능한 집합
• 계산 가능한 수

추가 읽기

• 로저스, H. (1967) 재귀함수와 유효 계산가능성의 이론. 맥그로힐 OCLC527706