정의 가능 집합

위키백과, 우리 모두의 백과사전.

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

정의[편집]

1차 논리 언어 에 대한 모형 이 주어졌다고 하자. 그렇다면, 의 부분 집합 이 다음 조건을 만족시킨다면, 정의 가능 집합이라고 한다.[1]:762, §3

이 성립하는, 하나의 자유 변수 를 갖는 명제 가 존재한다.

성질[편집]

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

이다.

자기 동형의 고정점[편집]

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

이다.

베트 정의 가능성 정리[편집]

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

  • 1차 논리 언어
  • 에 속하지 않는 술어 . 를 추가한 언어를 라고 하자.
  • -문장들의 집합

베트 정의 가능성 정리(영어: Beth definability theorem)에 따르면, 다음 두 조건이 서로 동치이다.[1]:762, §

  • (명시적 정의 가능성) 가 성립하는 -술어 가 존재한다.
  • (암시적 정의 가능성) 의 임의의 모형 에 대하여, 을 확장하는 -구조는 유일하다.

[편집]

전순서 집합으로서의 자연수[편집]

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

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

그렇다면, 모형 에서,

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

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

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

반환으로서의 자연수[편집]

반환1차 논리 언어

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

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

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

전순서 집합으로서의 정수[편집]

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

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

역사[편집]

베트 정리는 1900년에 알레산드로 파도아(이탈리아어: Alessandro Padoa, 1868~1937)가 최초로 도입하였다.[2] 이후 1953년에 에버르트 빌럼 베트(네덜란드어: Evert Willem Beth, 1908~1964)가 이를 1차 논리에 대하여 재증명하였다.[3]

각주[편집]

  1. Swijtink, Zeno (1998). 〈Beth’s theorem and Craig’s theorem〉 (PDF). Craig, Edward. 《Routledge Encyclopedia of Philosophy》 (영어). Routledge. 760–764쪽. doi:10.4324/9780415249126-Y021-1. ISBN 978-041507310-3. 
  2. Padoa, Alessandro (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쪽. 
  3. Beth, Evert Willem (1953). “On Padoa’s method in the theory of definition”. 《Indagationes Mathematicae》 (영어) 15: 30-39. ISSN 0019-3577. MR 58537. 

외부 링크[편집]