콤팩트성 정리

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

1. 개요

콤팩트성 정리는 1차 논리 이론 T의 모든 유한 부분 집합이 만족 가능하면 T도 만족 가능하다는 정리이다. 이 정리는 1차 논리 이론의 무모순성과 만족 가능성, 국소 무모순성과 국소 만족 가능성 간의 관계를 설명하며, 괴델의 완전성 정리와 동치이다. 콤팩트성 정리는 모델 이론에서 다양한 응용 분야를 가지며, 로빈슨의 원리, 상향 뢰벤하임-스콜렘 정리, 비표준 해석 구성 등에 활용된다. 이 정리는 괴델의 완전성 정리, 초곱, 초생성 등을 통해 증명할 수 있으며, 명제 논리에서의 콤팩트성은 티호노프 정리와 연관된다.

더 읽어볼만한 페이지

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

콤팩트성 정리
일반 정보
분야	수리논리학
하위 분야	모형 이론
관련 항목	괴델 완전성 정리 뢰벤하임-스콜렘 정리
정의
내용	주어진 논리식의 모든 유한 부분 집합이 모형을 가지면, 그 논리식 전체도 모형을 가진다.
설명	만약 Σ가 1차 논리 문장의 집합이고 Σ의 모든 유한 부분 집합이 모형을 가지면, Σ는 모형을 가진다. 또는 Γ가 1차 논리 문장의 집합이고 Γ의 모든 유한 부분 집합이 만족 가능하다면, Γ는 만족 가능하다.
성립 조건
조건	1차 논리에서만 성립한다.
활용
활용 분야	비표준 해석학
참고
관련 정리	괴델 완전성 정리 뢰벤하임-스콜렘 정리

2. 정의

'''콤팩트성 정리'''에 따르면, 부호수 $\sigma$ 의 (등호를 포함하는) 1차 논리 이론 $T$ 에 대하여, 다음은 서로 동치이다.

조건	설명
무모순성	$T\nvdash\bot$
만족 가능성	$M\models T$ 인 $\sigma$ -구조 $M$ 이 존재한다.
가산 만족 가능성	$M\models T$ 인 가산 $\sigma$ -구조 $M$ 이 존재한다.
국소 무모순성	$T$ 의 모든 유한 부분 집합 $S\subset T$ 에 대하여, $S\nvdash\bot$
국소 만족 가능성	$T$ 의 모든 유한 부분 집합 $S\subset T$ 에 대하여, $M_S\models S$ 인 $\sigma$ -구조 $M_S$ 가 존재한다.
국소 가산 만족 가능성	$T$ 의 모든 유한 부분 집합 $S\subset T$ 에 대하여, $M\models S$ 인 가산 $\sigma$ -구조 $M_S$ 가 존재한다.

이들은 1차 논리 이론의 콤팩트성 정리에 대한 여러 가지 동치인 정의들이다.

2. 1. 무모순성과 만족 가능성

1차 논리 이론

T

에 대하여, 다음 조건들은 서로 동치이다.

조건	설명
무모순성	$T\nvdash\bot$
만족 가능성	$M\models T$ 인 $\sigma$ -구조 $M$ 이 존재한다.
가산 만족 가능성	$M\models T$ 인 가산 $\sigma$ -구조 $M$ 이 존재한다.
국소 무모순성	$T$ 의 모든 유한 부분 집합 $S\subset T$ 에 대하여, $S\nvdash\bot$
국소 만족 가능성	$T$ 의 모든 유한 부분 집합 $S\subset T$ 에 대하여, $M_S\models S$ 인 $\sigma$ -구조 $M_S$ 가 존재한다.
국소 가산 만족 가능성	$T$ 의 모든 유한 부분 집합 $S\subset T$ 에 대하여, $M\models S$ 인 가산 $\sigma$ -구조 $M_S$ 가 존재한다.

2. 2. 국소 무모순성과 국소 만족 가능성

1차 논리 이론

T

에 대하여, 다음은 서로 동치이다.

명제	설명
국소 무모순성	$T$ 의 모든 유한 부분 집합 $S\subset T$ 에 대하여, $S\nvdash\bot$ 이다.
국소 만족 가능성	$T$ 의 모든 유한 부분 집합 $S\subset T$ 에 대하여, $M_S\models S$ 인 $\sigma$ -구조 $M_S$ 가 존재한다.
국소 가산 만족 가능성	$T$ 의 모든 유한 부분 집합 $S\subset T$ 에 대하여, $M\models S$ 인 가산 $\sigma$ -구조 $M_S$ 가 존재한다.

