완비 원순서 집합

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

1. 개요
2. 정의
- 2.1. 완비 부분 순서 집합 (cpo)
3. 성질
- 3.1. 고정점
- 3.2. 범주론적 성질
4. 예시
5. 완비 원순서 집합의 사상
참조

1. 개요

완비 원순서 집합은 원순서 집합의 일종으로, 특정 조건을 만족하는 집합을 의미한다. 완비 원순서 집합은 모든 사슬의 상한이 존재하거나, 최소 원소를 가지며 모든 상향 집합의 상한이 존재하는 등의 동치 조건을 가진다. 완비 원순서 집합 사이의 함수는 사슬의 상한을 보존하거나, 최소 원소를 보존하고 상향 집합의 상한을 보존하는 등의 특징을 갖는다. 완비 원순서 집합은 완비 격자의 개념을 일반화하며, 닫힌 원순서 집합이므로 초른 보조정리를 적용할 수 있다. 완비 원순서 집합의 예시로는 유한 부분 순서 집합, 완비 격자, 필터 집합 등이 있다. 완비 원순서 집합의 사상은 스콧 연속 함수이며, 데카르트 닫힌 범주를 형성한다.

더 읽어볼만한 페이지

순서론 - 스콧 위상
스콧 위상은 부분 순서 집합 위에 정의되는 위상으로, 하향 집합과 directed set의 상한에 대해 닫혀있는 집합을 닫힌 집합으로 정의하며, 컴퓨터 과학, 특히 프로그램 의미론에서 연속 함수의 개념을 일반화하고 프로그램의 계산 과정을 모델링하는 데 사용된다.
순서론 - 사전식 순서
사전식 순서는 정렬된 집합의 순서를 일반화하여 곱집합의 순서를 정의하는 데 사용되며, 단어 순서 정렬 방식과 유사하게 다양한 분야에 응용되는 수학적 개념이다.

완비 원순서 집합
개요
유형	순서론
분야	수학
정의
정의	방향 완비 부분 순서 (directed-complete partial order, dcpo) 또는 ω-완비 부분 순서 (ω-complete partial order)는 모든 방향 집합(directed set)이 최소 상한(least upper bound)을 갖는 부분 순서 집합이다.
특징
특징	방향 완비 부분 순서 집합은 모든 방향 집합에 대해 최소 상한이 존재한다는 점에서 완비성의 한 형태를 갖는다. 이는 스콧 연속 함수를 정의하는 데 사용되며, 프로그래밍 언어 의미론에서 특히 중요하다.
관련 개념
관련 개념	완비 원순서 집합

2. 정의

원순서 집합 $(P,\lesssim)$ 에 대하여, 다음 조건들은 서로 동치이며, 이 조건을 만족시키는 $P$ 를 '''완비 원순서 집합'''이라고 한다.

모든 사슬의 상한이 존재한다.
모든 정렬 사슬의 상한이 존재한다.
최소 원소를 가지며, 모든 상향 집합의 상한이 존재한다.
최소 원소를 가지며, 표준적인 매장 $\downarrow\colon P\to\operatorname{Ideal}(P)$ 는 (얇은 작은 범주 사이의 함자로 여겼을 때) 왼쪽 수반 함자를 갖는다.
임의의 순서 보존 함수 $f\colon P\to P$ 의 고정점 집합 $\{a\in P\colon a\sim f(a)\}$ 은 최소 원소를 갖는다.^[18]

완비 원순서 집합에서, 주 순서 아이디얼

\downarrow\colon P\to\operatorname{Ideal}(P)

의 왼쪽 수반 함자는 순서 아이디얼의 상한이다.

:

\bigvee\colon\operatorname{Ideal}(P)\to P

:

{\bigvee}\dashv{\downarrow}

보다 일반적으로, 순서수

\alpha

가 주어졌을 때, 원순서 집합

(P,\lesssim)

이 다음 조건을 만족시키면,

P

를 '''

\alpha

-완비 원순서 집합'''(

\alpha

-complete preordered set^영어)이라고 한다.

순서형 $\alpha$ 미만의 모든 정렬 사슬의 상한이 존재한다.

두 완비 원순서 집합

P

,

Q

사이의 함수

f\colon P\to Q

에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 함수를 완비 원순서 집합의 '''사상'''이라고 한다.

사슬의 상한을 보존한다. 즉, 임의의 사슬 $C\subseteq P$ 에 대하여, $f\left(\bigvee C\right)=\bigvee f(C)$ 이다.
최소 원소를 보존하며, 상향 집합의 상한을 보존한다. 즉, $f(\bot_P)=\bot_Q$ 이며, 임의의 상향 집합 $D\subseteq P$ 에 대하여, $f\left(\bigvee D\right)=\bigvee f(D)$ 이다.
정의역과 공역 위에 스콧 위상을 부여하였을 때, 연속 함수이다.

