콤팩트성 정리

수리논리학에서 콤팩트성 정리(compact性定理, 영어: compactness theorem)는 만약 어떤 1차 논리 이론의 모든 유한 부분 집합이 만족 가능하다면, 이론 전체가 만족 가능하다는 정리다. 1차 논리의 특징이며, 고차 논리나 무한 논리에서는 일반적으로 성립하지 않는다.

정의

콤팩트성 정리에 따르면, 부호수 $\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차 논리적 명제가 표수 0인 임의의 체에 대해 성립한다면, 상수 p가 존재해서 표수가 p보다 큰 임의의 체에 대해 이 명제가 성립함을 알 수 있다.

증명은 다음과 같다. φ가 그 명제일 때, 가정에 따라 그 부정 ¬φ와 체의 공리들 및 무한개의 명제들 1+1≠0, 1+1+1≠0, …로 이루어진 집합의 모형은 존재하지 않는다. 그러므로 그 집합의 어떤 유한 부분집합이 모형을 갖지 않으며, 이는 달리 말하면 표수가 몇몇 유한한 자연수들 중 하나가 아니면서 ¬φ가 성립하는 체가 존재하지 않는다는 뜻이므로 증명이 끝난다.

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

역사

쿠르트 괴델이 가산 부호수에 대한 콤팩트성 정리를 1930년에 증명하였다. 아나톨리 말체프가 일반적인 경우를 1936년에 증명하였다.

같이 보기

• 괴델의 완전성 정리
• 뢰벤하임-스콜렘 정리
• 약콤팩트 기수
• 강콤팩트 기수

각주

• 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. ISSN 0144-5340. Zbl 0794.03001. 

외부 링크

• Tao, Terry (2009년 4월 10일). “The completeness and compactness theorems of first-order logic”. 《What’s New》 (영어).