5.4 페아노 산술(Peano Arithmetic)의 공리 체계

1. 페아노 공리의 역사적 배경

페아노 공리(Peano Axioms)는 이탈리아의 수학자 주세페 페아노(Giuseppe Peano, 1858–1932)가 1889년 저서 “Arithmetices principia, nova methodo exposita“에서 제시한 자연수 체계의 공리적 정의이다. 다만, 이 공리 체계의 핵심 아이디어는 데데킨트(Richard Dedekind)가 1888년 “Was sind und was sollen die Zahlen?“에서 먼저 제시하였으며, 페아노가 이를 형식적으로 정리한 것이다.

2. 일차 페아노 산술(First-Order Peano Arithmetic, PA)

괴델의 불완전성 정리에서 다루는 페아노 산술은 일차 술어 논리(First-Order Predicate Logic)의 형식 체계로서 다음과 같이 정의된다.

2.1 언어(Language)

상수 기호: $0$ (영)
함수 기호: $S$ (후자, 단항), $+$ (덧셈, 이항), $\times$ (곱셈, 이항)
관계 기호: $=$ (등호, 이항)
논리 기호: $\neg, \rightarrow, \forall$ (다른 연결사와 양화사는 정의에 의해 도입)
변수: $x_0, x_1, x_2, \ldots$

2.2 논리적 공리와 추론 규칙

일차 술어 논리의 표준적 공리와 추론 규칙(전건 긍정, 전칭 일반화)을 포함한다. 등호에 관한 공리도 포함된다.

2.3 비논리적 공리(페아노 공리)

공리 1 (영의 비후자성):

$\forall x \, \neg(S(x) = 0)$

0은 어떤 자연수의 후자도 아니다. 즉, 0에 도달하기 위해 “뒤로” 가는 것이 불가능하며, 0이 자연수 체계의 시작점임을 보장한다.

공리 2 (후자의 단사성):

$\forall x \, \forall y \, (S(x) = S(y) \rightarrow x = y)$

후자 함수 $S$ 는 단사(Injective)이다. 서로 다른 자연수는 서로 다른 후자를 가진다.

공리 3 (덧셈의 기저):

$\forall x \, (x + 0 = x)$

공리 4 (덧셈의 재귀):

$\forall x \, \forall y \, (x + S(y) = S(x + y))$

공리 3과 4는 덧셈을 재귀적으로 정의한다. 이 정의에 의해 $2 + 3 = 2 + S(S(S(0))) = S(2 + S(S(0))) = S(S(2 + S(0))) = S(S(S(2 + 0))) = S(S(S(2))) = 5$ 로 계산된다.

공리 5 (곱셈의 기저):

$\forall x \, (x \times 0 = 0)$

공리 6 (곱셈의 재귀):

$\forall x \, \forall y \, (x \times S(y) = x \times y + x)$

공리 7 (수학적 귀납법 공리 도식, Induction Schema):

모든 공식 $\phi(x)$ 에 대해:

$[\phi(0) \wedge \forall x \, (\phi(x) \rightarrow \phi(S(x)))] \rightarrow \forall x \, \phi(x)$

이 공리 도식은 무한히 많은 공리의 집합이다. 언어의 각 공식 $\phi$ 에 대해 하나의 귀납법 공리가 생성된다.

페아노 산술의 표현력

자연수의 표현

자연수 $n$ 은 $S^n(0)$ (후자 함수를 $n$ 번 적용한 것)으로 표현된다:

$0 = 0$
$1 = S(0)$
$2 = S(S(0))$
$n = \underbrace{S(S(\cdots S}_{n}(0)\cdots))$

이를 $\overline{n}$ 으로 약기한다.

산술적 관계의 표현

기본 산술적 관계들이 PA의 언어로 정의 가능하다:

순서 관계: $x < y \equiv \exists z \, (x + S(z) = y)$
정제 관계(Divisibility): $x \mid y \equiv \exists z \, (x \times z = y)$
소수: $\text{Prime}(x) \equiv x > \overline{1} \wedge \forall y \, (y \mid x \rightarrow (y = \overline{1} \vee y = x))$

괴델 수 관련 관계의 표현

괴델의 불완전성 정리 증명의 핵심은 PA가 자기 자신의 구문론적 성질을 표현할 수 있을 만큼 충분히 강력하다는 것이다. 구체적으로:

“ $x$ 는 PA의 변수의 괴델 수이다” → PA의 공식으로 표현 가능
“ $x$ 는 PA의 적격식의 괴델 수이다” → PA의 공식으로 표현 가능
“ $x$ 는 PA의 공리의 괴델 수이다” → PA의 공식으로 표현 가능
“ $x$ 는 적격식 $y$ 의 PA에서의 증명의 괴델 수이다” → PA의 공식으로 표현 가능

이 표현 가능성이 자기 참조적 괴델 문장의 구성을 가능하게 한다.

PA의 모형(Model)

표준 모형(Standard Model)

PA의 의도된(Intended) 해석은 표준 자연수 $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ 이다. 이 해석에서 $0$ 은 자연수 0에, $S$ 는 $+1$ 에, $+$ 와 $\times$ 는 통상의 덧셈과 곱셈에 대응한다.

PA의 모든 공리는 표준 모형에서 참이다. 따라서 PA는 건전(Sound)하다—PA에서 증명 가능한 모든 문장은 표준 모형에서 참이다.

비표준 모형(Nonstandard Model)

괴델의 완전성 정리(1929)에 의해, PA가 무모순이면 PA의 모형이 존재한다. 뢰벤하임-스콜렘 정리(Löwenheim-Skolem Theorem)에 의해, PA는 비가산(Uncountable) 모형을 가진다. 이 비가산 모형은 표준 자연수 이외의 “비표준적(Nonstandard)” 원소를 포함하며, 이를 비표준 모형(Nonstandard Model)이라 한다.

괴델 문장 $G$ 는 표준 모형에서 참이지만 PA에서 증명 불가능하다. 불완전성 정리에 의해 $\neg G$ 도 PA에서 증명 불가능하다. 따라서 PA $\cup \{\neg G\}$ 도 무모순하며, 이 이론의 모형이 존재한다. 이 모형은 $G$ 가 거짓인 비표준 모형이다.

PA의 불완전성 정리에서의 역할

PA는 괴델의 불완전성 정리의 표준적 적용 대상이다. PA는 다음의 조건을 만족한다:

효과적 공리화: PA의 공리 집합은 결정 가능하다(귀납법 공리 도식의 각 인스턴스가 공리인지 기계적으로 판별 가능).
무모순성: PA는 무모순으로 믿어진다(겐첸의 증명에 의해 초한 귀납법 하에서 무모순성이 확인됨).
충분한 표현력: PA는 모든 원시 재귀 함수를 표현(Represent)할 수 있다.

이 조건들이 만족되므로, 괴델의 불완전성 정리가 PA에 적용되어 PA에서 증명도 반증도 불가능한 참인 문장(괴델 문장)의 존재가 보장된다.