페아노 공리계

3. 공리

페아노 공리계는 자연수 집합 '''N'''과 상수 0, 함수 S (후자 함수)에 대한 공리들로 구성된다. 페아노는 불과 슈뢰더의 작업에 기초해 자신의 논리적 도구를 만들었다.^[17]

페아노의 공리들은 '자연수 집합' '''N'''이 만족해야 할 성질들을 규정한다. 상수 0이 자연수이고, 자연수 집합이 "따름수" 함수 S에 대해 닫혀 있다고 정한다.

# 0은 자연수이다.

# 임의의 자연수 n에 대해, S(n)은 자연수이다.

페아노는 원래 형식에서 첫 자연수로 0이 아닌 1을 선택했다. 그러나 0이 덧셈에 대한 항등원이라는 점 때문에 현대에는 0에서 시작한다. 공리들을 통해 자연수를 1진법으로 규정한다. 즉, 1은 S(0)이며, 2는 S(S(0)) = S(1)이고, 비슷하게 임의의 자연수 n은 Sⁿ(0)이다.

# 임의의 자연수 n에 대해, S(n) ≠ 0. 즉, 따름수가 0인 자연수는 존재하지 않는다.

# 임의의 자연수 m과 n에 대해, S(m) = S(n)이면 m = n. 즉, S는 단사 함수이다.

이 두 공리는 자연수가 무한히 많음을 보장한다.

3. 1. 동일 관계 공리 (1차 논리)

• 임의의 자연수 x에 대해, x = x. (동일성은 반사관계)
• 임의의 자연수 x와 y에 대해, x = y이면 y = x. (동일성은 대칭관계)
• 임의의 자연수 x, y, z에 대해, x = y이고 y = z이면 x = z. (동일성은 추이관계)
• 임의의 a와 b에 대해, a가 자연수이고 a = b이면 b도 자연수. (자연수 집합은 동일성에 대해 닫혀 있음)

3. 2. 자연수 공리 (2차 논리)

3. 3. 1차 논리에서의 페아노 공리계

• $\backslash forall\; x\; \backslash \; (0\; \backslash neq\; S\; (\; x\; ))$
• $\backslash forall\; x,\; y\; \backslash \; (S(\; x\; )\; =\; S(\; y\; )\; \backslash Rightarrow\; x\; =\; y)$
• $\backslash forall\; x\; \backslash \; (x\; +\; 0\; =\; x\; )$
• $\backslash forall\; x,\; y\; \backslash \; (x\; +\; S(\; y\; )\; =\; S(\; x\; +\; y\; ))$
• $\backslash forall\; x\; \backslash \; (x\; \backslash cdot\; 0\; =\; 0)$
• $\backslash forall\; x,\; y\; \backslash \; (x\; \backslash cdot\; S\; (\; y\; )\; =\; x\; \backslash cdot\; y\; +\; x\; )$

4. 산술 연산 및 관계

페아노 공리계를 통해 자연수 집합에 덧셈, 곱셈, 전순서를 정의할 수 있다. 각 연산과 관계는 2차 논리에서 구성되며, 공리를 통해 유일성을 증명할 수 있다.^[6]

덧셈과 곱셈은 다음과 같이 재귀적으로 정의된다.

• 덧셈:

• 곱셈:

4. 1. 덧셈

4. 2. 곱셈

• `a · 1 = a · (S(0)) = a + (a · 0) = a + 0 = a`이므로, 1은 곱셈의 항등원이다.
• 곱셈은 교환 법칙과 결합 법칙을 만족하며, 덧셈에 대한 분배 법칙도 성립한다: `a · (b + c) = (a · b) + (a · c)`.

4. 3. 순서 관계

5. 모형

페아노 공리계를 만족시키는 논리학적 구조, 즉 모형은 $(\backslash mathbf\{N\},\; 0,\; S)$이다. 여기서 N은 무한집합이고, 0 ∈ N이며, S: N → N이다.

