뢰벤하임-스콜렘 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 상향 뢰벤하임-스콜렘 정리
- 2.2. 하향 뢰벤하임-스콜렘 정리
3. 증명
- 3.1. 하향 뢰벤하임-스콜렘 정리 증명
- 3.2. 상향 뢰벤하임-스콜렘 정리 증명
4. 예시 및 결과
- 4.1. 스콜렘 역설
- 4.2. 참 산술과 실수 닫힌 체
5. 역사
6. 다른 논리에서의 뢰벤하임-스콜렘 정리
참조

1. 개요

뢰벤하임-스콜렘 정리는 구조의 크기와 관련된 정리로, 상향 뢰벤하임-스콜렘 정리와 하향 뢰벤하임-스콜렘 정리로 나뉜다. 상향 정리는 구조가 무한대일 때, 주어진 크기 이상의 구조를 갖는다는 것이고, 하향 정리는 구조의 부분집합에 대해, 주어진 크기 이하의 구조를 갖는다는 것이다. 이 정리는 1차 논리로 서술된 집합론에서 비가산 집합의 존재를 증명할 수 있지만 가산 무한 모형을 갖는다는 '스콜렘의 역설'을 낳으며, 이는 가산성이 절대적이지 않음을 보여준다. 뢰벤하임-스콜렘 정리는 1915년 레오폴트 뢰벤하임과 토랄프 스콜렘에 의해 증명되었으며, 1차 논리 외 다른 논리에도 변형된 형태로 적용될 수 있다.

더 읽어볼만한 페이지

모형 이론 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
모형 이론 - 괴델의 완전성 정리
괴델의 완전성 정리는 1차 논리 이론에서 모형 이론적 진리와 증명 이론적 진리가 같음을 나타내며, 연역 체계가 완전함을 보장하고 일차 논리에서 통사론적 결과와 의미론적 결과가 동일하다는 것을 의미한다.
수학기초론 정리 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
수학기초론 정리 - 칸토어의 정리
칸토어의 정리는 집합 X의 멱집합의 크기가 X의 크기보다 항상 크다는 것을 나타내며, 임의의 기수 κ에 대해 2^κ > κ가 성립한다는 내용으로, 칸토어의 대각선 논법으로 증명되고 집합론의 역설과 관련되어 전체 집합의 존재를 가정할 때 칸토어의 역설을 유발한다.

뢰벤하임-스콜렘 정리
개요
분야	수리논리학
발견자	레오폴트 뢰벤하임 토랄프 스콜렘
발견 시기	뢰벤하임 (1915년) 스콜렘 (1919년, 1920년, 1922년)
내용
설명	1차 논리의 완전성 및 불완전성 정리를 다룸.
상향 뢰벤하임-스콜렘 정리	가산 1차 이론이 무한 모델을 가지면 모든 비가산 크기의 모델을 가짐.
하향 뢰벤하임-스콜렘 정리	가산 언어에서 유한하게 공리화 가능한 이론이 모델을 가지면, 모든 무한 기수 κ에 대해 크기 κ의 모델을 가짐. 특히, 가산 1차 논리 문장이 무한 모델을 가지면 가산 모델을 가짐.
참고
관련 항목	괴델의 완전성 정리 린드스트룀 정리 모형 이론 비표준 해석학

2. 정의

부호수(signature) $\sigma$ 는 함수 기호, 관계 기호, 그리고 각 기호가 받는 인수의 개수(항수, arity)를 지정하는 정보로 구성된다. 일차 논리의 맥락에서는 때때로 '언어'라고도 불린다. 부호수의 크기 $|\sigma|$ 는 부호수에 포함된 모든 기호들의 집합의 크기를 의미한다.^[3]

