페아노 공리계

페아노 공리계(Peano公理系, 영어: Peano’s axioms) 또는 데데킨트-페아노 공리계는 수리논리학에서 자연수 체계를 묘사하는 공리들이다. 19세기 이탈리아 수학자인 주세페 페아노에 의하여 제안되었다. 수론의 일관성 및 완전성 연구에도 사용된다.

페아노의 공리들은 세 종류로 나눌 수 있다. 처음의 네 공리는 동일성에 대한 일반적인 명제로, 현대에는 보통 순수 논리의 공리로 취급된다. 다음의 네 공리는 따름수 연산의 근본적인 성질들을 자연수에 대한 1차 논리적 명제로 표현한 것이다. 마지막 9번째 공리는 수학적 귀납법을 표현한 2차 논리의 명제이다. 이 마지막 공리를 1차 논리의 공리꼴로 대체한 체계를 페아노 산술이라고 하는데, 이는 페아노가 원래 제안한 것보다 약한 체계이다.

공리

페아노가 그의 공리들을 만들 당시 수리논리학의 언어는 요람기에 있었다. 그가 공리들을 표현하기 위해 사용한 논리 표기법은 그다지 널리 퍼지지 않았으며, 단지 집합 포함기호(페아노가 사용한 ε에서 ∈가 나왔다)와 논리적 함의 기호(페아노가 C를 거꾸로 쓴 것에서 ⊃가 나왔다) 등이 현재까지 사용되고 있다. 페아노는 수학 기호와 논리 기호를 엄격히 구분했는데, 이는 당시에는 일반적인 일이 아니었다. 이런 구분은 원래 고틀로프 프레게가 1879년에 출판된 "개념표기법"에서 도입했으나, 페아노는 프레게의 작업에 대해 모른 채 불과 슈뢰더의 작업에 기초해 자신의 논리적 도구를 만들어냈다.

페아노의 공리들은 '자연수 집합' N이 만족해야 할 성질들을 규정한다. 처음의 네 공리는 동일 관계를 묘사한다.

1. 임의의 자연수 x에 대해, x = x. 즉, 동일성은 반사관계이다.
2. 임의의 자연수 x와 y에 대해, x = y이면 y = x. 즉, 동일성은 대칭관계이다.
3. 임의의 자연수 x, y, z에 대해, x = y이고 y = z이면 x = z. 즉, 동일성은 추이관계이다.
4. 임의의 a와 b에 대해, a가 자연수이고 a = b이면 b도 자연수이다. 즉, 자연수 집합은 동일성에 대해 닫혀 있다.

나머지 공리들은 자연수의 성질을 다룬다. 먼저 상수 0이 자연수라 하고, 자연수 집합이 "따름수" 함수 S에 대해 닫혀 있다고 정한다.

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

페아노의 원래 형식화에서는 첫 자연수로 0이 아닌 1을 선택했다. 공리 5는 0이라는 상수에 대해 덧셈에 관하여 아무런 성질도 부여하지 않으므로, 어느 쪽을 선택하든 별 상관은 없다. 그러나 0이 덧셈에 대한 항등원이라는 점 때문에 현대에 페아노 공리들을 서술할 때는 대체로 0에서 시작한다. 공리 5와 6은 자연수를 1진법으로 규정하는 것이다. 즉, 1은 S(0)이며, 2는 S(S(0)) = S(1)이고, 비슷하게 임의의 자연수 n은 Sⁿ(0)이다. 다음의 두 공리는 이 1진법 표현의 성질을 정한다.

7. 임의의 자연수 n에 대해, S(n) ≠ 0. 즉, 따름수가 0인 자연수는 존재하지 않는다.
8. 임의의 자연수 m과 n에 대해, S(m) = S(n)이면 m = n. 즉, S는 단사 함수이다.

이 두 공리는 자연수가 무한히 많음을 보장한다. 왜냐하면, 최소한 {0, S(0), S(S(0)), ...}라는, 서로 다른 원소들로 이루어진 무한 부분집합이 자연수에 포함되기 때문이다. 마지막 공리는 '귀납법 공리'라고도 하는데, 자연수 전체에 대해 순차적인 논증을 할 수 있게 해준다. 이는 유일한 2차 논리적 공리이다.

9. K가 다음의 조건을 만족하는 집합이라 하자:
   • 0은 K의 원소이다.
   • 임의의 자연수 n에 대해, n이 K의 원소이면, S(n)은 K의 원소이다.
   이때, K는 모든 자연수를 포함한다.

