정의 가능 집합 문서 원본 보기

{{위키데이터 속성 추적}}
[[모형 이론]]에서 '''정의 가능 집합'''(定義可能集合, {{llang|en|definable set}})은 어떤 주어진 언어의 [[모형 (논리학)|모형]] 속의, 어떤 술어를 만족시키는 원소들로 구성된 [[부분 집합]]이다.

== 정의 ==
1차 논리 언어 <math>\mathcal L</math>에 대한 [[모형 (논리학)|모형]] <math>M</math>이 주어졌다고 하자. 그렇다면, <math>M</math>의 부분 집합 <math>A\subseteq M</math>이 다음 조건을 만족시킨다면, <math>A</math>를 <math>M</math>의 '''정의 가능 집합'''이라고 한다.<ref name="Swijtink">{{서적 인용|장=Beth’s theorem and Craig’s theorem|이름=Zeno|성=Swĳtink|doi=10.4324/9780415249126-Y021-1|제목=Routledge Encyclopedia of Philosophy|장url=https://www.princeton.edu/~hhalvors/teaching/phi520_f2012/beth-theorem.pdf|날짜=1998|isbn=978-041507310-3|쪽=760–764|출판사=Routledge|editor1-first=Edward|editor1-last=Craig|언어=en}}</ref>{{rp|762, §3}}
:<math>\{x\in M\colon \phi(m)\}</math>이 성립하는, 하나의 자유 변수 <math>x</math>를 갖는 명제 <math>\phi(x)</math>가 존재한다.

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

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

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

== 예 ==
=== 전순서 집합으로서의 자연수 ===
자연수의 [[전순서 집합]]의 [[1차 논리]] 언어
:<math>\mathcal L_{\text{toset}}=\{\le\}</math>
에서, 모든 유한 집합은 정의 가능 집합이다. 예를 들어, 다음과 같은 일련의 술어들을 정의하자.
:<math>\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)</math>
그렇다면, 모형 <math>(\mathbb N,\le)</math>에서,
:<math>\{x\in\mathbb N\colon \phi^{\mathbb N}_k(x)\}=\{k\}</math>
이며, 마찬가지로 모든 유한 집합은
:<math>\phi_{k_1}(x)\lor\phi_{k_2}(x)\lor\cdots\lor\phi_{k_p}(x)</math>
의 꼴의 술어로 정의할 수 있다.

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

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

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

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

== 역사 ==
베트 정리는 1900년에 알레산드로 파도아({{llang|it|Alessandro Padoa}}, 1868~1937)가 최초로 도입하였다.<ref>{{서적 인용|이름=Alessandro|성=Padoa|날짜=1901|장=Essai d’une théorie algébrique des nombres entiers, précédé d’une introduction logique à une théorie déductive quenconque|제목=Bibliothèque du congrès international de philosophie III: logique et histoire des sciences|위치=[[파리 (프랑스)|파리]]|출판사=Librairie Armand Colin|쪽=309–365|장url=https://archive.org/stream/bibliothqueducon03inte#page/309/|언어=fr}}</ref> 이후 1953년에 에버르트 빌럼 베트({{llang|nl|Evert Willem Beth}}, 1908~1964)가 이를 [[1차 논리]]에 대하여 재증명하였다.<ref>{{저널 인용|이름=Evert Willem|성=Beth|제목=On Padoa’s method in the theory of definition|저널=Indagationes Mathematicae|권=15|날짜=1953|쪽=30-39|issn=0019-3577|mr=58537|언어=en}}</ref>

== 각주 ==
{{각주}}
* {{서적 인용|이름=Michael|성=Makkai|제목=Duality and definability in first order logic|총서=Memoirs of the American Mathematical Society |권=503|날짜=1993|url=http://bookstore.ams.org/memo-105-503/|isbn=978-0-8218-2565-5|언어=en}}

== 외부 링크 ==
* {{eom|title=Beth definability theorem}}
* {{nlab|id=definable set|title=Definable set}}
* {{nlab|id=definability|title=Definability}}
* {{nlab|id=Beth definability theorem}}
* {{웹 인용|url=https://logiciansdoitwithmodels.com/2010/08/31/beths-definability-theorem/|제목=Beth’s definability theory|웹사이트=Logicians do it with models: a self-guided jaunt in philosophical logic|날짜=2010-08-31|언어=en}}{{깨진 링크|url=https://logiciansdoitwithmodels.com/2010/08/31/beths-definability-theorem/ }}
* {{웹 인용|url=http://www.etd.ceu.hu/2010/ravelomanantsoa-ratsimihah_joel.pdf|제목=Understanding definability in first-order logic|이름=Joël|성=Ravelomanantsoa-Ratsimihah|출판사=Közép-európai Egyetem|기타=석사 학위 논문 (지도 교수 Ildikó Sain)|날짜=2010|언어=en|확인날짜=2016-08-01|archive-date=2016-08-18|archive-url=https://web.archive.org/web/20160818224701/http://www.etd.ceu.hu/2010/ravelomanantsoa-ratsimihah_joel.pdf|url-status=}}

{{전거 통제}}

[[분류:모형 이론]]