원시재귀산술

원시 재귀산술(PRA)은 자연수의 계량자 없는 공식화다.그것은 스콜렘이^[1] 산술의 기초에 대한 그의 미세한 개념을 공식화한 것으로서 처음 제안되었으며, PRA의 모든 추론은 미세한 것이라는 데 널리 동의하고 있다.많은 사람들은 또한 모든 친유대주의가 PRA에 의해 포착된다고 믿지만,^[2] 다른 사람들은 친유대주의가 원시적 재귀가 아닌, 페아노 산술의 증명-이론적 서수인 ^[3]ε까지₀ 재귀의 형태로 확장될 수 있다고 믿는다.PRA의 입증 이론적 서수는 Ω이고^ω, 여기서 Ω은 가장 작은 트랜스핀라이트 서수이다.PRA는 때때로 스콜렘 산술이라고 불린다.

PRA의 언어는 덧셈, 곱셈, 지수의 연산을 포함한 자연수와 원시 재귀 함수를 포함하는 산술 명제를 표현할 수 있다.PRA는 자연수 영역에 걸쳐 명시적으로 수량화할 수 없다.PRA는 종종 증명 이론, 특히 1차 산술에 대한 겐첸의 일관성 증명과 같은 일관성 증명에 대한 기본적인 변형 형식 체계로 받아들여진다.

언어와 공리

PRA의 언어는 다음과 같이 구성된다.

• 변수 x, y, z, ...의 무한 수.
• 제안 연결부;
• 동일 기호 =, 상수 기호 0 및 후속 기호 S(하나를 추가한다는 의미)
• 각 원시 재귀 함수의 기호.

PRA의 논리적 공리는 다음과 같다.

• 명제 미적분학의 토폴로지
• 평등을 동등성 관계로서의 일반적인 공리화.

PRA의 논리적인 규칙은 모드 폰과 가변적 대체다.
비논리적 공리는 다음과 같다.

• ${\displaystyle S}$( ${\displaystyle x}$) ${\displaystyle \ne }$ ${\displaystyle 0}$ ${\displaystyle S(x)\neq$ 0$}$;
• ${\displaystyle S(x)=S(y)~\to ~x=y,}$

그리고 원하는 대로 모든 원시 재귀 함수에 대한 재귀 정의 방정식.예를 들어 원시 재귀함수의 가장 일반적인 특성은 0 상수 및 계승함수가 투영, 구성, 원시 재귀에서 닫히는 것이다.따라서 n-place base 함수 g 및 (n+2)-place 반복 함수 h에 대한 원시 재귀에 의해 정의된 (n+1)-place 함수의 경우 다음과 같은 정의 방정식이 있을 것이다.

• ${\displaystyle f(0,y_{1},\ldots,y_{n}=g(y_{1},\ldots,y_{n})$
• ${\displaystyle f(x),y_{1},\ldots,y_{n}=h(x,y_{1},\ldots,y_{n}),y_{1},\ldots,y_{n}}}}$

특히:

• ${\displaystyle x+0=x\ }$
• $[\displaystyle x+S(y)=S(x+y)\ }$
• $0=0\displaystyle x\cdot 0=0\ }$
• $(\displaystyle x\cdot S(y)=x\cdot y+x\ }$
• ... 등등.

PRA는 1차 산술에 대한 유도의 공리 스키마를 (양자 없는) 유도의 규칙으로 대체한다.

• $\phi {\displaystyle }$( ${\displaystyle 0}$) ${\displaystyle \varphi (0)}$ 및$$ $\phi {\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$→ ${\displaystyle \phi }$( ) ${\displaystyle \varphi (x)\to \varphi (S(x)}$에서$$$\phi {\displaystyle }$ ($){\displaysty$ style$\varphi$$(y$$)})$를 모든 술어로 추론한다.$${\\\\\\\\\\\$displaysty$}.

1차 산술에서 명시적으로 공리화해야 하는 원시 재귀함수는 덧셈과 곱셈밖에 없다.다른 모든 원시 재귀 술어는 이 두 원시 재귀 함수와 모든 자연수에 대한 정량화를 사용하여 정의할 수 있다.이러한 방식으로 원시 재귀 함수를 정의하는 것은 PRA에서는 정량자가 부족하기 때문에 불가능하다.

무논리 미적분학

PRA의 문장은 단지 두 용어 사이의 방정식일 뿐이다.이 설정에서 용어는 0개 이상의 변수의 원시 재귀 함수다.1941년에 Haskell Curry는 처음으로 그러한 시스템을 주었다.^[4]커리의 체제에서의 유도의 규칙은 예사롭지 않았다.나중에 르우벤 굿스타인(Leuben Goodstein)이 다듬었다.^[5]굿스타인의 시스템에서 유도의 규칙은 다음과 같다.

${\displaystyle {F(0)=G(0)\quad F(x)=H(x)\quad G(x)=H(x)=G(x)}}$

여기서 x는 변수, S는 후계 연산, F, G, H는 표시된 파라미터 이외의 파라미터를 가질 수 있는 원시 재귀 함수다.굿슈타인 시스템의 다른 추론 규칙으로는 다음과 같은 대체 규칙밖에 없다.

${\displaystyle {F(x)=G(x) \over F(A)=G(A)}\qquad {A=F(B)}\qquad {A=B=C}}$

여기서 A, B, C는 모든 용어(변수가 0개 이상인 1차 재귀 함수)이다.마지막으로 위의 스콜렘 시스템에서와 같이 해당 정의 방정식을 가진 원시 재귀 함수에 대한 기호가 있다.

이런 식으로 명제 미적분은 완전히 폐기될 수 있다.논리 연산자는 전적으로 산술적으로 표현될 수 있다. 예를 들어, 두 숫자의 차이의 절대값은 원시적 재귀에 의해 정의될 수 있다.

${\displaystyle {\begin{aligned}P(0)=0\quad &\quad P(S(x))=x\\x{\dot {-}}0=x\quad &\quad x{\mathrel {\dot {-}}}S(y)=P(x{\mathrel {\dot {-}}}y)\\ x-y =&(x{\mathrel {\dot {-}}}y)+(y{\mathrel {\dot {-}}}x).\\end{aigned}}$

${\displaystyle \mathrm{따라서}}$ 방정식 x=y와 ${\displaystyle x}$- ${\displaystyle y}$= 0 ${\displaystyle x-y =0}$은(는) 동등하다.${\displaystyle \mathrm{따라서}}$ 방정식 ${\displaystyle x}$- y${\displaystyle }$+ ${\displaystyle u=}$ 0 ${\displaystyle x-y$ +$u-v =0}$과 ${\displaystyle x}$- ${\displaystyle y}$y ${\displaystyle u}$- v${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle x-y \cdot u-v =0}$은 방정식 x=y와 u=v의 논리적 결합과 분리를 각각$$ 표현한다.부정은 $1{\displaystyle \mathrm{}}$ -${\displaystyle \dot{}}$ ${\displaystyle x}$- ${\displaystyle \mathrm{y}}$= ${\displaystyle 0}$ ${\displaystyle 1{\dot{-}} x-y =0}$ 로 표현할 수 있다$.$

참고 항목

• 기초재귀산술
• 헤이팅 산술
• 페아노 산수
• 2차 산술
• 원시재귀함수
• 유한가치논리학

참조

추가 판독값

• Rose, H. E. (1961), "On the consistency and undecidability of recursive arithmetic", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 7: 124–135, MR 0140413.

• 페퍼만, S(1992) 무엇에 대해 휴식할 것인가? 수학의 증명-이론적 분석.초청 강연, 제15회 비트겐슈타인 심포지엄