귀납법 공리는 다음과 같이 쓰기도 한다:

φ가 다음의 조건을 만족하는 1항 술어라 하자:

• φ(0)는 참이다.
• 임의의 자연수 n에 대해, φ(n)이 참이라면 φ(S(n))도 참이다.

이때, φ(n)은 임의의 자연수 n에 대해 참이다.

위의 두 형식화는 동치로, K는 φ에 의해 결정된다. 둘 중 후자 쪽이 논증할 때 실제로 사용하기에 적합하다.

산술

페아노 공리계로 정의된 자연수 집합에 덧셈과 곱셈 및 전순서를 부여할 수 있다. 각 함수와 관계는 2차 논리에서 구성되며, 공리를 이용해 이들이 유일함을 보일 수 있다.

자연수의 덧셈은 (보통 중위 표기법으로 표현되는) 함수 + : N × N → N으로, 다음과 같이 재귀적으로 정의된다:

$\begin{array}{cc}a+0& =a,\\ a+(S(b))& =S(a+b).\end{array}$

예를 들어, a + 1 = a + S(0) = S(a + 0) = S(a)이다.

구조 (N, +)는 0을 항등원으로 갖는 가환 모노이드이며, 소거법칙도 성립한다. 따라서 이는 군에 묻힐 수 있다. (N, +)가 묻히는 가장 작은 군은 정수 집합의 덧셈군이다.

덧셈이 주어졌으므로, 자연수의 곱셈 또한 아래의 반복법 조건을 만족하는 함수 ·: N × N → N로 정의할 수 있다:

$\begin{array}{cc}a\cdot 0& =0,\\ a\cdot (S(b))& =a+(a\cdot b).\end{array}$

이때 a · 1 = a · (S(0)) = a + (a · 0) = a + 0 = a이므로, 1이 곱셈의 항등원임을 알 수 있다. 또한, 곱셈의 덧셈에 대한 분배법칙 a · (b + c) = (a · b) + (a · c)가 성립한다는 것도 간단히 보일 수 있으며, 그러므로 (N, +, ·)은 가환 반환이다.

보통의 전순서 ≤ ∈ N × N은 다음과 같이 정의한다:

a, b ∈ N에 대해, a + c = b가 되는 c ∈ N이 존재하면 a ≤ b라 한다.

이 관계는 덧셈과 곱셈에 대해 안정적이다. 즉, a, b, c ≤ N일 때, a ≤ b이면 a + c ≤ b + c이며 또한 a · c ≤ b · c이다.

그러므로 구조 (N, +, ·, ≤)는 순서 반환이다. 또한 0과 1 사이에는 자연수가 존재하지 않으므로 이는 이산 순서 반환이다. 귀납법 공리는 ≤ 순서를 사용해서 다음의 '강력한' 형태로 서술되기도 한다: φ가 다음의 조건을 만족하는 1항 술어라 하자:

• φ(0)는 참이다.
• 임의의 자연수 n에 대해, k ≤ n이 성립하는 모든 자연수 k에 대해 φ(k)가 참이라면 φ(S(n))도 참이다.

이때, φ(n)은 임의의 자연수 n에 대해 참이다.

이를 이용하면 ≤ 순서에 대해 '강력한' 논증을 할 수 있다는 이유로 강력한 형태라 불리지만, 논리적으로는 원래 형태와 동치이다.

모형

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

데데킨트는 1888년 출판된 책에서 페아노 산술의 임의의 두 모형이 동형임을 증명하였다. 곧, 두 모형 $({𝐍}_A,0_A,S_A)$ 와 $({𝐍}_B,0_B,S_B)$ 이 주어졌을 때, 다음을 만족시키는 준동형사상 $f:{𝐍}_A\mapsto {𝐍}_B$ 가 유일하게 존재하며, 이는 전단사이기도 하다.

$\begin{array}{cc}f(0_A)& =0_B\\ f(S_A(n))& =S_B(f(n))\end{array}$

즉, 2차 논리의 페아노 공리계는 범주적(categorical), 즉 오직 하나의 모형만 갖는다는 것이다. 다만 이는 페아노 공리계를 1차 논리로 재서술한 것에 대하여서는 성립하지 않는다.

집합론적 모형

