페아노 공리계

위키백과 ― 우리 모두의 백과사전.

수리논리학에서 페아노 공리계(Peano -)는 19세기 이탈리아의 수학자 주세페 페아노가 제안한, 자연수 체계에 대한 공리들을 말한다. 그동안 이 공리들은 거의 변형되지 않은 형태로 수론의 일관성 및 완전성 연구에 사용되었다.

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

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

목차

[편집] 공리

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

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

  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에 대해 닫혀 있다고 정한다.

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

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

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

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

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

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

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

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

[편집] 산술

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

자연수의 덧셈은 (보통의 중치 표기법으로 표현되는) 함수 + : N × N → N으로, 반복법을 통해 다음과 같이 정의된다:

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

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

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

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

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

이때 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에 대해 참이다.

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

[편집] 함께 보기

[편집] 주석

  1. ↑ Grassmann 1861
  2. ↑ Dedekind 1888
  3. ↑ Peano 1889
  4. ↑ Van Heijenoort 1967, p. 2
  5. ↑ Van Heijenoort 1967, p. 83
  6. ↑ 여기의 공리 5는 페아노의 원래 논문에서는 1번이었으며, 여기의 공리 1에서 4까지는 원래 순서대로 2번에서 5번까지의 번호가 매겨졌다.

[편집] 참고자료

  • Hermann Grassmann, 1861. Lehrbuch der Arithmetik (산술 지도). Berlin.
  • Jean van Heijenoort, ed.. From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931, 3rd, Cambridge, Mass: Harvard University Press. ISBN 0-674-32449-8 (pbk.) 다음 두 논문에 대한 영어 번역 및 중요한 주석이 들어있다:
    • Richard Dedekind, 1890, "Letter to Keferstein." pp. 98-103. On p. 100, 1888년의 공리들을 재진술하며 이를 변호한다.
    • Guiseppe Peano, 1889. Arithmetices principia, nova methodo exposita (새로운 방법으로 표현된 산술의 원칙), pp. 83-97. 페아노가 그의 공리들을 처음으로 제시하고, 산술 연산을 반복법으로 정의한 부분을 인용.
원본 주소 ‘http://ko.wikipedia.org/wiki/%ED%8E%98%EC%95%84%EB%85%B8_%EA%B3%B5%EB%A6%AC%EA%B3%84’