뢰벤하임-스콜렘 정리

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

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

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

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

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

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

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

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

${\displaystyle X_{0}=X}$

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

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

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

이다. 그렇다면

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

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

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

이다.

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

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

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

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

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

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

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

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

독일의 수리논리학자 레오폴트 뢰벤하임(Leopold Löwenheim)과 노르웨이의 수리논리학자 토랄프 스콜렘이 1915년에 증명하였다.^[2]: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》 (영어).