일계논리의 콤팩트성은 무한한 문장 집합의 만족 가능성을 그 유한한 부분들만으로 판정할 수 있다는 정리이다.
정리 17.1. (일계논리의 콤팩트성)
\(\mathcal L\)이 가산 일계논리언어이고 \(\varSigma\)가 \(\mathcal L\)-문장들의 집합이면 다음은 서로 동치이다.
- \(\varSigma\)는 만족 가능하다.
- \(\varSigma\)의 모든 유한부분집합은 만족 가능하다.
증명 (1)에서 (2)는 자명하다. 반대로 모든 유한부분집합이 만족 가능하다고 하자. \(\varSigma\)가 무모순이 아니면 어떤 문장 \(\phi\)에 대해 \[ \varSigma\vdash\phi \quad\text{와}\quad \varSigma\vdash\neg\phi \] 인 유한한 두 증명이 존재한다. 두 증명에서 실제로 사용된 가정들을 모두 모으면 유한부분집합 \(\varSigma_0\subseteq\varSigma\)를 얻고, \(\varSigma_0\)도 모순적이다. 건전성 정리에 의해 \(\varSigma_0\)는 만족 가능하지 않아 가정과 모순이다. 따라서 \(\varSigma\)는 무모순이고, 완전성 정리에 의해 만족 가능하다.
콤팩트성의 대표적인 응용은 “임의로 큰 유한 모형”에서 실제 무한 모형을 만드는 것이다.
정리 17.2. (무한 모형의 존재)
\(\mathcal L\)이 가산 언어이고 \(T\)가 \(\mathcal L\)-문장들의 집합이라고 하자. 임의의 양의 정수 \(n\)에 대해 원소가 적어도 \(n\)개인 \(T\)의 모형이 존재하면 \(T\)는 무한 모형을 가진다.
증명 \(\sigma_n\)을 “서로 다른 원소가 적어도 \(n\)개 존재한다”는 문장 \[ (\exists x_1)\cdots(\exists x_n) \bigwedge_{1\le i<j\le n}x_i\ne x_j \] 이라고 하자. 집합 \[ T^*=T\cup\{\sigma_n\mid n\ge1\} \] 을 생각한다.
\(T^*\)의 임의의 유한부분집합 \(\Delta\)를 잡자. \(\Delta\)에 \(\sigma_n\)이 하나라도 나타나면 그 첨자들의 최댓값을 \(N\)이라 하자. 가정에 의하여 원소가 적어도 \(N\)개인 \(T\)의 모형이 존재하고, 이 모형은 \(\Delta\)를 만족시킨다. \(\Delta\)에 \(\sigma_n\)이 하나도 나타나지 않으면 원소가 적어도 하나인 \(T\)의 모형을 택하면 된다. 따라서 \(T^*\)의 모든 유한부분집합은 만족 가능하다.
콤팩트성 정리에 의해 \(T^*\)는 모형을 갖는다. 이 모형은 모든 \(\sigma_n\)을 만족시키므로 무한하다.
문제 17.1. 정리 17.2에서 사용한 문장 \(\sigma_n\)에 대하여 다음을 답하시오.
- \(\sigma_2,\sigma_3,\sigma_4\)를 \(\bigwedge\) 기호를 쓰지 않고 풀어 쓰시오.
- 모든 \(n\ge1\)에 대하여 \(\sigma_{n+1}\models\sigma_n\)임을 보이시오.
- 한 구조가 모든 \(\sigma_n\)을 만족시키면 그 영역이 무한임을 정의에서 직접 보이시오.
문제 17.2. \(T_{\mathrm{grp}}\)를 14장에서 적은 군 공리들의 집합이라고 하자. 임의의 양의 정수 \(n\)에 대하여 \(n\)개의 원소를 갖는 순환군이 존재한다는 사실을 사용하자.
- 정리 17.2의 가정이 \(T_{\mathrm{grp}}\)에 대해 성립함을 설명하시오.
- 콤팩트성으로부터 \(T_{\mathrm{grp}}\)가 무한 모형을 가짐을 결론내리시오.
- 이 논증에서 각 \(\sigma_n\)이 하는 역할을 설명하시오.
문제 17.3. 언어 \(\mathcal L=\{0,S,<\}\)에서 \[ \mathcal N=(\mathbb N,0,S,<) \] 을 생각하고 \[ \overline n=S^n(0) \] 으로 쓰자. 새 상수기호 \(c\)를 추가한 언어에서 \[ T=\operatorname{Th}(\mathcal N)\cup\{\overline n<c\mid n\in\mathbb N\} \] 로 두자.
- \(T\)의 임의의 유한부분집합이 만족 가능함을 보이시오. 이때 \(c\)를 \(\mathcal N\)의 어떤 원소로 해석하면 되는지 설명하시오.
- 콤팩트성 정리를 적용하여 \(T\)의 모형 \(\mathcal M\)이 존재함을 보이시오.
- \(\mathcal M\)에서 \(c^{\mathcal M}\)이 모든 \(\overline n^{\mathcal M}\)보다 큰 원소임을 보이시오. 왜 이 모형이 원래의 \(\mathcal N\)과 동형일 수 없는가?
문제 17.4. 등호만 있는 일계논리언어를 생각하자.
- \[ T_{\infty}=\{\sigma_n\mid n\ge1\} \] 의 모형이 정확히 무한한 구조들임을 보이시오.
- 유한한 구조들만을, 그리고 모든 유한한 구조를 정확히 모형으로 갖는 문장 집합 \(T_{\mathrm{fin}}\)이 존재한다고 가정하자. \(T_{\mathrm{fin}}\cup T_{\infty}\)의 모든 유한부분집합이 만족 가능함을 보이시오.
- 콤팩트성 정리를 사용하여 (2)의 가정이 모순임을 보이시오. 따라서 “영역이 유한하다”는 성질은 일계논리의 문장 집합을 사용하여 공리화할 수 없음을 결론내리시오.
일계논리의 또 다른 중요한 성질은 뢰벤하임-스콜렘 정리이다. 먼저 가산 언어에서 필요한 형태를 보자.
정리 17.3. (가산 모형 정리)
가산 일계논리언어의 만족 가능한 문장 집합은 원소가 유한 개이거나 가산무한 개인 모형을 가진다.
증명 완전성 정리의 항 모형 구성에서 확장된 언어는 가산이고, 유한 문자열인 닫힌항도 가산 개뿐이다. 항 모형의 영역은 닫힌항들의 동치류로 이루어지므로 많아야 가산이다.
정리 17.4. (뢰벤하임-스콜렘 정리: 가산 언어의 이론형)
가산 일계논리언어의 문장 집합 \(T\)가 무한 모형을 가지면 \(T\)는 가산무한 모형을 가진다.
증명 위 증명에서 사용한 문장 \(\sigma_n\)들을 모두 추가한 \[ T^*=T\cup\{\sigma_n\mid n\ge1\} \] 을 생각한다. 주어진 무한 모형이 \(T^*\)를 만족시키므로 \(T^*\)는 만족 가능하다. 정리 17.3에 의해 \(T^*\)는 많아야 가산인 모형을 가지며, 모든 \(\sigma_n\)을 만족시키므로 유한할 수 없다. 따라서 가산무한이다.
일반적인 뢰벤하임-스콜렘 정리는 언어의 크기가 임의의 기수일 때도 성립한다. 특히 선택공리와 임의 크기의 언어에 대한 콤팩트성 정리를 사용하면 다음 위방향 형태를 얻는다.
정리 17.5. (위방향 뢰벤하임-스콜렘 정리)
일계논리 이론 \(T\)가 무한 모형을 가지면, 충분히 큰 임의의 무한 기수 \(\kappa\)에 대해 \(T\)는 기수가 적어도 \(\kappa\)인 모형을 가진다. 더 정밀하게는 표준적인 일반형에서 \[ \kappa\ge\max\{|\mathcal L|,\aleph_0\} \] 이면 기수가 \(\kappa\)인 모형을 얻을 수 있다.
위 정리의 표준 증명에서는 \(\kappa\)개의 새 상수기호 \(c_\alpha\)를 추가하고 \[ c_\alpha\ne c_\beta \] 라는 문장들을 넣은 뒤 일반형 콤팩트성 정리를 적용한다. 정확히 기수 \(\kappa\)인 모형을 얻는 마지막 단계에는 일반형 아래방향 뢰벤하임-스콜렘 정리를 함께 사용한다. 이 일반형들의 완전한 증명은 이 책의 범위를 넘으므로 여기서는 사용하지 않는다.
이 결과들은 일계논리의 표현력에 본질적인 한계가 있음을 보여준다. 예를 들어 가산 언어로 \(\mathbb R\)을 기술하는 일계논리 이론이 무한 모형을 가진다면 가산무한 모형도 가지므로, \(\mathbb R\)과 동형인 구조만을 유일한 모형으로 갖는 일계논리 이론은 존재할 수 없다. 이 현상은 일계논리의 약점인 동시에, 매우 강한 일반 모형이론을 가능하게 하는 특징이기도 하다.
문제 17.5. 유한한 언어 \[ \mathcal L=\{0,1,+,\cdot,<\} \] 에서 실수의 순서체 구조 \[ \mathcal R=(\mathbb R,0,1,+,\cdot,<) \] 를 생각하고 \(T=\operatorname{Th}(\mathcal R)\)로 두자.
- 모든 \(n\ge1\)에 대해 \(\sigma_n\in T\)임을 설명하시오.
- 가산 모형 정리를 사용하여 \(T\)가 가산무한 모형 \(\mathcal M\)을 가짐을 보이시오.
- \(\mathcal M\)과 \(\mathcal R\)이 동형일 수 없는 이유를 설명하시오.
- 그럼에도 \(\mathcal M\models T\)이므로 \(\mathcal M\)은 \(\mathcal R\)에서 참인 모든 \(\mathcal L\)-문장을 만족시킨다. 이 사실이 가산 언어의 일계논리 이론을 사용하여 \(\mathcal R\)을 동형까지 유일하게 규정할 수 없다는 결론과 어떻게 연결되는지 설명하시오.