| 수학기초론 Foundations of Mathematics | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 다루는 대상과 주요 토픽 | ||
| 수리논리학 | 논리 · 논증{귀납논증 · 연역논증 · 귀추 · 유추} · 정리(보조정리) · 공리 및 공준 · 증명{반증 · PWW · 귀류법 · 수학적 귀납법 · 더블 카운팅 · 자동정리증명(증명보조기)} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문(조각적 정의) · 명제 논리(명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리(존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론 | ||
| 집합론 | 집합(원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계{동치관계} · 순서론{순서 관계(부분 순서 관계 · 하세 다이어그램) · 격자} · 순서쌍(튜플) · 서수(큰 가산서수 · 초한귀납법) · 수 체계 · ZFC 공리계(선택공리) · 기수(초한기수) · 초한수 · 절대적 무한 · 모임 | ||
| 범주론 | 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 | ||
| 계산 가능성 이론 | 계산 · 오토마타 · 튜링 머신 · 바쁜 비버 · 정지 문제 · 재귀함수 | ||
| 정리 | |||
| 드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 퍼스의 법칙 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리(괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리 | |||
| 기타 | |||
| 예비사항(약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학 | |||
| 틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | ||
1. 개요
뢰벤하임-스콜렘 정리는,어떤 규칙이나 조건을 만족하는 세계가 하나라도 있으면, 그런 세계를 훨씬 더 작게 만들 수도 있다.
는 사실을 보여주는 수리논리학의 중요한 발견이다.우리는 보통, 규칙을 세밀하게 정하면 세계도 자연스럽게 하나로 결정될 거라고 생각한다. 예를 들어, 유클리드 기하학의 다섯 개의 공리
하지만 뢰벤하임-스콜렘 정리는 이러한 기대를 완전히 무너뜨린다. 아무리 복잡하고 크고 정교한 세계를 규칙으로 묘사하더라도, 그 규칙을 만족하는 '셀 수 있을 정도로 작은' 또 다른 세계를 언제나 만들 수 있다. 겉으로는 거대한 세계를 말하는 것 같아도, 논리 구조만 맞춘 작고 압축된 다른 해석이 항상 존재하는 것이다.
'규칙을 세우면 세계가 하나로 고정된다'고 믿었던 우리의 기대는, 뢰벤하임-스콜렘 정리에 의하여, 논리적으로 전혀 보장되지 않는다.
2. 뢰벤하임-스콜렘 정리
| [math(\textbf{Löwenheim-Skolem Theorem})] 만약 어떤 1차 논리 체계(문장 집합)가 하나 이상의 모형을 가진다면, 그 체계는 크기가 가산(셀 수 있는 무한)인 논의 영역을 갖는 모형도 반드시 가진다. |
<기본 용어 해설>
- 1차 논리 체계:
* 어떤 규칙과 조건을 표현할 수 있도록 짜인 언어와 논리 구조를 말한다.
* "1차"라는 말은, 변수(예: [math(x)], [math(y)], [math(z)])가 개별 사물(대상)을 가리키고, 그 위에 술어(predicate)를 적용한다는 뜻이다. (변수끼리 직접 집합을 이루는 등 복잡한 구조를 다루지 않는다.)
* 쉽게 말하면, "대상과 그 대상들 사이의 관계"만을 표현할 수 있는 규칙 체계라고 볼 수 있다.
* 예시: "모든 사람은 부모가 있다.", "[math(x)]는 [math(y)]보다 크다." 같은 문장들을 만들 수 있는 틀.
* "1차"라는 말은, 변수(예: [math(x)], [math(y)], [math(z)])가 개별 사물(대상)을 가리키고, 그 위에 술어(predicate)를 적용한다는 뜻이다. (변수끼리 직접 집합을 이루는 등 복잡한 구조를 다루지 않는다.)
* 쉽게 말하면, "대상과 그 대상들 사이의 관계"만을 표현할 수 있는 규칙 체계라고 볼 수 있다.
* 예시: "모든 사람은 부모가 있다.", "[math(x)]는 [math(y)]보다 크다." 같은 문장들을 만들 수 있는 틀.
- 문장 집합:
* 1차 논리 체계 안에서 만들어진 문장들의 모임이다.
* 각각의 문장은 어떤 규칙이나 사실을 표현한다.
* 예시:
* 각각의 문장은 어떤 규칙이나 사실을 표현한다.
* 예시:
* 모든 사람은 부모가 있다.
* 모든 수는 자기 자신보다 크지 않다.
* 두 점을 잇는 직선은 하나뿐이다.
이런 식으로 여러 문장이 모여서 하나의 문장 집합을 이룬다.* 모든 수는 자기 자신보다 크지 않다.
* 두 점을 잇는 직선은 하나뿐이다.
- 모형 (model):
* 문장 집합 안에 있는 모든 문장을 '참'이 되게 해주는 구체적인 세계(또는 상황)를 말한다.
* 여기서 세계란,
* 요약하면, 문장들이 말하는 바를 실제로 만족시키는 '구성된 세계'가 바로 모형이다.
* 예시: "모든 사람은 부모가 있다"는 문장을 만족시키려면, 모든 사람마다 부모가 지정된 세계를 만들면 된다.
* 여기서 세계란,
* 어떤 대상을 논의하고 (예: 사람들, 수들),
* 그들 사이의 관계를 설정하고 (예: 부모 관계, 크다 관계),
* 이름을 부여하는 (예: '소크라테스'는 이 사람이다)
그런 구조를 갖춘 것이다.* 그들 사이의 관계를 설정하고 (예: 부모 관계, 크다 관계),
* 이름을 부여하는 (예: '소크라테스'는 이 사람이다)
* 요약하면, 문장들이 말하는 바를 실제로 만족시키는 '구성된 세계'가 바로 모형이다.
* 예시: "모든 사람은 부모가 있다"는 문장을 만족시키려면, 모든 사람마다 부모가 지정된 세계를 만들면 된다.
- 논의 영역 (domain):
* 모형이 다루는 모든 대상들의 집합이다.
* 예를 들어, '사람'이라는 개념을 다루는 모형이라면, 그 모형의 논의 영역은 "존재하는 모든 사람"들의 집합이다.
* 논의 영역 안에 무엇이 들어 있는지가, 그 세계가 어떤 세계인지를 결정한다.
* 예를 들어, '사람'이라는 개념을 다루는 모형이라면, 그 모형의 논의 영역은 "존재하는 모든 사람"들의 집합이다.
* 논의 영역 안에 무엇이 들어 있는지가, 그 세계가 어떤 세계인지를 결정한다.
| {{{#!folding 매우 포멀한 정리-증명 (영문-한글 번역 첨부) | Theorem. Let [math(L)] be a first-order language, and let [math(T)] be a set of [math(L)]-sentences. Suppose [math(T)] has an infinite model [math(M)]. Then for every infinite cardinal [math(\kappa)] such that [math(\kappa \geq |L|)] and [math(\kappa \leq |M|)], there exists an [math(L)]-model [math(M')] such that:
|
We give a proof sketch based on Skolemization and elementary substructure construction:
1. (Skolemization)
Extend the language [math(L)] by adding Skolem function symbols for every existential quantifier occurring in [math(T)]. Let [math(L^S)] denote the extended language and [math(T^S)] the corresponding Skolemized theory, logically equivalent to [math(T)] with respect to satisfiability.
2. (Build a countable set)Select a countable subset [math(A \subseteq M)] containing:
3. (Construct the submodel)* The interpretations of all constant symbols in [math(L^S)],
* Closed under the Skolem functions introduced.
That is, if [math(a_1, \dotsc, a_n)] are elements of [math(A)] and [math(f)] is a Skolem function, then [math(f(a_1, \dotsc, a_n))] must also be in [math(A)].* Closed under the Skolem functions introduced.
Define [math(M')] as the substructure of [math(M)] generated by [math(A)]:
4. (Verify satisfaction)* Interpret function symbols by restricting the functions from [math(M)] to [math(A)],
* Interpret relation symbols by restricting the relations from [math(M)] to [math(A)].
* Interpret relation symbols by restricting the relations from [math(M)] to [math(A)].
By the closure under Skolem functions, [math(M')] satisfies all Skolemized sentences [math(T^S)]. Since Skolemization preserves satisfiability, it follows that [math(M' \models T)].
5. (Cardinality)[math(M')] is at most countable because [math(A)] is countable and the language [math(L^S)] is at most countable.
6. (Conclusion)Hence, there exists a countable model [math(M')] satisfying [math(T)]. Q.E.D
스콜렘-뢰벤하임 정리 증명
정리. L을 1차 언어라 하고, T를 L-문장들의 집합이라 하자. T가 무한 모델 M을 갖는다고 가정하자. 그러면 κ≥∣L∣이고 κ≤∣M∣인 모든 무한 기수 κ에 대해, 다음을 만족하는 L-모델 M′가 존재한다:
M′⊨T,
∣M′∣=κ,
M′는 M의 기본 부분구조이다 (필요한 경우이지만, 기본적인 하향 L-S의 경우 단순히 부분모델).
특히, ∣L∣이 기껏해야 가산일 때 T의 가산 모델이 항상 존재한다.
증명. 스콜렘화와 기본 부분구조 구성에 기반한 증명 개요를 제시한다:
(스콜렘화)
T에서 발생하는 모든 존재 양화사에 대해 스콜렘 함수 기호를 추가하여 언어 L을 확장한다. L_S를 확장된 언어라 하고 T_S를 해당하는 스콜렘화된 이론이라 하자. 이는 충족가능성에 관해 T와 논리적으로 동치이다.
(가산 집합 구성)
다음을 포함하는 가산 부분집합 A⊆M을 선택한다:
L_S의 모든 상수 기호들의 해석,
도입된 스콜렘 함수들에 대해 닫혀있음.
즉, a₁,…,aₙ이 A의 원소들이고 f가 스콜렘 함수라면, f(a₁,…,aₙ)도 A에 속해야 한다.
(부분모델 구성)
A에 의해 생성되는 M의 부분구조로 M′를 정의한다:
함수 기호들을 M에서 A로 제한하여 해석,
관계 기호들을 M에서 A로 제한하여 해석.
(만족가능성 검증)
스콜렘 함수들에 대한 닫힘에 의해, M′는 모든 스콜렘화된 문장 T_S를 만족한다. 스콜렘화가 충족가능성을 보존하므로, M′⊨T가 성립한다.
(기수)
A가 가산이고 언어 L_S가 기껏해야 가산이므로, M′는 기껏해야 가산이다.
(결론)
따라서 T를 만족하는 가산 모델 M′가 존재한다. Q.E.D
}}} ||
3. 왜 중요한가?: 수학적 통찰과 철학적 함의
3.1. 수학적 통찰: '이름 붙이기의 한계'와 가산적 세계
이 정리의 수학적 의미는, 단순히 다양한 모델이 존재할 수 있다는 사실을 넘어서, 우리가 세계를 구성하고 이해하는 방식 자체가 본질적으로 가산적이라는 데 있다. 우리는 일상적으로, 마음만 먹으면 세상에 존재하는 모든 것에 이름을 붙일 수 있다고 생각한다. 별 하나하나, 나무 하나하나, 심지어 모래알 하나하나에도 이름을 줄 수 있을 것처럼 느낀다. 그러나 수학적으로 보면, 아무리 이름을 많이 지어도 "가능한 이름들"의 총량은 셀 수 있을 정도밖에 되지 않는다. 왜냐하면 우리가 이름을 만들 때 사용할 수 있는 기호나 글자는 유한하고, 그 조합도 유한한 길이로 제한되기 때문이다. 모든 가능한 이름(= 문자열 조합)을 다 만들어도, 결국 그것들은 가산 무한([math(\aleph_0)]), 즉 자연수처럼 셀 수 있는 무한 집합에 머문다.이 말은 곧, 우리가 이름 붙일 수 있는 세계는 기본적으로 "가산적"일 수밖에 없다는 것을 뜻한다.
하지만 실제 세계는 그렇게 단순하지 않다. 예를 들어, 실수(real number) 집합처럼 비가산 무한([math(2^{\aleph_0})]) 크기를 가진 세계가 존재한다. 실수는 무한히 조밀하고 복잡하여, 숫자 하나하나에 전부 이름을 붙이는 것은 수학적으로 불가능하다. 실수 전체를 포괄할 수 있는 이름 목록은 만들 수 없다.
그럼에도 불구하고, 뢰벤하임-스콜렘 정리에 따르면 다음과 같은 놀라운 사실이 가능해진다:
손에 닿지 않는 거대한 세계, 셀 수 없이 무한한 그 모든 존재라도, 그 안의 질서와 의미는 결국 셀 수 있는 작은 세계 속에 다시 그려낼 수 있다.
비가산적으로 보이는 대상을 다룰 때조차, 수학적 구조를 '가산적 모형'으로 재구성하는 것이 가능하며, 이 모형은 원래의 논리적 성질을 충실히 반영할 수 있다. 뢰벤하임-스콜렘 정리는 세계가 본질적으로 비가산적 복잡성을 지니더라도, 우리가 논리적 언어를 통해 그것을 이해하려 할 때는 필연적으로 가산적 구조 안에 재구성될 수밖에 없다는 깊은 통찰을 제공한다.이것이 바로 뢰벤하임-스콜렘 정리가 전하는 수학적 통찰이다.
3.2. 철학적 함의: 해석의 유동성과 진리의 미결정성
윌러드 밴 오먼 콰인(Willard Van Orman Quine)은 이 수학적 사실을 철학적으로 확장하였다. 그는 하나의 언어적 표현 집합이 주어졌을 때, 그 문장의 논리적 구조를 유지하면서도 서로 다른 의미 해석이 가능하다는 점에 주목하였다. 그리고 이들 해석 중 어느 하나만을 유일한 '정답'으로 확정하는 것은 불가능할 수 있다고 보았다. 콰인은 이를 번역 불확정성(indeterminacy of translation)이라 부른다. 외국어 문장을 한국어로 번역할 때를 생각해보자. 문장 구조는 같지만 의미는 여러 가지로 해석될 수 있으며, 이들 번역은 모두 논리적으로 일관될 수 있다. 콰인은 이를 통해, 언어의 의미 자체가 고정된 실체가 아니라 해석자와 상황에 따라 유동적일 수 있음을 설명하였다.이 논의는 과학철학에서도 같은 문제를 일으킨다. 실험적 데이터가 주어졌을 때, 그것을 설명하는 서로 다른 이론들이 존재할 수 있으며, 단순한 경험적 관찰만으로 어느 이론이 참인지 최종 결정하는 것은 불가능할 수 있다. 이 문제를 이론의 미결정성(underdetermination of theory)이라 부른다.
결국, 뢰벤하임-스콜렘 정리는 우리에게 다음과 같은 근본적 사실을 가르쳐준다:
논리 구조는 동일하더라도, 구체적 해석은 본질적으로 다양할 수 있다.
그리고 이 통찰은, 언어, 지식, 과학 이론 등 인간의 모든 인식 활동이 완전한 단일성과 확정성을 기대할 수 없음을 철학적으로 시사한다.