일계논리와 Peano 산술

By | September 2, 2017

일계논리 문장의 집합 \(\varSigma\)가 완전하다(complete)는 것은 임의의 문장 \(\alpha\)에 대하여 \(\alpha\) 또는 \((\lnot \alpha )\) 중 하나가 \(\varSigma\)의 논리적 귀결인 것이다. 완전성 정리에서는 형식계의 완전성을 말하기 때문에 완전성이라는 용어를 조금 다르게 사용한다. 그러나 두 상황에서 완전성이라는 개념은 서로 깊은 연관이 있다. 왜냐하면 \(\varSigma\)가 완전할 때 임의의 문장 \(\alpha\)에 대하여 \(\alpha\) 또는 \((\lnot \alpha )\)가 \(\varSigma\)로부터 증명될 수 있기 때문이다.

\(M\)이 구조일 때, \(M \models \sigma\)인 모든 \(\sigma\)들의 모임, 즉 \(M\)에서 성립하는 모든 일계논리 문장 \(\sigma\)들의 모임을 \(M\)의 이론(theory)이라고 부른다. 앞서 살펴본 바와 같이 \(M\)의 이론은 완전성을 가진다.

문장들의 모임 \(\varSigma\)가 무한 모델을 가지면 \(\varSigma\)는 여러 개의 모델을 가진다. 그러나 만약 \(\varSigma\)가 완전성을 가지면 \(\varSigma\)의 모델은 모두 동일한 일계논리 이론을 가진다. 동일한 일계논리 이론을 갖는다는 관계는 동형성보다는 약한 개념이지만 동치관계이다.

수학의 어떤 분야를 공리화한다고 가정해보자. 만약 그 분야가 군론이라면 군은 하나만 존재하는 것이 아니므로 우리는 공리릍 통해 완전한 하나의 집합을 정하고자 하지는 않을 것이다. 즉 군론을 공리화했을 경우 그 공리의 모델은 여러 개가 된다. 반면에 만약 하나의 모델만을 갖는 분야를 공리화한다면 일계논리의 문장을 적절히 구성하여 그 문장들이 그 모델을 완전히 결정하도록 해야 한다.

자연수계의 공리화

일계논리를 이용하여 공리화할 때 흥미로운 분야가 바로 자연수계이다. 자연수는 수학에서 가장 기본적인 연구 대상이며, 수학을 공부하는 사람이 가장 먼저 만나는 대상이기도 하다. 여기서는 자연수계에 \(0\)이 속하는 것으로 두겠다.

자연수계 \(\mathbb{N}\)은 집합론을 구성하지 않고 일계논리로 직접 공리화하는 것이 가능할까? 일계논리를 이용한 자연수계의 공리는 자연수를 구성하는 방법을 제공해야 한다. 즉 \(0\)으로부터 출발하여 직후자를 취함으로써 모든 자연수를 얻을 수 있어야 한다. 그러나 일계논리만으로는 '임의의 유한 번의 반복'에 대하여 논할 수 없다. 왜냐하면 이 과정 \[(\forall x)(\exists x_1 )\cdots (\exists x_{n-1} )(x_1 = s(0) \wedge \cdots \wedge x = s(x_{n-1} ))\] 과 같은 식으로 표현되는데, 이런 꼴의 식은 일계논리에서 허용되지 않기 때문이다.

자연수계 \(\mathbb{N}\)은 자기동형사상을 갖지 않는다. 왜냐하면 \(\mathbb{N}\)의 자기동형사상은 \(0\)을 부동점으로 갖고, 그에 따라 \(1,\) \(2,\) \(3,\) \(\cdots\)도 부동점으로 갖기 때문이다. 따라서 \(\mathbb{N}\)은 Oligomorphic이 아니며, \(\mathbb{N}\)과 동형이 아닌 가산 모델을 가진다. 그러므로 \(\mathbb{N}\)을 공리화할 때에는 \(\mathbb{N}\)의 성질을 모두 끌어낼 수 있는 완전성을 갖는 단순한 공리계를 구성하는 것이 최선이다. [즉, 모델의 유일성까지 기대할 수는 없다.]

