콤팩트성 정리
수리논리학에서 콤팩트성 정리(compact性定理, 영어: compactness theorem)는 만약 어떤 1차 논리 이론의 모든 유한 집합이 만족 가능하다면, 이론 전체가 만족 가능하다는 정리다. 1차 논리의 특징이며, 고차 논리나 무한 논리에서는 일반적으로 성립하지 않는다.
정의[편집]
콤팩트성 정리에 따르면, 부호수 의 (등호를 포함하는) 1차 논리 이론 에 대하여, 다음이 서로 동치이다.
- (무모순성)
- (만족 가능성) 인 -구조 이 존재한다.
- (가산 만족 가능성) 인 가산 -구조 이 존재한다.
- (국소 무모순성) 의 모든 유한 부분 집합 에 대하여,
- (국소 만족 가능성) 의 모든 유한 부분 집합 에 대하여, 인 -구조 가 존재한다.
- (국소 가산 만족 가능성) 의 모든 유한 부분 집합 에 대하여, 인 가산 -구조 가 존재한다.
응용[편집]
콤팩트성 정리를 이용하여, 어떤 1차 논리적 명제가 표수 0인 임의의 체에 대해 성립한다면, 상수 p가 존재해서 표수가 p보다 큰 임의의 체에 대해 이 명제가 성립함을 알 수 있다.
증명은 다음과 같다. φ가 그 명제일 때, 가정에 따라 그 부정 ¬φ와 체의 공리들 및 무한개의 명제들 1+1≠0, 1+1+1≠0, …로 이루어진 집합의 모형은 존재하지 않는다. 그러므로 그 집합의 어떤 유한 부분집합이 모형을 갖지 않으며, 이는 달리 말하면 표수가 몇몇 유한한 자연수들 중 하나가 아니면서 ¬φ가 성립하는 체가 존재하지 않는다는 뜻이므로 증명이 끝난다.
명제 논리의 콤팩트성 정리는 불 대수의 스톤 쌍대성에 따라, 스톤 공간에 대한 티호노프 정리(콤팩트 공간의 임의의 곱이 여전히 콤팩트 공간)와 동치이다.[1] "콤팩트성 정리"라는 이름은 이로부터 기인하였다.
역사[편집]
쿠르트 괴델이 가산 부호수에 대한 콤팩트성 정리를 1930년에 증명하였다.[2] 아나톨리 말체프가 일반적인 경우를 1936년에 증명하였다.[3][4]
같이 보기[편집]
각주[편집]
- ↑ Truss, John K. (1997). 《Foundations of Mathematical Analysis》. Oxford University Press. ISBN 0198533756.
- ↑ Gödel, Kurt (1930). “Die Vollständigkeit der Axiome des logischen Functionenkalküls”. 《Monatshefte für Mathematik und Physik》 (독일어) 37 (1): 349–360. doi:10.1007/BF01696781. ISSN 0026-9255.
- ↑ Vaught, Robert L.: Alfred Tarski's work in model theory. J. Symbolic Logic 51 (1986), no. 4, 869–882
- ↑ Robinson, A.: Non-standard analysis. North-Holland Publishing Co., Amsterdam 1966. page 48.
- 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》 (영어).