뢰벤하임-스콜렘 정리(Löwenheim–Skolem theorem)는 수리논리학, 특히 모형 이론(model theory)에서 다루어지는 정리로, 1차 논리(first-order logic)의 모형이 가지는 크기(기수, cardinality)에 관한 근본적인 결과이다. 이 정리는 독일의 수학자 레오폴트 뢰벤하임(Leopold Löwenheim)과 노르웨이의 수학자 토랄프 스콜렘(Thoralf Skolem)의 이름에서 유래하였다.
정리의 내용
뢰벤하임-스콜렘 정리는 일반적으로 하향 정리(downward part)와 상향 정리(upward part)로 나뉜다. 부호수(signature) σ와 무한 σ-구조 M이 주어졌을 때, 임의의 무한 기수 κ ≥ |σ|에 대하여 다음이 성립한다.
- 하향 뢰벤하임-스콜렘 정리: κ < |M|인 경우, 크기가 κ인 M의 기본 부분 구조(elementary substructure) N이 존재한다.
- 상향 뢰벤하임-스콜렘 정리: κ ≥ |M|인 경우, 크기가 κ인 M의 기본 확장(elementary extension) N이 존재한다.
이로부터 다음과 같은 중요한 귀결이 도출된다. 만약 가산(first-order) 이론이 무한 모형을 가진다면, 모든 무한 기수 κ에 대하여 크기가 κ인 모형이 존재한다. 즉, 무한 모형을 가진 1차 이론은 동형(isomorphism)까지 유일한 모형을 가질 수 없으며, 이는 1차 이론이 무한 모형의 기수 크기를 통제할 수 없음을 의미한다.
증명 개요
하향 정리의 증명은 스콜렘 함수(Skolem function)를 도입하고 타르스키-보트 판정법(Tarski–Vaught test)을 사용하여 주어진 구조의 기본 부분 구조를 구성하는 방식으로 이루어진다. 상향 정리의 증명은 기본 도표(elementary diagram)와 콤팩트성 정리(compactness theorem)를 활용하여 더 큰 기수의 모형을 구성한 후, 하향 정리를 적용하여 원하는 크기의 모형을 얻는 방식으로 진행된다.
스콜렘 역설
뢰벤하임-스콜렘 정리의 가장 주목할 만한 결과 중 하나는 스콜렘 역설(Skolem's paradox)이다. 1차 논리로 서술된 집합론(예: ZFC)이 비가산 집합의 존재를 증명할 수 있음에도 불구하고, 하향 뢰벤하임-스콜렘 정리에 따르면 이 집합론은 가산 무한 모형을 가진다. 이는 모순이 아니라, 가산성(countability)의 개념이 절대적(absolute)이지 않음을 보여준다. 즉, 모형 내부에서는 비가산으로 간주되는 집합이 모형 외부의 관점에서는 가산일 수 있다.
역사
1915년 뢰벤하임이 처음으로 가산 부호수에 대해 만족 가능한 문장이 가산 모형에서 만족 가능함을 증명하였다. 1920년과 1922년에 스콜렘이 이를 일반화하고 단순화된 증명을 제시하였다. 이후 1936년 아나톨리 말체프(Anatoly Maltsev)가 정리의 완전한 일반 형태를 증명하였으며, 알프레트 타르스키(Alfred Tarski)의 이름을 붙여 뢰벤하임-스콜렘-타르스키 정리(Löwenheim–Skolem–Tarski theorem)로도 불린다.
의의
뢰벤하임-스콜렘 정리는 콤팩트성 정리와 함께 린드스트룀 정리(Lindström's theorem)에서 1차 논리를 특징짓는 두 가지 핵심 성질 중 하나로 사용된다. 이 정리는 1차 논리가 무한 구조의 기수 크기를 구별할 수 없음을 보여주며, 2차 논리(second-order logic)와 같은 더 강력한 논리 체계에서는 성립하지 않는다. 또한 이 정리는 형식화(formalization) 자체의 한계를 시사하는 결과로 철학적으로도 중요한 함의를 가진다.
