콤팩트성 정리

수학적 논리학에서 콤팩트성 정리(compactness theorem)는 모든 유한 부분 집합이 모형을 갖는 경우에만 1차 문장 집합이 모형을 갖는다는 것을 말합니다.이 정리는 모든 문장 집합의 모델을 유한하게 일관되게 구성하는 유용한(일반적으로 효과적이지 않은) 방법을 제공하기 때문에 모델 이론에서 중요한 도구입니다.

명제적 미적분학에 대한 콤팩트함 정리는 콤팩트한 스톤 공간에 적용된 티초노프의 정리(콤팩트 공간의 곱이 콤팩트하다는 것을 말한다)의 결과이며,^[1] 따라서 그 정리의 이름이 지어졌습니다.마찬가지로 위상 공간에서 콤팩트함의 유한 교집합 속성과 유사합니다. 콤팩트 공간에서 닫힌 집합의 집합은 모든 유한 부분 집합에 비어 있지 않은 교집합이 있을 경우 비어 있지 않은 교집합이 있습니다.

콤팩트성 정리는 린드스트룀의 정리에서 1차 논리를 특성화하는 데 사용되는 하향 뢰벤하임-스콜렘 정리와 함께 두 가지 주요 성질 중 하나입니다.콤팩트성 정리를 1차가 아닌 논리로 일반화한 것이 몇 가지 있지만, 매우 제한된 수의 예제를 제외하고는 콤팩트성 정리 자체가 성립하지 않습니다.^[2]

역사

쿠르트 괴델은 1930년에 계산 가능한 콤팩트성 정리를 증명했습니다.아나톨리 말체프는 1936년에 셀 수 없는 사건을 증명했습니다.^[3][4]

적용들

콤팩트성 정리는 모델 이론에 많은 응용을 가지고 있으며, 몇 가지 전형적인 결과가 여기에 스케치되어 있습니다.

로빈슨의 원리

콤팩트성 정리는 에이브러햄 로빈슨이 1949년 논문에서 밝힌 다음과 같은 결과를 의미합니다.

로빈슨의 원칙:^[5][6]만약 1차 문장이 특성 0의 모든 필드에 성립한다면, 문장이 $p$보다 큰 특성의 모든 필드에 성립하는$$ 일정한 $p{\displaystyle }$ ${\displaystyle p}$가 존재합니다.${\displaystyle p.}$$$ 다음과 같이 볼 수 있습니다. $\phi$ ${\displaystyle \varphi$}이$($가) 특성 0의 모든 필드에 성립하는 문장이라고 가정합니다.그렇다면 필드 공리 및 문장의 무한 순서와 함께 그것의 부정 ¬ φ${\displaystyle ,}$ ${\displaystyle \lnot \varphi}$

