뢰벤하임-스콜렘 정리

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

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

정의[편집]

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

  • (상향 뢰벤하임-스콜렘 정리 영어: upward Löwenheim–Skolem theorem) 만약 이라면, 모든 기수 에 대하여, 다음 두 조건을 만족시키는 -구조 이 존재한다.
    • 기본 매장 이 존재한다.
  • (하향 뢰벤하임-스콜렘 정리 영어: downward Löwenheim–Skolem theorem) 모든 부분집합 에 대하여, 다음 두 조건을 만족시키는 -구조 이 존재한다.
    • 기본 매장 이 존재하며, 이다.

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

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

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

증명[편집]

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

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

임의의 자연수 의 각 1차 논리 명제 에 대하여, 선택 공리를 사용하여 다음 성질을 만족시키는 함수 를 정의할 수 있다.

  • 이거나, 아니면 이다.

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

로 놓으면, 인 것을 알 수 있다. 또한,

이다. 그렇다면

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

이다.

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

부호수 에, 의 각 원소에 대응하는 0항 연산을 추가한 부호수 을 정의하자. 그렇다면, 에 대한 이론 을 생각하자. 이를 기본 도표(영어: elementary diagram)라고 한다. 개의 새 0항 연산 를 추가하고, 기본 도표 개의 명제

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

[편집]

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

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

  • 단사 함수 가 존재한다.
  • 전사 함수 는 존재하지 않는다.

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

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

역사[편집]

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

같이 보기[편집]

참고 문헌[편집]

  1. Marker, David (2002). 《Model theory: an introduction》. Graduate Texts in Mathematics (영어) 217. Springer. ISBN 978-0-387-98760-6. ISSN 0072-5285. Zbl 1003.03034. doi:10.1007/b98860. 
  2. Enderton, Herbert B. (2002). 《A mathematical introduction to logic》 (영어) 2판. Academic Press. ISBN 978-0-12-238452-3. Zbl 0992.03001. doi:10.1016/B978-0-08-049646-7.50001-1. 
  3. Johan, van Benthem; Kees Doets (2001). 〈Higher-order logic〉 (PDF). D. M. Gabbay, F. Guenthner. 《Handbook of philosophical logic, volume 1》 (영어) 2판. Kluwer. 189–243쪽. Zbl 1003.03513. doi:10.1007/978-94-015-9833-0_3. 
  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. 

외부 링크[편집]