페아노 체계는 (ZF 집합론에 더하여) 자연수의 집합론적 구성법으로부터도 도출될 수 있다. 존 폰 노이만에 의해 정립된 자연수의 표준 구성법에서는 0을 공집합으로 정의하는 것에서 시작하여 따름수 연산자 s를 다음과 같이 정의한다.

$s(a)=a\cup \{a\}$

자연수 집합 N은 s에 대하여 닫힌 모든 집합들의 교집합으로 정의된다. 다음과 같이, 각 자연수는 그것보다 작은 모든 자연수들을 모은 집합과 동등하게 된다:

$\begin{array}{cc}0& =\mathrm{\varnothing }\\ 1& =s(0)=s(\mathrm{\varnothing })=\mathrm{\varnothing }\cup \{\mathrm{\varnothing }\}=\{\mathrm{\varnothing }\}=\{0\}\\ 2& =s(1)=s(\{0\})=\{0\}\cup \{\{0\}\}=\{0,\{0\}\}=\{0,1\}\\ 3& =s(2)=s(\{0,1\})=\{0,1\}\cup \{\{0,1\}\}=\{0,1,\{0,1\}\}=\{0,1,2\}\end{array}$

이제 0을 포함한 집합 N과 따름수 함수 s : N → N에서 페아노 공리들이 성립한다.

페아노 산술은 몇몇 약한 집합론 체계들과 등무모순적임이 알려져 있다. 예를 들어, ZFC에서 무한 공리를 무한 공리의 부정으로 대체한 체계(ZFC - inf + ~inf) 등이 있다.

무모순성

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

1936년 게르하르트 겐첸은 원시 재귀 산술(영어: primitive recursive arithmetic, PRA)에 더하여 양화사가 없는 초한귀납법이 순서수 ${\epsilon }_0$까지 확장된다는 법칙을 추가한 것으로부터 페아노 공리계의 일관성을 증명해냈다. 여기서 원시 재귀 산술은 자연수와 원시 재귀 함수(덧셈, 곱셈, 제곱 따위)로 이루어진 진술들을 서술할 수 있는 언어체계이며, 순서수 ${\epsilon }_0$는 $\epsilon ={\omega }^{\epsilon }$이 되는 최소의 순서수로, 그것보다 작은 극한 순서수를 모두 모은 수열의 극한으로 볼 수 있다. (즉, ${\epsilon }_0={\omega }^{{\omega }^{{\omega }^{{\cdot }^{{\cdot }^{\cdot }}}}}=\sup \{\omega ,{\omega }^{\omega },{\omega }^{{\omega }^{\omega }},{\omega }^{{\omega }^{{\omega }^{\omega }}},\dots \}$ 가 성립한다.)

역사

페아노 공리계는 19세기 이탈리아의 수학자 주세페 페아노가 제안하였다.

산술을 형식화할 필요성은 1860년대에 헤르만 그라스만이 산술의 많은 사실들이 따름수 연산과 수학적 귀납법에 대한 보다 단순한 사실들로부터 유도될 수 있다는 것을 보이기 전까지는 그다지 인식되지 않았다. 1888년, 리하르트 데데킨트는 수에 대한 공리들을 제안했으며, 1889년 페아노는 보다 구체적인 형태의 공리들을 《새로운 방법으로 표현된 산술의 원칙》(라틴어: Arithmetices principia: nova methodo exposita)이라는 책에서 발표했다.

같이 보기

• 자연수
• 수학기초론
• 겐첸의 일관성 증명
• 굿스타인의 정리
• 패리스-해링턴 정리
• 프레스버거 산술
• 로빈슨 산술
• 2차 산술
• 비표준 산술

참고 자료

• Hermann Grassmann, 1861. Lehrbuch der Arithmetik (산술 지도). Berlin.
• Jean van Heijenoort, ed. (1967, 1976 3rd printing with corrections). 《From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931》 3판. Cambridge, Mass: Harvard University Press. ISBN 0674-32449-8.  (Paperback) 다음 두 논문에 대한 영어 번역 및 중요한 주석이 들어있다:
  • Richard Dedekind, 1890, "Letter to Keferstein." pp. 98-103. On p. 100, 1888년의 공리들을 재진술하며 이를 변호한다.
  • Giuseppe Peano, 1889. Arithmetices principia, nova methodo exposita (새로운 방법으로 표현된 산술의 원칙), pp. 83-97. 페아노가 그의 공리들을 처음으로 제시하고, 산술 연산을 반복법으로 정의한 부분을 인용.