정의 가능 집합

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

## 정의
1차 논리 언어 \mathcal L에 대한 모형 M이 주어졌다고 하자. 그렇다면, M의 부분 집합 A\subseteq M이 다음 조건을 만족시킨다면, A를 M의 **정의 가능 집합**이라고 한다.
:\{m\in M\colon \phi(m)\}이 성립하는, 하나의 자유 변수 x를 갖는 명제 \phi(x)가 존재한다.

## 성질
언어 \mathcal L의 모형 M이 주어졌다고 하자. 그렇다면, (고전 명제 논리의 경우) M의 정의 가능 부분 집합들의 집합족 \operatorname{Def}(M)\subseteq\mathcal P(M)은 불 대수인 멱집합 \mathcal P(M)의 부분 불 대수를 이룬다. 즉,
:M\setminus\{x\in M\colon\phi^M(x)\}
=\{x\in M\colon(\lnot\phi)^M(x)\}
:\{x\in M\colon\phi^M(x)\}\cap\{x\in M\colon\chi^M(x)\}
=\{x\in M\colon(\phi\land\chi)^M(x)\}
:\{x\in M\colon\phi^M(x)\}\cup\{x\in M\colon\chi^M(x)\}
=\{x\in M\colon(\phi\lor\chi)^M(x)\}
이다.

### 자기 동형의 고정점
언어 \mathcal L의 모형 M 및 그 위의 \mathcal L-자기 동형 사상 \phi\colon M\to M이 주어졌다고 하자. 그렇다면, M의 정의 가능 집합 A\subseteq M은 \phi의 고정점이다. 즉,
:\phi(A)=\{\phi(a)\colon a\in A\}=A
이다.

### 베트 정의 가능성 정리
다음과 같은 데이터가 주어졌다고 하자.
* 1차 논리 언어 \mathcal L
* \mathcal L에 속하지 않는 술어 \mathsf P(-). \mathcal L에 \mathsf P를 추가한 언어를 \mathcal L_{\mathsf P}라고 하자.
* \mathcal L-문장들의 집합 \mathcal T\subseteq\operatorname{Sent}(\mathcal L)
**베트 정의 가능성 정리**()에 따르면, 다음 두 조건이 서로 동치이다.
* (명시적 정의 가능성) \mathcal T\vdash\forall x(\mathsf P(x)\iff \phi(x))가 성립하는 \mathcal L-술어 \phi가 존재한다.
* (암시적 정의 가능성) \mathcal T의 임의의 모형 M에 대하여, M을 확장하는 \mathcal L_{\mathsf P}-구조는 유일하다.

## 예
### 전순서 집합으로서의 자연수
자연수의 전순서 집합의 1차 논리 언어
:\mathcal L_{\text{toset}}=\{\le\}
에서, 모든 유한 집합은 정의 가능 집합이다. 예를 들어, 다음과 같은 일련의 술어들을 정의하자.
:\phi_k(x)=\lnot\phi_0(x)\land\cdots\land\lnot\phi_{k-1}(x)\land\forall n\colon\left(n\le x\implies n=x\lor\phi_0(n)\lor\cdots\lor\phi_{k-1}(n)\right)
그렇다면, 모형 (\mathbb N,\le)에서,
:\{x\in\mathbb N\colon \phi^{\mathbb N}_k(x)\}=\{k\}
이며, 마찬가지로 모든 유한 집합은
:\phi_{k_1}(x)\lor\phi_{k_2}(x)\lor\cdots\lor\phi_{k_p}(x)
의 꼴의 술어로 정의할 수 있다.

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

### 반환으로서의 자연수
반환의 1차 논리 언어
:\mathcal L_{\text{semiring}}=\{0,1,+,\cdot\}
를 생각하자. 자연수의 반환 \mathbb N은 이 언어의 모형을 이룬다. 반환의 언어로 정의 가능한 \mathbb N의 부분 집합을 **[[산술 집합]]**()이라고 한다.

반환의 언어로 자연수의 전순서를 다음과 같이 정의할 수 있다.
:x\le y\iff\exists z\colon x+z=y
따라서, 전순서 집합의 언어로 정의 가능한 자연수 집합은 항상 반환의 언어로도 정의 가능하지만, 그 역은 일반적으로 성립하지 않는다.

### 전순서 집합으로서의 정수
정수의 전순서 집합 (\mathbb Z,\le)는 전순서 집합의 1차 논리 언어
:\mathcal L_{\text{toset}}=\{\le\}
의 모형이다. 이 경우, n\mapsto n+1은 \mathbb Z의 자기 동형 사상이다. 따라서, \mathbb Z의 정의 가능 집합들은 이 자기 동형 사상에 대하여 불변이어야 하므로, \mathbb Z의 정의 가능 집합은 공집합과 \mathbb Z 전체밖에 없다. (이들은 각각 항상 거짓인 술어와 항상 참인 술어를 통해 정의된다.)

### 전순서 집합으로서의 실수
마찬가지로, 실수의 전순서 집합 (\mathbb R,\le)는 전순서 집합의 1차 논리 언어
:\mathcal L_{\text{toset}}=\{\le\}
의 모형이며, 그 정의 가능 집합은 \varnothing과 \mathbb R밖에 없다.

전순서 집합의 언어에 유한 개의 상수 기호를 추가한 1차 논리 언어
:\mathcal L_{\text{toset},\mathsf c_1,\dots,\mathsf c_n}=\{\le\}\sqcup\{\mathsf c_1,\dots,\mathsf c_n\}
를 생각하자. 그렇다면, 임의의
:c_1,\dots,c_n\in\mathbb R
:c_1
에 대하여,
:(\mathbb R,\le,c_1,\dots,c_n)
는 이 언어의 모형이다. 또한, (\mathbb R,\le,c_1,\dots,c_n)의 자기 동형 사상은 각 (-\infty,c_1),\le) 및 ((c_i,c_{i+1}),\le) 및 ((c_n,\infty),\le)의 자기 동형 사상의 (n+1)조와 일대일 대응한다. (\mathbb R,\le,c_1,\dots,c_n)의 정의 가능 집합은 그 자기 동형 사상에 대하여 불변이어야 하는데, 각 ((a,b),\le)의 자기 동형 사상들은 (a,b) 위에 추이적으로 작용한다. 따라서, (\mathbb R,\le,c_1,\dots,c_n)의 정의 가능 집합은 끝점이 \{c_1,\dots,c_n\}\cup\{-\infty,\infty\}의 원소인 유한 개의 구간들의 합집합밖에 없다.

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

## 참고 문헌

* 

## 외부 링크
* 
* 
* 
* 
* 
* 

분류:모형 이론