정의 가능 집합

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 매개변수를 사용한 정의
- 2.2. 매개변수 없는 정의
3. 성질
4. 예
5. 역사
참조

1. 개요

정의 가능 집합은 1차 논리 언어의 모형에서 특정 조건을 만족하는 부분 집합을 의미한다. 집합 A가 정의 가능하기 위해서는, A의 원소를 특징짓는 자유 변수를 가진 명제가 존재해야 한다. 정의 가능성은 매개변수를 사용하거나 사용하지 않는 경우로 나뉘며, 함수와 원소의 정의 가능성도 이와 유사하게 정의된다. 정의 가능 집합은 불 대수를 이루며, 자기 동형 사상에 불변하는 성질을 갖는다. 베트 정의 가능성 정리는 명시적 정의 가능성과 암시적 정의 가능성이 동치임을 보여준다. 자연수, 정수, 실수 등 다양한 수학적 구조에서 정의 가능 집합의 예시를 찾아볼 수 있으며, 이는 구조의 특성을 파악하는 데 중요한 역할을 한다. 알레산드로 파도아는 이 개념과 관련된 아이디어를 처음 제시했으며, 에버르트 빌럼 베트는 베트 정의 가능성 정리를 재증명했다.

더 읽어볼만한 페이지

모형 이론 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
모형 이론 - 괴델의 완전성 정리
괴델의 완전성 정리는 1차 논리 이론에서 모형 이론적 진리와 증명 이론적 진리가 같음을 나타내며, 연역 체계가 완전함을 보장하고 일차 논리에서 통사론적 결과와 의미론적 결과가 동일하다는 것을 의미한다.

정의 가능 집합
일반 정보
정의	수학적 대상의 모임. 주어진 수학적 구조에서, 그 구조의 언어로 표현 가능한 성질을 만족시키는 대상들의 모임.
관련 학문	모델 이론
추가 정보
예시	실수체 (R; +, ×, 0, 1)에서 정의 가능한 집합은 다음과 같음: 유한 집합, 구간, 대수적 수의 집합.
특징	정의 가능한 집합은 모델 이론에서 중요한 연구 대상이며, 수학적 구조의 성질을 이해하는 데 도움을 줌.

2. 정의

1차 논리 언어 $\mathcal L$ 에 대한 모형 $M$ 이 주어졌을 때, $M$ 의 부분 집합 $A\subseteq M$ 이 다음 조건을 만족시킨다면, $A$ 를 $M$ 의 '''정의 가능 집합'''이라고 한다.^[1]

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

즉, $M$ 의 부분 집합 $A$ 가 정의 가능 집합이라는 것은, $A$ 의 원소들을 특정 짓는 논리식 $\phi$ 가 존재함을 의미한다.

함수는 그 그래프가 $\mathcal{M}$ 에서 정의 가능한 경우 $\mathcal{M}$ 에서 정의 가능하다.
원소 $a$ 는 단원 집합 $\{a\}$ 가 $\mathcal{M}$ 에서 정의 가능한 경우 $\mathcal{M}$ 에서 정의 가능하다.

2. 1. 매개변수를 사용한 정의

\mathcal{L}

을 일차 언어,

\mathcal{M}

을 정의역이

M

인

\mathcal{L}

-구조,

X

를

M

의 고정된 부분집합,

m

을 자연수라고 하자.

집합

A\subseteq M^m

이 "

\mathcal{M}

에서

X

의 매개변수를 사용하여 정의 가능"하다는 것은, 모든

a_1,\ldots,a_m\in M

에 대해 다음을 만족하는 공식

\varphi[x_1,\ldots,x_m,y_1,\ldots,y_n]

과 원소

b_1,\ldots,b_n\in X

가 존재한다는 것을 의미한다.

:

(a_1,\ldots,a_m)\in A

는

\mathcal{M}\models\varphi[a_1,\ldots,a_m,b_1,\ldots,b_n]

일 때와 동일하다.

여기서 괄호 표기법은 공식 내의 자유 변수의 의미론적 평가를 나타낸다.

이는

A

가

