부분순서완료

수학에서 완전 부분 순서라는 구절은 적어도 세 개의 유사하지만 구별되는 부분 순서 집합을 지칭하기 위해 다양하게 사용되는데, 특히 완전성 특성이 특징이다.완전한 부분 순서는 이론 컴퓨터 과학의 중심적 역할을 한다: 변절적 의미론과 영역 이론.

정의들

cpo라는 전체 부분 순서는 맥락에 따라 다음 개념 중 하나를 참조할 수 있다.

• 부분 주문 집합은 지시된 하위 집합 각각에 우월성이 있는 경우 지시된 완전한 부분 주문(dcpo)이다.부분 순서의 부분 집합은 비어 있지 않고 모든 요소 쌍이 부분 집합에 상한선을 갖는 경우 지시된다.문헌에서 dcpo는 때때로 라벨 업-완전 포셋 아래에 나타나기도 한다.

• 부분 순서는 dcpo가 최소 요소인 경우 지시된 완전한 부분 순서다.그것들은 때때로 약칭으로 쓰이기도 한다.

• 일부 순서 집합은 모든 Ω 체인(x₁≤x₂≤x₃≤x₄≤...)이 포셋의 기본 집합에 속하는 우월성을 갖는 포셋인 경우 Ω 완전 부분 순서(Ω-cpo)이다.모든 dcpo는 Ω-cpo인데, 모든 Ω 체인은 지시된 집합이지만 그 역은 사실이 아니기 때문이다.그러나 기초가 있는 모든 Ω-cpo도 dcpo(기반이 같은)이다.^[1]기초가 있는 Ω-cpo(dcpo)를 연속 Ω-cpo(연속 dcpo)라고도 한다.

완전한 부분 순서는 모든 하위 집합이 우월성을 갖는 포셋을 의미하는 데 결코 사용되지 않으며, 이 개념에는 완전 격자(complete lattice)라는 용어가 사용된다.

지시된 우월성의 존재를 요구하는 것은 지시된 집합을 일반화된 근사 시퀀스로 보고 우월성을 각 (대략적) 계산의 한계로 보는 것으로 동기 부여될 수 있다.이러한 직관은, 변절적 의미론의 맥락에서, 도메인 이론의 발달의 동기가 되었다.

지시-완전 포셋의 이중 개념은 여과-완전 부분 순서라고 불린다.그러나 이러한 개념은 일반적으로 이중 순서를 명시적으로 작업할 수 있기 때문에 실제로는 훨씬 덜 빈번하게 발생한다.

예

• 모든 유한양행은 완전한 방향이다.
• 모든 완전한 격자도 완전하게 지시된다.
• 모든 포셋의 경우, 부분 집합 포함에 의해 정렬된 모든 비어 있지 않은 필터 집합은 dcpo이다.빈 필터와 함께 그것은 또한 가리킨다.주문에 이진수가 일치하면 이 구조(빈 필터 포함)는 실제로 완전한 격자를 산출한다.
• 모든 세트 S는 최소 요소 ⊥을 추가하고 모든 s에 대해 ⊥ s s와 s ≤ s로 평탄한 순서를 도입하여 뾰족한 dcpo로 바꿀 수 있다.
• g가 f를 확장하는 경우에만, 즉 f의 영역이 g의 영역의 부분집합이고 f와 g의 값이 두 기능이 정의된 모든 입력에 동의하는 경우에만 f와 g에 대한 모든 부분함수의 집합은 f와 g에 대해 f ≤ g를 정의함으로써 주문할 수 있다. (f와 g가 f와 g와 함께 식별되는 경우, f g g와 f f g의 값이 동일한 경우에만).각 그래프)이 순서는 dcpo로, 여기서 최소 요소는 (빈 도메인이 있는) 아무 곳에도 정의되지 않은 함수다.사실 ≤도 완비되어 있다.이 예는 또한 왜 가장 큰 요소를 갖는 것이 항상 자연스럽지 않은지를 보여준다.
• 냉정한 공간의 특화 순서는 dcpo이다.
• 결과(결과의 개념을 정의하기 위해, 예를 들어, "고려력 시스템"이라는 용어를 결과에서 닫힌 문장 집합으로 사용하자.알프레드 타르스키의 대수적 접근법^[2][3]).일련의 연역적 시스템이 지시-완전한 부분 순서라는 것에 관한 흥미로운 이론들이 있다.^[4]또한, 빈 집합의 모든 결과 집합(즉, "논리적으로 증명할 수 있는/논리적으로 유효한 문장의 집합")이 (1) 모든 연역시스템이 포함하는 연역시스템 (2)이기 때문에, 연역시스템 집합은 자연적인 방법으로 최소한의 요소를 갖도록 선택할 수 있다.

특성.

주문된 집합 P는 모든 체인이 P에 우월성을 가지고 있는 경우에만, 즉 P가 체인 완전체인 경우, 그리고 경우에만 뾰족한 dcpo이다.^[5]또는 모든 주문 보관 자가 지도에 최소의 고정점이 있는 경우에만 정렬된 집합 P는 뾰족한 dcpo이다.

연속 기능 및 고정점

두 dcpos P와 Q 사이의 함수 f는 (스코트) 연속(scottenuous)이라고 불리며, 그 우월성을 보존하면서 지시된 집합에 매핑된다.

• ${\displaystyle f}$( ${\displaystyle D}$) ${\displaystyle \subseteq }$ ${\displaystyle Q}$ ${\displaystyle f(D)\subseteq Q}$은(는) 모든 방향 $D{\displaystyle }$ ${\displaystyle \subseteq }$ ${\displaystyle P}$ ${\displaystyle D\subseteq P}$에 대해 지시된다$.$
• ${\displaystyle }$$f{\displaystyle }$${\displaystyle }$( ${\displaystyle Sup}$ ${\displaystyle D}$)${\displaystyle }$= ${\displaystyle supp}$ ${\displaystyle f}$( D${\displaystyle }$) ${\displaystyle f(\supp$ D$)=\supp f(D)}$ 모든 지시 D${\displaystyle }${ ${\displaystyle P}$ ${\displaystyle D\subseteq P$에 대한 .

dcpos 사이의 모든 연속적인 기능은 단조로운 기능이라는 점에 유의한다.이러한 연속성의 개념은 Scott 위상에 의해 유도된 위상적 연속성과 동일하다.

두 dcpos P와 Q 사이의 모든 연속 기능 세트는 [P → Q]로 표시된다.포인트와이즈 오더가 갖추어진 이것은 다시 dcpo, Q가 cpo일 때마다 cpo이다.따라서 Scott-연속 지도가 포함된 전체 부분 주문은 데카르트 폐쇄 범주를 형성한다.^[6]

cpo(P, ⊥)의 모든 주문 보존 자가 지도 f에는 최소한의 고정 지점이 있다.^[7]f가 연속적인 경우, 이 고정 지점은 of의 반복체(⊥, f(⊥), f(⊥), …fⁿ(⊥)의 우월성과 동일하다(클레인 고정 지점 정리 참조).

참고 항목

지시된 완전성만 가지고는 대수적 포셋과 스콧 위상 등을 사용하는 다른 질서-이론적 조사에서 자주 발생하는 꽤 기본적인 속성이다.

지시된 완전성은 체인 완전성과 같은 다른 완전성 개념과 다양한 방식으로 관련된다.

메모들

참조

• Davey, B.A.; Priestley, H. A. (2002). Introduction to Lattices and Order (Second ed.). Cambridge University Press. ISBN 0-521-78451-4.