일계논리의 긴밀성과 Löwenheim-Skolem 정리

By | August 19, 2017

긴밀성 정리와 Löwenheim-Skolem 정리는 일계논리에서 핵심적인 역할을 하는 정리이다. 이들 두 정리는 모두 Gödel의 불완전성 정리로부터 나온다. 여기서는 Gödel의 불완전성 정리를 도입하는 대신 긴밀성 정리와 Löwenheim-Skolem 정리의 증명을 간략하게 살펴보기로 한다. 또한 이 글에서는 일계논리언어가 가산인 경우로 논의를 한정한다.

정리 1.  일계논리의 긴밀성.
\(\varSigma\)가 가산인 일계논리언어의 문장의 모임이고 \(\varSigma\)의 임의의 유한부분집합이 모델을 가지면 \(\varSigma\)도 모델을 가진다.

증명. 완전성 정리에 의하여 \(\varSigma\)가 모델을 가질 필요충분조건은 \(\varSigma\)가 완전한 것, 즉 \(\varSigma\)로부터 모순이 유도되지 않는 것이다.

결론에 반하여 \(\varSigma\)가 문장들의 집합이고 모델을 갖지 않는다고 가정하자. 그러면 \(\varSigma\)로부터 모순을 유도하는 증명이 존재한다. 증명의 각 줄은 공리이거나, \(\varSigma\)의 원소이거나, 증명의 앞 줄에 추론 규칙을 적용하여 얻어지는 것이다. 증명은 유한 개의 논리식을 나열한 것이므로 \(\varSigma\)의 원소 중 유한 개만 증명에 나타난다. 즉 \(\varSigma\)의 유한부분집합으로부터 모순을 유도하는 증명을 얻는다. 이것은 \(\varSigma\)의 유한부분집합이 모델을 갖지 않는다는 것을 뜻하므로 가정에 위배된다.

그러므로 \(\varSigma\)는 모델을 가진다.

정리 2.  Löwenheim-Skolem 정리.
\(\varSigma\)가 가산인 일계논리언어의 문장의 모임이고 모델을 가지면 \(\varSigma\)는 유한이거나 가산인 모델을 가진다.

증명의 개요. \(\varSigma\)가 문장들의 모임이고 모델을 갖는다고 하자. 그러면 \(\varSigma\)는 무결하다. 완전성 정리의 증명에서처럼 세 단계를 통해 \(\varSigma\)의 모델을 구성한다.

  • \(\varSigma\)에 가산 개의 새로운 상수기호를 추가하여 완전한 집합 \(T\)를 구성한다. 이때 새로 구성된 언어와 \(T\)는 여전히 가산이다.
  • 언어의 닫힌항들로 구성된 구조 \(N\)을 구성한다. 이때 \(N\)도 여전히 가산이다.
  • \(N\)에서 관계 \(\sim\)을 '\(t_1 \sim t_2\)일 필요충분조건은 \((t_1 = t_2 )\)가 \(T\)에서 증명 가능한 것이다'라고 정의한다. 그러면 \(\sim\)은 동치관계이다. 다음으로 상집합 \(N / \sim\)을 취하여 구조를 만든다. 그러면 이 구조는 가산이고 \(T\)의 모델이며 \(\varSigma\)의 모델이 된다.

이로써 \(\varSigma\)의 가산인 모델을 구성하였다.

사실 긴밀성 정리와 Löwenheim-Skolem 정리에서 언어가 가산이라는 조건을 기호의 집합이 정렬 가능하다는 조건으로 바꾸어도 여전히 두 정리는 유효하다. 이때 증명 과정은 초한귀납법을 사용하게 된다.

두 정리는 일계논리에서 다양하게 활용된다. 예컨대 긴밀성 정리는 다음과 같은 Upward Löwenheim-Skolem 정리를 증명하는 데에 사용된다.

정리 3.  Upward Löwenheim-Skolem 정리.
\(\varSigma\)가 문장의 집합이고 \(X\)가 무한인 정렬집합이라고 하자. 또한 \(\varSigma\)가 무한 모델을 가진다고 하자. 그러면 \(\varSigma\)는 \(X\)보다 더 큰 모델 \(M\)을 가진다. 즉 \(X\)로부터 \(M\)으로의 일대일 함수가 존재하는 \(\varSigma\)의 모델 \(M\)이 존재한다.

