해당 문서는 만들고 있는 문서들을 위해 마련해놓은 사용자 문서입니다.

도메인 이론[편집]

도메인 이론(영어: Domain theory)은 수학에서 특별한 종류의 일반적으로 도메인이라 불리는 부분순서에 대하여 연구하는 분야이다. 따라서, 도메인 이론은 순서론의 한 분야라고 생각할 수 있다. 이 분야는 컴퓨터 과학에서 표기 의미론을 특정지을 때 사용되며, 특히 함수형 프로그래밍 언어의 연구에서 주로 사용된다. 도메인 이론은 근사와 수렴에 대한 직관적인 아이디어를 형식화해놓은 것이며, 위상수학과 밀접한 연관이 있다. 컴퓨터 과학에서 표기 의미론에 접근하는 또 다른 중요한 방법으로 거리공간이 있다.

동기와 직관[편집]

데이나 스콧에 의해 1960년대 이후부터 도메인이 연구되었다. 도메인이 등장한 주된 이유는 람다 대수의 표기 의미론를 찾기 위해서였다. 그러한 형식화 내에서, 언어의 특정한 항으로 이뤄진 "함수"를 고려할 필요가 있었다. 순수히 구문론적인 관점에서, 단순한 함수를 다른 함수의 입력 인자로 집어넣음으로써 다른 복잡한 함수들을 만들어낼 수 있다.

그러한 형식화 내에서 사용 가능한 구문론적 변환을 다시 사용하면 고정점 결합자를 얻을 수 있다. (그 중 대표적인 것은 Y 결합자이고, 이는 $f({\mathsf {Y}}(f))={\mathsf {Y}}(f)$ 라는 성질을 만족한다.)

그러한 표기 의미론을 형식화하기 위해서, 람다 대수의 모형을 먼저 구성하려고 시도할 수 있다. 그리고 람다 대수 내에서 각 (전)함수는 각 람다 항에 대응한다. 그러한 모형은 순수히 구문론적인 체계로서 람다 대수와 수학적 함수를 다루기 위한 표기 체계로써의 람다 대수간의 관계를 형식화함으로써 얻을 수 있다. 결합자 대수는 그러한 모형 중 하나이다. 하지만 결합자 대수의 각 원소들은 함수를 함수로 보내는 함수이다. 람다 대수의 모형 내의 원소는 임의의 정의역과 치역을 가질 수도 있으며, 그런 함수는 전함수가 아니라 부분함수일 수도 있다.

스콧은 그러한 문제를, 아직 결과를 내놓지 않은 계산을 가리키는 "부분적" 혹은 "불완전한" 정보라는 개념을 형식화함으로써 피했다. 이는 각 계산 상태의 도메인 (가령, 자연수 집합)에 "정의되지 않음"이라는 뜻을 갖는 원소를 고려하는 방식으로 모형화되었다. 즉, "계산이 끝나지 않음"을 계산 결과로써 고려하는 것이다. 그리고 계산 상태의 도메인에서 "정의되지 않음"이란 원소가 극소원이 되게 준다.

람다 대수의 모형을 찾을 때 제일 중요한 단계는 최소의 고정점을 갖는다는 것이 보장된 (위에서 말한 반순서집합 위의) 함수만을 고려하는 것이다. 그러한 함수들의 집합에 적당한 순서를 준 것은 도메인 이론의 관점에서 또 다른 "도메인"이 된다. 하지만 이러한 함수들로 고려 범위를 제한하면 상당한 이점이 생긴다; 이 경우 자신의 함수 공간을 포함하는 도메인을 가질 수도 있다. 가령, 자기 자신을 인자로 가질 수 있는 함수를 가질 수도 있다.

도메인 이론은 그러한 바람직한 성질뿐 아니라 흥미로운 직관적인 해석 또한 가능하게 한다. 위에서 언급했듯, 계산 상태의 도메인은 반순서집합이다. 그 순서는 정보나 지식의 위계를 의미한다. 원소가 더 클수록 그 원소가 담고 있는 정보의 양도 많아진다. 작은 원소들은 불완전한 정보나 중간 결과를 의미한다.