직후자 원리(succession principle)는 수학적 귀납법의 근거가 되며, 이것을 구현하는 방법은 수학적 귀납법의 원리(principle of induction)를 허용하는 것이다. 문제는 여기서 발생한다. 성질 \(\mathrm{P}\)가 \(0\)에 대하여 성립하고, \(\mathrm{P}\)가 \(n\)에 대하여 성립할 때마다 \(n+1\)에 대해서도 성립하면, \(\mathrm{P}\)는 임의의 \(n\)에 대하여 성립하도록 해야 한다. 그러나 일계논리에서는 일계논리로 표현 가능한 성질만 표현할 수 있다.

자연수계를 공리화하기 위하여 먼저 직후자 함수(successor function)와 관련된 공리를 도입하자. 우리의 언어는 상수기호 \(0\)과 일항함수 \(s\)를 가지는 것으로 약속한다. 여기서 \(s\)는 직후자 함수를 나타낸다.

  • (P1) \(0\)을 제외한 임의의 원소 \(x\)는 유일한 \(y\)의 직후자이다.
  • (P2) \(0\)은 어떠한 원소의 직후자도 아니다.

이들 공리는 일계논리의 문장으로 표현된다. 예컨대 (P2)는 \((\forall x)(\lnot (s(x) =0))\)으로 표현된다. (P1)과 (P2)는 서로 동형이 아닌 가산 모델을 무한히 많이 가진다.

이제 덧셈과 곱셈을 다룰 수 있는 공리를 추가하고자 한다. 이를 위해 다음 네 개의 공리를 도입한다.

  • (P3) \((\forall x)(x+0=x)\)
  • (P4) \((\forall x)(\forall y)(x+s(y) = s(x+y))\)
  • (P5) \((\forall x)(x \cdot 0 =0 )\)
  • (P6) \((\forall x)(\forall y)(x \cdot s(y) = x \cdot y + x )\)

끝으로 수학적 귀납법의 원리를 위한 공리를 도입하자. 이 공리는 하나의 공리가 아닌 공리족(axiom schema)이다. 즉 하나의 자유변수 \(x\)를 가진 언어의 각 논리식 \(\phi\)에 대하여 공리가 하나씩 대응되는 것이다.

  • (P7) \(((\phi [0/x] \wedge (\forall x)(\phi \rightarrow \phi [s(x)/x])) \rightarrow (\forall x)\phi )\)

이 공리계를 Peano 산술(Peano arithmetic)이라고 부른다. Peano 산술은 가산범주적이지 않다. 즉 Peano 산술은 \(\mathbb{N}\)는 다른 모델을 가진다. [그러한 모델을 '비표준 모델'이라고 부른다.] Peano 산술의 비표준 모델이 존재함을 간단히 밝힐 수 있다. 우리의 언어에 새로운 상수기호 \(c\)를 추가한다. \(c > n\)일 때 \(\sigma _n\)이 새로운 언어의 문장이라고 하고 \(s\)를 \(n\)번 합성한 식 \(s(s( \cdots s(0) \cdots ))\)을 \(n\)으로 나타내자. \[\varSigma = \left\{ \sigma _n \,\vert\, n \in \mathbb{N} \right\}\] 이라고 하자. 그러면 \(\varSigma\)의 유한부분집합 \(\varSigma _0\)는 Peano의 공리에 대하여 무결하다. 왜냐하면 \(c\)를 \(\varSigma_0\)에 있는 임의의 식 \(\sigma_n \)의 첨수보다 더 큰 자연수로 해석하면 되기 때문이다. 긴밀성 정리에 의하여 \(\varSigma\)를 만족시키는 Peano의 공리의 모델이 존재한다. 이 모델에서 \(c\)는 '무한대'로 해석된다.