주어진 부호수 $\sigma$ 에 대하여, $\sigma$ -구조(structure) $M$ 은 부호수 $\sigma$ 에 속한 기호들에 대한 구체적인 해석을 제공한다. 이는 기본 집합(종종 $M$ 으로 표기)과 함께, 부호수 내의 함수 기호와 관계 기호에 대한 해석으로 이루어진다. 예를 들어, $n$ -항 함수 기호 $f$ 의 해석은 $M^n$ 에서 $M$ 으로 가는 함수이고, $n$ -항 관계 기호 $R$ 의 해석은 $M^n$ 의 부분 집합이다.^[3]

일반적인 형태의 '''뢰벤하임-스콜렘 정리'''는 모든 서명 $\sigma$ , 모든 무한 $\sigma$ -구조 $M$ , 그리고 모든 무한 기수 $\kappa \ge |\sigma|$ 에 대해, 크기가 $|N| = \kappa$ 인 $\sigma$ -구조 $N$ 이 존재하며 다음 두 조건 중 하나를 만족한다고 명시한다:^[14]^[17]

만약 $\kappa < |M|$ 이면, $N$ 은 $M$ 의 초등 부분 구조이다. ('''하향 뢰벤하임-스콜렘 정리''')
만약 $\kappa \ge |M|$ 이면, $N$ 은 $M$ 의 초등 확장(elementary extension)이다. ('''상향 뢰벤하임-스콜렘 정리''')

간단히 말해, 하향 정리는 어떤 무한 구조가 주어졌을 때, 그 구조의 특정 부분집합을 포함하면서 동시에 특정 조건을 만족하는 더 '작은' (혹은 같은 크기의) 초등 부분 구조를 찾을 수 있음을 보장한다.^[1] 반대로 상향 정리는 어떤 무한 구조가 주어졌을 때, 그 구조를 초등 부분 구조로 포함하는 더 '큰' 초등 확장을 항상 찾을 수 있음을 보장한다.^[2]

표준 모형(standard model^영어)을 사용하는 고차 논리에서는 뢰벤하임-스콜렘 정리가 일반적으로 성립하지 않는다.^[15] 그러나 고차 논리에서 헹킨 모형(Henkin model^영어 또는 general model^영어)이라는 다른 종류의 모형을 고려하면, 이는 사실상 1차 논리의 틀 안에서 다룰 수 있게 되어 뢰벤하임-스콜렘 정리가 적용될 수 있다.

2. 1. 상향 뢰벤하임-스콜렘 정리

부호수

\sigma

를 갖는 구조

M

이 무한 집합일 때 (

|M|\ge\aleph_0

),

M

의 크기와

\sigma

의 크기보다 크거나 같은 임의의 기수

\kappa

(

\kappa\ge|M|+|\sigma|

)에 대해, 다음 두 조건을 만족하는

\sigma

-구조

N

이 존재한다.^[14]^[17]

$N$ 의 크기는 $\kappa$ 이다 ( $|N|=\kappa$ ).
$M$ 에서 $N$ 으로 가는 기본 매장 $j\colon M\hookrightarrow N$ 이 존재한다.

이는 어떤 무한 모델

M

이 주어졌을 때,

M

을 기본 부분 구조로 포함하면서 주어진 임의의 더 큰 크기

\kappa

를 갖는 모델

N

을 항상 찾을 수 있다는 것을 의미한다.^[2] 즉, 구조는 모든 더 큰 기수의 기본 확장을 가진다. 예를 들어, 실수 집합과 그 위의 연산 및 순서 관계를 나타내는 모델이 있다면, 이 모델을 부분 구조로 포함하면서 더 큰 초실수 모델 등을 구성할 수 있음을 보여준다.

증명의 핵심 아이디어는 다음과 같다. 먼저, 원래 구조

M

의 모든 원소에 해당하는 새로운 상수 기호를 부호수

\sigma

에 추가하여 확장된 부호수

\sigma'

을 만든다. 이 확장된 부호수 위에서

M

이 만족하는 모든 문장들의 집합, 즉

M

의 '''elementary diagram|기본 도표^영어'''를 고려한다.

다음으로, 원하는 크기

\kappa

만큼의 새로운 상수 기호

\{c_i\}_{i\in I}

