기본 함수 산술

Elementary function arithmetic
"초등 재귀 산술"은 여기서 리디렉션된다.계산 복잡도 클래스는 ENTERIC을 참조하십시오.

증명 이론에서 기초 산술과 지수 함수 산술이라고도 하는 수학적 논리학의 한 가지, 기초 함수 산술(EFA)은 경계 정량자를 가진 공식에 대한 유도와 함께 통상적인 기초 성질이 0, 1, +, ×, x인y 산술의 계통이다.

EFA는 증명 이론 서수가 Ω인3 매우 약한 논리 체계지만, 여전히 1차 산술의 언어로 진술할 수 있는 보통의 수학의 상당 부분을 증명할 수 있는 것으로 보인다.

정의

EFA는 (평등을 가진) 첫 번째 순서 논리학의 시스템이다.이 언어에는 다음이 포함된다.

  • 두 상수 0, 1,
  • 3개의 이진 연산 +, ×, exp, exp(x,y)는 보통 x로y 기록된다.
  • 이항 관계 기호 < (이항은 다른 연산의 관점에서 쓰여질 수 있고 때로는 생략되기도 하지만 경계 정량자를 정의하는데 편리하기 때문에 실제로 필요한 것은 아니다.)

경계 정량자는 ∀(x < y)와 ∃(x < y) → ...x (x < y) → ∃x (x < y)∧...의 약어인 ((x < y)형이다.상례로

EFA의 공리는 다음과 같다.

  • 0, 1, +, ×, < 로빈슨 산수의 공리
  • 지수에 대한 공리: x0 = 1, xy+1 = xy x x
  • 계량자가 경계로 되어 있는 모든 공식(자유 변수를 포함할 수 있음)에 대한 유도.

프리드먼의 거창한 추측

하비 프리드먼의 대견한 추측은 페르마의 마지막 정리 같은 많은 수학 이론들이 EFA와 같은 매우 약한 시스템에서 증명될 수 있다는 것을 암시한다.

프리드먼(1999년)의 추측에 대한 원문은 다음과 같다.

"수학연보에 발표된 모든 정리는 EFA에서 증명될 수 있다. 그 진술은 오직 미세한 수학적 목적(즉, 논리학자들이 산술적 진술이라고 부르는 것)만을 포함한다.EFA는 0, 1, +, ×, exp에 대한 통상적인 계량자 없는 공리에 근거한 페아노 산술의 약한 파편이며, 모든 계량자가 경계를 이루고 있는 언어의 모든 공식에 대한 유도 체계와 함께 말이다."

EFA에서는 사실이지만 증명할 수 없는 인공 산술 문장을 만드는 것은 쉽지만, Friedman의 추측의 요점은 수학에서 그러한 문장의 자연적인 예가 드문 것처럼 보인다는 것이다.자연적인 예로는 논리로부터 나온 일관성문, 스제메레디 규칙성 보조정리, 그래프 마이너 정리 등 램지 이론과 관련된 여러 진술 등이 있다.

관련 시스템

관련된 몇 가지 계산 복잡성 클래스는 EFA와 유사한 속성을 가지고 있다.

  • 로빈슨 산술과 함께 한정된 정량자를 가진 모든 공식에 대한 유도와 함수가 모든 곳에서 정의되는 함수임을 대략적으로 나타내는 공리를 취함으로써 언어에서 2진 함수 기호 exp를 생략할 수 있다.이는 EFA와 비슷하고 입증 이론적 강도는 동일하지만 작업하기가 더 번거롭다.
  • 2차0
    2     산술 RCA*
    0    , WKL이라는*
    0     약한 파편이 EFA와 일치강도가 같고 Ⅱ 문장에[further explanation needed] 대해서는 보수적인데, 역수학(심슨 2009)으로 연구되기도 한다.
  • 기초재귀산술(ERA)은 재귀가 경계가 있는 총액과 상품으로 제한되는 원시재귀산술(PRA)의 서브시스템이다.또한 EFA가 P 계량자가 없는 ∀x whenevery P(x,y)를 증명할 때마다 평균자책은 개방형 공식 P(x,T(x)를 증명한다는 점에서 EFA와 동일한 π0
    2     문장이 있다.    평균자책은 PRA와 마찬가지로 대체와 유도의 규칙만으로 완전히 논리가[clarification needed] 없는 방식으로 정의될 수 있으며, 모든 기본적인 재귀 함수에 대한 방정식을 정의할 수 있다.그러나 PRA와는 달리, 기초 재귀 함수는 유한한 수의 기본 함수의 구성과 투영에 따라 폐쇄되는 특성을 가질 수 있으므로, 한정된 수의 정의 방정식만 있으면 된다.

참고 항목

참조

  • Avigad, Jeremy (2003), "Number theory and elementary arithmetic", Philosophia Mathematica, Series III, 11 (3): 257–284, doi:10.1093/philmat/11.3.257, ISSN 0031-8019, MR 2006194
  • Friedman, Harvey (1999), grand conjectures
  • Simpson, Stephen G. (2009), Subsystems of second order arithmetic, Perspectives in Logic (2nd ed.), Cambridge University Press, ISBN 978-0-521-88439-6, MR 1723993