준비운동
논리학이 생소한 독자를 위해 기본 개념을 간단히 설명하고 시작하겠다. 이것은 본론에 없는 내용이며, 논리학에 익숙하다면 넘겨도 괜찮다.
가산(countable): 자연수 집합보다 크기가 크지 않은 집합을 가산이라고 하고, 자연수 집합보다 크기가 큰 집합을 비가산(uncountable)이라고 한다. 자세한 설명은 ‘1. 배경’의 첫 두 문단을 참조.
1차 논리(first order logic): 변수, 함수, 술어, 논리 연산자(∧, ∨, ¬, →, =), 그리고 양화사(∃, ∀)를 사용하는 논리 체계. 단, 양화사는 변수 앞에서만 사용할 수 있다. 예를 들어 ∀x P(x, f(x))는 1차 논리 문장이지만 ∀x ∃P P(x)는 1차 논리 문장이 아니며 2차 논리 문장이다.
문장(sentence): 자유변수가 없는 논리식. 예를 들어 ∀x ∃y P(x, y)는 문장이지만 ∀x P(x, y)는 문장이 아니다.
이론(theory): 하나 이상 문장들의 묶음. 이론은 무한히 많은 문장을 가질 수 있다.
구조(structure): 문장과 이론은 그저 기호일 뿐이다. 문장이 의미를 가지기 위해서는 변수가 가질 수 있는 값의 집합과 더불어 각 함수 및 술어 기호의 의미를 명시해야 한다. 이 정보를 명시하는 명세서를 구조라고 한다. 변수가 가질 수 있는 값의 집합을 그 구조의 정의역(universe)이라고 부른다.
예를 들어 다음 두 개의 문장으로 이루어진 이론 T = { ψ, φ }를 생각해 보자.
ψ := ∀x ∀y P(x, f(x, y))
φ := ∀x P(x, x)
T는 함수 f와 술어 P를 사용한다. 따라서 T의 구조는 변수가 가질 수 있는 값의 집합과 더불어 f와 P의 의미를 명시해야 한다.
한 가지 가능한 구조는 다음과 같다.
A = < N, +, ≤ >
즉, 구조 A에서 정의역은 자연수 집합 N이며 f는 덧셈을, P는 ‘작거나 같다’를 의미하게 된다. 이에 따라 논리식 ψ는 ‘임의의 자연수 x, y에 대하여 x ≤ x + y이다’라는 의미이며, 참이다. 한편 다음 구조를 고려해 보자.
B = < Z, +, ≤ >
구조 B에서 ψ는 참이 아니다. 왜냐하면 y가 음수일 수 있기 때문이다. 이것은 문장의 참 · 거짓 여부가 모델에 따라서 달라질 수 있음을 보여준다.
모델(model): 앞선 예시에서 A ⊨ φ라는 사실 또한 쉽게 알 수 있다. 따라서 구조 A에서 T의 모든 문장은 참이다. 이를 두고 “A는 T를 만족한다(A satisfies T)”라고 하며, 수식으로는 A ⊨ T와 같이 표기한다.
주어진 이론을 만족하는 구조를 모델이라고 한다. 이론은 여러 개의 모델을 가질 수도 있고, 아무 모델을 가지지 않을 수도 있다. 단적인 예시로 ψ := ∀x (x = x)만을 포함하는 이론은 무한히 많은 모델을 가지는 한편 φ := ∃x ¬(x = x) 를 포함하는 이론은 아무런 모델도 가지지 않는다.
정의역이 무한히 큰 모델을 무한 모델, 가산집합인 모델을 가산 모델이라고 부른다. 간단한 예시로 다음 문장 φn을 고려해 보자.
φn := ∃x1 ∃x2 ... ∃xn [¬( x1 = x2 ) ∧ ... ∧ ¬ (xn-1 = xn) ∧ ¬ (xn = x1)]
이 문장은 정의역의 크기가 n 이상인 구조에서 성립한다. 따라서 다음 이론은 무한 모델만을 가진다.
T = { φ1, φ2, ... , φn, ... }
자연수 집합 N은 T의 모델 중 하나이다. 한편 짝수 집합 2N 또한 T의 모델이다. 이처럼 어떤 모델의 부분집합 또한 모델일 경우 그 부분집합을 부분모델(submodel)이라고 부른다.
이해를 돕기 위해 몇 가지 다른 예시를 소개한다.
-
평면 기하학은 유클리드 공리계의 모델이며, 쌍곡 기하학은 유클리드 공리계의 모델이 아니다.
-
자연수 집합은 페아노 공리계의 모델이다. 2차 논리 페아노 공리계는 오직 자연수만을 모델로 가지지만 1차 논리 페아노 공리계는 본문에서 소개하는 뢰벤하임-스콜렘 정리로 인해 자연수가 아닌 모델 또한 수없이 가진다.
-
집합론에서 표준적으로 채택하는 공리계는 ZFC이다. 대부분의 수학자는 ZFC가 모델을 가진다고 생각한다. ZFC의 유력한 모델 중 하나는 ‘폰 노이만 전체’라고 부르는 구조이다. 그러나 괴델의 불완전성 정리로 인해 폰 노이만 전체가 정말로 ZFC의 모델인지는 알 수 없다.
참과 증명 가능성. 증명 가능성은 이론에 관한 것이다. 즉, 어떤 문장 ψ는 주어진 이론 T에서 증명 가능하거나, 가능하지 않다. 증명 가능한 경우를 수식으로는 T ⊢ ψ와 같이 표기한다. 한편 참은 구조에 관한 것이다. 즉, 어떤 문장 ψ는 주어진 구조 A에서 참이거나 거짓이다. 참인 경우를 수식으로는 A ⊨ ψ와 같이 표기한다. 만약 T의 모든 구조에서 ψ가 참이라면 T ⊨ ψ라고 표기한다.
일반적으로 T ⊢ ψ와 T ⊨ ψ는 서로를 시사하지 않는다. T ⊢ ψ가 T ⊨ ψ를 시사하는 체계를 건전(sound)하다고 한다. 거의 모든 체계는 건전하다. T ⊨ ψ가 T ⊢ ψ를 시사하는 체계를 완전(complete)하다고 한다. 1차 논리는 완전하지만 2차 논리는 완전하지 않다.
0. 서론
스콜렘의 역설은 고전 논리학의 두 가지 정리가 서로 모순되듯이 보이는 역설이다. 뢰벤하임-스콜렘 정리에 따르면 무한 모델을 가지는 1차 논리 이론은 가산 모델을 가진다. 칸토어의 정리에 따르면 어떤 집합들은 비가산이다. 스콜렘의 역설은 비가산집합의 존재를 증명하는 칸토어의 집합론을 1차 논리 이론으로 공리화할 수 있다는 사실에서 비롯한다. 어떻게 비가산집합의 존재를 증명하는 공리들이 가산 모델에서 성립할 수 있는 것일까? 어떻게 실수와 같은 비가산 개수의 대상들이 존재한다는 내용의 1차 논리 문장이 가산 모델에서 참일 수 있는 것일까?
이 역설에 관한 철학적 논의는 세 가지 주요 질문에 집중되어 왔다. 먼저 순수 수학적인 질문이 있다. 왜 스콜렘의 역설은 집합론에 명명백백한 모순을 일으키지 않는가? 둘째는 역사적인 질문이다. 스콜렘 본인은 어째서 이 역설이 수학적 모순을 일으키지 않는지를 제법 괜찮게 설명했다. 그렇다면 왜 스콜렘을 포함하여 당시의 학자들은 이 역설의 철학적 의미를 두고 골몰했던 것인가? 마지막으로 순수 철학적인 질문이 있다. 스콜렘의 역설은 집합론에 대한 우리의 이해와, 집합론의 의미론에 관해 무엇을 알려 주는가?
1. 배경
스콜렘의 역설을 이해하기 위해 우리는 고전 논리학의 두 가지 정리를 떠올려야 한다. 첫 번째 정리는 19세기 후반에 밝혀졌다. 1873년, 게오르크 칸토어는 집합의 크기 — 기수(cardinality)라고도 부른다 — 를 비교하는 새로운 이론을 고안했다. 그의 발상에 따르면 두 집합의 크기가 같다는 것은 곧 두 집합의 원소들을 일대일로 대응할 수 있다는 것이다. 예를 들어 집합 {1, 2, ..., 26}과 집합 {A, B, ..., Z}는 1 - A, 2 - B, 3 - C...와 같이 일대일 대응될 수 있으므로 크기가 같다. 자연수 집합과 짝수 집합은 f(x) = 2x라는 관계를 통해 일대일 대응될 수 있다.
이 아이디어를 무한집합에 적용한 칸토어는 무한에도 다양한 크기가 있다는 놀라운 결론에 도달했다. 짝수 집합, 정수 집합, 그리고 유리수 집합은 가장 작은 크기의 무한이다. 이 집합들은 모두 자연수 집합과 일대일로 대응될 수 있으며, 그렇기에 가산(countable)이라고 부른다. 그러나 이들보다 훨씬 더 ‘큰’ 무한집합도 있다. 실수 집합, 복소수 집합, 그리고 자연수 집합의 멱집합 등은 자연수 집합과 일대일 대응 관계를 맺기에는 크기가 너무나 크며, 그렇기에 비가산(uncountable)이라고 부른다. 비가산 집합이 존재한다는 것이 칸토어의 정리이다.
두 번째 정리는 20세기 초에 밝혀졌다. 1915년, 레오폴트 뢰벤하임은 어떤 1차 논리 문장이 모델을 가지면 그 문장은 가산 모델 또한 가진다는 사실을 증명했다. 1922년, 토랄프 스콜렘은 이 사실이 1차 논리 문장‘들’에 대해서도 성립함을 증명했다. 엄밀히 말하자면, 가산 개수의 1차 논리 문장들이 무한 모델을 가진다면 가산 모델 또한 가진다. 이 결과는 보통 뢰벤하임-스콜렘 정리로 불린다. 이야기를 진행하기에 앞서 이 정리의 세 가지 세부 정리를 살펴보도록 하자.
T가 가산 개의 1차 논리 문장들로 이루어진 이론이라고 하고 A가 무한집합이라고 하자. 상향 뢰벤하임-스콜렘 정리에 따르면 T가 아무 무한 모델을 가진다면 T는 정의역이 A와 같은 크기인 모델을 가진다(나아가 해당 모델의 정의역이 A라고 두어도 무방하다). 하향 뢰벤하임-스콜렘 정리에 따르면 N이 무한 기수 𐡠의 모델이고 λ가 𐡠보다 작은 무한 기수일 때, N과 정확히 동일한 문장들을 만족하는 동시에 기수가 λ인 N의 부분모델이 존재한다. 마지막으로 전치 부분모델 정리는 하향 뢰벤하임-스콜렘 정리를 강화한 정리로서, 앞선 N이 집합론에서 전치 모델이라고 부르는 모델이라면 하향 뢰벤하임-스콜렘 정리가 시사하는 N의 부분모델 중에도 전치 모델이 있다는 정리이다.
이제 다시 뢰벤하임-스콜렘 정리(무한 모델을 가지는 이론은 가산 모델을 가진다)로 돌아가자. 스콜렘의 역설은 표준 집합론이 가산 개의 1차 논리 문장들로 공리화될 수 있다는 사실에서 비롯한다. 그러므로 만약 집합론의 공리계가 모델을 가진다면 뢰벤하임-스콜렘 정리에 따라 집합론은 가산 모델을 가진다. 이것은 꽤 당혹스러운 결론이다. 어떻게 비가산집합의 존재를 보장하는 공리들이 가산 모델에 의해 만족될 수 있다는 것일까? 어떻게 비가산 개수의 대상들이 존재한다는 ‘내용’의 1차 논리 문장이 가산 모델에서 참일 수 있는 것일까?
구체적인 경우를 고려해 보면 이 의문들의 요지가 명확해진다. T가 표준 집합론의 1차 논리 공리계라고 하자. 편의를 위해 본문에서는 T가 ZFC인 경우에 집중할 것이지만 다른 공리계에 대해서도 마찬가지 논지가 성립한다. T가 모델을 가진다면(역자주: 괴델의 불완전성 정리에 의해 이 가정은 표준적인 방법으로 증명될 수 없다) 뢰벤하임-스콜렘 정리에 따라 T는 가산 모델 M을 가진다. 한편 칸토어의 정리에 따라 T ⊢ ∃x “x는 비가산집합이다” 가 성립한다. 그러므로 M의 정의역 중 어떤 s가 존재하여 M ⊨ “s는 비가산집합이다”가 성립한다. 그러나 M은 가산 모델이므로 M ⊨ m ∈ s를 만족하는 m은 가산 개밖에 있을 수 없다. 이것은 명백한 모순처럼 보인다. s는 비가산집합이지만, 가산 개의 원소만을 가지고 있다.
이 모순의 해결책을 알아보기에 앞서 해결책이 필요한 이유를 조금 더 자세히 설명하는 것이 적절하겠다. 어떤 모델이 그 모델이 기술하고자 하는 세계의 세부 특징을 완전히 포착하지 못하는 현상은 그리 기이한 일이 아니다. 예를 들어 아원자 입자와 시공간을 연구하는 물리학 이론의 수학적 모델은 오직 실수로만 이루어져 있을 수도 있다. 또한 교실에서 흔히 볼 법한 태양계의 모델은 실제 태양계의 어떤 특징은 정확하게 기술하는 한편 어떤 특징은 틀리게 기술한다. 예를 들어 행성들의 상대적 크기는 올바르게 묘사할지언정 절대적 크기를 제대로 묘사하지는 않는다. 또한 행성들이 태양을 돈다는 사실은 정확하게 표현할지언정 어떻게 태양을 도는지는 제대로 드러내지 못한다(행성들이 톱니바퀴에 의해 태양을 돌지는 않는다!). 이런 사실을 고려하면 집합론의 1차 논리 모델이 가산집합과 비가산집합의 구분을 정확히 묘사할 것이라는 생각 자체가 근거 없이 보일 수도 있다. 다시 말해, 스콜렘의 역설이 애초에 역설처럼 보이지 않는다는 의견이 가능하다.
이 의견에 대해서는 나중에 더 자세히 의논할 것이지만(특히 2.1절과 3.1절을 참조) 몇 가지 사항은 언급하겠다. 첫째, 1차 논리 모델이 정확하게 포착하는 집합론적 개념이 분명 있다는 사실을 잊어서는 안 된다. 3.1절에서 자세히 이야기하겠지만, 1차 논리 모델은 “x는 공집합이다”, “x는 두 개의 원소를 가진다” 등의 유한 크기 개념은 정확히 포착한다. 집합론의 공리가 무한히 많아도 된다는 가정이 있으면 “x는 무한집합이다”라는 개념 또한 포착할 수 있다. 또한 원소의 포함 관계 ∈를 표준적으로 해석한다면 “x는 유한집합이다”라는 개념 또한 포착할 수 있다.
그러므로 스콜렘의 역설은 가산과 비가산의 구분이, 어떤 심오한 의미에서는, 우리의 모델 이론이 크기 개념을 포착하는 데 처음으로 실패하는 경우임을 보여준다. 이 사실은 모델과 세계 사이의 대응이 때때로 완벽하지 않다는 사실을 시인하더라도 스콜렘의 역설이 당혹스럽게 느껴지는 이유 중 하나이다. 가산과 비가산의 경계선 ‘아래에’ 있는 수많은 크기 개념은 올바르게 포착할 수 있지만 그 경계선을 밟는 순간 이상한 모델들이 튀어나온다는 사실은 일견 매우 놀랍다.
둘째, 스콜렘의 역설은 어떤 집합론의 공리계를 사용하냐의 여부와 무관하다. 뢰벤하임-스콜렘 정리는 모든 1차 논리 이론에 대해 성립하며, 그러므로 모든 집합론의 1차 논리 공리계는 역설의 먹잇감이다. 이것은 새로운 집합론 공리계를 구성하거나, 기존의 공리계에 공리를 더 추가한다고 해서 스콜렘의 역설이 해소될 수 없음을 시사한다. 이처럼 스콜렘의 역설이 1차 논리 체계에 본질적이라는 사실, 다시 말해 1차 논리를 사용하는 집합론 공리계에 필연적이라는 사실은 스콜렘의 역설이 당혹스러운 또 다른 이유이다.
이것이 스콜렘의 역설의 기본적인 내용이다. 다음 절에서는 왜 단순한 형태의 스콜렘의 역설은 실제로 모순이 아닌지를 설명하는 한편, 스콜렘의 역설을 더욱 정교히 다듬은 역설들을 소개한다. 3절에서는 철학적 · 역사적 주제들을 다룬다. 3.1절에서는 스콜렘 본인이 어떻게 이 역설을 이해했는지를 소개한다. 3.2 - 3.4절에서는 최근에 이루어진 논의 중에서 스콜렘의 역설이 수학적 모순으로 이어지지는 않지만, 우리가 집합론을 이해하는 방식에 관하여 철학적으로 중요한 시사점을 지닌다는 주장을 살펴본다.
