같은 논리 규칙을
따르는 두 세계는
크기도 같을까?

같은 문장, 다른 크기의 모형

6. 아래로 향하는 정리는 무엇을 주장하나요?

이제 조건을 붙여 정리를 읽어 봅시다. 사용하는 1차 논리 언어 L에 기호가 가산 개이고, 이 언어로 만든 이론 T에 무한한 모형이 하나라도 존재한다고 합시다. 그러면 T에는 가산 무한 모형도 존재합니다. 이를 하향 뢰벤하임–스콜렘 정리의 기본 형태라고 합니다. 기호가 가산 개라는 것은 관계·함수·상수 기호가 유한 개이거나 자연수로 번호를 매길 수 있을 만큼만 있다는 뜻입니다.

'무한한 모형이 하나라도 있다'는 조건을 확인해야 합니다. T의 유일한 모형이 정확히 학생 세 명으로 이루어진 경우에는 네 명 또는 무한 명의 모형을 강제로 만들 수 없습니다. 하향 정리는 원래 존재하지 않는 무한모형을 만들어 주는 규칙이 아닙니다. 이미 무한한 모형이 있다고 알고 있을 때, 그 이론을 만족하는 가산 무한 모형까지 찾을 수 있다는 주장입니다.

정리에는 더 강한 형태도 있습니다. 원래 모형 M이 무한하고 언어 L이 가산이라면, M의 원소를 일부 골라 M의 1차 논리 문장을 모두 보존하는 가산 무한 부분모형 N을 만들 수 있습니다. 기호 N≺M을 'N은 M의 초등 부분구조'라고 읽습니다. 단순히 N이 M에 포함된다는 뜻을 넘어, N에 속하는 원소들을 이름 붙여 만든 1차 논리식도 N과 M에서 참과 거짓이 같다는 뜻입니다. 뒤에서 그 이유를 살펴보겠습니다.

7. 아무 관계 기호도 없는 세계부터 비교해 봅시다

가장 단순한 언어로 출발하면 정리의 결론을 금방 확인할 수 있습니다. 언어에 =만 있고 별도의 <, +, ∈ 같은 기호가 없다고 합시다. 우리는 이 세계에서 '어떤 두 원소가 같은가', '서로 다른 원소가 있는가'만 질문할 수 있습니다. 자연수 전체를 영역으로 삼아도 되고, 실수 전체를 영역으로 삼아도 됩니다. 원소 수는 크게 다르지만 사용 가능한 질문의 종류는 같습니다.

이론 T∞를 생각합니다. T∞에는 '서로 다른 원소가 적어도 한 개 있다', '적어도 두 개 있다', '적어도 세 개 있다' 같은 문장이 끝없이 들어 있습니다. n을 임의의 양의 정수로 잡으면 다음과 같이 쓸 수 있습니다.

φₙ := ∃x₁ … ∃xₙ ∧₁≤i<j≤n (xᵢ≠xⱼ)

이 식은 '서로 다른 원소를 n개 골라낼 수 있다'는 뜻입니다. T∞는 모든 n에 대한 φₙ을 포함하므로, 원소가 유한한 집합은 T∞의 모형이 될 수 없습니다. 그러나 자연수 전체도, 실수 전체도 이 문장들을 모두 만족합니다. 그래서 같은 이론에 가산 무한 모형과 비가산 모형이 함께 존재한다는 사실을 직접 확인할 수 있습니다.

더 강한 사실도 있습니다. =만 사용하는 언어에서 모든 무한한 순수 집합은 같은 1차 논리 문장들을 만족합니다. '어떤 원소가 누구와 같다'는 비교만으로는 무한 원소의 정확한 크기를 가를 수 없기 때문입니다. 이 결론을 언어에 다른 기호를 추가한 뒤에도 무조건 적용할 수는 없습니다. 언어와 해석을 정하지 않은 채 '자연수와 실수는 논리적으로 똑같다'고 말하면 설명의 범위를 넘어서게 됩니다.

8. 유리수와 실수는 '순서'에 관해 어디까지 같을까요?

이제 =뿐 아니라 <도 허용하겠습니다. 유리수 집합 Q와 실수 집합 R에 통상적인 '작다' 관계를 부여하면 둘 다 다음 규칙을 만족합니다. 첫째, 서로 다른 두 수 가운데 어느 쪽이 작은지 비교할 수 있습니다. 둘째, 모든 수에는 더 작은 수도 있고 더 큰 수도 있습니다. 셋째, x<y인 두 수 사이에는 x<z<y인 또 다른 수 z가 있습니다. 이를 양 끝이 없고 조밀한 선형순서라고 부릅니다.