(

|I|=\kappa

)를 부호수에 더 추가한다. 그리고 이 새로운 상수 기호들이 모두 서로 다른 대상을 지칭하도록 하는 문장들(

c_i\ne c_j

여기서

i,j\in I,\;i\ne j

)을 기본 도표에 추가한다.

콤팩트성 정리에 따르면, 이렇게 만들어진 이론은 모순이 없으며 따라서 모델을 가진다. 이 모델은 최소

\kappa

개의 원소를 가져야 한다 (새로운 상수 기호들 때문에). 마지막으로, 하향 뢰벤하임-스콜렘 정리를 이 모델에 적용하여 정확히 크기가

\kappa

인 모델

N

을 얻을 수 있다. 이렇게 구성된 모델

N

은 정의에 따라 원래의 구조

M

의 동형 사본을 기본 부분 구조로 포함하게 된다.^[5]^[6]

2. 2. 하향 뢰벤하임-스콜렘 정리

부호수

\sigma

의 구조

M

과 그 임의의 부분 집합

X\subset M

에 대하여, 다음 두 조건을 만족시키는

\sigma

-구조

N

이 존재한다.^[14]^[17] 이를 '''하향 뢰벤하임-스콜렘 정리'''(downward Löwenheim–Skolem theorem^영어)라고 한다.

$N$ 의 크기는 $|N|\le|X|+|\sigma|+\aleph_0$ 를 만족한다. 즉, $N$ 의 크기는 원래 부분집합 $X$ 의 크기, 부호수 $\sigma$ 의 크기, 그리고 가산 무한( $\aleph_0$ )을 넘지 않는다.
$M$ 으로 들어가는 기본 매장 $j\colon N\hookrightarrow M$ 이 존재하며, $X\subset j(N)\subset M$ 이다. 이는 $N$ 이 $M$ 의 기본 부분 구조이며 원래 부분집합 $X$ 를 포함한다는 것을 의미한다.

이 정리는 어떤 무한 구조

M

과 그 부분집합

X

가 주어졌을 때,

X

를 포함하면서

M

과 동일한 1차 논리 문장을 만족시키는, 비교적 '작은' 기본 부분 구조

N

을 항상 찾을 수 있음을 보여준다.^[1] 어떤 구조가 자신보다 작거나 같은 기수를 가지는 기본 부분 구조를 가진다는 내용이다.^[2]

증명의 핵심 아이디어는 스콜렘 함수를 이용하여 주어진 부분집합

X

를 포함하는 폐포(closure)를 구성하는 것이다. 모든 1차

\sigma

공식

\varphi(y,x_{1}, \ldots, x_{n})

에 대해, 선택 공리를 사용하여 함수

f_{\varphi}: M^n\to M

를 정의한다. 이 함수는 모든

a_{1}, \ldots, a_{n} \in M

에 대해, 만약

M\models\exists y\, \varphi(y, a_1, \dots, a_n)

이면

M\models\varphi(f_{\varphi} (a_1, \dots, a_n), a_1, \dots, a_n)

를 만족시킨다. 이러한 함수를 '''스콜렘 함수'''(Skolem function^영어)라고 부른다.

이 스콜렘 함수들을 이용하여

M

의 멱집합에 대한 연산

F

를 다음과 같이 정의한다 (

A \subseteq M

):

:

F(A) = A \cup \{f_{\varphi}(a_1, \dots, a_n) \in M \mid \varphi \in \sigma ; \, a_1, \dots, a_n \in A \}

이제 주어진 부분집합

X \subseteq M

에 대해

X_0 = X

로 시작하여,

X_{i+1} = F(X_i)

로 반복 적용한다. 이렇게 얻어진 집합들의 합집합

:

N = \bigcup_{i=0}^\infty X_i

를 정의하면,

N

은 모든 스콜렘 함수에 대해 닫혀 있다. 타르스키-보트 판정법(Tarski–Vaught test^영어)에 의해

N

은

M

의 기본 부분 구조가 된다.