데데킨트는 페아노 공리계의 임의의 두 모형이 동형임을 증명하여, 2차 논리에서 페아노 공리계는 범주적임을 보였다. 그러나 1차 논리에서는 뢰벤하임-스콜렘 정리에 따라 비표준 모형이 존재한다.

5. 1. 범주성 (2차 논리)

5. 2. 비표준 모형 (1차 논리)

5. 3. 집합론적 모형

• $0\; =\; \backslash emptyset\; =\; \backslash \{\backslash \}$
• $1\; :=\; S(0)\; =\; \backslash \{0\backslash \}\; =\; \backslash \{\backslash \{\backslash \}\backslash \}$
• $2\; :=\; S(1)\; =\; \backslash \{0,\; 1\backslash \}\; =\; \backslash \{\backslash \{\backslash \},\; \backslash \{\backslash \{\backslash \}\backslash \}\backslash \}$
• $3\; :=\; S(2)\; =\; \backslash \{0,\; 1,\; 2\backslash \}\; =\; \backslash \{\backslash \{\backslash \},\; \backslash \{\backslash \{\backslash \}\backslash \},\; \backslash \{\backslash \{\backslash \},\; \backslash \{\backslash \{\backslash \}\backslash \}\backslash \}\backslash \}$

6. 무모순성

페아노 공리계가 처음 발표되었을 때 버트런드 러셀을 비롯한 많은 논리학자들은 이것이 직관적으로 생각하는 자연수의 정의와 부합한다고 동의했다. 그러나 앙리 푸앵카레 등 직관주의자들은 이 체계가 일관적(무모순적)이지 않으면 "0 = 1"과 같은 모순적인 문장을 낳게 되므로 무의미하게 된다고 지적하였다.^[9] 1900년 다비트 힐베르트는 힐베르트 문제 중 2번째 문제로 "유한적인 방법만 사용하여 산술 체계의 일관성을 증명하라"는 내용을 제시했다. 그러나 1931년 쿠르트 괴델의 제2 불완전성 정리에 의해 페아노 산술의 무모순성이 페아노 산술 내부에서 증명될 수 없음이 밝혀져 큰 난관에 부딪혔다.

1936년 게르하르트 겐첸은 원시 재귀 산술(primitive recursive arithmetic|프리미티브 리커시브 애리스메틱^영어)에 양화사가 없는 초한귀납법을 순서수 $\backslash varepsilon\_0$까지 확장하는 법칙을 추가하여 페아노 공리계의 일관성을 증명했다.^[11] 여기서 원시 재귀 산술은 자연수와 원시 재귀 함수(덧셈, 곱셈, 제곱 등)로 이루어진 진술들을 서술할 수 있는 언어 체계이며, 순서수 $\backslash varepsilon\_0$는 $\backslash varepsilon\; =\; \backslash omega^\backslash varepsilon$이 되는 최소의 순서수로, 그보다 작은 극한 순서수를 모두 모은 수열의 극한으로 볼 수 있다. (즉, $\backslash varepsilon\_0\; =\; \backslash omega^\{\backslash omega^\{\backslash omega^\{\backslash cdot^\{\backslash cdot^\backslash cdot\}\}\}\}\; =\; \backslash sup\; \backslash \{\; \backslash omega,\; \backslash omega^\{\backslash omega\},\; \backslash omega^\{\backslash omega^\{\backslash omega\}\},\; \backslash omega^\{\backslash omega^\{\backslash omega^\backslash omega\}\},\; \backslash dots\; \backslash \}$ 가 성립한다.)

7. 페아노 산술 (PA)

Peano arithmetic^영어 또는 PA로 불리는 페아노 산술은 등호가 있는 일차 술어 논리에 페아노 공리를 추가한 형식 체계이다. 이 체계는 비논리적 기호로 상수 기호 0, 함수 기호 S, +, ⋅, 술어 기호 < 를 가진다.

페아노 산술은 다음 공리들을 포함한다.

