뢰벤하임-스콜렘 정리

모형 이론에서 뢰벤하임-스콜렘 정리(Löwenheim-Skolem定理, 영어: Löwenheim–Skolem theorem)는 논리적 언어의 특정한 크기를 갖는 모형의 존재에 대한 정리다. 1차 논리의 중요한 특성 가운데 하나이다.

정의

부호수 $\sigma$의 구조 $M$에 대하여, 다음 두 명제가 성립한다.^{:44–48:151–154}

• (상향 뢰벤하임-스콜렘 정리 영어: upward Löwenheim–Skolem theorem) 만약 $|M|\geq \aleph _{0}$이라면, 모든 기수 $\kappa \geq |M|+|\sigma |$ 에 대하여, 다음 두 조건을 만족시키는 $\sigma$-구조 $N$이 존재한다.
  • $|N|=\kappa$
  • 기본 매장 $j\colon M\hookrightarrow N$이 존재한다.
• (하향 뢰벤하임-스콜렘 정리 영어: downward Löwenheim–Skolem theorem) 모든 부분집합 $X\subset M$에 대하여, 다음 두 조건을 만족시키는 $\sigma$-구조 $N$이 존재한다.
  • $|N|\leq |X|+|\sigma |+\aleph _{0}$
  • 기본 매장 $j\colon N\hookrightarrow M$이 존재하며, $X\subset j(N)\subset M$이다.

여기서 $|\sigma |$는 부호수 $\sigma$에 속한 연산의 집합의 크기와 관계의 집합의 크기의 합이다.

고차 논리에서의 부재

표준 모형(영어: standard model)을 갖춘 고차 논리에서는 뢰벤하임-스콜렘 정리가 성립하지 않는다. 다만, 고차 논리에서 헹킨 모형(영어: Henkin model 또는 영어: general model)을 사용하면, 고차 논리는 사실상 1차 논리가 된다. 이 경우, 뢰벤하임-스콜렘 정리가 자명하게 적용된다.

증명

뢰벤하임-스콜렘 정리는 다음과 같이 증명될 수 있다.

하향 뢰벤하임-스콜렘 정리

임의의 자연수 $n$ 및 $M$의 각 1차 논리 명제 $\phi (x_{1},\dots ,x_{n},y)$에 대하여, 선택 공리를 사용하여 다음 성질을 만족시키는 함수 $f_{\phi }\colon M^{n}\to M$를 정의할 수 있다.

• $M\models \exists y\colon \phi ({\vec {x}},f_{\phi }({\vec {x}}))$이거나, 아니면 $M\models \lnot \exists y\colon \phi ({\vec {x}},y)$이다.

이러한 함수를 스콜렘 함수(영어: Skolem function) $X\subset M$에 대하여, 다음을 정의하자.

$X_{0}=X$

$X_{i+1}=\{f_{\phi }({\vec {x}})\colon n\in \mathbb {N} ,\;{\vec {x}}\in M^{n},\;\phi \in \sigma \}$

$\phi$를 $x=y$로 놓으면, $X_{i+1}\supset X_{i}$인 것을 알 수 있다. 또한,

$|X_{i}|\leq |X_{i+1}|\leq |X_{i}|+|\sigma |+\aleph _{0}$

이다. 그렇다면

$N=\bigcup _{i\in \mathbb {N} }X_{i}\supset X$

는 타르스키-보트 판정법(영어: Tarski–Vaught test)에 따라서 $M$의 기본 부분 구조이며,

$|N|\leq |X|+|\sigma |+\aleph _{0}$

이다.

상향 뢰벤하임-스콜렘 정리

부호수 $\sigma$에, $M$의 각 원소에 대응하는 0항 연산을 추가한 부호수 $\sigma \sqcup M$을 정의하자. 그렇다면, $M$의 $\sigma \sqcup M$에 대한 이론 $\operatorname {Th} _{\sigma \sqcup M}(M)$을 생각하자. 이를 $M$의 기본 도표(영어: elementary diagram)라고 한다. $\sigma \sqcup M$에 $\kappa$개의 새 0항 연산 $\{c_{i}\}_{i\in I}$를 추가하고, 기본 도표 $\operatorname {Th} _{\sigma \sqcup M}(M)$에 $\kappa ^{2}$개의 명제