또한, 각 단계에서 집합의 크기는

|X_{i+1}| = |F(X_i)| \le |X_i| + |\sigma| + \aleph_0

이므로, 최종적으로 얻어지는

N

의 크기는

:

|N| = \left| \bigcup_{i=0}^\infty X_i \right| \le |X| + |\sigma| + \aleph_0

를 만족한다. 따라서

N

은 원하는 크기 조건을 만족하는

M

의 기본 부분 구조이다.

3. 증명

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

3. 1. 하향 뢰벤하임-스콜렘 정리 증명

임의의 자연수

n

및

M

의 각 1차 논리 명제

\phi(x_1,\dots,x_n,y)

에 대하여, 선택 공리를 사용하여 다음 성질을 만족시키는 함수

f_\phi\colon M^n\to M

를 정의할 수 있다.

모든 $\vec x \in M^n$ 에 대해, $M\models\exists y\colon\phi(\vec x, f_\phi(\vec x))$ 이거나, 아니면 $M\models\lnot\exists y\colon\phi(\vec x,y)$ 이다.

이러한 함수를 '''스콜렘 함수'''(Skolem function^영어)라고 부른다.

이제

M

의 부분집합

X

가 주어졌다고 하자. 다음과 같이 집합열

X_i

를 정의한다:

:

X_0=X

:

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

여기서

\sigma

는 해당 언어의 모든 공식을 의미하며,

f_\phi

는 각 공식

\phi

에 대응하는 스콜렘 함수이다. 만약

\phi

를

x=y

(항등 함수)로 놓으면, 모든

x \in X_i

에 대해

f_\phi(x) = x

가 되어

X_{i+1}\supset X_i

임을 알 수 있다. 또한, 각 단계에서 추가되는 원소의 수는 최대

|X_i| + |\sigma| + \aleph_0

이다.

다음으로, 이 집합열의 합집합을 정의한다:

:

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

이 집합

N

은

X

를 포함하며 (

N \supset X

), 타르스키-보트 판정법(Tarski–Vaught test^영어)에 따라

M

의 기본 부분 구조이다.

N

의 기수는 다음과 같은 부등식을 만족한다:

:

|N|\le|X|+|\sigma|+\aleph_0

이 증명 과정은 스콜렘 함수들을 이용하여

M

의 멱집합에 대한 준폐포 연산자

F

를 정의하고, 이를 가산 번 반복하여 폐포 연산자

F^{\omega}

를 만드는 것으로도 이해할 수 있다.

:

F(A) = A \cup \{f_{\varphi}(a_1, \dots, a_n) \in M \mid \varphi \in \sigma ; \, a_1, \dots, a_n \in A \}

:

N = F^{\omega}(X) = \bigcup_{k \in \mathbb N} F^k(X)

이 증명 기법은 본질적으로 스콜렘에 의해 고안되었으며, 그는 언어 자체에 스콜렘 함수를 나타내는 함수 기호를 도입하는 아이디어를 사용했다. 스콜렘 함수는

M \models \exists y\, \varphi(y,a_1,\ldots,a_n)

일 때와 그 때만 정의되는 부분 함수로 정의될 수도 있다. 핵심은 구성된 집합

N

(또는

F^\omega(X)

)이

X

의 원소들을 매개변수로 사용하는 모든 공식에 대해

M

내에 해가 존재할 경우 그 해를 포함하며, 그 크기가

|X| + |\sigma| + \aleph_0

를 넘지 않는다는 점이다.

3. 2. 상향 뢰벤하임-스콜렘 정리 증명

주어진 모델

M

이 있다고 가정하자. 먼저,

M

의 각 원소에 해당하는 새로운 상수 기호를 추가하여 시그니처

\sigma

를 확장한다. 이렇게 확장된 시그니처를

\sigma \sqcup M

이라고 하자. 확장된 시그니처

\sigma \sqcup M

에 대한

M

의 완전한 이론

\operatorname{Th}_{\sigma \sqcup M}(M)