M

의 특정 원소(매개변수)들을 사용하여 정의될 수 있음을 의미한다.

2. 2. 매개변수 없는 정의

집합 ''A''가 공집합의 매개변수를 사용하여

\mathcal{M}

에서 정의 가능하다는 것은, 정의 공식에 매개변수가 없는 경우이다. 즉, A가 매개변수 없이,

\mathcal{L}

의 기호와 논리식만으로 정의될 수 있음을 의미한다.

3. 성질

정의 가능 집합은 불 대수를 이루며, 자기 동형 사상에 대해 불변하는 성질을 갖는다.

3. 1. 불 대수 구조

언어

\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)\}

3. 2. 자기 동형 사상과의 관계

언어

\mathcal L

의 모형

M

과 그 위의

\mathcal L

-자기 동형 사상

\phi\colon M\to M

이 주어졌다고 할 때,

M

의 정의 가능 집합

A\subseteq M

은

\phi

의 고정점이다. 즉, 다음이 성립한다.

:

\phi(A)=\{\phi(a)\colon a\in A\}=A

정의 가능한 집합은 자기 동형 사상 하에서 보존된다는 중요한 결과가 있다.

:

\mathcal{M}

을 영역

M

을 가진

\mathcal{L}

-구조라고 하고,

X\subseteq M

이며,

A\subseteq M^m

을

X

의 매개변수를 사용하여

\mathcal{M}

에서 정의 가능한 집합이라고 하자.

\pi:M\to M

을

X

에서 항등 사상인

\mathcal{M}

의 자기 동형 사상이라고 할 때, 모든

a_1,\ldots,a_m\in M

에 대해, 다음이 성립한다.

::

(a_1,\ldots,a_m)\in A

이면 그리고 그 반대도 성립한다면

(\pi(a_1),\ldots,\pi(a_m))\in A.

이 결과는 주어진 구조의 정의 가능한 부분 집합을 분류하는 데 사용될 수 있다. 예를 들어,

\mathcal{Z}=(\mathbb{Z},<)

의 경우,

\mathcal{Z}

의 모든 평행 이동은 매개변수의 공집합을 보존하는 자기 동형 사상이며, 따라서

\mathcal{Z}

에서 매개변수 없이 특정 정수를 정의하는 것은 불가능하다. 사실, 두 정수는 평행 이동과 그 역에 의해 서로 이동되므로,

\mathcal{Z}

에서 매개변수 없이 정의 가능한 정수의 유일한 집합은 공집합과

\mathbb{Z}

자체이다. 반면에,

\mathcal{Z}

의 원소 쌍(또는 실제로 고정된 모든 ''n'' > 1에 대한 ''n''-튜플)의 정의 가능한 집합이 무한히 많다. ''n'' = 2인 경우, 집합

\{(a, b) \mid a - b = m\}

(

m \in \mathbb Z

)의 부울 조합이 그 예시이다. 특히, 모든 자기 동형 사상(평행 이동)은 두 요소 간의 "거리"를 보존한다.

3. 3. 베트 정의 가능성 정리

Beth definability theorem^영어에 따르면, 다음 두 조건은 서로 동치이다.^[1]

(명시적 정의 가능성) $\mathcal T\vdash\forall x(\mathsf P(x)\iff \phi(x))$ 가 성립하는 $\mathcal L$ -술어 $\phi$ 가 존재한다.
(암시적 정의 가능성) $\mathcal T$ 의 임의의 모형 $M$ 에 대하여, $M$ 을 확장하는 $\mathcal L_{\mathsf P}$ -구조는 유일하다.

4. 예

자연수를 전순서 집합으로 나타내는 1차 논리 언어에서는 모든 유한 집합이 정의 가능하지만, 무한 부분 집합은 정의 가능하지 않을 수 있다. 반환의 언어에서는 자연수의 전순서를 정의할 수 있으며, 이 언어로 정의 가능한 자연수 집합을 산술 집합이라 한다. 정수의 전순서 집합에서는 자기 동형 사상에 의해 정의 가능한 집합이 공집합과 전체 집합밖에 없다.

