로빈슨 산술

Robinson arithmetic

수학에서 로빈슨 산수는 1950년 R. M. 로빈슨에 의해 처음 시작된 1차 페이노 산술(PA)의 정밀 공리화된 단편이다.[1] 그것은 보통 Q로 표시된다. Q는 수학적 유도의 공리 스키마가 없는 거의 PA이다. Q는 PA보다 약하지만 언어가 같고, 두 이론 모두 불완전하다. Q는 반복적으로 완벽하지 않고 본질적으로 이해할 수 없는 PA의 정밀하게 공리화된 파편이기 때문에 중요하고 흥미롭다.

공리

Q의 배경논리는 아이덴티티를 가진 1차 논리로서 infix '='로 표시된다. 자연수라고 불리는 개인은 N이라는 세트의 멤버로, 0이라는 뛰어난 멤버를 가지고 있다. N에 대한 세 가지 작업이 있다.

Q에 대한 다음 공리는 Burgess(2005, 페이지 42)의 Q1–Q7이다. (cf. 또한 1차 산술의 공리). 실존적 계량기에 의해 구속되지 않는 변수는 암묵적 보편적 계량기에 의해 구속된다.

  1. Sx ≠ 0
    • 0은 어떤 숫자의 후계자가 아니다.
  2. (Sx = Sy) → x = y
    • x의 후계자가 y의 후계자와 동일하다면, x와 y는 동일하다. (1)과 (2) 비경쟁성에 필요한 N (0으로 경계가 되는 무한 집합)과 S (영역이 N인 주입 함수)에 대한 사실의 최소치를 산출한다. (2)의 역은 정체성의 속성에서 따온 것이다.
  3. y=0 ∨ ∃x(Sx = y)
    • 모든 숫자는 0이거나 어떤 숫자의 후속이다. Q보다 강한 산술에 존재하는 수학적 유도의 공리 스키마는 이 공리를 하나의 정리로 바꾼다.
  4. x + 0 = x
  5. x + Sy = S(x + y)
  6. x·0 = 0
  7. x·Sy = (x·y) + x

변형 공리화

로빈슨(1950)의 공리는 멘델슨 (2015, 페이지 202–203)의 (1)–(13)이다. 로빈슨의 13개 공리 중 처음 6개는 여기서와 달리 배경 논리에 정체성이 포함되어 있지 않을 때만 필요하다.

N에 대한 통상적인 엄격한 총 주문, "보다 작음"("<"으로 표기)은 규칙 x < y £z(Sz + x = y)를 통해 추가의 관점에서 정의할 수 있다. 마찬가지로, 우리는 "<"를 원시적인 것으로 받아들이고 이 규칙을 8번째 공리로 추가함으로써 Q의 정의상 보수적인 확장을 얻는다; 이 시스템은 Boolos, Burgess & Jeffrey (2002년, 16.4절)에서 "Robinson 산술 R"이라고 불린다.

우리가 일시적으로 Q+라고 부르는 Q의 다른 연장은 우리가 "<"를 원시적인 것으로 받아들이고 (마지막 정의 공리 대신에) Q의 공리 (1)~(7)에 다음과 같은 세 가지 공리를 추가하면 얻어진다.

  • ¬(x < 0)
  • x < Sy £ (x < y ∨ x = y)
  • x < y ∨ x = y ∨ y < > x

Q+는 기호 "<"를 포함하지 않고 Q+에서 증명할 수 있는 어떤 공식도 Q에서 이미 증명할 수 있다는 점에서 여전히 Q의 보수적인 연장이다. (위의 세 가지 공리 중 처음 두 개만 Q에 추가하면 버지스(2005년, 페이지 56년)가 Q*라고 부르는 것과 동등한 Q의 보수적인 연장이 된다. Burgess(2005, 페이지 230, fn. 24)도 참조하지만, 위의 세 가지 공리 중 두 번째 공리는 공리 x < y zz (Sz + x = y)만을 추가하여 얻은 Q의 "순수 정의 확장"에서 추론할 수 없다는 점에 유의한다.

Q의 공리(1)~(7) 가운데 공리(3)는 내적 실존적 정량자가 필요하다. 쇼엔필드(1967, 페이지 22)는 Q의 공리 (3)로 분사하되 < 원시적>으로 위의 세 공리를 추가함으로써 외부 범용 정량자만을 (불분명하게) 갖는 공리화를 제공한다. 즉, Shoenfield의 시스템은 Q+ 마이너스 공리(3)이며, 공리 (3)은 다른 공리와 독립적이기 때문에 Q+보다 약하다예: Ωomega }}). Sv가 v + 1로 해석될 때 (3)을 제외한 모든 공리의 모델을 형성한다. 쇼엔필드의 시스템은 볼로스, 버지스 & 제프리(2002년, 16.2절)에서도 나타나는데, 여기서 '최소 산술'(Q로도 표기)이라고 한다. "<" 대신에 "≤"를 사용하는 밀접하게 관련된 공리화는 마하버(1996, 페이지 256–257)에서 찾을 수 있다.