을 생각할 수 있는데, 이를

M

의 '''기본 도표'''(elementary diagram^영어)라고 부른다.

다음으로, 임의의 기수

\kappa

에 대해,

\kappa

개의 새로운 상수 기호

\{c_i\}_{i \in I}

(여기서

|I| = \kappa

)를 시그니처에 추가한다. 그리고

M

의 기본 도표에 "서로 다른 새로운 상수 기호는 서로 다른 값을 갖는다"는 명제들, 즉

c_i \neq c_j

(모든

i, j \in I, i \neq j

)을 추가한다.

이렇게 구성된 이론은 콤팩트성 정리에 의해 일관성이 있으며, 따라서 모델을 가진다. 이 모델은 최소

\kappa

개의 원소를 가져야 한다 (새로운 상수 기호

\kappa

개가 모두 다른 값을 가지므로).

이제 이 모델에 하향 뢰벤하임-스콜렘 정리를 적용하면, 크기가 정확히

\kappa

인 모델

N

을 찾을 수 있다. 이 모델

N

은 구성 방식에 따라 원래 모델

M

의 동형 사본을 기본 부분 구조로 포함한다.^[5]^[6] 즉,

M

을 포함하면서 크기가

\kappa

인 기본 확장

N

이 존재한다.

4. 예시 및 결과

뢰벤하임-스콜렘 정리는 1차 논리와 모형 이론에서 여러 중요한 결과를 제시하며, 특히 20세기 초 논리학자들에게는 일부 결과가 직관에 어긋나는 것으로 받아들여졌다. 이는 당시 1차적 속성과 비-1차적 속성 사이의 구분이 아직 명확하게 이해되지 않았기 때문이다.^[1]

주요 결과 중 하나는 이른바 '''스콜렘 역설'''이다. 체르멜로-프렝켈 집합론과 같은 강력한 집합론은 비가산 집합의 존재를 증명할 수 있지만, 뢰벤하임-스콜렘 정리에 따르면 이러한 집합론조차 가산 모형을 가진다. 이는 집합론 내에서 '비가산'이라고 증명된 집합이 실제로는 가산적인 모형 안에 존재할 수 있다는 역설적인 상황을 보여준다. 이 역설은 토랄프 스콜렘이 1922년에 지적했으며,^[16] 가산성 개념이 절대적인 것이 아니라 사용하는 모형에 따라 상대적임을 시사한다.^[4]

다른 중요한 결과는 '''참 산술과 실수 닫힌 체에 대한 모형'''의 존재이다. 자연수 '''N'''에 대한 이론(참 산술)은 비가산 모형을 가지며, 실수 '''R'''에 대한 이론(실수 닫힌 체)은 가산 모형을 가진다.^[1] 이는 자연수나 실수를 유일하게 특징짓는 공리화가 1차 논리만으로는 불가능함을 보여준다. 예를 들어, 실수를 완비 순서체로 특징짓는 데 필요한 완비성 공리는 1차 논리적 속성이 아니다.^[1]

또한, 뢰벤하임-스콜렘 정리는 수학 기초론에도 큰 영향을 미쳤다. 어떤 이론이 동형 사상을 제외하고 단 하나의 모형만을 가질 때 그 이론을 '''범주적'''(categorical^영어)이라고 한다. 오스왈드 베블렌이 1904년에 이 용어를 도입한 이후,^[8] 수학자들은 한때 범주적인 1차 집합론을 통해 수학의 확고한 기초를 세우고자 했다. 그러나 뢰벤하임-스콜렘 정리는 무한 모형을 가진 1차 이론은 결코 범주적일 수 없음을 보여주며 이러한 희망에 첫 타격을 가했다. 이후 괴델의 불완전성 정리(1931년)는 이러한 기대를 완전히 무너뜨렸다.^[1]

뢰벤하임-스콜렘 정리는 더 일반화된 형태로 존재하며, 이는 상향(upward) 및 하향(downward) 정리로 나뉜다.