# $\backslash forall\; n\; \backslash lnot[S(n)\; =\; 0]$

# $\backslash forall\; n\; \backslash forall\; m\; [S(n)\; =\; S(m)\; \backslash to\; n\; =\; m]$

# $\backslash forall\; n\; [n\; +\; 0\; =\; n]$

# $\backslash forall\; n\; \backslash forall\; m[n\; +\; S(m)\; =\; S(n\; +\; m)]$

# $\backslash forall\; n\; [n\; \backslash cdot\; 0\; =\; 0]$

# $\backslash forall\; n\; \backslash forall\; m\; [n\; \backslash cdot\; S(m)\; =\; n\; \backslash cdot\; m\; +\; n]$

#

#

# $[\backslash varphi(0)\; \backslash land\; \backslash forall\; n\; [\backslash varphi(n)\; \backslash to\; \backslash varphi(S(n))]]\; \backslash to\; \backslash forall\; n\; [\backslash varphi(n)]$

자연수의 표준 모델 ℕ에서 참인 닫힌 논리식은 페아노 산술로부터 증명할 수 있다(PA의 완전성).

괴델의 제1 불완전성 정리에 의해 페아노 산술은 불완전하며, 결정 불가능하다. 즉, 페아노 산술로부터 증명도 반증도 할 수 없는 명제가 존재한다. 유명한 예로는 굿스타인의 정리와 파리스-해링턴 정리가 있다.

참조

_[1] 사전 Peano http://www.dictionar[...] Random House Webster's Unabridged Dictionary
_[2] 문서 the nearest light piece corresponding to 0, and a neighbor piece corresponding to successor
_[3] 문서 Mathematical Induction https://www.sfu.ca/~[...] Simon Fraser University
_[4] 웹사이트 Mathematical Induction http://www.math.harv[...] Harvard University 2013-05-02
_[5] 문서 The non-contiguous set satisfies axiom 1 as it has a 0 element, 2–5 as it doesn't affect equality relations, 6 & 8 as all pieces have a successor, bar the zero element and axiom 7 as no two dominos topple, or are toppled by, the same piece.
_[6] 파일 Inductive proofs of properties of add, mult from recursive definitions.pdf
_[7] 인용
_[8] 서적 An illustration of 'interpretation' is Russell's own definition of 'cardinal number'. The uninterpreted system in this case is Peano's axioms for the number system, whose three primitive ideas and five axioms, Peano believed, were sufficient to enable one to derive all the properties of the system of natural numbers. Actually, Russell maintains, Peano's axioms define any progression of the form $x\_0,x\_1,x\_2,\backslash ldots,x\_n,\backslash ldots$ of which the series of the natural numbers is one instance. https://books.google[...]
_[9] 서적 So Poincaré turned to see whether logicism could generate arithmetic, more precisely, the arithmetic of ordinals. Couturat, said Poincaré, had accepted the Peano axioms as a definition of a number. But this will not do. The axioms cannot be shown to be free of contradiction by finding examples of them, and any attempt to show that they were contradiction-free by examining the totality of their implications would require the very principle of mathematical induction Couturat believed they implied. For (in a further passage dropped from S&M) either one assumed the principle in order to prove it, which would only prove that if it is true it is not self-contradictory, which says nothing; or one used the principle in another form than the one stated, in which case one must show that the number of steps in one's reasoning was an integer according to the new definition, but this could not be done (1905c, 834). https://archive.org/[...]
_[10] 인용
_[11] 인용
_[12] 서적 現代代数学概論 https://dl.ndl.go.jp[...] 白水社
_[13] 인용
_[14] 인용
_[15] 인용
_[16] 인용
_[17] 인용
_[18] 문서 여기의 공리 5는 페아노의 원래 논문에서는 1번이었으며, 여기의 공리 1에서 4까지는 원래 순서대로 2번에서 5번까지의 번호가 매겨졌다.
_[19] 인용
_[20] 인용
_[21] 인용