위 정리는 \(\varSigma\)가 무한 모델을 가지면 \(\varSigma\)는 임의로 큰 기수를 갖는 모델을 가진다는 뜻이다. 특히 서수는 무한히 많이 존재하므로 \(\varSigma\)가 무한 모델(원소가 무한인 모델)을 가지면 \(\varSigma\)의 모델의 수는 무한이 된다.

정리 3의 증명. \(X\)와 일대일 대응되는 상수기호들의 집합 \(\left\{ c(x) \,\vert\, x \in X \right\}\)을 언어에 추가하여 확장하고, 서로 다른 임의의 \(x,\,y\in X\)에 대하여 \(( c(x) \ne c(y))\)인 모든 문장들의 모임 \(T\)를 \(\varSigma\)에 추가한다. 이제 \(N\)이 \(\varSigma\)의 모델이라고 하자. 새로 추가된 문장들의 유한집합이 모두 참이 되도록 \(N\)의 상수기호에 값매김을 준다. 그러면 \(\varSigma \cup T\)의 임의의 유한부분집합은 모델을 가진다. 일계논리의 긴밀성 정리에 의하여 \(\varSigma \cup T\)는 모델을 가진다. 그 모델을 \(M\)이라고 하자. 명백히 \(M\)은 \(\varSigma\)의 모델이며, 대응 \(x \mapsto c(x)\)는 \(X\)로부터 \(M\)으로의 일대일 함수가 된다.

긴밀성 정리는 유한 4색 정리로부터 무한 4색 정리를 증명하는 데에도 사용될 수 있다. [4색 정리와 관련된 용어는 이전 글을 참고하기 바란다.]

정리 4.  평면지도의 4색 정리.
임의의 평면지도를 채색하는 데에는 4가지 색이면 충분하다.

증명. 지도 \(M\)이 주어졌다고 하자. 지도에서 국가의 수는 가산이다. 왜냐하면 각 국가는 유리수 좌표인 점을 원소로 갖기 때문이다. 이제 일계논리언어를 구성하자. 각 국가 \(C_i\)에 대하여 상수기호 \(c_i\)를 배정한다. 그리고 4개의 일항관계기호 \(K_1 ,\) \(K_2 ,\) \(K_3 ,\) \(K_4\)를 생각한다. 또한 \(\varSigma\)는 다음과 같은 문장으로 이루어져 있다고 하자.

  • 각 국가 \(C_i\)에 대하여 \(K_1 (c_i ),\) \(K_2 (c_i ),\) \(K_3 (c_i ),\) \(K_4 (c_i )\) 중 딱 하나가 성립한다.
  • 자명하지 않은 경계를 갖는 두 국가 \(C_i\)와 \(C_j\), 그리고 임의의 \(k \in \left\{ 1,\,2,\,3,\,4\right\}\)에 대하여 \(\lnot (K_k (c_i )\wedge K_k (c_j ))\)가 성립한다.

\(K_k (c_i )\)가 성립할 때 국가 \(C_i\)가 \(k\)번째 색을 가진다는 관점에서 \(\varSigma\)의 모델은 주어진 지도의 채색이 된다. 그러므로 \(\varSigma\)의 모델을 구성하면 증명이 완료된다.

\(\varSigma\)의 유한부분집합 \(\varSigma_0\)를 생각하자. \(\varSigma_0\)의 문장은 유한 개의 상수기호 \(c_i\)를 포함한다. \(\varSigma_0\)에 포함되는 상수기호가 나타내는 국가로 구성된 지도 \(M_0\)를 생각하자. 그러면 \(M_0\)는 유한 4색 정리에 의하여 4가지 색으로 채색된다. 그러므로 \(\varSigma_0\)는 모델을 가진다. 그런데 긴밀성 정리에 의하여 \(\varSigma\) 또한 모델을 가진다. 따라서 \(M\) 또한 4색으로 채색된다.

Löwenheim-Skolem 정리는 긴밀성 정리와는 다른 상황에서 사용된다. 예컨대 모델이 실수계 \(\mathbb{R}\) 뿐인 일계논리 공리나 모델이 유클리드 평면 뿐인 일계논리 공리가 존재하지 않음을 증명하는 데에 사용된다. 왜냐하면 이들 공리는 가산인 모델을 가지게 되기 때문이다. 또한 Löwenheim-Skolem 정리는 Skolem 역리를 증명하는 데에도 사용된다.

Leave a Reply