완비 원순서 집합의 사상은 항상 순서 보존 함수이지만, 그 역은 성립하지 않는다.

2. 1. 완비 부분 순서 집합 (cpo)

'''완비 부분 순서 집합'''(Complete Partial Order, cpo)은 문맥에 따라 여러 의미로 사용될 수 있다.

방향 완비 부분 순서 집합(Directed Complete Partial Order, dcpo): 모든 방향 집합이 상한을 가지는 부분 순서 집합이다. 여기서 방향 집합은 공집합이 아니고, 모든 두 원소가 그 부분 집합 내에서 상한을 갖는 집합을 의미한다.^[1] dcpo는 '상향 완비 포셋'이라고도 불린다.
점있는 방향 완비 부분 순서 집합(Pointed dcpo, cppo): 최소 원소(보통 $\bot$ 로 표시)를 가진 dcpo이다. 모든 방향 부분 집합 또는 공집합에 대한 상한을 가진다. 점있는 dcpo는 모든 체인이 상한을 갖는 포셋으로 특징지어지기 때문에 '체인 완비 부분 순서 집합'이라고도 불린다.^[1]
ω-완비 부분 순서 집합(ω-cpo): 모든 ω-체인( $x_1 \leq x_2 \leq x_3 \leq ...$ )이 상한을 갖는 포셋이다. 모든 ω-체인은 방향 집합이지만, 그 역은 성립하지 않는다.^[1]^[2]

모든 dcpo는 ω-cpo이다. 기저를 가진 모든 ω-cpo는 dcpo이기도 하다. 기저를 가진 ω-cpo (dcpo)는 '''연속''' ω-cpo (또는 연속 dcpo)라고도 한다.

'완비 부분 순서 집합'이라는 용어는 ''모든'' 부분 집합이 상한을 갖는 포셋을 의미하는 데는 사용되지 않으며, 이러한 개념에는 완비 격자라는 용어가 사용된다.

방향 상한의 존재를 요구하는 것은 방향 집합을 일반화된 근사 수열로, 상한을 해당 (근사적인) 계산의 ''극한''으로 간주함으로써 영역 이론의 발전을 이끌었다.

방향 완비 부분 순서 집합의 쌍대 개념은 '''여과 완비 부분 순서 집합'''이라고 한다.

순서 집합이 dcpo가 되기 위한 필요충분 조건은 모든 공집합이 아닌 사슬이 상한을 갖는 것이다. 순서 집합이 점을 가진 dcpo가 되기 위한 필요충분 조건은 모든 (비어 있을 수도 있는) 사슬이 상한을 갖는 것이며, 이는 곧 사슬 완비인 것과 같다.^[1]^[6]^[7]^[8]

순서 집합

P

가 점을 가진 dcpo가 되기 위한 필요충분 조건은

P

의 모든 순서 보존 자기 사상이 최소 고정점을 갖는 것이다.

3. 성질

모든 완비 원순서 집합은 닫힌 원순서 집합이므로, 초른 보조정리를 적용할 수 있다. 격자 $L$ 에 대하여, 다음 두 조건은 서로 동치이다.

완비 원순서 집합이다.
완비 격자이다.

즉, 완비 원순서 집합은 완비 격자의 개념을 일반화한다.

이 밖에도 완비 원순서 집합은 다음과 같은 성질을 갖는다.

임의의 유한 반순서 집합은 유향 완비이다.
임의의 완비 격자도 역시 유향 완비이다.
임의의 반순서 집합에 대해, 그 공집합이 아닌 필터 전체의 집합은 포함 관계에 의해 유향 완비 반순서 집합이다.
집합 ''S'' 위의 부분 사상 전체의 집합은 특정 조건에서 점이 있는 유향 완비 반순서 집합이 된다.
임의의 sober space|소버 공간^영어의 specialization order|특수화 순서^영어는 유향 완비 반순서 집합이다.
인과 관계로 닫혀있는 문장의 집합으로서 연역계의 집합은 유향 완비 반순서 집합이 된다.
순서 집합 ''P''가 유향 완비 반순서 집합이 되기 위한 필요충분 조건은 임의의 사슬이 ''P''에서 상한을 갖는 것이다.

3. 1. 고정점

완비 원순서 집합

(P,\lesssim)

위의 순서 보존 함수

f\colon P\to P

의 고정점 집합

\{a\in P\colon a\sim f(a)\}

은 완비 원순서 집합이다. 이는 타르스키 고정점 정리를 일반화한다.^[18]

완비 원순서 집합

(P,\lesssim)

위의 순서 보존 함수들의 집합

(f_i\colon P\to P)_{i\in I}

가 다음 조건을 만족시킨다고 하자.