'''하방 뢰벤하임-스콜렘 정리''': 모든 무한 모형 ''M''과 그 모형의 언어 크기 이상의 임의의 무한 기수 κ < |''M''|에 대해, 크기가 κ인 ''M''의 초등 부분 구조 ''N''이 존재한다.
'''상방 뢰벤하임-스콜렘 정리''': 모든 무한 모형 ''M''과 그 모형의 언어 크기 이상의 임의의 무한 기수 κ > |''M''|에 대해, 크기가 κ인 ''M''의 초등 확장 ''N''이 존재한다.

간단히 말해, 어떤 1차 이론이 무한 모형을 하나라도 가지면, 임의의 다른 무한 크기의 모형도 가진다는 것을 의미한다. 때때로 임의로 큰 유한 모형을 가진 이론은 반드시 무한 모형을 가져야 한다는 사실도 이 정리의 일부로 간주된다.^[1]

4. 1. 스콜렘 역설

1차 논리로 서술된 집합론(예를 들어, 선택 공리를 추가한 체르멜로-프렝켈 집합론)이 충분히 강력하다면, 이 집합론 내에서 비가산 집합의 존재를 증명할 수 있다. 그러나 하향 뢰벤하임-스콜렘 정리에 따르면, 이러한 집합론은 가산 무한 모형을 가진다. 즉, 집합론의 모든 요소들을 자연수와 일대일 대응시킬 수 있는 모형이 존재한다는 것이다. 이는 비가산 집합의 존재를 증명하는 이론이 실제로는 가산적인 모형을 가질 수 있다는 모순처럼 보이는 상황을 야기한다. 이를 '''스콜렘 역설'''(Skolem’s paradox^영어)이라고 하며, 토랄프 스콜렘이 1922년에 지적하였다.^[16]^[4]

스콜렘 역설은 실제로는 논리적인 모순이 아니며, 다음과 같이 해소될 수 있다. 집합론에서는 함수 역시 집합의 한 종류로 다루어진다. 어떤 집합

S

가 비가산 집합이라는 것은 다음 두 조건을 만족함을 의미한다.

단사 함수 $f\colon\mathbb N\to S$ 가 존재한다. (자연수 집합에서 $S$ 로 가는 일대일 함수가 있다.)
전사 함수 $f\colon\mathbb N\to S$ 는 존재하지 않는다. (자연수 집합에서 $S$ 로 가는 전사 함수, 즉 $S$ 의 모든 원소를 포함하는 함수는 없다.)

집합론의 가산 모형

M

안에서 이 명제들을 해석하면 다음과 같다.

모형 $M$ 속에는, 단사 함수 $f\colon\mathbb N\to S$ 를 나타내는 원소(집합)가 존재한다.
모형 $M$ 속에는, 전사 함수 $f\colon\mathbb N\to S$ 를 나타내는 원소(집합)가 존재하지 않는다.

그러나 모형

M

자체가 가산 집합이므로, 모형 외부의 관점에서는

M

안의 집합

S

역시 가산 집합이다. 따라서 모형 외부에서는 자연수에서

S

로 가는 전사 함수를 실제로 정의할 수 있다. 즉, 어떤 집합이 '가산'인지 '비가산'인지의 여부는 절대적인 것이 아니라, 어떤 모형 안에서 해석하느냐에 따라 달라질 수 있다는 것이다.^[1]^[4] 이 역설은 가산성이라는 개념이 절대적이지 않음을 보여주는 중요한 사례이다.^[4]

예를 들어, 실수 집합 '''R'''에 대한 이론(실수 닫힌 체의 이론)은 뢰벤하임-스콜렘 정리에 의해 가산 모형을 가진다. 이 가산 모형 안에서는 실수가 비가산 집합이라는 칸토어의 정리가 성립하지만, 모형 자체는 외부에서 보면 가산적이다.^[1]