$c_{i}\neq c_{j}\qquad (i,j\in I,\;i\neq j)$

를 추가하자. 이 이론은 콤팩트성 정리에 따라 모형을 가지며, 그 모형의 크기는 항상 $\kappa$ 이상이다. 그렇다면 이 모형에서 추가한 0항 연산들을 망각하고, 하향 뢰벤하임-스콜렘 정리를 사용하여 크기가 정확히 $\kappa$인 $\sigma$-모형을 찾을 수 있으며, 이 모형은 정의에 따라 $M$을 기본 부분 구조로 갖는다.

예

1차 논리로 서술된 집합론(예를 들어, 선택 공리를 추가한 체르멜로-프렝켈 집합론)을 생각하자. 만약 이 집합론이 충분히 강력하다면, 이 집합론에서 비가산 집합의 존재를 증명할 수 있다. 그러나 하향 뢰벤하임-스콜렘 정리에 따르면 이 집합론은 가산 무한 모형을 가진다. 이를 스콜렘 역설(영어: Skolem’s paradox)이라고 하며, 토랄프 스콜렘이 1922년에 지적하였다.

스콜렘 역설은 모순이 아니며, 다음과 같이 해소된다. 집합론에서는 함수 역시 집합의 일종으로 구현된다. 비가산 집합의 존재는 다음 성질을 만족시키는 집합 $S$의 존재를 의미한다.

• 단사 함수 $f\colon \mathbb {N} \to S$가 존재한다.
• 전사 함수 $f\colon \mathbb {N} \to S$는 존재하지 않는다.

집합론의 가산 모형에서, 이는 다음과 같이 해석된다.

• 모형 속에서, 단사 함수 $f\colon \mathbb {N} \to S$를 나타내는 원소가 존재한다.
• 모형 속에서, 전사 함수 $f\colon \mathbb {N} \to S$를 나타내는 원소는 존재하지 않는다. (그러나 물론 모형이 가산 모형이므로 모형 밖에서는 이러한 전사 함수를 정의할 수 있다.)

역사

독일의 수리논리학자 레오폴트 뢰벤하임(Leopold Löwenheim)과 노르웨이의 수리논리학자 토랄프 스콜렘이 1915년에 증명하였다.^:151

같이 보기

• 괴델의 완전성 정리
• 콤팩트성 정리

참고 문헌

• Van Dalen, Dirk; Heinz-Dieter Ebbinghaus. “Zermelo and the Skolem paradox”. 《The Bulletin of Symbolic Logic》 (영어): 145–161. doi:10.2307/421203. JSTOR 421203. MR 1782347. Zbl 0976.03002. 
• Ebbinghaus, Heinz-Dieter (2007). 〈Löwenheim-Skolem theorems〉. Dale Jacquette. 《Philosophy of logic》. Handbook of the Philosophy of Science (영어). North-Holland. 587–614쪽. doi:10.1016/B978-044451541-4/50018-X. ISBN 978-0-444-51541-4. Zbl 1107.03001. 
• Bays, Timothy (2007). 〈The Mathematics of Skolem’s Paradox〉 (PDF). Dale Jacquette. 《Philosophy of logic》. Handbook of the Philosophy of Science (영어). North-Holland. 615–648쪽. doi:10.1016/B978-044451541-4/50019-1. ISBN 978-0-444-51541-4. Zbl 1107.03001. 

외부 링크

• Weisstein, Eric Wolfgang. “Löwenheim-Skolem theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Skolem paradox”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Bays, Timothy (2014년 11월 11일). “Skolem’s paradox”. 《Stanford Encyclopedia of Philosophy》 (영어). 
• Suber, Peter (2002). “The Löwenheim-Skolem theorem” (영어). 
• “Löwenheim-Skolem theorem”. 《nLab》 (영어). 
• “Skolem's paradox”. 《nLab》 (영어).