그리고 계산을, 결과를 정확하게 하기 위해서 도메인 위의 원소에 단조함수를 계속 합성하는 것으로 모형화할 수 있다. 그리고 고정점에 도달하는 것을 계산이 끝나는 것과 동일시할 수 있다. 단조함수의 고정은 항상 존재하고 추가적인 조건 하에 아래로부터 근사될 수 있으므로, 도메인은 계산에 대한 아이디어를 다루는 데 최적의 환경을 제공한다.

형식적 정의에 대한 가이드[편집]

이 문단에선 도메인 이론의 주요한 개념을 소개할 것이다. 위에서 말한 "정보들에 대한 순서"에 대한 직관은 도메인 이론의 수학적 형식화의 강한 동기가 된다. 정확한 정의는 각 개념을 소개하고 있는 문서에서 찾아볼 수 있을 것이다.

수렴하는 대상으로서의 유향집합[편집]

위에서 언급했듯 계산 상태의 도메인을 모형화한 반순서집합을 다룬다. 여기서 목표는 각 순서집합의 원소를 "정보의 부분"이나 "계산의 (부분적) 결과"로 해석하는 것이다. 여기서 a≤b는 a라는 '적은' 정보를 일관되게 b라는 정보로 확장할 수 있다는 것을 의미한다. 이러한 간단한 직관으로부터 도메인이 최대원을 가지지 않을 수도 있음을 생각해볼 수 있는데, 왜냐면 최대원이 있단 것은 다른 원소의 모든 정보를 포함하는 원소가 존재함을 의미하기 때문이다. 그리고 이는 별로 흥미 없는 케이스이다.

이 이론에서 제일 핵심적인 역할을 하는 개념은 유향집합이다. 유향 부분집합은 그 부분집합 안에 속한 임의의 두 원소가 그 집합 안에서 상계를 갖는 부분집합이다. 도메인에 대한 직관으로부터, 유향집합의 정의가 그 집합 안에 있는 임의의 두 정보를 무모순하게 합칠 수 있다는 의미로 받아들일 수 있다. 따라서 유향집합을 상호 무모순한 정보들의 모임으로 볼 수 있다. 즉, 임의의 두 원소가 상호모순이 아닌 집합으로 볼 수 있다. 이러한 해석은 해석학에서 나타나는, 각 원소가 어떤 원소를 점점 더 자세히 표현하는, 수렴하는 수열과 비교해볼 수 있다. 실제로, 거리공간을 다룰 때 수열들은 도메인 이론의 유향집합과 꽤 비슷한 역할을 한다.

이제 수열의 경우에서와 같이 유향집합의 극한에 대해 생각해보자. 위에서 말한 경우에 따르면, 극한값은 주어진 유향집합이 담고 있는 정보를 모두 담고 있으며 딱 그 유향집합 안에 있는 정보만을 담고 있는 유일한 원소일 것이다. 순서 이론으로의 형식화로부터, 이는 주어진 유향 집합의 최소상계가 된다. 수열의 극한의 경우와 같이, 유향집합의 최소상계는 존재하지 않을 수도 있다.

계산과 도메인[편집]

계산 상태의 도메인이 어때야 하는지에 대한 약간의 형식적 기술을 마련했으므로, 이제 계산 자체가 어때야 하는지 알아보도록 하자. 명백히, 계산은 computational domain에서 값을 받아서 어떤 (다를 수도 있는) 도메인으로 결과를 내놓는 함수여야 할 것이다. 그런데, 입력값의 정보가 많을수록 결과가 가진 정보 역시 많아야 할 것이라고 예측할 수 있다. 형식적으로, 이는 우리들이 원하는 함수가 단조함수여야 함을 의미한다. 완비 반순서집합을 다룰 때, 유향집합의 극한의 정의와 양립가능하기를 기대할 수 있다.

형식적으로, 이는 어떤 함수 f에 대해 그 유향집합 D 상 f(D) 역시 유향집합이며 그 최소상계는 D의 최소상계의 상임을 의미한다. 즉, f가 유향집합의 상한 또한 보존해야 함을 알 수 있다. 또한 유향집합의 원소 두 개를 비교해봄으로써, 그러한 함수는 단조여야 함을 알 수 있다. 이러한 성질들로부터 스콧 연속함수란 개념을 이끌어낼 수 있다. 맥락상 애매하지 않을 경우 이를 그냥 연속함수라 부르기도 힌다.