Peano 산술이 완전성을 가질까? 그렇지 않다는 것이 1930년에 Kurt Gödel에 의하여 밝혀졌다. [이로 인하여 자연수계의 성질에 기초한 참인 모든 명제를 형식적으로 증명하고자 했던 Hilbert의 프로그램은 무산되고 말았다.] 즉 \(\mathbb{N}\)에서 참이지만 Peano의 공리를 이용하여 증명할 수 없는 문장 \(\sigma\)가 존재한다.

Gödel의 불완전성 정리는 20세기에 손꼽히는 위대한 지적 업적 중 하나이다. 여기서는 불완전성 정리의 핵심적인 아이디어와 증명의 개요만 살펴보기로 한다.

Gödel 숫자붙이기

Gödel의 아이디어는 각 논리식을 자연수에 대응시키는 것이다. 이것을 Gödel 숫자붙이기(Gödel numbering)라고 부른다. 십진법으로 나타낸 자연수는 알파벳 \[\left\{ 0 ,\, 1 ,\, 2 ,\, 3 ,\, 4 ,\, 5 ,\, 6 ,\, 7 ,\, 8 ,\, 9 \right\}\] 으로 구성된 문자열이다. 논리식은 서로 다른 문자들로 구성된 문자열이므로 논리식을 자연수에 대응시키는 것은 그리 놀랄만한 일이 아니다. 그러나 일계논리의 변수는 무한히 많을 수도 있으므로 이와 같은 방법으로 대응시키는 일은 간단하지 않다. 보통은 정수론의 기본 정리, 즉 임의의 자연수는 유일한 꼴로 인수분해된다는 성질과 소수의 무한성을 이용하여 이 문제를 해결한다. 하지만 여기서는 Hofstadter의 'Typographic Number Theory'에 기초한 더 간단한 방법을 사용하기로 한다. (관련 내용은 Douglas Hofstadter의 책 『Gödel, Escher, Bach: An Eternal Golden Braid』를 참고하기 바란다.)

먼저 언어를 구성하는 기호 중에서 변수가 아닌 것들을 다음 표에서와 같이 변환한다.

( ) = s + . 0
1 2 3 4 5 6 7 8 9 0

여기에 두 개의 기호가 더 필요하다. 즉 '변수 표시 기호'와 '논리식 표시 기호'가 필요하다. 이들 두 기호를 각각 \(A,\) \(B\)로 나타내자. 이로써 논리식을 자연수로 나타내는 데에는 10진법이 아니라 12진법을 사용해야 한다.

'변수 표시 기호'는 HTML의 VAR 태그와 비슷하다. 다른 점은 HTML에는 시작 태그와 끝 태그를 구분하여 <VAR>, </VAR>로 나타내지만 변수 표시 기호는 시작과 끝을 구분하지 않고 \(A\)로 나타내며 변수 기호는 그 사이에 들어간다. 예컨대 \(A2A\)는 변수 \(x_2\)를 나타낸다. 변수의 첨자를 나타낼 때에는 10진법을 사용한다. 왜냐하면, 만약 변수의 첨자를 나타낼 때 12진법을 사용하면 첨자에도 \(A\)가 나타나게 되는데, 이때에는 \(A\)가 변수의 끝을 표기하는 문자인 경우와 구분할 수 없기 때문이다. 예컨대 \(A35A\)는 \(x_{41}\)이 아니라 \(x_{35}\)를 나타낸다.

논리식 표시 기호는 두 논리식 사이에 넣는다. 그러므로 논리식이 하나인 경우 논리식 표시 기호는 사용할 필요가 없다.

