페아노 공리계 문서 원본 보기

{{위키데이터 속성 추적}}
'''페아노 공리계'''(Peano公理系, {{llang|en|Peano’s axioms}}) 또는 '''데데킨트-페아노 공리계'''는 [[수리논리학]]에서 [[자연수]] 체계를 묘사하는 [[공리]]들이다. 19세기 이탈리아 수학자인 [[주세페 페아노]]에 의하여 제안되었다. [[수론]]의 [[무모순성|일관성]] 및 [[완전성]] 연구에도 사용된다.

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

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

페아노의 공리들은 '자연수 집합' '''N'''이 만족해야 할 성질들을 규정한다. 처음의 네 공리는 [[동일성|동일]] [[관계 (수학)|관계]]를 묘사한다.<ref>여기의 공리 5는 페아노의 원래 논문에서는 1번이었으며, 여기의 공리 1에서 4까지는 원래 순서대로 2번에서 5번까지의 번호가 매겨졌다.</ref>

# 임의의 자연수 x에 대해, x = x. 즉, 동일성은 [[반사관계]]이다.
# 임의의 자연수 x와 y에 대해, x = y이면 y = x. 즉, 동일성은 [[대칭관계]]이다.
# 임의의 자연수 x, y, z에 대해, x = y이고 y = z이면 x = z. 즉, 동일성은 [[추이관계]]이다.
# 임의의 a와 b에 대해, a가 자연수이고 a = b이면 b도 자연수이다. 즉, 자연수 집합은 동일성에 대해 [[닫힘 (수학)|닫혀 있다]].

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

<ol>
<li value="5">0은 자연수다.</li>
<li>임의의 자연수 n에 대해, S(n)은 자연수이다.
</ol>

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

<ol>
<li value="7">임의의 자연수 n에 대해, S(n) ≠ 0. 즉, 따름수가 0인 자연수는 존재하지 않는다.
<li>임의의 자연수 m과 n에 대해, S(m) = S(n)이면 m = n. 즉, S는 [[단사 함수]]이다.
</ol>

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

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

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

:φ가 다음의 조건을 만족하는 1항 술어라 하자:
:* φ(0)는 참이다.
:* 임의의 자연수 n에 대해, φ(n)이 참이라면 φ(S(n))도 참이다.
:이때, φ(n)은 임의의 자연수 n에 대해 참이다.

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

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

'''자연수의 덧셈'''은 (보통 [[중위 표기법]]으로 표현되는) 함수 + : '''N''' × '''N''' → '''N'''으로, 다음과 같이 재귀적으로 정의된다:
:<math>\begin{align}
a + 0       &= a ,\\
a + (S (b)) &= S (a + b).
\end{align}</math>
예를 들어, a + 1 = a + S(0) = S(a + 0) = S(a)이다.

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

덧셈이 주어졌으므로, '''자연수의 곱셈''' 또한 아래의 반복법 조건을 만족하는 함수 ·: '''N''' × '''N''' → '''N'''로 정의할 수 있다:
:<math>\begin{align}
a \cdot 0 &= 0, \\
a \cdot (S (b)) &= a + (a \cdot b).
\end{align}</math>
이때 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에 대해 참이다.

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

== 모형 ==
페아노 공리계를 만족시키는 논리학적 구조, 곧 [[모형 (논리학)|모형]]은 <math>(\mathbf{N}, 0, S)</math>이다. 여기서 N 은 무한집합이고, 0 ∈ N이며, S: N → N이다.

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

: <math>\begin{align}

f(0_A) &= 0_B \\
f(S_A (n)) &= S_B (f (n))
\end{align}</math>

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

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

: <math>s(a) = a \cup \{a\}</math>

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

: <math>\begin{align}

0 &= \emptyset \\
1 &= s(0) = s(\emptyset) = \emptyset \cup \{ \emptyset \} = \{ \emptyset \} = \{ 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{align}</math>

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

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

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

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

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

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

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

== 각주 ==
<references />

== 참고 자료 ==
* [[헤르만 그라스만|Hermann Grassmann]], 1861. ''Lehrbuch der Arithmetik'' (산술 지도). Berlin.
* {{서적 인용 | 저자 = [[Jean van Heijenoort]], ed.| coauthors = | 제목 = From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931| url = https://archive.org/details/fromfregetogdels0000jean| 판 = 3rd | 출판사 = Harvard University Press | 출판위치 = Cambridge, Mass| 연도 = 1967, 1976 3rd printing with corrections|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. 페아노가 그의 공리들을 처음으로 제시하고, 산술 연산을 반복법으로 정의한 부분을 인용.

[[분류:산술]]
[[분류:수리논리학]]
[[분류:공리]]