근사와 유한성[편집]

도메인 이론은 정보 상태의 구조를 모델링화하는 순수한 질적 접근법이다. 여기서 어떤 대상이 정보를 좀 더 포함한다고 말할 수는 있지만, 얼마나 많이 포함하는지 구체적으로 명시되진 않는다. 그럼에도, 주어진 정보의 상태볻 훨씬 단순한 원소들에 대해 이야기할 필요가 있는 몇몇 상황이 있다. (가령, 자연수 집합의 멱집합에 부분순서 관계를 준 것. 무한집합은 임의의 유한집합보다 정보가 많다고 볼 수 있다.)

그러한 관계를 모형화할 때, 순서 ≤로부터 얻어지는 진순서 <를 먼저 고려해볼 수 있을 것이다. 하지만 이는 전순서일 때는 유용하지만 반순서일 때는 정보의 양에 대해 별로 알려주는 것이 없다. 다시 집합 포함관계를 생각해보면, 한 무한집합이 다른 무한집합에 원소 하나 차이로 포함되어 있을 수 있다. 여기서 작은 무한집합이 큰 무한집합보다 '단순'하다고 말하기 어려울 것이다.

Way-below relation[편집]

더 정교한 방법으로 근사의 정도를 생각할 수 있다. 이는 또한 (way-below relation)이라 불리기도 한다. 어떤 원소 x is way below an element y, if, for every directed set D with supremum such that

y\sqsubseteq \sup D

,

there is some element d in D such that

x\sqsubseteq d

.

따라서 이를 x가 y를 근사한다고 말할 수도 있으며

x\ll y

.

라고 쓴다. 단원집합 {y}이 유향집합이므로, 이는 다음을 이끌어낸다:

x\sqsubseteq y

.

가령 예시로, 자연수 집합 위의 포함관계를 생각했을 때, 무한집합은 임의의 유한 집합의 way above이다. 반면, 다음과 같은 유한집합들의 유향집합을 생각해보자. (사실은 사슬 (순서론)이다.)

\{0\},\{0,1\},\{0,1,2\},\ldots

이 집합의 상한은 모든 자연수들의 집합 N과 같으므로, 이로부터 어떤 무한집합도 N의 way below일 수 없음을 알 수 있다.

하지만, 어떤 원소의 way below라는 것은 상대적인 개념이며 따라서 원소 자체에 대해선 많이 드러내지 못 한다. 가령, 유한 집합을 순서론적 방법으로 특징지으려고 시도할 수 있을 것이다. 하지만 심지어 무한집합도 다른 집합의 way below일 수 있다. The special property of these finite elements x is that they are way below themselves, i.e.

x\ll x

.

저러한 성질을 갖는 원소를 컴팩트하다고 부른다. 하지만, 저러한 원소는 실제로 "유한"할 필요도 어떤 위상에 대해 "컴팩트"할 필요도 없다. 그럼에도 불구하고 해당 용어는 집합론과 위상수학에서 나오는 그 용어로부터 motivate되었다. 도메인 상의 컴팩트 원소는 자기 자신이 나타나지 않는 유향집합의 극한일 수 없단 중요한 성질을 가지고 있다.

Way-below relation과 관련된 다른 중요한 결과들은 그 정의가 도메인의 많은 주요한 부분을 잡아내기에 적당하단 걸 보여준다.

Bases of domains[편집]

