정의 가능 집합

모형 이론에서 정의 가능 집합(定義可能集合, )은 어떤 주어진 언어의 모형 속의, 어떤 술어를 만족시키는 원소들로 구성된 부분 집합이다.

정의 
1차 논리 언어 에 대한 모형 이 주어졌다고 하자. 그렇다면, 의 부분 집합 이 다음 조건을 만족시킨다면, 를 의 정의 가능 집합이라고 한다.
이 성립하는, 하나의 자유 변수 를 갖는 명제 가 존재한다.

성질 
언어 의 모형 이 주어졌다고 하자. 그렇다면, (고전 명제 논리의 경우) 의 정의 가능 부분 집합들의 집합족 은 불 대수인 멱집합 의 부분 불 대수를 이룬다. 즉,

이다.

자기 동형의 고정점 
언어 의 모형  및 그 위의 -자기 동형 사상 이 주어졌다고 하자. 그렇다면, 의 정의 가능 집합 은 의 고정점이다. 즉,

이다.

베트 정의 가능성 정리 
다음과 같은 데이터가 주어졌다고 하자.
 1차 논리 언어 
 에 속하지 않는 술어 . 에 를 추가한 언어를 라고 하자.
 -문장들의 집합 
베트 정의 가능성 정리()에 따르면, 다음 두 조건이 서로 동치이다.
 (명시적 정의 가능성) 가 성립하는 -술어 가 존재한다.
 (암시적 정의 가능성) 의 임의의 모형 에 대하여, 을 확장하는 -구조는 유일하다.

예

전순서 집합으로서의 자연수 
자연수의 전순서 집합의 1차 논리 언어

에서, 모든 유한 집합은 정의 가능 집합이다. 예를 들어, 다음과 같은 일련의 술어들을 정의하자.

그렇다면, 모형 에서,

이며, 마찬가지로 모든 유한 집합은

의 꼴의 술어로 정의할 수 있다.

반면, 의 무한 부분 집합들은 정의 가능 집합이 아닐 수 있다. 사실, 의 정의 가능 집합들의 수는 이지만 의 모든 부분 집합들의 수는 이므로, 의 대부분의 부분 집합들은 정의 가능 집합이 아니다.

반환으로서의 자연수 
반환의 1차 논리 언어

를 생각하자. 자연수의 반환 은 이 언어의 모형을 이룬다. 반환의 언어로 정의 가능한 의 부분 집합을 산술 집합()이라고 한다.

반환의 언어로 자연수의 전순서를 다음과 같이 정의할 수 있다.

따라서, 전순서 집합의 언어로 정의 가능한 자연수 집합은 항상 반환의 언어로도 정의 가능하지만, 그 역은 일반적으로 성립하지 않는다.

전순서 집합으로서의 정수 
정수의 전순서 집합 는 전순서 집합의 1차 논리 언어

의 모형이다. 이 경우, 은 의 자기 동형 사상이다. 따라서, 의 정의 가능 집합들은 이 자기 동형 사상에 대하여 불변이어야 하므로, 의 정의 가능 집합은 공집합과  전체 밖에 없다. (이들은 각각 항상 거짓인 술어와 항상 참인 술어를 통해 정의된다.)

역사 
베트 정리는 1900년에 알레산드로 파도아(, 1868~1937)가 최초로 도입하였다. 이후 1953년에 에버르트 빌럼 베트(, 1908~1964)가 이를 1차 논리에 대하여 재증명하였다.

참고 문헌

외부 링크 
 
 
 
 
 
 

모형 이론