뢰벤하임-스콜렘 정리의 이러한 결과들은 20세기 초의 논리학자들에게 매우 직관에 어긋나는 것으로 받아들여졌다. 이는 당시 1차 논리적 속성과 고차 논리적 속성 사이의 구분이 명확하게 이해되지 않았기 때문이다.^[1] 스콜렘 역설은 집합론의 형식적 체계와 그 해석(모형) 사이의 관계에 대한 깊은 이해를 요구하며, 수리논리학의 발전에 중요한 영향을 미쳤다.

4. 2. 참 산술과 실수 닫힌 체

뢰벤하임-스콜렘 정리의 결과 중 하나는 참 산술(true arithmetic)의 비가산 모델과 실수 닫힌 체(real closed field)의 가산 모델의 존재이다. 이는 20세기 초 논리학자들에게 직관에 어긋나는 것으로 받아들여졌는데, 당시에는 일차적 속성과 비일차적 속성 사이의 구분이 명확하지 않았기 때문이다.^[1]

자연수를 '''N''', 실수를 '''R'''이라고 표기하자. 뢰벤하임-스콜렘 정리에 따르면, ('''N''', +, ×, 0, 1)의 이론, 즉 참 산술의 이론은 비가산 모델을 가진다. 이러한 비가산 모델은 모든 일차 페아노 공리를 만족시키면서도, 표준 모델에는 없는 비귀납적 부분 집합을 포함할 수 있다.^[1] 반대로, ('''R''', +, ×, 0, 1)의 이론, 즉 실수 닫힌 체의 이론은 가산 모델을 가진다.^[1]

물론, 동형 사상을 제외하면 ('''N''', +, ×, 0, 1)과 ('''R''', +, ×, 0, 1)을 유일하게 특징짓는 공리화가 존재한다. 그러나 뢰벤하임-스콜렘 정리는 이러한 공리화가 일차 논리에서는 불가능함을 보여준다. 예를 들어, 실수 이론에서 실수가 완비 순서 체임을 특징짓는 데 사용되는 선형 순서의 완비성(completeness)은 일차 논리적 속성이 아니다.^[1]

이와 관련하여 특히 문제가 되었던 결과는 집합론의 가산 모델의 존재이다. 이러한 모델은 실수 집합이 비가산적이라는 문장(칸토어의 정리)을 만족시키면서도 그 자체는 가산 집합이다. 이 역설적인 상황은 스콜렘의 역설로 알려져 있으며, 가산성이라는 개념이 모델에 따라 상대적이며 절대적이지 않음을 보여준다.^[4]

5. 역사

독일의 수리논리학자 레오폴트 뢰벤하임과 노르웨이의 수리논리학자 토랄프 스콜렘이 1915년에 처음으로 이 정리의 특정 형태를 증명하였다.^[17]

모형 이론 분야에서 나온 최초의 중요한 결과 중 하나는 레오폴트 뢰벤하임이 1915년 발표한 "Über Möglichkeiten im Relativkalkül" 논문에 실린 '뢰벤하임 정리'였다.^[9] 이 정리는 다음과 같이 요약될 수 있다.

> 모든 가산 서명 ''σ''에 대해, 충족가능한 모든 ''σ'' 문장은 가산 모형에서 충족가능하다.

뢰벤하임의 논문은 실제로는 찰스 샌더스 퍼스와 슈뢰더의 표기법을 사용한 더 일반적인 내용을 다루었다. 일반적으로 뢰벤하임의 증명은 당시 아직 발표되지 않았던 쾨니그의 보조정리를 암묵적으로 사용하여 결함이 있었다고 알려져 있다. 그러나 뢰벤하임의 증명이 완전했다는 수정주의적 시각도 존재한다.

이후 토랄프 스콜렘은 1920년에 선택 공리에 기반하여 '스콜렘 표준형'이라 불리는 형식을 사용하여 올바른 증명을 제시했다.^[10]

> 모형 ''M''에서 충족가능한 모든 가산 이론은 ''M''의 가산 부분 구조에서 충족가능하다.

