일계논리와 범주

By | August 20, 2017

수학의 분야 중에서는 일계논리만으로 그 분야를 논하기에 충분한 경우가 있고, 그렇지 않은 경우도 있다. 예컨대 군론(group theory)은 일계논리만으로 다룰 수 있지만 위상수학은 일계논리만으로는 직접 다룰 수 없다. 그렇다면 자연스럽게 다음과 같은 의문이 생긴다.

어떤 구조가 일계논리의 문장으로 다루어지기에 충분한가?

이를 논하기 위해 몇 가지 개념을 도입해야 한다. 두 \(\mathcal{L}\)-구조 \(M\)과 \(N\) 사이의 동형사상(isomorphism)이라 함은 다음 조건을 만족시키는 일대일대응 \(\phi\)를 의미한다.

  • 임의의 \(n\)항관계기호 \(R\)와 \(a_1 ,\) \(a_2 ,\) \(\cdots ,\) \(a_n \in M\)에 대하여, \(R ( a_1 ,\, a_2 ,\, \cdots ,\, a_n )\)이 \(M\)에서 성립할 때마다 \(R(\phi (a_1 ) ,\, \phi (a_2 ) ,\, \cdots ,\, \phi (a_n ))\)이 \(N\)에서 성립한다.
  • 임의의 \(n\)항함수기호 \(f\)와 \(a_1 ,\) \(a_2 ,\) \(\cdots ,\) \(a_n \in M\)에 대하여, \(f(\phi (a_1 ) ,\, f(\phi (a_2 ) ,\, \cdots ,\, \phi (a_n )) =\)\(\phi (f(a_1 ,\, a_2 ,\, \cdots ,\, a_n ))\).
  • 임의의 상수기호 \(c\)에 대하여 \(\phi (c) = c \).

마지막 조건은 \(M\)에서 \(c\)를 해석한 원소를 \(N\)에서 \(c\)를 해석한 원소로 대응시킨다는 의미이다. 이것은 마치 군준동형사상이 \(0\)을 \(0\)에 대응시키는 것과 비슷하다. [그러나 두 \(0\)은 서로 다른 군의 원소이다.]

수학의 여느 분야에서와 마찬가지로 두 구조가 동형일 때에는 두 구조를 완전히 같은 것으로 간주한다. 속성 \(\mathrm{P}\)를 가진 두 구조가 서로 동형일 때, '속성 \(\mathrm{P}\)는 구조를 특성화한다(characterize)'라고 말한다.

\(M\)이 유한인 경우 \(M\)의 모든 구성 요소에 대하여 논할 수 있다. 즉 모든 원소에 이름을 붙이고, 모든 관계와 모든 함수에 각각 인수를 대입하는 경우의 수를 모두 따져볼 수 있다. 특히 언어가 논리기호가 아닌 기호를 유한 개만 가지고 있다면 그 언어는 유한 개의 문장의 집합에 의하여 특성화된다.

그러나 \(M\)이 무한인 경우 일계논리의 문장의 집합으로 그것을 특성화할 수 없다. 심지어는 문장의 집합이 무한인 경우까지 고려해도 그렇다. [Upward Löwenheim-Skolem 정리에 의하여 \(M\)의 모델은 임의로 큰 모델을 가지기 때문이다.]

일계논리언어 \(\mathcal{L}\) 위에서의 구조 \(M\)이 가산범주적이다(countably categorical) 또는 \(\omega\)-범주적이다는 것은 \(\mathcal{L}\) 위에서 가산 구조가 \(M\)으로서의 동일한 일계논리 문장을 만족시킬 때마다 \(M\)과 동형이 됨을 의미한다.

직관적으로 \(M\)이 가산범주적이라는 것은 일계논리공리들의 집합이 존재하여 이 공리들의 임의의 가산 모델이 \(M\)과 동형이 되는 것을 뜻한다.

그 대표적인 예로 \(\mathbb{Q}\)에 대한 칸토어의 정리를 들 수 있다.

정리 1. 순서집합 \(\mathbb{Q}\)는 가산범주적이다. 즉 가산인 전순서집합 \((X,\, < )\)가 조밀하고 최대원소와 최소원소를 갖지 않으면 \(X\)는 \(\mathbb{Q}\)와 순서동형이다.

흥미롭게도 가산범주적 성질은 대칭적(symmetry condition)이다. \(M\)이 집합 \(X\) 위에서의 \(\mathcal{L}\)-구조라고 하자. 이때 \(M\)으로부터 \(M\)으로의 동형사상을 \(M\)의 자기동형사상(automorphism)이라고 부른다. \(M\)의 자기동형사상들의 모임은 \(X\)의 치환군을 형성하는데, 이 치환군을 \(M\)의 자기동형사상군(automorphism group)이라고 부르고 \(\mathrm{Aut}(M)\)으로 나타낸다.

\(X\) 위의 임의의 치환군 \(G\)는 \(X\)를 궤도(orbit)로 분할한다. 즉 \(X\)의 두 원소가 동일한 궤도에 있다는 것은 \(G\)의 적당한 치환이 한 원소를 다른 원소에 대응시키는 것으로 정의한다. 이러한 관계는 동치관계이며, 이 동치관계에 의한 \(X\)의 동치류가 곧 궤도가 된다. 또한 \(n\)이 자연수일 때 \(X\) 위의 임의의 치환군은 \(X^n\) 위의 작용을 유도한다. 이 작용은 \(n\)-순서쌍에 좌표별로 작용한다. \(X\) 위의 치환군 \(G\)가 Oligomorphic 군이라는 것은 각 \(n\)에 대하여 \(X^n\) 위의 궤도의 개수가 유한인 것을 의미한다.

이제 비로소 서두에서 제시한 질문의 답을 진술할 준비가 되었다.

정리 2.  Engeler, Ryll-Nardzewski, Svenonius의 정리.
가산 구조 \(M\)이 가산범주적일 필요충분조건은 그것의 자기동형군이 Oligomorphic 군인 것이다.

여기서는 이 정리의 증명을 기술하지는 않겠다. 이 정리를 증명할 때 가장 어려운 부분은 완전성 정리를 증명할 때와 비슷하다. 또한 \(\mathrm{Aut}(M)\)이 Oligomorphic 군이 아닌 경우 \(M\)의 이론의 가산 모델 중 서로 동형이 아닌 것을 두 개 구성해야 한다.

순서집합 \(\mathbb{Q}\)를 살펴봄으로써 위 정리의 내용을 음미해 보자.

\(\mathbb{Q}\)에서 공집합이 아닌 임의의 두 구간은 서로 동형이다. 서로 다른 유리수들을 좌표로 갖는 두 \(n\)-순서쌍 \((a_1 ,\, a_2 ,\, \cdots ,\, a_n ),\) \((b_1 ,\, b_2 ,\, \cdots ,\, b_n )\)에 대하여 좌표성분의 순서를 바꿈으로써 \(i < j\)일 때마다 \(a_i < a_j ,\) \(b_i < b_j\)가 성립하도록 할 수 있다. 그러면 \((a_i ,\, a_{i+1} )\)을 \((b_i ,\, b_{i+1} )\)에 대응시키고, \((-\infty ,\,a_1 )\)을 \((-\infty ,\,b_1 )\)에 대응시키며, \((a_n ,\,\infty )\)를 \((b_n ,\, \infty )\)에 대응시킬 수 있다. 이러한 대응을 하나로 합친 대응은 \(\mathbb{Q}\)의 자기동형사상이며 \(n\)-순서쌍 \((a_i )_{i=1}^{n}\)을 \((b_i )_{i=1}^{n}\)에 대응시킨다. 마찬가지로 \(n\)-순서쌍의 좌표의 순서를 재배열할 때마다 하나의 궤도가 결정된다. 따라서 \(\mathrm{Aut}(\mathbb{Q} )\)는 서로 다른 좌표로 이루어진 \(n\)-순서쌍 위에서 정확히 \(n ! \)개의 궤도를 가진다. 그러므로 \(\mathrm{Aut}(\mathbb{Q} )\)는 Oligomorphic 군이다.

정리 1에서 살펴본 바와 같이 \(\mathbb{Q}\)는 가산범주적이므로, 지금까지의 논의를 통해 순서집합 \(\mathbb{Q}\)에 대해서 정리 2가 성립함을 알 수 있다.

Leave a Reply