The previous thoughts raise another question: is it possible to guarantee that all elements of a domain can be obtained as a limit of much simpler elements? This is quite relevant in practice, since we cannot compute infinite objects but we may still hope to approximate them arbitrarily closely. More generally, we would like to restrict to a certain subset of elements as being sufficient for getting all other elements as least upper bounds. Hence, one defines a base of a poset P as being a subset B of P, such that, for each x in P, the set of elements in B that are way below x contains a directed set with supremum x. The poset P is a continuous poset if it has some base. Especially, P itself is a base in this situation. In many applications, one restricts to continuous (d)cpos as a main object of study. Finally, an even stronger restriction on a partially ordered set is given by requiring the existence of a base of compact elements. Such a poset is called algebraic. From the viewpoint of denotational semantics, algebraic posets are particularly well-behaved, since they allow for the approximation of all elements even when restricting to finite ones. As remarked before, not every finite element is "finite" in a classical sense and it may well be that the finite elements constitute an uncountable set. In some cases, however, the base for a poset is countable. In this case, one speaks of an ω-continuous poset. Accordingly, if the countable base consists entirely of finite elements, we obtain an order that is ω-algebraic.

Special types of domains[편집]

A simple special case of a domain is known as an elementary or flat domain. This consists of a set of incomparable elements, such as the integers, along with a single "bottom" element considered smaller than all other elements. One can obtain a number of other interesting special classes of ordered structures that could be suitable as "domains". We already mentioned continuous posets and algebraic posets. More special versions of both are continuous and algebraic cpos. Adding even further completeness properties one obtains continuous lattices and algebraic lattices, which are just complete lattices with the respective properties. For the algebraic case, one finds broader classes of posets which are still worth studying: historically, the Scott domains were the first structures to be studied in domain theory. Still wider classes of domains are constituted by SFP-domains, L-domains, and bifinite domains.

All of these classes of orders can be cast into various categories of dcpos, using functions which are monotone, Scott-continuous, or even more specialized as morphisms. Finally, note that the term domain itself is not exact and thus is only used as an abbreviation when a formal definition has been given before or when the details are irrelevant.

순열 모형[편집]

집합론에서 순열 모형(영어: Permutation Model)이란 것은 기본원소의 순열의 군으로부터 구성되는 원자 있는 체르멜로-프란켈 공리계의 모형이다. 대칭 모형(영어: Symmetric model)은 원자 대신 강제법 순서의 순열의 군을 써서 구성되는 모형을 가리킨다. 이를 이용하면 선택공리가 ZF와 독립임을 보일 수 있으며, 선택공리와 관련된 많은 무모순성 결과가 이로부터 얻어진다.

순열 모형의 구성[편집]

A를 모든 원자들의 집합이라 하자. 그리고 G를 A에서 A로 가는 모든 전단사집합들의 군이라 하자. 즉, G를 A 위의 대칭군으로 두자. 이 때 G의 부분군으로 이루어진 필터 ${\mathcal {F}}$ 가 정규 필터(영어: Normal filter)라는 것은 다음 조건을 만족하는 것을 말한다:

$G\in {\mathcal {F}}$ 이다.
$H\in {\mathcal {F}}$ 이고 $H\subseteq K$ 이면 $K\in {\mathcal {F}}$ 이다.
$H,\,K\in {\mathcal {F}}$ 이면 $H,\cap K\in {\mathcal {F}}$ 이다.
임의의 $\pi \in G$ 와 $H\in {\mathcal {F}}$ 에 대해 $\pi H\pi ^{-1}\in {\mathcal {F}}$ 이다.
임의의 $a\in A$ 에 대해 $\{\pi \in G:\pi a=a\}\in {\mathcal {F}}$ 이다.

원자들의 집합 A 위의 순열 π를 다음과 같이 재귀적으로 임의의 집합에 대해 확장할 수 있다:

\pi (\varnothing )=\varnothing

\pi (x)=\{\pi (y):y\in x\}

이제 각 집합 x에 대해, x의 대칭군 $\operatorname {sym} _{G}(x)$ 를 x를 고정하는 모든 G의 순열을 모은 집합이라 하자.

\operatorname {sym} _{G}(x)=\{\pi \in G:\pi (x)=x\}

그리고 $\operatorname {sym} _{G}(x)\in {\mathcal {F}}$ 인 집합을 대칭적이라 하자. 이 때 x가 유전적으로 대칭(영어: Hereditary symmetric)이란 것은 x와 x의 추이적 폐포(영어: Transitive closure)의 모든 원소가 대칭인 것이라 하자.

이 때 유전적으로 대칭인 집합을 모두 모은 모임은 ZFA의 모형이 된다. 이를 순열 모형이라 부른다.