스콜렘은 1922년에는 선택 공리를 사용하지 않고 다음과 같은 약한 형태의 정리도 증명했다.^[11]

> 어떤 모형에서 충족가능한 모든 가산 이론은 가산 모형에서도 충족가능하다.

1929년 스콜렘은 1920년의 증명을 더욱 단순화했다.^[12] 마지막으로 아나톨리 말체프가 1936년에 뢰벤하임-스콜렘 정리를 완전한 일반성을 갖춘 형태로 증명했다.^[13] 말체프는 스콜렘의 메모를 인용하며, 알프레트 타르스키가 1928년 세미나에서 이미 이 정리를 증명했다고 언급했다. 이 때문에 일반적인 형태의 정리는 때때로 '뢰벤하임-스콜렘-타르스키 정리'라고도 불린다. 하지만 타르스키 자신은 증명 사실을 기억하지 못했으며, 콤팩트성 정리 없이 어떻게 증명했는지는 명확하지 않다.

스콜렘의 이름이 정리의 하향(downward) 방향뿐만 아니라 상향(upward) 방향과도 연결되어 있다는 점은 다소 아이러니하다. 스콜렘은 비가산 집합의 실제 존재를 믿지 않았기 때문에, 특히 정리의 상향 버전에 자신의 이름이 붙는 것을 탐탁지 않게 여겼다고 전해진다. 그는 비가산 집합을 실체가 없는 허구로 간주했기 때문에, 이러한 결과가 무의미하다고 생각했다는 일화가 있다.

6. 다른 논리에서의 뢰벤하임-스콜렘 정리

(고전적인) 뢰벤하임-스콜렘 정리는 일차 논리와 깊은 관련이 있지만, 다른 논리에도 변형된 형태로 적용되기도 한다. 예를 들어, 2차 논리의 모든 일관적인 이론은 첫 번째 초강력 기수보다 작은 크기의 모형을 가진다(단, 해당 기수가 존재한다고 가정할 경우).

어떤 논리에서 (하향) 뢰벤하임-스콜렘 정리와 비슷한 성질이 성립하는 최소 크기를 뢰벤하임 수라고 부르며, 이는 그 논리의 표현력을 나타내는 척도로 사용될 수 있다. 또한, 일차 논리를 넘어서는 더 강력한 논리 체계에서는 가산 콤팩트성, 하향 뢰벤하임-스콜렘 정리, 추상 논리의 특정 속성 중 적어도 하나는 포기해야만 한다.^[7]

참조

_[1] 서적 A Functorial Model Theory: Newer Applications to Algebraic Topology, Descriptive Sets, and Computing Categories Topos https://books.google[...] Apple Academic Press; CRC Press 2014
_[2] 서적 The Logic of Infinity https://books.google[...] Cambridge University Press 2014
_[3] 서적 Parameterized Complexity in the Polynomial Hierarchy: Extending Parameterized Complexity Theory to Higher Levels of the Hierarchy https://books.google[...] Springer 2019
_[4] 간행물 Skolem's Paradox https://plato.stanfo[...] 2014
_[5] 간행물 The Journal of Symbolic Logic Association for Symbolic Logic 1981
_[6] 서적 A Friendly Introduction to Mathematical Logic https://books.google[...] Milne Library 2015
_[7] 서적 Model Theory https://books.google[...] Dover Publications 1990
_[8] 문서 Veblen 1904
_[9] 문서 Löwenheim 1915
_[10] 문서 Skolem 1920
_[11] 문서 Skolem 1923
_[12] 문서 Skolem 1929
_[13] 문서 Maltsev 1936
_[14] 서적 Model theory: an introduction Springer 2002
_[15] 서적 Handbook of philosophical logic, volume 1 https://web.archive.[...] Kluwer 2001
_[16] 서적 Fünften Kongress der skandinavischen Mathematiker in Helsingfors vom 4. bis 7. Juli 1922 1923
_[17] 서적 A mathematical introduction to logic https://web.archive.[...] Academic Press 2002

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com