이와 같은 방법으로 논리식을 자연수로 변환한 것을 논리식의 Gödel 수(Gödel number)라고 부른다. 예컨대 Peano 공리 중 하나인 논리식 \[(\forall x_0 )(\lnot (s (x_0 ) =0 ))\] 을 Gödel 수로 나타내면 다음과 같다. \[43A0A541474A0A56055\] 이것을 만약 10진법으로 나타낸다면 \(115011419876663965121\)이 된다. 단순한 논리식도 Gödel 수로 변환하면 큰 수가 된다.

여러 개의 논리식을 나열한 것도 Gödel 수로 나타낼 수 있다. 그러므로 모든 증명 또한 각각 Gödel 수로 나타낼 수 있다. 논리식 \(\phi\)의 Gödel 수롤 \(G(\phi )\)로 나타내자.

일계논리의 언어에서 고정된 자연수 \(n\)은 \(s(s( \cdots s(0) \cdots ))\)으로 나타낼 수 있다. 예컨대 \(2\)는 \(s(s(0))\)으로 나타낼 수 있다. 자연수를 논리식으로 나타낼 때에는 이와 같은 방식으로 나타내는 것으로 약속한다. 즉 일계논리 언어에서의 자연수는 논리식으로 나타내고, 논리식의 Gödel 수를 생각할 때에는 일상적으로 사용하는 자연수를 사용한다.

Gödel의 핵심 아이디어는 다음과 같다.

정리 1.  Gödel 증명의 아이디어.

(ⅰ) 두 개의 변수 \(x_0 ,\) \(x_1\)을 가진 일계논리 산술의 논리식 \(\pi\)가 존재하여 다음을 만족시킨다.

  • \(\mathbb{N} \models \pi [n/x_0 ,\, m/x_1 ]\), \(m = G(\phi )\)이고 \(n\)이 \(\mathrm{PA}\)에서 \(\phi\)의 증명의 Gödel 수일 때.
  • \(\mathbb{N} \models ( \lnot \pi [n/x_0 ,\, m/x_1 ]) \), 그 외의 경우.

(ⅱ) 두 개의 변수 \(x_0 ,\) \(x_1\)을 가진 일계논리 산술의 논리식 \(\omega\)가 존재하여 다음을 만족시킨다.

  • \(\mathbb{N} \models \omega [m/x_0 ,\, n/x_1 ]\), 변수 \(x_0\)가 자유변수로서 나타나는 적당한 논리식 \(\phi\)와 \(\mathrm{PA}\)에서의 \(\phi [m/x_0 ]\)의 증명의 Gödel 수 \(n\)에 대하여 \(m=G(\phi )\)일 때.
  • \(\mathbb{N} \models (\lnot \omega [m/x_0 ,\, n/x_1 ])\), 그 외의 경우.

Gödel 숫자붙이기의 다양한 성질이 논리식을 이용하여 비슷한 방법으로 표현될 수 있다는 것을 보이는 증명의 논리식열의 끝에 위와 같은 정리가 존재한다. 예컨대 적당한 \(\phi\)에 대하여 \(n = G(\phi )\)이며, 다시 적당한 \(\phi\)에 대하여 \(n = G(\phi )\)이며, 이것이 계속 반복된다. 더 정확히 말하자면, 기계적인 절차에 의해 밝혀질 수 있는 문자열의 성질은 논리식으로 표현될 수 있으며, 그 논리식이 \(n\)의 값을 가질 때 참일 필요충분조건은 \(n\)이 주어진 문자열의 Gödel 수인 것이다. 더욱이 문자열의 변수를 치환하는 것또한 기계적 절차이므로 같은 방법으로 논리식으로 기술될 수 있다. 즉 위 정리의 (ⅱ)는 (ⅰ)로부터 나온다.

Gödel의 불완전성 정리

Gödel의 정리는 만약 Peano 산술이 무모순적이면 증명이 가능하지도 않고 불가능하지도 않은 진술(statement)이 존재한다는 것이다. 여기서는 그보다 조금 더 간단한 내용을 보이기로 하자.