만족스럽지 않습니다(왜냐하면 ¬ φ ${\displaystyle \lnot \varphi$}이(가) 유지되는 특성 0의 필드가 없고, 문장의 무한한 시퀀스가 어떤 모델이든 특성 0의 필드가 되도록 보장하기 때문입니다).따라서 이러한 문장의 유한$$ 부분 $집합{\displaystyle }$ A ${\displaystyle$ A$}$는 만족스럽지 않습니다.${\displaystyle A$에는 ¬ ${\displaystyle \phi }$ ${\displaystyle \not \varphi}$이(가) 포함되어 있어야 합니다.$A$ ${\displaystyle A}$에 문장을 더 추가해도 만족스럽지 않음이 변하지 않으므로, $A$ ${\displaystyle$ $A$$}$에 필드 공리가 포함되어 있고, 일부 $k$의 경우${\displaystyle ,}$ $1{\displaystyle }$+ ${\displaystyle 1}$+${\displaystyle }$⋯ + ${\displaystyle 1}$ ≠ 0의 첫 k ${\displaystyle k}$개의 문장이 포함되어 있다고 가정할 수 있습니다${\displaystyle \mathrm{.}}$ ${\displaystyle$ 1+1$+\cdots +1\neq 0.}$ $B$ ${\displaystyle B}$에 모든 문장이 포함되어 있다고 가정합니다.${\displaystyle f}$$$¬ φ을(를) 제외한 {\$displaystyle A$${\displaystyle \}.}${\$displaystyle \not \varphi$$.}$ 그러면 $특성$이$$k보다 큰 필드가 $B$${\displaystyle ,}${\$displaystyle B,}$ 및 ¬ φ ${\displaystyle \not \varphi}$의 모델이며 B ${\displaystyle$ B$}$과(와) 함께 사용할 수 없습니다.$즉$, ${\displaystyle \varphi$} φ은(는$)$ $B$의 모든 모델${\displaystyle B}$에 고정되어야 합니다. 즉, ${\displaystyle \varphi$} φ은(는$)$ $k$보다 큰 특성의 모든 필드에 고정됩니다${\displaystyle .}$ ${\displaystyle$ k$.}$ 이로써 증명이 완료됩니다.

전이 원리의 첫 번째 예 중 하나인 Lefschetz 원리는 이 결과를 확장합니다.링 언어의 1차 문장 φ ${\displaystyle \varphi }$은 특성 0의 일부(예를 들어 복소수와 같이) 대수적으로 닫힌 필드에서 참이며, 이는 φ ${\displaystyle \varphi }$이(가) 어떤 대수적으로 cl에서 참인 $소수$ ${\displaystyle p}$가 무한히 많은 경우에만 해당됩니다.특성 $p{\displaystyle ,}$ ${\displaystyle p,}$ 이 경우 φ ${\displaystyle \varphi}$는 충분히 큰 0이 아닌 특성 $p$의 모든 대수적으로 닫힌 필드에서 참입니다${\displaystyle .}$ ${\displaystyle p.}$ 하나의 결과는 다음과 같은 Ax-Grothendiek 정리의 특수한 경우이다: 모든 주입 복소수 다항식 ${\displaystyle {}^{}}$ → ${\displaystyle {}^{}}$ ${\displaystyle \mathbb {C}$$^{n}\to \mathbb {C} ^{n}}$는 사사적입니다^[5](실제로, 그 역이 다항식이 ^[7]될 것이라는 것을 보여줄 수도 있습니다).사실, $임의$의$$주입 $다항식$ Fn${\displaystyle {}^{}}$→ $Fn$ {\$displaystyle F^{n}\to$ F$^{n}$에 대해서도, F{\displaystyle F$}$가 유한장이거나 그러한 장의 대수적 폐쇄에 대해서도 주관성 결론은 그대로 유지됩니다.

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

콤팩트성 정리의 두 번째 적용은 임의로 큰 유한 모델 또는 단일 무한 모델을 갖는 이론이 임의로 큰 카디널리티의 모델을 갖는다는 것을 보여줍니다(이는 상향 뢰벤하임-스콜렘 정리).예를 들어, 셀 수 없이 많은 '자연수'를 가진 페아노 산술의 비표준 모델이 있습니다.이를 위해 $T$ ${\displaystyle T}$를 초기 이론이라 하고 κ ${\displaystyle$\kappa$}$을(를) 임의의 기수라고 합니다.$T$ ${\displaystyle T}$의 언어에 κ의 모든 요소에 대해 하나의 상수 기호를 추가합니다${\displaystyle .}$ ${\displaystyle \kappa .}$ 그런 다음 $T$ ${\displaystyle T}$에 새 집합에서 구별되는 두 개의 상수 기호로 표시되는 객체가 서로 다르다는 문장 모음을 추가합니다(이는 κ ${\displaystyle 2^{}}$ ${\displaystyle \kappa ^{2}}$개의 문장 모음입니다).이 새로운 이론의 모든 유한 부분 집합은 $충분히{\displaystyle }$ 큰 T${\displaystyle ,}$ ${\displaystyle T}$의 유한 모델 또는 무한$$ 모델에 의해 만족될 수 있기 때문에, 전체 확장 이론은 만족될 수 있습니다.그러나 확장 이론의 모형은 최소 κ ${\displaystyle \kappa}$개의 카디널리티를 가집니다$.$

비표준분석

콤팩트성 정리의 세 번째 적용은 실수의 비표준 모델, 즉 "무한한" 수를 포함하는 실수 이론의 일관된 확장의 구성입니다.이것을 보기 위해서, σ ${\displaystyle \Sigma}$를 실수 이론의 1차 공리화라고 하자.언어에 새로운 상수 기호 ε ${\displaystyle \varepsilon$}을$($를) 추가하고$$σ {\displaystyle \$Sigma$ 공리 ε > 0 {\$displaystyle$$\varepsilon >0}$ 및 모든 양의 정수에 대한 공리$$ε < 1 n ${\displaystyle \varepsilon$<{\tfrac {$1}$ {$n}}$에 인접하여 얻은 이론을 생각해 $보십시오$. {\displaystyle $n.}$ 분명 표준 실수입니다.$s$ ${\displaystyle \mathbb {R}}$은$($는) 이러한 공리들의 모든 유한 부분집합에 대한 모형이며, 실수는 σ ${\displaystyle \Sigma}$의 모든 것을 만족하고, ε의 적절한 선택에 의해${\displaystyle \varepsilon,}$은(는) ε에 관한 공리들의 유한 부분집합을 만족하도록 만들어질 수 있습니다${\displaystyle .}$ ${\displaystyle \varepsilon.}$ 콤팩트성 정리에 의해, is σ ${\displaystyle \Sigma$}을(를$)$ 충족하고 무한소 원소 ε을 포함하는 ${\displaystyle {}^{*}\mathbb {R}}$ ${\displaystyle {}^{}}$ ∗${\displaystyle \varepsilon}$

비슷한 논법으로, 이번에는 공리 ω> ω> ${\displaystyle \omega >0,\;\omega >1,\ldots,}$ 등과 인접하여, 무한히 큰 크기를 가진 수의 존재는 실수의 공리화 σ ${\displaystyle \Sigma}$에 의해 배제될 수 없음을 보여줍니다.

초실수 ∗ ${\displaystyle {}^{}}$ ${\displaystyle {}^{*}\mathbb {R}}이($가) 전달 원리를 만족한다는 것을 알 수 있습니다. 1차 문장은$$∗ ${\displaystyle {}^{}}$에 참인 $경우$에만 R ${\$displaystyle \$mathbb {R}$에 참입니다${\displaystyle .}$ ${\displaystyle {}^{*}\mathbb {R}.$

프루프

어떤 모순도 증명할 수 없는 경우에만 만족할 수 있다는 것을 확립하는 괴델의 완전성 정리를 사용하여 콤팩트성 정리를 증명할 수 있습니다.증명은 항상 유한하기 때문에 주어진 문장의 많은 부분만 포함하기 때문에 콤팩트성 정리는 다음과 같습니다.사실, 콤팩트성 정리는 괴델의 완전성 정리와 동등하며, 둘 다 선택 공리의 약한 형태인 부울 프라임 아이디얼 정리와 동등합니다.^[10]

괴델은 원래 이런 방식으로 콤팩트성 정리를 증명했지만, 나중에 콤팩트성 정리의 "순수한 의미론적" 증명들이 발견되었습니다. 즉, 진리를 언급하지만 증명 가능성을 언급하지 않는 증명들입니다.이러한 증명 중 하나는 다음과 같이 선택 공리에 의존하는 울트라 제품에 의존합니다.

증명: 1차 언어 $L$ ${\displaystyle$ L$,}$을(를) 고정하고 σ ${\displaystyle \Sigma}$를 L {\$displaystyle L}$ 문장의 $모든$ 유한 부분 집합 i ⊆ $$σ ${\displaystyle$ i\$subseteq \Sigma}$문장이 모델 ${\displaystyle {Mi}_{}}$를${\displaystyle {}_{}}$가지도록$$L 문장의 $집합$이라고 합니다. ${\displaystyle$ {\mathcal ${M}_{i}$$}$또한 $∏$ $\underset{}{i}$ $σ$$$$⊆$ ${Mi}_{}$ ${\textstyle$ \$prod$ $_{i\$$subset$eq $\Sigma }{\mathcal {M}_{i}}$를 구조의 직접 곱이라 하고 $I$ ${\displaystyle$ I$}$을(를) $σ$의 유한 부분 집합이라고 합니다${\displaystyle .}$ ${\displaystyle \Sigma .}$ 각 $i$ $∈$ ${\displaystyle I}$에 대해${\displaystyle i\in$ I$,}$을(를) $A$ ${\displaystyle i_{}}$ $=$${\displaystyle }${${\displaystyle j}$ $∈$ ${\displaystyle I}$: ${\displaystyle j}$ $⊇$ ${\displaystyle i}$ ${\displaystyle \}}$이라 합니다${\displaystyle .}$ ${\displaystyle A_{i$}$=$\{$j\in$ I $:j\supsequ i\}}.$$$ 이 모든 집합의 패밀리 ${\displaystyle {Ai}_{}}$ ${\$는 적절한 필터를 생성하므로$$ 형식 ${\displaystyle {Ai}_{}}$의 모든 집합을 포함하는$$ 울트라필터 U ${\displaystyle U}$가 있습니다${\displaystyle {}_{}}$ ${\displaystyle A_{i}}$

$이제$ σ의 모든 공식$$φ {\displaystyle \$varphi$${\displaystyle \}:}$ ${\displaystyle \Sigma :}$

• 집합 $A$ {${\displaystyle {}_{}}$φ } ${\displaystyle A_{\{\varphi \}}$가 $U$ ${\displaystyle U}$에 있습니다.
• ${\displaystyle {}_{}}$가 {φ },${\displaystyle j\in A_{\varphi \}}$를 φ ∈할 때마다 ${\displaystyle j,}$ ${\displaystyle \varphi \in$ j$,}$를 φ하므로 {\$displaystyle$\varphi$}$가 Mj$$${\displaystyle {M}_{j}$에 $있습니다.$
• φ ${\displaystyle$ \$varphi$}이$($가) Mj ${\displaystyle$ {M$}_{j}$에 있는 속성을 가진 모든 $j$ ${\displaystyle$ j$}$의 집합은 A {${\displaystyle {}_{}}$φ }, ${\displaystyle A_{\varphi \}}$의 상위 집합이므로 U {\$displaystyle$ U}에도 있습니다$.$

ś의 정리는 이제 ${\displaystyle \varphi}$φ가 초자수 ∏ i ⊆ σ 미${}_{}$/ $U.$ ${\textstyle \prod _{i\subseteq \Sigma }{\mathcal {M}_{i}/U.}$ 따라서 이 초자수 제품은 σ의${\displaystyle }$모든 공식을 만족시킵니다. ${\displaystyle \Sigma .}$

참고 항목

• 바르와이즈 콤팩트성 정리
• Herbrand의 정리 – 1차 수학적 논리를 명제 논리로 축소 위키데이터 설명을 폴백으로 표시하는 페이지
• 부울 대수학 주제 목록
• 뢰벤하임-스콜렘 정리 – 논리 이론 모형의 존재와 카디널리티

메모들

참고문헌

• Boolos, George; Jeffrey, Richard; Burgess, John (2004). Computability and Logic (fourth ed.). Cambridge University Press.
• Chang, C.C.; Keisler, H. Jerome (1989). Model Theory (third ed.). Elsevier. ISBN 0-7204-0692-7.
• Dawson, John W. junior (1993). "The compactness of first-order logic: From Gödel to Lindström". History and Philosophy of Logic. 14: 15–37. doi:10.1080/01445349308837208.
• Hodges, Wilfrid (1993). Model theory. Cambridge University Press. ISBN 0-521-30442-3.
• Goldblatt, Robert (1998). Lectures on the Hyperreals. New York: Springer Verlag. ISBN 0-387-98464-X.
• Gowers, Timothy; Barrow-Green, June; Leader, Imre (2008). The Princeton Companion to Mathematics. Princeton: Princeton University Press. pp. 635–646. ISBN 978-1-4008-3039-8. OCLC 659590835.
• Marker, David (2002). Model Theory: An Introduction. Graduate Texts in Mathematics. Vol. 217. Springer. ISBN 978-0-387-98760-6. OCLC 49326991.
• Robinson, J. A. (1965). "A Machine-Oriented Logic Based on the Resolution Principle". Journal of the ACM. Association for Computing Machinery (ACM). 12 (1): 23–41. doi:10.1145/321250.321253. ISSN 0004-5411. S2CID 14389185.
• Truss, John K. (1997). Foundations of Mathematical Analysis. Oxford University Press. ISBN 0-19-853375-6.

외부 링크

• 컴팩트성 정리, 인터넷 철학 백과사전