뢰벤하임-스콜렘 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

정의[편집]

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

  • (상향 뢰벤하임-스콜렘 정리 영어: upward Löwenheim–Skolem theorem) 만약 |M|\ge\aleph_0이라면, 모든 기수 \kappa\ge|M|+|\sigma| 에 대하여, 다음 두 조건을 만족시키는 \sigma-구조 N이 존재한다.
  • (하향 뢰벤하임-스콜렘 정리 영어: downward Löwenheim–Skolem theorem) 모든 부분집합 X\subset M에 대하여, 다음 두 조건을 만족시키는 \sigma-구조 N이 존재한다.

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

고차 논리에서의 부재[편집]

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

증명[편집]

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

하향 뢰벤하임-스콜렘 정리[편집]

임의의 자연수 nM의 각 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\}

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

|X_i|\le |X_{i+1}|\le|X_i|+|\sigma|+\aleph_0

이다. 그렇다면

N=\bigcup_{i\in\mathbb N}X_i\supset X

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

|N|\le|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\ne c_j\qquad(i,j\in I,\;i\ne j)

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

[편집]

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

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

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

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

역사[편집]

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

참고 문헌[편집]

  1. (영어) Marker, David (2002년). 《Model theory: an introduction》, Graduate Texts in Mathematics 217, ISSN 0072-5285. Springer. doi:10.1007/b98860. Zbl 1003.03034. ISBN 978-0-387-98760-6
  2. (영어) Enderton, Herbert B. (2001년). 《A mathematical introduction to logic》, 2판, Academic Press. doi:10.1016/B978-0-08-049646-7.50001-1. Zbl 0992.03001. ISBN 978-0-12-238452-3
  3. (영어) Johan, van Benthem, Kees Doets (2001년). 〈Higher-order logic〉, D. M. Gabbay, F. Guenthner: 《Handbook of philosophical logic, volume 1》, 2판, Kluwer, 189–243쪽. doi:10.1007/978-94-015-9833-0_3. Zbl 1003.03513
  4. (독일어) Skolem, Thoralf (1923년). 〈Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre〉, 《Fünften Kongress der skandinavischen Mathematiker in Helsingfors vom 4. bis 7. Juli 1922》, 217–232쪽. JFM 49.0138.02

바깥 고리[편집]

같이 보기[편집]