\(\phi\)가 자유변수 \(x\)를 가진 논리식이고 각 자연수 \(n\)에 대하여 \(\phi[n/x]\)가 증명 가능할 때마다 \((\lnot (\forall x)\phi )\)가 증명 가능할 때, Peano 산술은 \(\omega\)-무모순이다(omega-consistent)라고 말한다. 이 조건은 무모순성보다 더 강한 조건이다. 왜냐하면 모든 \(n\)에 대하여 \(\phi [n/x]\)가 증명 가능한 논리식 \(\phi\)가 존재할 수도 있기 때문이다. \((x=x)\)와 같은 논리식이 그 예이다. 그러므로 \(\omega\)-무모순성은 증명 가능하지 않은 논리식 \((\lnot (\forall x )\phi ))\)이 적어도 하나 이상 존재한다는 뜻이다. 그러나 만약 Peano 산술이 무모순적이지 않다면 모든 논리식은 증명 가능하게 된다.

\(\mathbb{N}\)을 유일한 모델로 가지는 일계논리 문장을 구성하는 것이 가능했다면 \(\omega\)-무모순성은 무모순성과 동일한 뜻을 가졌을 것이다. 그러나 앞서 살펴본 바와 같이 그것은 가능하지 않다.

이제 Peano 산술이 \(\omega\)-무모순이면 증명이 가능하지도 않고 불가능하지도 않은 논리식이 존재함을 보이자. 사실 \(\omega\)-무모순이라는 조건을 무모순이라는 조건으로 바꾸어도 같은 결과를 얻을 수 있지만 증명 과정은 더 복잡하다.

\(p\)가 논리식 \[(\forall x_1 )(\lnot \omega )\] 의 Gödel 수라고 하자. 여기서 \(\omega\)는 자유변수 \(x_0\)와 \(x_1\)을 가지고 있다. 이 논리식에서 \(x_0\)를 \(p\)로 치환한 논리식을 \(\zeta\)라고 하자. 그러면 \(\zeta\)는 임의의 \(n\)에 대하여 논리식 \(\psi [p/x_0 ]\)의 증명의 Gödel 수가 \(n\)이고 \(\psi\)가 Gödel 수 \(p\)를 가진다는 것으로 해석된다. 그런데 이와 같은 성질을 가진 논리식 \(\psi\)은 \((\forall x_1 )(\lnot \omega )\)이며, \(x_0\)를 \(p\)로 치환한 결과는 \(\zeta\)이다. 그러므로 \(\zeta\)의 해석은 \(\zeta\)의 증명 불가능성이다.

이제 Peano 산술이 \(\omega\)-무모순적이면 \(\zeta\)가 증명 가능하지도 않고 불가능하지도 않음을 보이자.

Peano 산술이 무모순적이라고 가정하자. 그러면 \(\zeta\)는 증명 불가능하다. 이를 증명하기 위해 \(\zeta\)가 증명 가능하다고 하고 \(q\)가 그 증명의 Gödel 수라고 가정해보자. \(\phi\)를 \((\forall x_1 )(\lnot \omega )\)라고 하면 다음을 얻는다. \[\mathrm{PA} \vdash \omega[p/x_0 ,\, q/x_1 ] .\] 그러나 가정에 의하여 \((\forall x_1 )(\lnot \omega [p/x_0 ])\)는 \(\zeta\)와 같으므로 증명 가능하다. (A5)와 Modus Ponens를 이용하면 다음을 얻는다. \[\mathrm{PA} \vdash (\lnot \omega [p/x_0 ,\, q/x_1 ]) .\] 이것은 Peano 산술이 무모순적이지 않음을 의미하므로, 가정에 모순이다.