2. 3. 가산 만족 가능성

'''콤팩트성 정리'''에 따르면, 부호수

\sigma

의 (등호를 포함하는) 1차 논리 이론

T

에 대하여,

M\models T

인 가산

\sigma

-구조

M

이 존재한다는 내용이다.

3. 역사

콤팩트성 정리는 쿠르트 괴델이 1930년에 가산 부호수에 대한 경우를 증명하였고,^[12] 아나톨리 말체프가 1936년에 이를 비가산 집합을 포함하는 일반적인 경우로 확장하였다.^[13]^[14]

3. 1. 쿠르트 괴델의 초기 증명 (1930)

쿠르트 괴델은 1930년에 가산 부호수에 대한 콤팩트성 정리를 증명하였다.^[12]

3. 2. 아나톨리 말체프의 확장 (1936)

쿠르트 괴델은 1930년에 가산 부호수에 대한 콤팩트성 정리를 증명하였다.^[12] 아나톨리 말체프는 1936년에 이를 비가산 집합을 포함하는 일반적인 경우로 확장하였다.^[13]^[14]

4. 응용

콤팩트성 정리는 모형 이론에서 여러 중요한 결과들을 증명하는 데 사용된다.

콤팩트성 정리를 이용하면, 1차 논리적 명제가 표수가 0인 임의의 체에 대해 성립한다면, 어떤 상수 p가 존재해서 표수가 p보다 큰 임의의 체에 대해서도 이 명제가 성립함을 보일 수 있다.^[11]

명제 논리의 콤팩트성 정리는 불 대수의 스톤 쌍대성에 따라, 스톤 공간에 대한 티호노프 정리(콤팩트 공간의 임의의 곱이 여전히 콤팩트 공간)와 동치이다. "콤팩트성 정리"라는 이름은 이로부터 기인하였다.

콤팩트성 정리는 악스-그로텐디크 정리의 특수한 경우를 증명하는데 사용될 수 있다. 예를 들어 모든 단사 복소수 다항식 $\Complex^n \to \Complex^n$ 은 전사이다.

또한, 콤팩트성 정리는 상향 뢰벤하임-스콜렘 정리를 증명하거나, 비표준 모형을 구성하는 등 다양한 분야에 응용된다.

4. 1. 로빈슨의 원리

로빈슨의 원리는 1차 논리가 체의 표수가 0인 모든 체에서 성립한다면, 상수

p

가 존재하여 그 논리가 표수가

p

보다 큰 모든 체에서 성립한다는 정리이다.

이 정리는 다음과 같이 증명할 수 있다.

\varphi

가 표수가 0인 모든 체에서 성립하는 논리라고 가정하자. 그러면 그 부정

\lnot \varphi

는 체 공리 및 다음 무한 수열의 논리와 함께 만족가능하지 않다.

1 + 1 \neq 0, \;\; 1 + 1 + 1 \neq 0, \; \ldots

왜냐하면

\lnot \varphi

가 성립하는 표수 0인 체가 없고, 위 무한 수열의 논리는 모든 모델이 표수 0인 체가 되도록 보장하기 때문이다. 따라서, 이러한 논리의 유한 부분 집합

A

는 만족가능하지 않다. 만약

A

가

\lnot \varphi

를 포함하지 않는다면,

A

는 만족가능할 것이다. 따라서

A

는

\lnot \varphi

를 포함해야 한다.

A

에 더 많은 논리를 추가해도 만족 불가능성은 유지되므로,

A

가 체 공리와

k

에 대해

1 + 1 + \cdots + 1 \neq 0

형식의 처음

k

개 논리를 포함한다고 가정할 수 있다. 이제

B

를

\lnot \varphi

를 제외한

A

의 모든 논리라고 하자. 그러면 표수가

k

보다 큰 모든 체는

B

의 모델이 되고,

\lnot \varphi

와

B

는 함께 만족가능하지 않다. 이는

\varphi

가

B

의 모든 모델에서 성립해야 함을 의미하며, 이는 정확히

\varphi

가 표수가

k

보다 큰 모든 체에서 성립함을 의미한다.

4. 2. 레프셰츠 원리

