지수화 및 곱셈을위한 기본 재귀 술어
나는 다음과 같이 비공식적으로 언급되고 약한 신념을 가지고 있는데, 그 중 일부는 더 깊이 생각해 보면 저에게 일관성이 없어 보입니다. 내 생각에 오류의 원인이 어디인지 궁금합니다. 기본 정의의 오류는 분명한 가능성입니다.
덧셈과 곱셈이있는 정수의 1 차 이론에서 수량 자 제거를 수행하는 것은 불가능합니다. (이것은 내가 말할 수있는 한 첫 번째 불완전 성 정리의 약간 더 강력한 버전입니다.)
덧셈과 곱셈이있는 정수의 1 차 이론에서는 지수화를위한 원시 재귀 술어를 정의 할 수 있습니다. (지수에 대한 술어에 의해, 나는 단지 "$Fabc\text{ just when }a^b = c.$")
이다 두 가지 작업으로 정수의 1 차 이론 정량 제거 할 수$a \oplus b = \min(a, b)$ 과 $a \otimes b = a + b$(즉, 정수의 일반적인 추가). 소수가 실제로 수량 자 제거를 수행하려면 나눗셈 술어와 곱셈 연산자도 필요하다는 것을 알고 있습니다.
연산과 정수의 1 차 이론에서 $\oplus$ 과 $\otimes$, 곱셈을위한 기본 재귀 술어를 정의하는 것이 가능합니다 (위의 지수화 술어와 거의 똑같은 방식으로).
대략적으로 말하면 "일반적인 작전 타워"사이의 비유에 문제가있는 것 같습니다. $(+, \times, \hat{\phantom{n}}, \cdots)$ 그리고 "열대 작전 타워" $(\min, +, \times, \cdots)$.
좀 더 구체적으로 말하면, (4)와 (3)이 사실이라면 왜 곱셈 술어를 자유롭게 사용할 수 없는지 그리고 (3)을 통해 수량 자 제거를 할 수 있고하지 않을 수도있는 상황을 이해하지 못합니다. 수량 자 제거 ((1)을 통해). (2)가 사실이지만 (4)가 아니라면 나를 매우 놀라게 할 것이고, (2)가 거짓이면 나를 더욱 놀라게 할 것입니다.
지수 술어가 의미하는 바를 이해하지 못하는 것 같습니다 (예 : $Fabc$ 부정확하거나, 그렇지 않으면 내가 알지 못하는 "곱하기 술어를 자유롭게 사용"에 관한 더 자세한 사항이 있습니다.
답변
귀하의 주장 $(1), (2)$, 및 $(3)$각각 정확합니다. 청구$(4)$그러나, 올바르지 않습니다 . 실제로 곱셈을 정의 할 수 있다면$(\mathbb{N};\max,+)$ 다음 이론 $Th(\mathbb{N};\max,+)$ 다음과 같이 복잡 할 것입니다. $Th(\mathbb{N};+,\times)$. 그러나 전자는 재귀 적이지만 후자는 산술적으로 정의 할 수도 없습니다.
문제는 더하기 측면에서 곱셈의 "명백한"정의 가 실제로 1 차가 아니라는 것입니다. 재귀 적 정의는 1 차 논리가 할 수있는 선험적 인 것이 아닙니다. 충분히 풍부한 구조에서 우리는 1 차 방식으로 재귀 적 정의를 수행하는 방법을 찾을 수 있습니다.$Th(\mathbb{N};+,\times)$이런 의미에서 Godel의 eorem을 가능하게하지만 추가만으로는이 작업을 수행 할 수있을만큼 강력하지 않습니다. 핵심은 우리가 덧셈과 곱셈을 모두 가지고 있다면 우리는 각각의 자연에 의해 유한 한 자연수 시퀀스를 "코딩"할 수 있다는 것입니다.$\beta$함수 )를 사용하여 "단계별 동작"을 코딩하는 시퀀스에 대해 이야기함으로써 재귀 적 구성에 대해 이야기하지만 더하기만으로는 개별 숫자 로 숫자 쌍을 코딩 할 수도 없습니다 .
마지막 문장에 대해 자세히 설명하고 주장으로 돌아 가기 $(2)$, 다음은 1 차 방식으로 덧셈과 곱셈을 사용하여 지수를 정의하는 방법에 대한 개요입니다.
우리는 $a^b=c$ 시퀀스로 해석 될 때 길이가있는 숫자가있는 경우 $b$, 첫 학기 $a$, 마지막 학기 $c$, 및 $i+1$다음과 같음 $a$ 배 $i$th 용어.
이것은 "재귀 적 프로세스"에 의한 정의가 아니라 "한 번에"정의하는 것임을 유의하십시오. 유한 시퀀스를 숫자로 코딩하는 세부 사항을 모듈로, 개별 숫자를 정량화하고 기본 속성을 확인하는 작업이 포함됩니다. 주문 로직이 할 수 있습니다. 유한 시퀀스를 1 차 방식으로 개별 숫자로 코딩 할 수없는 경우-$(\mathbb{N};\max,+)$ 부족-우리는 일반적인 비 1 차 정의에 갇히게 될 것입니다.
- 제쳐두고, 이것이 이론에서 "확인 가능한 정의"라는 것이 중요합니다. $\mathsf{Q}$, 전체 이론의 작은 조각 $Th(\mathbb{N};+,\times)$, 우리는 각각에 대해 $a,b,c$ 약어 문장 $$\underline{a}^{\underline{b}}=\underline{c}$$ (어디 $\underline{k}$ 자연수를 나타내는 숫자 $k$)에서 증명 가능 $\mathsf{Q}$ 만약 $a^b=c$ 그리고에서 증명할 수 없다 $\mathsf{Q}$ 만약 $a^b\not=c$. 이것은 대표성 이라고 불리며 고델의 증명의 핵심 아이디어 중 하나입니다. 사실, 모든 재귀 함수는 표현 가능 합니다.