조밀하다는 말을 '모든 수 사이의 간격이 물리적으로 빽빽하다'는 뜻으로 읽을 필요는 없습니다. 정해진 서로 다른 두 수 사이에 또 다른 수가 있다는 관계의 규칙입니다. 예를 들어 1과 2 사이에 3/2가 있고, 1과 3/2 사이에 5/4가 있습니다. 유리수만으로도 이 규칙을 만족합니다. 실수 역시 그렇습니다.

흥미롭게도 이 순서 언어 {<}에서는 두 구조 (Q,<)와 (R,<)가 모든 같은 1차 논리 문장을 똑같이 참으로 만듭니다. 이를 '초등 동치'라고 합니다. 조밀한 선형순서 이론의 양화사 제거 결과가 이를 정당화합니다. 실수에 있는 √2가 유리수 영역에 없다는 사실은 문제가 되지 않을까요? 이 언어에는 +, ×, '√2'라는 이름이 없습니다. 순서 언어로 직접 지정할 수 있는 관계만 비교하고 있기 때문입니다. 만약 +와 ×를 추가하여 두 구조를 순서체로 비교하면 √2 같은 수의 존재를 가르는 1차 논리 문장을 적을 수 있어 결론이 달라집니다. 모형 비교에는 언제나 '어떤 언어로 질문했는가'가 붙어야 합니다.

존재한다는 문장에 실제 증인 남기기

9. 큰 모형에서 작은 모형을 만들려면 무엇을 남겨야 할까요?

예시를 확인했으니 이제 정리가 왜 성립하는지 살펴봅시다. 무한한 모형 M이 하나 있다고 합시다. M에서 가산 무한 개의 원소를 먼저 고른 집합 A₀를 만듭니다. 이때 '고른 원소만 그대로 남기면 되겠지'라고 생각하기 쉽지만, 그렇게 줄이면 원래 참이던 문장이 거짓이 될 수 있습니다.

가령 M이 '모든 원소 x에는 x와 다른 친구 y가 있다'는 규칙 ∀x∃y(x≠y)을 만족한다고 생각합시다. M에서 학생 한 명만 남기면, 원래 세계에서는 친구가 있던 학생도 남겨 놓은 세계에서는 다른 학생을 찾을 수 없습니다. 또 함수 기호 s가 있다면 남긴 원소 a에 대해 s(a)가 밖으로 빠져나가서는 구조의 함수가 제대로 정의되지 않습니다. 원소를 고른 다음 존재를 보장하던 증인과 함수값도 함께 남겨야 합니다.

여기서 증인이라는 말은 어떤 존재 문장 ∃y φ(y,a)가 참일 때 조건 φ를 실제로 만족시키는 원소 y를 가리킵니다. 학생 a에게 질문할 상대가 있다는 규칙이 참이라면, 그 학생에 대해 실제 질문 상대 한 명을 남기는 식입니다. 한 원소만 예외적으로 처리해서는 충분하지 않습니다. 모든 공식, 모든 현재 원소 매개변수에 대해 필요한 증인을 확보해야 합니다.

10. 참인 '누군가 있다'에 필요한 증인을 차곡차곡 넣습니다

시작 집합 A₀를 확보했다면, A₀의 원소를 매개변수로 사용한 존재 문장들을 살펴봅니다. 예를 들어 M⊨∃y φ(y,a₁,…,aₖ)이고 a₁,…,aₖ가 모두 A₀에 속한다고 합시다. 이 말은 M 안에 그 조건을 만족하는 y가 적어도 하나 있다는 뜻입니다. 그러면 그런 y 가운데 하나를 골라 A₁에 넣습니다. 사용 중인 언어에 함수 기호가 있으면 A₀ 원소들을 함수에 대입한 결과도 A₁에 넣고, 상수 기호가 가리키는 대상 역시 포함합니다.

한 번 추가한 뒤 끝내면 부족합니다. 새로 들어온 증인 y를 매개변수로 한 존재 문장이 참일 수 있고, 그 문장에 필요한 다른 증인 z가 아직 없을 수 있습니다. 그러므로 A₁의 매개변수들에 대해서도 같은 절차를 수행하여 A₂를 만듭니다. 그다음 A₃, A₄, …로 이어 갑니다. 이 작업의 목적은 '모든 원소를 다 저장하는 것'이 아닙니다. 남겨 둔 원소들에 대해 참이라고 말해야 할 존재 조건을 충족시키는 데 필요한 대상만 단계적으로 확보하는 것입니다.