이번에는 Peano 산술이 \(\omega\)-무모순이라고 가정하자. 그러면 \((\lnot \zeta )\)는 증명 불가능하다. 이를 증명하기 위해 \((\lnot \zeta )\)가 증명 가능하다고 가정해보자. \((\lnot \zeta )\)는 \[(\lnot (\forall x_1 )(\lnot \omega [p/x_0 ]))\] 를 나타내므로 \((\lnot \omega [p/x_0 ,\, q/x_1 ])\)은 적당한 \(q\)에 대하여 증명 불가능하다. \(\omega\)의 정의에 의하여, 이것은 \(q\)가 \(\phi [p/x_0 ]\)의 증명의 Gödel 수이고 \(p\)가 \(\phi\)의 Gödel 수임을 의미한다. \(p\)의 정의에 의하여 \(\phi\)는 \((\forall x_1 )(\lnot \omega )\)를 나타낸다. 그러므로 \(\phi[p/x_0 ]\)는 \(\zeta\)와 같다. 그러나 \(\zeta\)의 증명은 존재하지 않으므로 이것은 모순이다.

앞서 언급한 바와 같이, 이 결과는 다음과 같이 강화될 수 있다.

정리 2.  Gödel의 불완전성 정리(Incompleteness Theorem).
Peano 산술이 무모순적이면 Peano 산술에서 증명 가능하지도 않고 불가능하지도 않은 문장이 존재한다.

앞의 증명 과정에서 살펴본 논리식 \(\zeta\)처럼, 위 정리에서 '문장'은 자기 자신의 증명 불가능성을 주장하는 문장이다. 정확히 말하자면, 그 문장의 증명의 Gödel 수에 해당하는 자연수는 존재하지 않는다. 그러므로 \(\mathbb{N}\)에서 \(\zeta\)는 참이다. 이로써 Gödel의 불완전성 정리를 변형한 Tarski의 정리를 얻는다.

정리 3.  Tarski의 정리.
Peano 산술이 무모순적이면 \(\mathbb{N}\)에서는 참이지만 Peano 산술에서는 증명 가능하지 않은 문장이 존재한다.

그러므로 Peano의 공리들이 무모순적이라고 가정하면 Peano의 공리들은 불완전하다. 하지만 그 효용성은 훨씬 더 크다. 위 정리는 직후자(successor), 자연수의 합, 곱을 다룰 수 있는 형식계는 동일한 불완전성을 갖고 있음을 보여준다. Gödel 숫자붙이기 과정만 바꾸면 동일한 방법으로 그 결과를 얻을 수 있다.