:

\forall i\in I\forall a\in P\colon a\le f_i(a)

그렇다면,

(f_i)_{i\in I}

는 최소 공통 고정점을 갖는다.^[18]

점 있는 dcpo (''P'', ⊥)의 모든 순서 보존 자기 사상 ''f''는 최소 고정점을 갖는다.^[10] 만약 ''f''가 연속 함수라면, 이 고정점은 ⊥의 반복 (⊥, ''f''(⊥), ''f''(''f''(⊥)), … ''f''^''n''(⊥), …)의 상한과 같다 (클레인 고정점 정리 참조).

3. 2. 범주론적 성질

범주

\operatorname{Cpo}

는 데카르트 닫힌 범주를 이룬다.^[9] 두 방향 완비 부분 순서 집합(dcpo) ''P''와 ''Q'' 사이의 모든 연속 함수의 집합은 점별 순서를 갖춘 dcpo이다.^[16]

4. 예시

모든 유한 부분 순서 집합은 방향 완비이다.
모든 완비 격자는 또한 방향 완비이다.
모든 부분 순서 집합에 대해, 비어 있지 않은 모든 필터 집합은 부분 집합 포함 관계에 의해 정렬되어 dcpo를 이룬다.
모든 집합 ''S''는 최소 원소 ⊥을 추가하고, 평탄 순서를 도입하여 점있는 dcpo로 바꿀 수 있다.
주어진 집합 ''S''에 대한 모든 부분 함수 집합은 확장 관계에 의해 정렬된 점있는 dcpo이다.
선형 독립 부분 집합들의 집합은 벡터 공간 ''V''에 속하며, 포함 관계에 의해 정렬된다.
환의 모든 소 아이디얼 집합은 포함 관계에 의해 정렬된다.
모든 소버 공간의 특수화 순서는 dcpo이다.
연역 시스템의 집합은 방향 완비 부분 순서 집합이다.^[5]

5. 완비 원순서 집합의 사상

두 완비 원순서 집합 $P$ , $Q$ 사이의 함수 $f\colon P\to Q$ 에 대하여, 다음 세 조건은 서로 동치이며, 이를 만족시키는 함수를 완비 원순서 집합의 '''사상'''이라고 한다. 완비 원순서 집합의 사상은 항상 순서 보존 함수이지만, 그 역은 성립하지 않는다.^[18]

사슬의 상한을 보존한다. 즉, 임의의 사슬 $C\subseteq P$ 에 대하여, $f\left(\bigvee C\right)=\bigvee f(C)$ 이다.
최소 원소를 보존하며, 상향 집합의 상한을 보존한다. 즉, $f(\bot_P)=\bot_Q$ 이며, 임의의 상향 집합 $D\subseteq P$ 에 대하여 $f\left(\bigvee D\right)=\bigvee f(D)$ 이다.
정의역과 공역 위에 스콧 위상을 부여하였을 때, 연속 함수이다.

두 dcpo 사이의 함수가 스콧 연속이라는 것은, 방향 집합을 방향 집합으로 매핑하고 상한을 보존하는 것을 의미한다.

참조

_[1] 논문 Chain-complete posets and directed sets with applications
_[2] 서적 Handbook of Logic in Computer Science, volume 3 Clarendon Press
_[3] 서적 Bizonyítás és igazság / Válogatott tanulmányok Gondolat, Budapest
_[4] 웹사이트 A Course in Universal Algebra http://www.math.uwat[...]
_[5] 웹사이트 Universal Algebra https://www.math.uwa[...]
_[6] 웹사이트 Iwamura's Lemma, Markowsky's Theorem and ordinals https://topology.lmf[...] 2015-02-23
_[7] 서적 Universal Algebra Harper and Row
_[8] 웹사이트 Markowsky or Cohn? https://topology.lmf[...] 2018-01-28
_[9] Webarchive "The lambda calculus, its syntax and semantics" http://www.elsevier.[...] "[[North-Holland Publishing Company|North-Holland]]"
_[10] 논문 Realizability at Work: Separating Two Constructive Notions of Finiteness https://doi.org/10.4[...]
_[11] 논문 Sur le théorème de Zorn
_[12] 논문 Beweisstudien zum Satz von M. Zorn
_[13] 서적 Bizonyítás és igazság / Válogatott tanulmányok Gondolat, Budapest
_[14] 웹사이트 A Course in Universal Algebra http://www.math.uwat[...]
_[15] 웹사이트 Universal Algebra
_[16] Webarchive "The lambda calculus, its syntax and semantics" http://www.elsevier.[...] "[[North-Holland]]"
_[17] 서적 The foundations of program verification John Wiley & Sons
_[18] 서적 Continuous lattices and domains Cambridge University Press 2003

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

문의하기 : help@durumis.com