예를 들어 어떤 관계 E가 'x의 후속 담당자는 y다'라고 해석되면, A₀의 a가 갖는 담당자 y를 A₁에 넣고, 새로 들어온 y의 담당자를 A₂에 넣는 식으로 확장할 수 있습니다. 이 작은 이야기는 존재 증인을 계속 추가하는 동작을 설명하는 사례입니다. 실제 정리의 증명에서는 이렇게 눈에 띄는 규칙 몇 개만 다루지 않고, 언어로 쓸 수 있는 모든 존재 공식을 대상으로 합니다.

모든 문장의 참을 보존하는 가산 부분모형

11. 이렇게 계속 늘리는데 왜 여전히 셀 수 있을까요?

여기서 '모든 공식'이라는 말 때문에 집합이 걷잡을 수 없이 커질 것처럼 느껴질 수 있습니다. 가산 언어의 기호들을 유한한 길이로 이어 만든 식 전체는 가산입니다. 길이가 한 개인 식, 길이가 두 개인 식, 길이가 세 개인 식, …을 길이별로 모으면, 각 길이의 가능한 문자열은 가산하고 그 전체 역시 가산하기 때문입니다. 실제 문법에 맞는 공식의 집합은 그 문자열 집합의 일부입니다.

A₀의 원소 수가 가산이면, A₀ 원소로 만든 유한한 매개변수 묶음도 가산 개입니다. 각 공식과 매개변수 묶음에 대해 증인을 한 개씩 선택하면, 추가해야 할 원소도 많아야 가산 개입니다. 따라서 A₁은 가산이고, 같은 이유로 A₂, A₃, …도 가산입니다. 함숫값과 상숫값을 보충해도 여전히 가산입니다.

모든 단계에서 골라낸 원소를 하나로 합칩니다.

N = A₀ ∪ A₁ ∪ A₂ ∪ A₃ ∪ ···

가산 개의 가산집합을 합친 집합은 표준적인 집합론의 배경 가정 아래에서 가산입니다. 처음에 A₀를 가산 무한 집합으로 잡았으므로 N 역시 가산 무한입니다. 중요한 점은 '무한히 많은 단계를 진행했으니 비가산이 된다'는 주장이 성립하지 않는다는 것입니다. 한 단계씩 순번을 붙일 수 있고, 각 단계의 원소에도 순번을 붙일 수 있다면 단계 번호와 원소 번호의 쌍을 이용해 전체를 열거할 수 있습니다.

12. 작은 세계에서도 모든 1차 논리 문장의 참을 보존할 수 있을까요?

이제 N의 역할을 확인해야 합니다. N은 M에서 고른 원소들로 만든 부분구조이므로 처음부터 모든 사실을 보존한다고 말할 수는 없습니다. 그러나 방금 만든 N은 존재 공식에 필요한 증인을 빠짐없이 갖추었습니다. N의 원소 a₁,…,aₖ에 대해 M에서 ∃y φ(y,a₁,…,aₖ)가 참이라면, 그 매개변수들은 어떤 유한 단계 Aₙ에 모두 들어 있습니다. 다음 단계 Aₙ₊₁을 만들 때 해당 존재 공식의 증인을 선택했으므로 N에도 그런 y가 들어 있습니다.

이 성질에 함수·관계 기호의 해석을 제대로 제한한다는 조건을 더하면 타르스키–보트(Tarski–Vaught) 판정 기준을 적용할 수 있습니다. 이 기준은 N에 있는 매개변수들로 만든 모든 1차 논리식의 참과 거짓이 N과 M에서 같다는 사실을 보장합니다. '작은 세계'에서 누군가가 존재한다고 말할 때 그 사람을 실제로 찾을 수 있도록 충분히 보충한 것입니다.

기호로는 다음과 같이 정리합니다.

N ≺ M, |N| = ℵ₀

여기서 왼쪽 식은 N이 M의 초등 부분구조라는 뜻이고, 오른쪽 식은 N의 원소를 자연수 순서대로 셀 수 있다는 뜻입니다. 특히 M이 이론 T를 만족하면 N도 T를 만족합니다. 여기서 역사적 스콜렘의 증명과 구분해야 할 점이 있습니다. 우리가 방금 따라온 증인 확장과 초등 부분구조의 설명은 현대 모형이론의 표준적인 증명 개요이며, 1915년 또는 1920년 논문의 페이지를 그대로 번역한 것이 아닙니다.