특히 Gödel의 증명 과정에서 문장 \(\zeta\)를 산술의 새로운 공리로 추가해보자. \(\zeta\)가 \(\mathbb{N}\)에서 참이므로, 만약 \(\zeta\)를 추가하기 전의 공리들이 무모순적이었다면 추가하여 얻은 새로운 공리들도 무모순적이다. 그러나 Gödel의 정리를 다시 적용하면 \(\zeta\)를 추가한 공리들을 이용하여 증명 가능하지도 않고 불가능하지도 않은 새로운 문장 \(\zeta '\)을 얻는다.

놀랍게도 불완전성 정리가 적용되지 않는 자연수계의 공리들의 집합이 존재한다. 즉 \(\mathbb{N}\)에서 참인 문장들의 모임 \(\mathrm{Th}(\mathbb{N} )\)이다. 참인 모든 문장은 \(\mathrm{Th}(\mathbb{N} )\)에서 한 줄짜리 증명을 가진다. 얼핏 보면 이것은 불완전성 정리에 모순인 것처럼 보이지만 그렇지 않다. 형식계의 조건 중에는 각 논리식은 기계적인 절차에 의하여 그것이 공리인지 아닌지 판별할 수 있어야 한다. 앞서 살펴본 증명 과정에서 이것을 상세히 기술하지는 않았지만, 불완전성 정리의 증명에서 주어진 논리식이 공리인지의 여부를 기계적으로 판별할 수 있어야 한다는 사실은 중요한 역할을 한다. 그러므로 자연수계에서 참인 문장들이 모두 기계적인 절차에 의하여 증명될 수는 없다는 결론을 얻는다. 즉 \(\mathrm{Th}(\mathbb{N} )\)은 형식계가 아니다. 이 사실은 비록 Hilbert의 꿈을 무너뜨리기는 했지만 우리에게는 긍정적인 의미로 다가온다. 왜냐하면 수학자들의 컴퓨터로 대체될 수 없다는 것을 의미하기 때문이다.

흥미로운 정리들

Gödel의 증명 과정에서 살펴본 문장 \(\zeta\)는 자연수계와 관련된 '초정리'에서 중요한 역할을 한다. 그러나 산술 체계 밖에서는 Peano 산술에서 \(\zeta\)가 가졌던 흥미로운 특징이 크게 부곽되지는 않는다. 1970년대에 Jeff Paris와 Leo Harrington은 \(\mathbb{N}\)에서는 참이지만 Peano 산술에서는 증명 불가능한 정리를 찾아냈다. 그 정리는 Ramsey의 정리에 바탕을 두고 있으므로, 먼저 Ramsey의 정리부터 살펴보자.

정리 4.  유한 Ramsey 정리.
\(k,\) \(l,\) \(r\)가 양의 정수라고 하자. 그러면 다음 조건을 만족시키는 양의 정수 \(n\)이 존재한다 : 만약 \(n = \left\{0,\, \cdots ,\, n-1 \right\}\)의 부분집합 중 원소가 \(k\)개인 것들이 모두 \(r\)개의 색으로 채색된다면 크기가 \(l\)인 단색(monochromatic) 부분집합, 즉 \(k\)개의 원소를 가진 모든 부분집합이 동일한 색상을 갖는 부분집합이 존재한다.

이 정리는 얼핏 보기에는 Peano 산술로 기술될 수 있는지초가 확실하지 않다. 왜냐하면 이 정리는 부분집합들과 채색들에 대하여 한정사를 사용하고 있기 때문이다. 그러나 다음과 같은 방법을 통해 위 정리를 Peano 산술로 기술할 수 있다. \(n\)의 부분집합 중 원소가 \(k\)개인 것들의 모임으로부터 \(N = \, _n \mathrm{C} _k\)로의 일대일대응이 존재한다. \(r\)개의 색상을 이용한 \(N\)의 채색은 \(r^N\)개의 원소를 가진 집합 \(\left\{0,\, \cdots ,\, r^N -1 \right\}\)에 일대일로 대응된다. 이와 같은 방법으로 위 정리는 Peano 산술로 기술될 수 있다. 더욱이 위 정리는 Peano의 공리를 이용하여 증명 가능하다.

\(\mathbb{N}\)의 유한부분집합 \(X\)에 대하여 \(\lvert X \rvert > \min (X) \)가 성립할 때 \(X\)는 거대하다(large)라고 말하기로 하자. Paris-Harrington의 정리는 다음과 같다.

정리 5.  Paris-Harrington 정리.
\(k ,\) \(l ,\) \(r\)가 양의 정수라고 하자. 그러면 다음 조건을 만족시키는 양의 정수 \(n\)이 존재한다 : 만약 \(n = \left\{ 0 ,\, \cdots ,\, n-1 \right\}\)의 부분집합 중 원소가 \(k\)개인 것들이 \(r\)개의 색으로 채색되면 적어도 크기가 \(l\)인 거대한 단색 부분집합이 존재한다.

이 정리는 유한 Ramsey의 정리보다 강력하다. 왜냐하면 거대한 집합은 찾기가 쉽지 않지 않기 때문이다. 거대한 집합을 찾으려면 그 집합의 원소를 하나 찾아낸 뒤 그것의 크기를 늘려서 거대한 집합을 만들어내야 한다. Paris와 Harrington은 이 정리가 \(\mathbb{N}\)에서는 참이지만 Peano 산술에서 증명 불가능함을 보였다.

위 정리가 \(\mathbb{N}\)에서 참이라는 사실은 다음과 같은 무한 Ramsey 정리로부터 얻어진다.

정리 6.  무한 Ramsey 정리.
\(k,\) \(r\)가 양의 정수라고 하자. 만약 \(\mathbb{N}\)의 부분집합 중 원소가 \(k\)인 것들이 \(r\)개의 색으로 채색된다면 \(\mathbb{N}\)의 무한 단색 부분집합이 존재한다.

증명의 개요. \(k\)에 관한 수학적 귀납법을 사용하자. \(k=1\)인 경우는 비둘기집의 원리에 의하여 증명된다. 즉 \(\mathbb{N}\)의 원소들이 유한 개의 비둘기집합 담겨 있다면 \(\mathbb{N}\)의 원소를 무한히 많이 담고 있는 비둘기집이 존재하게 된다. 이제 정리에서 \(k\)를 \(k-1\)로 바꾼 정리가 참이라고 가정하자. 그리고 \(\mathbb{N}\)의 부분집합 중 원소가 \(k\)개인 것들이 모두 유한 개의 색 \(c_0 ,\) \(\cdots ,\) \(c_{r-1}\)로 채색된다고 가정하자.

증가하는 무한 자연수열 \(x_0 ,\) \(x_1 ,\) \(\cdots\)을 만들고, 감소하는 \(\mathbb{N}\)의 무한 부분집합열 \(X_0 ,\) \(X_1 ,\) \(\cdots\)을 만들며, 색상들의 무한 열 \(c_0 ,\) \(c_1 ,\) \(\cdots\)을 만들되 \(X_i\)의 부분집합 중 \(x_i\)를 원소로 갖고 원소의 수가 \(k\)인 것들이 색상 \(c_i\)를 갖도록 한다.

비둘기집의 원리에 의하여 상수열 \((c_0 ,\, c_1 ,\, \cdots )\)을 얻는다. 이 상수열에 대응하는 부분수열 \((x_0 ,\, x_1 ,\, \cdots )\)이 곧 바라는 단색 집합이 된다.

사실 위 정리는 집합론의 ZFC 공리계를 이용하여 증명될 수 있다. 또한 유한 Ramsey 정리는 위 정리에 일계논리의 긴밀성 정리를 적용하여 얻을 수 있다. 그 방법은 유한 4색 정리로부터 무한 4색 정리를 얻은 것과 비슷하다. [즉 유한 Ramsey 정리가 거짓이라고 가정하자. 그러면 고정된 양의 정수 \(l\)이 존재하여 원소의 개수가 \(l\)인 단색 부분집합을 갖지 않는 임의의 거대한 유한집합의 부분집합 중 원소의 개수가 \(k\)인 것의 채색이 존재한다. 긴밀성 정리에 의하여 앞의 거대한 유한집합과 동일한 성질을 갖는 무한집합이 존재하고 그 무한집합의 부분집합 중 원소의 개수가 \(k\)인 것들의 채색이 존재한다. 이것은 무한 Ramsey 정리에 모순이다.] 비슷한 방법으로 무한 Ramsey 정리로부터 Paris-Harrington 정리를 이끌어낼 수 있다.

이로써 Paris-Harrington 정리가 \(\mathbb{N}\)에서는 참이지만 Peano 산술에서는 증명 불가능하고 ZFC 집합론에서는 증명 가능하다는 사실을 살펴보았다. 자세한 내용은 Paris와 Harrington의 책 『Handbook of Mathematical Logic』의 내용을 참고하기 바란다. Ramsey 정리와 관련된 다양한 논의는 Ronald Graham, Bruce Rothschild, Joel Spencer의 책 『Ramsey Theory』를 참고하기 바란다.

Leave a Reply