4. 1. 전순서 집합으로서의 자연수

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

:

\mathcal L_{\text{toset}}=\{\le\}

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

:

\phi_k(x)=\forall n\colon\left(n\le x\implies n=x\lor\phi_1(x)\lor\cdots\lor\phi_{k-1}(x)\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

의 대부분의 부분 집합들은 정의 가능 집합이 아니다.

\mathcal{N}=(\mathbb{N},<)

를 자연수에 일반적인 순서를 부여한 구조라고 하면, 모든 자연수는

\mathcal{N}

에서 매개변수 없이 정의될 수 있다. 숫자

0

은 'x'보다 작은 요소가 없음을 나타내는 공식

\varphi(x)

로 정의된다.

:

\varphi=\neg\exists y(y

그리고 자연수

n>0

은 'x'보다 작은 요소가 정확히

n

개 있음을 나타내는 공식

\varphi(x)

로 정의된다.

:

\varphi = \exists x_0\cdots\exists x_{n-1}(x_0

4. 2. 반환으로서의 자연수

반환의 1차 논리 언어

:

\mathcal L_{\text{semiring}}=\{0,1,+,\cdot\}

를 생각하자. 자연수의 반환

\mathbb N

은 이 언어의 모형을 이룬다. 반환의 언어로 정의 가능한

\mathbb N

의 부분 집합을 '''산술 집합'''(arithmetical set^영어)이라고 한다.

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

:

x\le y\iff\exists z\colon x+z=y

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

\mathcal{N}=(\mathbb{N},+, \cdot, <)

을 자연수와 일반적인 산술 연산 및 순서 관계로 구성된 일계 구조라고 하자. 이 구조에서 정의 가능한 집합은 산술적 집합으로 알려져 있으며, 산술적 위계로 분류된다. 만약 이 구조를 일계 논리 대신 이계 논리로 고려한다면, 결과 구조에서 정의 가능한 자연수 집합은 해석적 위계로 분류된다. 이러한 위계는 이 구조에서의 정의 가능성과 계산 가능성 이론 사이의 많은 관계를 드러내며, 기술 집합론에서도 관심의 대상이 된다.

4. 3. 전순서 집합으로서의 정수

전순서 집합 $(\mathbb{Z}, \le)$에서 정의 가능한 집합은 공집합과 $\mathbb{Z}$ 전체뿐이다. 이는 정수 집합의 자기 동형 사상(평행 이동)에 의해 설명된다.^[1]

정수 집합의 자기 동형 사상은

n\mapsto n+1

와 같이 나타낼 수 있다. $\mathbb{Z}$의 정의 가능 집합들은 이 자기 동형 사상에 대하여 불변이어야 한다. 따라서, 정의 가능한 집합은 항상 거짓인 술어로 정의되는 공집합과 항상 참인 술어로 정의되는 $\mathbb{Z}$ 전체 밖에 없다.^[1]

반면, $\mathbb{Z}$의 원소 쌍 (또는 n-튜플)의 정의 가능한 집합은 무한히 많다. 예를 들어, $a - b = m$ ($m \in \mathbb{Z}$)를 만족하는 $(a, b)$의 집합은 정의 가능하다. 모든 자기 동형 사상(평행 이동)은 두 요소 간의 "거리"를 보존하기 때문이다.^[1]

4. 4. 실수체

Real closed field^영어 $(\mathbb{R}, 0, 1, +, \cdot)$에서 정의 가능한 집합은 반대수 집합이라고 불리며, o-최소성 연구와 관련된다.^[1] $\mathcal{R}^{\le}$의 이론은 양화 기호 제거를 가지므로, 정의 가능한 집합은 다항식의 등식과 부등식 해의 불 대수 조합이다.^[1]

5. 역사

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

참조

_[1] 서적 Routledge Encyclopedia of Philosophy Routledge 1998
_[2] 서적 Bibliothèque du congrès international de philosophie III: logique et histoire des sciences Librairie Armand Colin 1901
_[3] 간행물 On Padoa’s method in the theory of definition 1953

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com