콤팩트성으로 원하는 크기까지 확장하기

13. 위로 향하는 정리는 모형을 얼마나 크게 만들 수 있나요?

하향 정리가 작은 모형의 존재를 말한다면, 상향 뢰벤하임–스콜렘 정리는 충분히 큰 모형들의 존재를 말합니다. 가산 언어의 1차 논리 이론 T에 무한한 모형이 있으면, 어떤 무한한 기수 κ를 정해도 원소 수가 정확히 κ개인 T의 모형이 존재합니다. ℵ₀처럼 자연수로 셀 수 있는 크기부터 더 큰 무한의 크기까지 모두 포함됩니다. 원래 모형이 비가산이었다고 해서 가산 모형이 사라지거나, 원래 모형이 가산이었다고 해서 비가산 모형이 불가능해지는 것이 아닙니다.

어떻게 그런 모형을 만들까요? 증명의 핵심 생각은 κ개만큼 새로운 이름 cᵢ를 도입하고, 서로 다른 두 이름은 서로 다른 원소를 가리키게 한다는 요구 cᵢ≠cⱼ를 추가하는 것입니다. 요구를 유한 개만 선택하면, 이미 무한한 모형이 있으므로 서로 다른 원소를 충분히 골라 만족시킬 수 있습니다. 콤팩트성 정리에 따라 이러한 유한한 요구들이 모두 만족 가능하면 전체 요구를 만족하는 모형도 존재합니다. 이렇게 만든 모형의 크기는 적어도 κ입니다. 언어의 기호 수가 κ 이하라는 조건에서 하향 정리를 다시 이용하면 원소 수가 정확히 κ인 모형을 얻을 수 있습니다.

콤팩트성은 제09회 괴델 완전성 정리와도 연결됩니다. 여기서 '콤팩트하다'는 말은 그림이나 자료를 압축한다는 뜻이 아니라, 문장 집합 전체의 만족 가능성을 모든 유한 부분집합의 만족 가능성과 연결하는 논리적 성질입니다. 상향 정리와 하향 정리의 증명 전략이 다른 이유도 이 지점에서 드러납니다.

이 정리를 적용하기 전에 확인할 조건

14. 정리의 조건을 지우면 어떤 말이 잘못될까요?

첫째, '언어의 기호가 가산 개'라는 조건이 빠지면 가산 무한 모형을 기대할 수 없습니다. 예를 들어 서로 다른 대상들을 가리키는 상수 기호를 비가산 개 준비하고, 두 상수가 가리키는 대상은 항상 서로 다르다는 문장을 이론에 넣으면, 그 이론을 만족하는 모형에는 처음부터 비가산 개의 원소가 필요합니다. 따라서 하향 정리의 일반적인 형태에서는 얻을 부분모형의 크기를 언어의 기호 수와 함께 계산합니다.

둘째, 유한 모형만 있는 이론에 무한 모형을 강요할 수 없습니다. ∃x∃y(x≠y ∧ ∀z(z=x∨z=y))라는 문장은 영역의 원소가 정확히 두 개라는 뜻입니다. 이 문장의 모형을 셋이나 무한히 많은 원소로 늘리면 원래 문장은 거짓이 됩니다. 상향 정리에 무한 모형의 존재를 조건으로 붙이는 까닭입니다.

셋째, '작은 모형과 큰 모형이 같다'는 표현은 주의해서 사용해야 합니다. 이 정리는 모든 모형이 서로 동형이라는 주장이 아닙니다. 가산 모형과 비가산 모형은 원소 수부터 다르므로 일대일 대응으로 구조를 완전히 일치시킬 수 없습니다. 그러나 같은 1차 논리 이론의 문장들을 모두 만족할 수 있습니다. '같은 문장들이 참이다'와 '두 구조가 동형이다'를 구별해야 결과가 정확해집니다.

넷째, 1차 논리의 정리를 모든 고차 논리와 모든 수학적 기술 방식에 그대로 옮길 수 없습니다. 예를 들어 실수의 순서에 대해 '상계가 있는 비어 있지 않은 모든 부분집합에는 최소상계가 있다'는 성질은 부분집합 전체를 양화하는 표준적인 2차 논리 표현으로 나타낼 수 있습니다. 이 표현은 실수의 순서와 유리수의 순서를 가르는 중요한 특성을 담습니다. 어떤 대상과 어떤 집합들을 양화 범위에 포함했는지를 먼저 확인해야 합니다.