변성학

Q의 변성법에 대해서는 Boolos, Burgess & Jeffrey(2002, 16장), Tarski, Mostowski & Robinson(1953년), Smullyan(1991년), Mendelson(2015년, 페이지 202–203년), Burgess(2005년, 제1.5a, 2.2조)를 참조한다. Q의 의도된 해석은 자연수와 그 통상적인 산술로서 덧셈과 곱셈이 관습적인 의미를 가지며, 정체성은 평등이고, Sx = x + 1이며, 0은 자연수 0이다.

가능한 공리를 제외한 Q의 모든 공리를 만족시키는 모델(구조)은 표준 자연수(N, +, ·, S, 0)에 대해 고유한 하위 모델("표준 부분")을 가지고 있다.(Axiom (3)은 충족시킬 필요가 없다. 예를 들어 음수가 아닌 정수 계수를 가진 다항식이 (3)을 제외한 모든 공리를 만족시키는 모델을 형성한다.

Q는 페아노 산술과 마찬가지로 모든 무한 추기경의 비표준 모델을 가지고 있다. 그러나 페아노 산술과는 달리 테넨바움의 정리는 Q에는 적용되지 않으며, 연산 가능한 비표준 모델을 가지고 있다. 예를 들어, 양의 선행 계수를 갖는 정수 효율 다항식, 그리고 통상적인 산술과 함께 0 다항식으로 구성된 Q의 계산 가능한 모델이 있다.

Q의 눈에 띄는 특징은 유도의 공리체계가 없다는 것이다. 따라서 자연수에 관한 사실의 모든 구체적인 예를 Q에서 증명하는 것이 가능하지만 관련 일반 정리는 불가능하다. 예를 들어, 5 + 7 = 7 + 5는 Q에서 증명할 수 있지만, 일반 문장은 x + y = y + x가 아니다. 마찬가지로, Sx[2]인데 ≠을 증명할 수 없다는 Q의 표준 사실의 많은 자연수의 표준 모델과 = 사 명확히 x모든 x+a=b와 x+b)x에 대한,+nx고 b+nxb만약 n은 표준 자연수, x·0=0a·n=b와 두개의 뚜렷한 새로운 원소 a와 b를, Sb)b을 접한 실패한 모델이다. b·n = a if n이 0이 아닌 표준 자연수인 경우 x·a = a를 제외한 모든 x에 대해 x = a, x·b = b를 제외한 모든 x에 대해 x·a = b, a·b = a.[3]

Q는 제르멜로의 자칭 집합 이론의 단편에서 해석할 수 있는데, 확장성, 빈 집합의 존재, 부속의 공리로 구성되어 있다. 이 이론은 타르스키, 모스토프스키 & 로빈슨(1953, 페이지 34), 버지스의 ST(2005, 페이지 90–91, 223)에서 S'이다. 자세한 내용은 일반 집합 이론을 참조하십시오.

Q는 페아노 산술(PA)보다 상당히 약한 정밀하게 공리화된 1차 이론으로, 공리에는 실존 정량자가 하나만 들어 있다. 그러나 PA와 마찬가지로 괴델의 불완전성 이론의 의미에서 불완전하고 불완전하며, 본질적으로 이해할 수 없는 것이다. 로빈슨(1950)은 모든 계산 가능한 함수가 PA에서 대표할 수 있다는 것을 증명하기 위해 PA 공리가 필요한 것에 주목함으로써 위의 Q 공리 (1)–(7)를 도출했다.[5]

이 증명서가 PA 공리 유도 스키마를 사용하는 유일한 방법은 위의 공리 (3)을 증명하는 것이므로 계산 가능한 모든 함수는 Q로 나타낼 수 있다. [6][7][8] 괴델의 두 번째 불완전성 정리의 결론도 Q를 유지한다: 우리가 괴델의 증거 수를 정의 가능한 컷으로 추가적으로 제한하더라도 Q의 일관된 재귀화된 확장은 그 자체의 일관성을 증명할 수 없다.[9][10][11]