콤팩트성 정리는 모형 이론과 여러 분야에서 다양하게 응용된다. 콤팩트성 정리를 사용하여 증명되는 대표적인 예시는 다음과 같다.

로빈슨의 원리: 일계 술어 논리 문장 φ가 표수가 0인 임의의 체에서 성립하면, 어떤 자연수 k가 존재하여 φ는 표수가 k 이상인 모든 체에서 성립한다.^[9]

4. 3. 악스-그로텐디크 정리

콤팩트성 정리는 모형 이론에서 여러 분야에 응용된다. 다음은 콤팩트성 정리를 이용해 증명되는 명제들이다.

상향 뢰벤하임-스콜렘 정리
실수나 자연수의 초표준 모델의 존재
로빈슨의 원리(일계 술어 논리의 문장 φ가 임의의 표수 0의 체에서 성립한다면, 어떤 자연수 k가 존재하여, φ는 표수가 k 이상인 모든 체에서 성립한다)
국가의 수가 무한한 경우의 사색 정리^[9]
임의의 순서 집합이 전순서로 확장될 수 있다는 것 ^[9]

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

콤팩트성 정리의 응용 사례로 임의로 큰 유한 모델 또는 단일 무한 모델을 갖는 모든 이론은 임의로 큰 기수의 모델을 갖는다는 것을 보여주는 것이 있는데, 이를 상향 뢰벤하임-스콜렘 정리라고 한다. 예를 들어 '자연수'가 무한히 많은 비표준 페아노 산술 모델이 존재한다. 이를 증명하는 방법은 다음과 같다.^[11]

:

T

를 초기 이론,

\kappa

를 임의의 기수라고 하자.

T

의 언어에

\kappa

의 모든 원소에 대해 하나의 상수 기호를 추가한다. 그리고 새로운 컬렉션의 서로 다른 두 상수 기호에 의해 표시되는 객체가 서로 다르다고 말하는 문장의 모음을

T

에 추가한다(이것은

\kappa^2

문장의 모음이다). 이 새로운 이론의 모든 하위 집합은

T

의 충분히 큰 유한 모델 또는 임의의 무한 모델에 의해 만족될 수 있으므로, 전체 확장된 이론은 만족될 수 있다. 그러나 확장된 이론의 모든 모델은 기수가 최소한

\kappa

이다.^[11]

4. 5. 비표준 해석

초실수에 대한 비표준 모형을 구성하는 것은 콤팩트성 정리의 응용 중 하나이다. 이를 위해 실수 이론의 일차 논리적 공리화인

\Sigma

를 생각하자. 여기에 새로운 상수 기호

\varepsilon

를 추가하고,

\Sigma

에 공리

\varepsilon > 0

와 모든 양의 정수

n

에 대해 공리

\varepsilon < \tfrac{1}{n}

을 추가한 이론을 고려한다.

표준 실수의 집합

\R

는 이 공리들의 모든 유한 부분 집합에 대한 모형이 된다. 왜냐하면 실수는

\Sigma

의 모든 것을 만족시키고,

\varepsilon

를 적절하게 선택하여

\varepsilon

에 대한 공리의 모든 유한 부분 집합을 만족시킬 수 있기 때문이다. 콤팩트성 정리에 의해,

\Sigma

를 만족시키면서 무한소 원소

\varepsilon

를 포함하는 모형

{}^* \R

이 존재한다.

비슷한 논증으로, 공리

\omega > 0, \; \omega > 1, \ldots

등을 추가하여 무한히 큰 크기를 가진 숫자의 존재가 실수에 대한 어떤 공리화

\Sigma

로도 배제될 수 없음을 보일 수 있다.

초실수

{}^* \R

은 전달 원리를 만족한다. 즉, 일차 논리적 문장이

\R

에 대해 참일 필요충분조건은

{}^* \R

에 대해서도 참인 것이다.

4. 6. 기타 응용 (일본어 위키 참고)

콤팩트성 정리는 모델 이론을 비롯한 다양한 분야에서 응용된다. 예를 들어, 다음 정리나 명제는 콤팩트성 정리를 사용하여 증명할 수 있다.

국가의 수가 무한한 경우의 사색 정리^[9]
임의의 순서 집합이 전순서로 확장될 수 있다는 것^[9]

5. 증명

