| 수학기초론 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
}}} ||3. 왜 중요한가?: 수학적 통찰과 철학적 함의
3.1. 수학적 통찰: '이름 붙이기의 한계'와 가산적 세계
이 정리의 수학적 의미는, 단순히 다양한 모델이 존재할 수 있다는 사실을 넘어서, 우리가 세계를 구성하고 이해하는 방식 자체가 본질적으로 가산적이라는 데 있다. 우리는 일상적으로, 마음만 먹으면 세상에 존재하는 모든 것에 이름을 붙일 수 있다고 생각한다. 별 하나하나, 나무 하나하나, 심지어 모래알 하나하나에도 이름을 줄 수 있을 것처럼 느낀다. 그러나 수학적으로 보면, 아무리 이름을 많이 지어도 "가능한 이름들"의 총량은 셀 수 있을 정도밖에 되지 않는다. 왜냐하면 우리가 이름을 만들 때 사용할 수 있는 기호나 글자는 유한하고, 그 조합도 유한한 길이로 제한되기 때문이다. 모든 가능한 이름(= 문자열 조합)을 다 만들어도, 결국 그것들은 가산 무한([math(\aleph_0)]), 즉 자연수처럼 셀 수 있는 무한 집합에 머문다.이 말은 곧, 우리가 이름 붙일 수 있는 세계는 기본적으로 "가산적"일 수밖에 없다는 것을 뜻한다.
하지만 실제 세계는 그렇게 단순하지 않다. 예를 들어, 실수(real number) 집합처럼 비가산 무한([math(2^{\aleph_0})]) 크기를 가진 세계가 존재한다. 실수는 무한히 조밀하고 복잡하여, 숫자 하나하나에 전부 이름을 붙이는 것은 수학적으로 불가능하다. 실수 전체를 포괄할 수 있는 이름 목록은 만들 수 없다.
그럼에도 불구하고, 뢰벤하임-스콜렘 정리에 따르면 다음과 같은 놀라운 사실이 가능해진다:
손에 닿지 않는 거대한 세계, 셀 수 없이 무한한 그 모든 존재라도, 그 안의 질서와 의미는 결국 셀 수 있는 작은 세계 속에 다시 그려낼 수 있다.
비가산적으로 보이는 대상을 다룰 때조차, 수학적 구조를 '가산적 모형'으로 재구성하는 것이 가능하며, 이 모형은 원래의 논리적 성질을 충실히 반영할 수 있다. 뢰벤하임-스콜렘 정리는 세계가 본질적으로 비가산적 복잡성을 지니더라도, 우리가 논리적 언어를 통해 그것을 이해하려 할 때는 필연적으로 가산적 구조 안에 재구성될 수밖에 없다는 깊은 통찰을 제공한다.이것이 바로 뢰벤하임-스콜렘 정리가 전하는 수학적 통찰이다.
3.2. 철학적 함의: 해석의 유동성과 진리의 미결정성
윌러드 밴 오먼 콰인(Willard Van Orman Quine)은 이 수학적 사실을 철학적으로 확장하였다. 그는 하나의 언어적 표현 집합이 주어졌을 때, 그 문장의 논리적 구조를 유지하면서도 서로 다른 의미 해석이 가능하다는 점에 주목하였다. 그리고 이들 해석 중 어느 하나만을 유일한 '정답'으로 확정하는 것은 불가능할 수 있다고 보았다. 콰인은 이를 번역 불확정성(indeterminacy of translation)이라 부른다. 외국어 문장을 한국어로 번역할 때를 생각해보자. 문장 구조는 같지만 의미는 여러 가지로 해석될 수 있으며, 이들 번역은 모두 논리적으로 일관될 수 있다. 콰인은 이를 통해, 언어의 의미 자체가 고정된 실체가 아니라 해석자와 상황에 따라 유동적일 수 있음을 설명하였다.이 논의는 과학철학에서도 같은 문제를 일으킨다. 실험적 데이터가 주어졌을 때, 그것을 설명하는 서로 다른 이론들이 존재할 수 있으며, 단순한 경험적 관찰만으로 어느 이론이 참인지 최종 결정하는 것은 불가능할 수 있다. 이 문제를 이론의 미결정성(underdetermination of theory)이라 부른다.
결국, 뢰벤하임-스콜렘 정리는 우리에게 다음과 같은 근본적 사실을 가르쳐준다:
논리 구조는 동일하더라도, 구체적 해석은 본질적으로 다양할 수 있다.
그리고 이 통찰은, 언어, 지식, 과학 이론 등 인간의 모든 인식 활동이 완전한 단일성과 확정성을 기대할 수 없음을 철학적으로 시사한다.3.2.1. 예시1: 언어 번역의 불확정성
어떤 사람이 토끼를 가리키며 "Gavagai!"라고 외쳤다고 가정하자. 우리는 이를 '토끼 전체'라고 번역할 수도 있고, '토끼의 일부(예: 다리)'로 번역할 수도 있으며, 심지어 '토끼가 뛰는 행동'으로 번역할 수도 있다. 즉, 이 사람의 행동이나 처한 상황을 관찰하더라도, 그가 정확히 무엇을 지칭하고 있는지는 확정할 수 없다. 다양한 해석이 모두 논리적으로 가능한 것이다. 문장의 구조는 같지만, 의미 해석은 다양할 수 있으며, 경험적 관찰만으로 유일한 해석을 확정하는 것은 불가능하다. 이는 우리가 언어를 이해하고 해석하는 방식 자체가 근본적으로 유동적임을 보여준다.3.2.2. 예시2: 빛의 파동성과 입자성
과학에서도 뢰벤하임-스콜렘 정리와 맞닿는 깊은 통찰을 엿볼 수 있다. 고전 물리학 시대, 빛의 본질을 둘러싼 논쟁은 그 대표적인 사례다.17세기 말, 아이작 뉴턴은 빛을 아주 작은 입자들의 직선 운동으로 설명했다(입자설). 반면 동시대의 크리스티안 하위헌스는 빛이 연속적으로 퍼져나가는 파동이라고 보았다(파동설). 두 이론은 같은 현상을 설명하려 했지만, 전혀 다른 세계를 그리고 있었다.
19세기 초, 토머스 영은 역사적인 이중 슬릿 실험을 통해 빛이 간섭 현상을 일으킨다는 놀라운 사실을 밝혀냈다. 이 실험은 빛이 파동이라는 주장을 뒷받침했고, 이후 물리학은 파동설 중심으로 전개되었다. 모든 것이 명확해지는 듯 보였다.
그러나 20세기 초, 물리학은 또 한 번 뒤집힌다. 막스 플랑크는 흑체복사 문제를 해결하기 위해 에너지가 연속적으로 방출되지 않고, 불연속적인 양자 단위로 분출된다고 가정했다. 이어 알베르트 아인슈타인은 광전효과 실험을 분석하며, 빛이 입자처럼 개별 에너지를 지닌 광자 단위로 작용함을 밝혀냈다.
결국 드러난 것은 놀라운 진실이었다. 빛은 상황에 따라 파동처럼 행동하기도 하고, 입자처럼 행동하기도 한다는 것. 빛의 본질은 하나의 이론으로 완전히 포착될 수 없었다. 둘 중 하나가 옳고 다른 하나가 틀린 것이 아니었다. 서로 모순되어 보이는 두 해석이 동시에 세계를 설명하고 있었다.
이 사건은 과학이 단순히 "정답을 찾는 과정"이 아님을 분명히 보여준다. 같은 현상을 두고도 서로 다른 논리 구조를 지닌 해석들이 공존할 수 있으며, 각각은 세계의 한 단면을 성공적으로 포착한다. 오히려 하나의 해석만을 유일한 진리로 확정하려 할 때, 우리는 세계를 심각하게 축소해버리게 된다.
빛의 입자성과 파동성 사례는 이렇게 말해준다.
하나의 자연 현상 안에도, 진실은 여러 갈래로 흐른다.
과학사 속 이 극적인 장면은 뢰벤하임-스콜렘 정리의 철학적 함의를 놀랍도록 생생하게 증명하고 있다.