뢰벤하임-스콜렘 정리

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

정의 
부호수 의 구조 에 대하여, 다음 두 명제가 성립한다.
 (상향 뢰벤하임-스콜렘 정리 ) 만약 이라면, 모든 기수  에 대하여, 다음 두 조건을 만족시키는 -구조 이 존재한다.
 
 기본 매장 이 존재한다.
 (하향 뢰벤하임-스콜렘 정리 ) 모든 부분집합 에 대하여, 다음 두 조건을 만족시키는 -구조 이 존재한다.
 
 기본 매장 이 존재하며, 이다.
여기서 는 부호수 에 속한 연산의 집합의 크기와 관계의 집합의 크기의 합이다.

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

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

하향 뢰벤하임-스콜렘 정리 
임의의 자연수  및 의 각 1차 논리 명제 에 대하여, 선택 공리를 사용하여 다음 성질을 만족시키는 함수 를 정의할 수 있다.
 이거나, 아니면 이다.
이러한 함수를 스콜렘 함수()
에 대하여, 다음을 정의하자.

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

이다. 그렇다면

는 타르스키-보트 판정법()에 따라서 의 기본 부분 구조이며,

이다.

상향 뢰벤하임-스콜렘 정리 
부호수 에, 의 각 원소에 대응하는 0항 연산을 추가한 부호수 을 정의하자. 그렇다면, 의 에 대한 이론 을 생각하자. 이를 의 기본 도표()라고 한다. 에 개의 새 0항 연산 를 추가하고, 기본 도표 에 개의 명제

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

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

스콜렘 역설은 모순이 아니며, 다음과 같이 해소된다. 집합론에서는 함수 역시 집합의 일종으로 구현된다. 비가산 집합의 존재는 다음 성질을 만족시키는 집합 의 존재를 의미한다.
 단사 함수 가 존재한다.
 전사 함수 는 존재하지 않는다.
집합론의 가산 모형에서, 이는 다음과 같이 해석된다.
 모형 속에서, 단사 함수 를 나타내는 원소가 존재한다.
 모형 속에서, 전사 함수 를 나타내는 원소는 존재하지 않는다. (그러나 물론 모형이 가산 모형이므로 모형 밖에서는 이러한 전사 함수를 정의할 수 있다.)

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

같이 보기 
 괴델의 완전성 정리
 콤팩트성 정리

참고 문헌

외부 링크 
 
 
 
 
 
 

수학기초론 정리
모형 이론