괴델의 완전성 정리를 사용하면 콤팩트성 정리를 증명할 수 있다. 괴델의 완전성 정리는 문장 집합이 모순으로부터 증명될 수 없는 경우에만 만족할 수 있음을 보여준다.^[6] 수학적 증명은 항상 유한하므로 주어진 문장 중 유한 개만 포함되어 콤팩트성 정리가 성립한다. 콤팩트성 정리는 괴델의 완전성 정리와 동치이며, 이 둘은 선택 공리의 약한 형태인 불 대수 소 아이디얼 정리와도 동치이다.^[6]

괴델은 처음에 이 방식으로 콤팩트성 정리를 증명했지만, 나중에 콤팩트성 정리의 "순수하게 의미론적인" 증명이 발견되었다. 이 증명은 증명 가능성^영어이 아닌 진실^영어을 언급하며, 초생성을 사용하고 선택 공리에 의존한다.

콤팩트성 정리는 괴델의 완전성 정리로부터 유도할 수 있다. 일차 술어 논리의 문장 집합 S가 모델을 갖지 않는다고 가정하면, 완전성 정리에 의해 S는 모순을 갖게 된다. 어떤 증명도 길이는 유한하므로, 모순의 증명에 나타나는 S의 문장은 많아야 유한 개이다. 따라서 S의 어떤 유한 부분으로부터 모순이 유도된다는 것, 즉 S는 충족 불가능한 부분 집합을 갖는다는 것을 알 수 있다. 이것의 대우가 콤팩트성 정리이다.^[9]

이 외에도, 초곱을 사용한 증명도 알려져 있다.

5. 1. 괴델의 완전성 정리를 이용한 증명

괴델의 완전성 정리를 사용하면 콤팩트성 정리를 증명할 수 있다. 괴델의 완전성 정리는 문장 집합이 모순으로부터 증명될 수 없는 경우에만 만족할 수 있다는 것을 보여준다.^[6] 수학적 증명은 항상 유한하고 따라서 주어진 문장 중 유한 개만 포함되므로 콤팩트성 정리가 성립한다. 콤팩트성 정리는 괴델의 완전성 정리와 동치이며, 이 둘은 선택 공리의 약한 형태인 불 대수 소 아이디얼 정리와도 동치이다.^[6]

괴델은 처음에 이 방식으로 콤팩트성 정리를 증명했지만, 나중에 콤팩트성 정리의 "순수하게 의미론적인" 증명이 발견되었다. 이 증명은 ~~이 아닌 ~~ 을 언급하며, 초생성을 사용하고 선택 공리에 의존한다.
증명:1차 언어

L

을 고정하고,

\Sigma

를

L

-문장의 모음이라고 하자.

L

-문장의 모든 유한 부분 모음

i \subseteq \Sigma

가 모델

\mathcal{M}_i

를 가진다고 가정한다. 구조들의 직접곱을

\prod_{i \subseteq \Sigma}\mathcal{M}_i

로 놓고,

I

를

\Sigma

의 유한 부분 집합 모음으로 둔다. 각

i \in I

에 대해

A_i = \{j \in I : j \supseteq i\}

로 정의한다.

이러한 모든 집합

A_i

의 모임은 고유 필터 (집합론)를 생성하므로,

A_i

형태의 모든 집합을 포함하는 초필터 (집합론)

U

가 존재한다.

이제

\Sigma

의 모든 문장

\varphi

에 대해 다음이 성립한다.

집합 $A_{\{\varphi\}}$ 는 $U$ 에 속한다.
$j \in A_{\{\varphi\}}$ 인 경우마다 $\varphi \in j$ 이므로 $\varphi$ 는 $\mathcal M_j$ 에서 성립한다.
$\varphi$ 가 $\mathcal M_j$ 에서 성립하는 모든 $j$ 의 집합은 $A_{\{\varphi\}}$ 의 상위 집합이므로 $U$ 에도 속한다.

Łoś의 정리에 따르면

\varphi

는 초생성

\prod_{i \subseteq \Sigma} \mathcal{M}_i/U

에서 성립한다. 따라서 이 초생성은

\Sigma

의 모든 공식을 만족시킨다.