첫 번째 불완전성 정리는 필요한 코딩 구성(Gödel 번호 매기기)을 수행하기에 충분한 산술을 정의하는 자명 시스템에만 적용된다. Q의 공리는 이러한 목적을 위해 충분히 강하다는 것을 보장하기 위해 특별히 선택되었다. 따라서 첫 번째 불완전성 정리에 대한 통상적인 증거를 사용하여 Q가 불완전하고 해독할 수 없다는 것을 보여줄 수 있다. PA가 Q와 차별화하는 단면, 즉 유도의 공리 스키마 때문에 PA의 불완전성과 불분명한 것을 탓할 수 없다는 의미다.

괴델의 이론은 위의 일곱 가지 공리 중 어느 하나라도 떨어졌을 때 성립되지 않는다. Q의 이러한 단편들은 여전히 불해독으로 남아 있지만, 더 이상 본질적으로 불해독할 수 없는 것은 아니다: 그들은 일관성 있는 해독 가능한 확장뿐만 아니라 흥미 없는 모델(즉, 표준 자연수의 최종 확장이 아닌 모델)을 가지고 있다.

참고 항목

참조

  1. ^ 로빈슨 1950.
  2. ^ 버지스 2005 페이지 56.
  3. ^ Boolos, Burgess & Jeffrey 2002, 16.4항.
  4. ^ 멘델슨 2015, 페이지 188, 발의안 3.24.
  5. ^ 함수 은(는) 1,, x , , 와 같은 공식 에서 나타낼 수 있다고 한다.
  6. ^ 1989년 오디프레디
  7. ^ 멘델슨 2015, 203 페이지 발의안 3.33.
  8. ^ Rautenberg 2010, 페이지 246.
  9. ^ 베즈보루아 & 셰퍼드슨 1976.
  10. ^ 푸들라크 1985년
  11. ^ 하예크 & 푸들라크 1993, 387페이지.

참고 문헌 목록

  • Bezboruah, A.; Shepherdson, John C. (June 1976). "Gödel's Second Incompleteness Theorem for Q". Journal of Symbolic Logic. 41 (2): 503–512. doi:10.2307/2272251.
  • Boolos, George; Burgess, John P.; Jeffrey, Richard (2002). Computability and Logic (4th ed.). Cambridge University Press. ISBN 0-521-00758-5.
  • Burgess, John P. (July 2005). Fixing Frege. Princeton University Press. ISBN 978-0691122311.
  • Hájek, Petr; Pudlák, Pavel (1993). Metamathematics of first-order arithmetic (2nd ed.). Springer-Verlag.
  • Jones, James P.; Shepherdson, John C. (1983). "Variants of Robinson's essentially undecidable theoryR". Archiv für mathematische Logik und Grundlagenforschung. 23: 61–64. doi:10.1007/BF02023013.
  • Lucas, John R. Conceptual Roots of Mathematics. Routledge.
  • Machover, Moshé (1996). Set Theory, Logic, and Their Limitation. Cambridge University Press.
  • Mendelson, Elliott (2015). Introduction to Mathematical Logic (6th ed.). Chapman & Hall. ISBN 9781482237726.
  • Odifreddi, Piergiorgio (1989). Classical recursion theory, Vol. 1 (The Theory of Functions and Sets of Natural Numbers). Studies in logic and the foundations of mathematics. Vol. 125. North-Holland. ISBN 9780444894830.
  • Pudlák, Pavel (June 1985). "Cuts, consistency statements and interpretations". Journal of Symbolic Logic. 50 (2): 423–441. doi:10.2307/2274231.
  • Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic (3rd ed.). New York: Springer Science+Business Media. doi:10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6..
  • Robinson, R. M. (1950). "An Essentially Undecidable Axiom System". Proceedings of the International Congress of Mathematics: 729–730.
  • Shoenfield, Joseph R. (1967). Mathematical logic. Addison Wesley. (Reprinted by Association for Symbolic Logic and A K Peters in 2000).
  • Smullyan, Raymond (1991). Gödel's Incompleteness Theorems. Oxford University Press.
  • Tarski, Alfred; Mostowski, A.; Robinson, R. M. (1953). Undecidable theories. North Holland.
  • Vaught, Robert L. (1966). "On a Theorem of Cobham Concerning Undecidable Theories". Studies in Logic and the Foundations of Mathematics. 44: 14–25. doi:10.1016/S0049-237X(09)70566-X.