정의 가능 집합

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

정의

1차 논리 언어 $ℒ$에 대한 모형 $M$이 주어졌다고 하자. 그렇다면, $M$의 부분 집합 $A\subseteq M$이 다음 조건을 만족시킨다면, $A$를 $M$의 정의 가능 집합이라고 한다.틀:Rp

$\{x\in M:\varphi (m)\}$이 성립하는, 하나의 자유 변수 $x$를 갖는 명제 $\varphi (x)$가 존재한다.

성질

언어 $ℒ$의 모형 $M$이 주어졌다고 하자. 그렇다면, (고전 명제 논리의 경우) $M$의 정의 가능 부분 집합들의 집합족 $\mathrm{Def}(M)\subseteq 𝒫(M)$은 불 대수인 멱집합 $𝒫(M)$의 부분 불 대수를 이룬다. 즉,

$M\setminus \{x\in M:{\varphi }^M(x)\}=\{x\in M:(\mathrm{\neg }\varphi {)}^M(x)\}$

$\{x\in M:{\varphi }^M(x)\}\cap \{x\in M:{\chi }^M(x)\}=\{x\in M:(\varphi \wedge \chi {)}^M(x)\}$

$\{x\in M:{\varphi }^M(x)\}\cup \{x\in M:{\chi }^M(x)\}=\{x\in M:(\varphi \vee \chi {)}^M(x)\}$

이다.

자기 동형의 고정점

언어 $ℒ$의 모형 $M$ 및 그 위의 $ℒ$-자기 동형 사상 $\varphi :M\to M$이 주어졌다고 하자. 그렇다면, $M$의 정의 가능 집합 $A\subseteq M$은 $\varphi$의 고정점이다. 즉,

$\varphi (A)=\{\varphi (a):a\in A\}=A$

이다.

베트 정의 가능성 정리

다음과 같은 데이터가 주어졌다고 하자.

• 1차 논리 언어 $ℒ$
• $ℒ$에 속하지 않는 술어 $𝖯(-)$. $ℒ$에 $𝖯$를 추가한 언어를 ${ℒ}_{𝖯}$라고 하자.
• $ℒ$-문장들의 집합 $𝒯\subseteq \mathrm{Sent}(ℒ)$

베트 정의 가능성 정리(틀:Llang)에 따르면, 다음 두 조건이 서로 동치이다.틀:Rp

• (명시적 정의 가능성) $𝒯⊢\mathrm{\forall }x(𝖯(x)⟺\varphi (x))$가 성립하는 $ℒ$-술어 $\varphi$가 존재한다.
• (암시적 정의 가능성) $𝒯$의 임의의 모형 $M$에 대하여, $M$을 확장하는 ${ℒ}_{𝖯}$-구조는 유일하다.

예

전순서 집합으로서의 자연수

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

${ℒ}_{\text{toset}}=\{\le \}$

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

${\varphi }_k(x)=\mathrm{\forall }n:(n\le x⟹n=x\vee {\varphi }_1(x)\vee \cdots \vee {\varphi }_{k-1}(x))$

그렇다면, 모형 $(\mathbb{N},\le )$에서,

$\{x\in \mathbb{N}:{\varphi }_k^{\mathbb{N}}(x)\}=\{k\}$

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

${\varphi }_{k_1}(x)\vee {\varphi }_{k_2}(x)\vee \cdots \vee {\varphi }_{k_p}(x)$

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

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

반환으로서의 자연수

반환의 1차 논리 언어

${ℒ}_{\text{semiring}}=\{0,1,+,\cdot \}$

를 생각하자. 자연수의 반환 $\mathbb{N}$은 이 언어의 모형을 이룬다. 반환의 언어로 정의 가능한 $\mathbb{N}$의 부분 집합을 산술 집합(틀:Llang)이라고 한다.

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

$x\le y⟺\mathrm{\exists }z:x+z=y$

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

전순서 집합으로서의 정수

정수의 전순서 집합 $(\mathbb{Z},\le )$는 전순서 집합의 1차 논리 언어

${ℒ}_{\text{toset}}=\{\le \}$

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

역사

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

각주

• 틀:서적 인용

외부 링크

• 틀:Eom
• 틀:Nlab
• 틀:Nlab
• 틀:Nlab
• 틀:웹 인용틀:깨진 링크
• 틀:웹 인용