콤팩트성 정리는 괴델의 완전성 정리로부터 유도할 수 있다. 일차 술어 논리의 문장 집합 S가 모델을 갖지 않는다고 가정하면, 완전성 정리에 의해 S는 모순을 갖게 된다. 어떤 증명도 길이는 유한하므로, 모순의 증명에 나타나는 S의 문장은 많아야 유한 개이다. 따라서 S의 어떤 유한 부분으로부터 모순이 유도된다는 것, 즉 S는 충족 불가능한 부분 집합을 갖는다는 것을 알 수 있다. 이것의 대우가 콤팩트성 정리이다.^[9]

5. 2. 초곱을 이용한 증명

1차 논리 언어

L

을 고정하고,

\Sigma

를

L

-문장의 모음으로 하여,

L

-문장의 모든 유한 부분 모음

i \subseteq \Sigma

가 모델

\mathcal{M}_i

를 갖도록 한다. 또한 구조들의 직접곱을

\prod_{i \subseteq \Sigma}\mathcal{M}_i

로,

I

를

\Sigma

의 유한 부분 집합 모음으로 한다. 각

i \in I

에 대해

A_i = \{j \in I : j \supseteq i\}

로 놓는다. 이러한 모든 집합

A_i

의 모임은 고유 필터 (집합론)를 생성하므로,

A_i

형태의 모든 집합을 포함하는 초필터 (집합론)

U

가 존재한다.

이제

\Sigma

의 모든 문장

\varphi

에 대해:

집합 $A_{\{\varphi\}}$ 는 $U$ 에 속한다.
$j \in A_{\{\varphi\}}$ 인 경우마다 $\varphi \in j$ 이므로 $\varphi$ 는 $\mathcal M_j$ 에서 성립한다.
$\varphi$ 가 $\mathcal M_j$ 에서 성립하는 모든 $j$ 의 집합은 $A_{\{\varphi\}}$ 의 상위 집합이므로 $U$ 에도 속한다.

Łoś의 정리에 따르면

\varphi

는 초곱

\prod_{i \subseteq \Sigma} \mathcal{M}_i/U

에서 성립한다. 따라서 이 초곱은

\Sigma

의 모든 공식을 만족한다.

6. 다른 논리 체계에서의 콤팩트성

명제 논리에서의 콤팩트성 정리는 위상 공간론의 티호노프 정리를 스톤 공간에 적용하여 얻을 수 있다^[10]. 린드스트룀의 정리는 콤팩트성 정리와 (아래로) 레벤하임-뢰벤하임-스콜렘 정리가 일계 술어 논리를 특징짓는 성질임을 보여준다. 고계 술어 논리에서는 어떤 종류의 콤팩트성은 유지되지만, 콤팩트성 정리 자체는 성립하지 않는다^[10].

6. 1. 명제 논리와 티호노프 정리

명제 논리에서의 콤팩트성 정리는 위상 공간론의 티호노프 정리를 스톤 공간에 적용하여 얻을 수 있다^[10]. 린드스트룀의 정리는 콤팩트성 정리와 (아래로) 레벤하임-뢰벤하임-스콜렘 정리가 일계 술어 논리를 특징짓는 성질임을 보여준다. 고계 술어 논리에서는 어떤 종류의 콤팩트성은 유지되지만, 콤팩트성 정리 자체는 성립하지 않는다.

6. 2. 고차 논리

고계 술어 논리에서는 어떤 종류의 콤팩트성은 유지되지만, 콤팩트성 정리 자체는 성립하지 않는다.^[10]

참조

_[1] 문서 Truss (1997)
_[2] 논문 Model-Theoretic Logics https://projecteucli[...] Springer-Verlag 1985
_[3] 논문 Alfred Tarski's work in model theory 1986
_[4] 서적 Non-standard analysis North-Holland Publishing Co. 1966
_[5] 웹사이트 Infinite fields, finite fields, and the Ax-Grothendieck theorem https://terrytao.wor[...] 2009-03-07
_[6] 문서 Hodges (1993)
_[7] 논문 Alfred Tarski's work in model theory 1986
_[8] 서적 Non-standard analysis North-Holland Publishing Co. 1966
_[9] url http://www.math.tsuk[...]
_[10] 문서 Truss (1997)
_[11] 서적 Foundations of Mathematical Analysis https://archive.org/[...] Oxford University Press 1997
_[12] 저널 Die Vollständigkeit der Axiome des logischen Functionenkalküls 1930
_[13] 논문 Alfred Tarski's work in model theory 1986
_[14] 서적 Non-standard analysis North-Holland Publishing Co. 1966

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

문의하기 : help@durumis.com