원순서 집합

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

1. 개요
2. 정의
3. 성질
4. 예시
5. 관련 개념
6. 구성
7. 구간
참조

1. 개요

원순서 집합은 반사성과 추이성을 만족하는 이항 관계이다. 원순서가 주어진 집합을 의미하며, 전순서 또는 유사순서라고도 한다. 원순서 집합은 부분 순서, 동치 관계, 전체 전순서 등의 관련 개념을 갖는다. 범주론, 그래프 이론, 컴퓨터 과학 등 다양한 분야에서 활용되며, 알렉산드로프 공간과 동치 관계를 이룬다. 원순서 집합은 추이적 폐포와 반사적 폐포를 통해 구성될 수 있으며, 구간 개념을 정의할 수 있다.

더 읽어볼만한 페이지

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

원순서 집합
원순서 관계
유형	이항 관계
성질	반사 관계(Reflexive relation)와 추이적 관계(Transitive relation)
다른 이름	준순서 관계(quasi-order)
관련 개념
확장	전순서 관계
약화	반사 관계, 추이적 관계
반대 관계	역관계
쌍대 관계	비교 가능성
특수 관계	동치 관계, 부분 순서, 전순서 관계

2. 정의

순서론에서 '''원순서 집합'''은 이항 관계를 갖춘 집합이며, 범주론에서는 '''원순서 집합'''을 얇은 작은 범주로 정의한다. 위상수학에서는 위상 공간의 특별한 종류인 알렉산드로프 공간으로 정의하며, 이 세 가지 정의는 서로 동치이다.

집합 $P$ 에 대한 이항 관계 $\,\lesssim\,$ 는 $P \times P$ 의 부분 집합이며, $a \lesssim b$ 는 $(a, b) \in \,\lesssim.$ 를 나타낸다. $\,\lesssim\,$ 가 반사적이고 추이적이면, '''전순서''' 또는 '''유사순서'''라고 하며 다음을 만족한다.

# 반사성: 모든 $a \in P$ 에 대해 $a \lesssim a$ .

# 추이성: 모든 $a, b, c \in P$ 에 대해 $a \lesssim b$ 이고 $b \lesssim c$ 이면 $a \lesssim c$ .

전순서가 주어진 집합을 '''전순서 집합'''(또는 '''프로셋''')이라고 한다.^[1]

2. 1. 순서론적 정의

집합 ''X'' 위의 원순서는 다음 조건들을 만족시키는 이항 관계

\lesssim \subseteq X^2

이다.

(반사성) 임의의 $a\in X$ 에 대하여, $a\lesssim a$
(추이성) 임의의 $a,b,c\in X$ 에 대하여, $a\lesssim b\lesssim c$ 라면 $a\lesssim c$

원순서를 갖춘 집합을 '''원순서 집합'''(preordered set|프로셋^영어)이라고 한다.^[1] 이 정의에 반대칭성(

a\lesssim b\land b\lesssim a\implies a=b

)을 추가하면 부분 순서를 얻는다.

\,\lesssim\,

를 집합 ''P''에 대한 이항 관계라고 할 때,

a \lesssim b

표기는

(a, b) \in \,\lesssim.

대신 사용된다.

원순서는 반사적이고 추이적인 관계이므로, 다음을 만족한다.

반사성: 모든 $a \in P$ 에 대해 $a \lesssim a$
추이성: 모든 $a, b, c \in P$ 에 대해 $a \lesssim b$ 이고 $b \lesssim c$ 이면 $a \lesssim c$

원순서가 주어진 집합을 '''원순서 집합'''(또는 프로셋)이라고 한다.

임의의 원순서

\,\lesssim\,

는

a \lt b

이면

a \lesssim b

이고

b \lesssim a

가 아닌 것으로 정의되는 엄격한 부분 순서를 생성한다.

만약 원순서

\,\lesssim\,

가 반대칭 관계이면, 동치 관계

\,\sim\,

는 동일성이 되며, 이 경우

\,<\,

의 정의는 다음과 같이 표현될 수 있다.

:

a \lt b \quad \text{ if and only if } \quad a \lesssim b \; \text{ and } \; a \neq b

2. 2. 범주론적 정의

범주론적으로, '''원순서 집합'''은 얇은 작은 범주이다. 구체적으로, 원순서 집합

(X,\lesssim)

은 다음과 같은 범주로 여길 수 있다.

$(X,\lesssim)$ 의 대상은 $X$ 의 원소이다.
$(X,\lesssim)$ 의 사상은 $a\lesssim b$ 인 두 원소의 순서쌍 $(a,b)$ 이며, 이는 $a$ 에서 $b$ 로 가는 사상이다. 즉, 사상 모임은 다음과 같다.
: $\hom(a,b)=\begin{cases}\{(a,b)\}&a\lesssim b\\\varnothing&a\not\lesssim b\end{cases}$

'''얇은 범주'''(얇은 範疇, thin category^영어)

\mathcal C

는 다음 조건을 만족시키는 범주이다.

임의의 두 대상 $X,Y\in\mathcal C$ 및 그 사이의 두 사상 $f,g\colon X\to Y$ 에 대하여, $f=g$ 이다. 즉, 사상 모임 $\hom_{\mathcal C}(X,Y)$ 는 한원소 집합이거나 공집합이다.

2. 3. 위상수학적 정의

'''알렉산드로프 공간'''(Александров空間, Alexandrov space^영어)은 임의의 열린집합들의 (유한 또는 무한) 족의 교집합이 열린집합인 위상 공간이다.

알렉산드로프 공간의 개념은 원순서 집합의 개념과 동치이다. 구체적으로, 임의의 위상 공간

X

에 대하여 다음과 같은 원순서를 줄 수 있다.

:

x\lesssim y\iff x\in\operatorname{cl}\{y\}

여기서

\operatorname{cl}\{y\}

는 한원소 집합의 폐포이다. 반대로, 임의의 원순서 집합

(X,\lesssim)

이 주어졌을 때, 상집합을 열린집합으로, 하집합을 닫힌집합으로 하는 위상을 부여할 수 있으며, 이렇게 하여 얻는 위상 공간은 항상 알렉산드로프 공간이다. 사실, 이러한 대응 관계는 원순서 집합과 순서 보존 함수의 범주

\operatorname{Proset}

및 위상 공간과 연속 함수의 범주

\operatorname{Top}

사이의 한 쌍의 수반 함자

:

\operatorname{Proset}\leftrightarrows\operatorname{Top}

를 이루며,

\operatorname{Top}

를 알렉산드로프 공간의 범주로 제한하면 범주의 동형이 된다.

3. 성질

원순서 집합 $(X,\lesssim)$ 가 주어졌을 때, $X$ 위에 동치 관계를 다음과 같이 정의할 수 있다.

: $a\sim b\stackrel{\text{def}}\iff a\lesssim b\land b\lesssim a$

이에 따른 몫집합 $X/{\sim}$ 위에서 $\lesssim$ 은 부분 순서를 정의한다. 반대로, 어떤 집합 $X$ 의 몫집합 위에 부분 순서가 주어지면, 이는 $X$ 위의 원순서를 정의한다.

크기가 $n$ 인 유한 집합 위의 가능한 원순서의 수는 다음과 같다 ( $n=0,1,2,\dots$ ).

n	0	1	2	3	4	5	6	7	8
원순서의 수	1	1	4	29	355	6942	209527	9535241	642779354

이 수열은 온라인 정수열 백과사전에 A798로 등록되어 있다.

유한 집합 위의 위상들과 원순서들 사이에는 표준적인 일대일 대응이 존재한다. 구체적으로, 위상 $\mathcal T$ (열린집합들의 집합)가 주어졌다면, 다음과 같이 원순서를 정의할 수 있다.

: $a\lesssim b\stackrel{\text{def}}\iff\left(\forall U\in\mathcal T\colon b\in U\implies a\in U\right)$

반대로, 원순서 $\lesssim$ 가 주어졌다면, $\{\{a\colon a\lesssim b\}\colon b\}$ 를 기저로 하는 위상을 정의할 수 있다.

4. 예시

다음은 원순서 집합의 예시이다.

유향 그래프에서 도달 가능성 관계는 원순서이다.^[1] 여기서 $x \lesssim y$ 는 ''x''에서 ''y''로 가는 경로가 있는 경우에만 해당된다.
그래프 마이너 관계는 원순서이다.^[2]
함수 $f: \mathbb{N} \to \mathbb{N}$ 에 대한 점근적 순서는 원순서이며, 이에 해당하는 동치 관계는 점근적 동치라고 한다.
다항 시간, 일대일 (매핑) 및 튜링 환원은 복잡도 클래스에 대한 원순서이다.
서브타이핑 관계는 일반적으로 원순서이다.^[2]
시뮬레이션 부분 순서는 원순서이다.
추상 재작성 시스템에서 환원 관계는 원순서이다.
항 집합에 대한 포괄 부분 순서는 원순서로, $s \lesssim t$ 는 ''t''의 부분 항이 ''s''의 대입 인스턴스인 경우 정의된다.
세타-포함은 원순서이며,^[3] 여기서 선언적 일차 논리 공식의 리터럴은 전자에 대입을 적용한 후 다른 리터럴에 의해 포함된다.
범주론에서 원순서 집합은 얇은 작은 범주이다.
모든 유한 위상 공간에서 점에 대한 원순서를 정의할 수 있다.
넷은 유향 원순서이다.
''f''가 어떤 원순서로의 함수일 경우, $f(x) \lesssim f(y)$ 로 정의된 관계는 $x \lesssim y$ 로 정의된다.^[2]
''x''에서 ''y''로의 단사가 존재할 경우 $x \lesssim y$ 로 정의된 관계이다.
가산 전순서에 대한 매장 관계.^[4]
전체 원순서의 예로 일반적인 모델에 따른 선호도가 있다.^[5]

4. 1. 그래프 이론

유향 그래프에서 도달 가능성 관계는 원순서이다.^[1] 여기서

x \lesssim y

는 ''x''에서 ''y''로 가는 경로가 있는 경우에만 해당된다. 반대로, 모든 원순서는 유향 그래프의 도달 가능성 관계이다. (예:

x \lesssim y

인 모든 쌍 (''x'', ''y'')에 대해 ''x''에서 ''y''로 가는 모서리를 갖는 그래프). 그러나 여러 다른 그래프가 서로 동일한 도달 가능성 원순서를 가질 수 있다. 마찬가지로, 사이클이 없는 유향 그래프의 도달 가능성은 부분 순서 집합을 생성한다.^[1]

그래프 마이너 관계 또한 원순서이다.^[2]

4. 2. 컴퓨터 과학

점근적 순서는 함수 $f: \mathbb{N} \to \mathbb{N}$ 에 대한 원순서이다. 이에 해당하는 동치 관계는 점근적 동치라고 한다.
다항 시간, 일대일 (매핑) 및 튜링 환원은 복잡도 클래스에 대한 원순서이다.
서브타이핑 관계는 일반적으로 원순서이다.^[2]
시뮬레이션 부분 순서는 원순서이다 (이름에서 알 수 있듯이).
환원 관계는 추상 재작성 시스템에서 원순서이다.
포괄 부분 순서는 항 집합에 대한 원순서로, $s \lesssim t$ 는 ''t''의 부분 항이 ''s''의 대입 인스턴스인 경우 정의된다.
세타-포함은 원순서이며,^[3] 여기서 선언적 일차 논리 공식의 리터럴은 전자에 대입을 적용한 후 다른 리터럴에 의해 포함된다.

4. 3. 범주론

범주론에서 원순서 집합은 얇은 작은 범주이다. 원순서 집합

(X,\lesssim)

은 다음과 같은 범주로 나타낼 수 있다.

$(X,\lesssim)$ 의 대상은 $X$ 의 원소이다.
$(X,\lesssim)$ 의 사상은 $a\lesssim b$ 인 두 원소의 순서쌍 $(a,b)$ 이며, 이는 $a$ 에서 $b$ 로 가는 사상이다. 즉, 사상 모임은 다음과 같다.
: $\hom(a,b)=\begin{cases}\{(a,b)\}&a\lesssim b\\\varnothing&a\not\lesssim b\end{cases}$

원순서 집합은 범주

2 = (0 \to 1)

을 통해 강화된 강화된 범주로 이해할 수도 있다.^[1]

4. 4. 기타

모든 유한 위상 공간에서 $x \lesssim y$ 를 ''x''가 ''y''의 모든 근방에 속할 경우에만 정의함으로써 점에 대한 원순서를 생성한다. 모든 유한 원순서는 이와 같은 방식으로 위상 공간의 특수화 전순서로 형성될 수 있다. 즉, 유한 위상과 유한 원순서 사이에는 일대일 대응이 있다. 그러나 무한 위상 공간과 그 특수화 전순서 간의 관계는 일대일이 아니다.

넷은 유향 원순서, 즉, 각 요소 쌍이 상계를 갖는 원순서이다. 넷을 통한 수렴의 정의는 원순서를 중요한 기능을 잃지 않고 부분 순서 집합으로 대체할 수 없는 위상수학에서 중요하다.^[1]

''f''가 어떤 원순서로의 함수일 경우, $f(x) \lesssim f(y)$ 로 정의된 관계는 $x \lesssim y$ 로 정의된다.^[2]

''x''에서 ''y''로의 단사가 존재할 경우 $x \lesssim y$ 로 정의된 관계이다. 단사는 전사 함수, 또는 환 준동형 사상, 순열과 같은 구조 보존 함수로 대체될 수 있다.^[3]

가산 전순서에 대한 매장 관계.^[4]

전체 원순서의 예로 일반적인 모델에 따른 선호도가 있다.^[5]

5. 관련 개념

원순서 집합 $(X,\lesssim)$ 에서, $X$ 위에 동치 관계를 다음과 같이 정의할 수 있다.

: $a\sim b\stackrel{\text{def}}\iff a\lesssim b\land b\lesssim a$

이에 따른 몫집합 $X/{\sim}$ 위에서 $\lesssim$ 은 부분 순서를 정의한다.

반사율을 비반사성으로 대체하고 전이성을 유지하면 강 부분 순서의 정의를 얻게 된다.

임의의 전순서 $\,\lesssim\,$ 에서 $a \lt b$ 이면 $a \lesssim b$ 이고 $b \lesssim a$ 가 아닌 것으로 정의되는 엄격한 부분 순서를 생성한다. 위에 소개된 동치 관계 $\,\sim\,$ 를 사용하면, $a \lt b$ 는 $a \lesssim b \text{ 이고 } a \sim b$ 가 아닌 것과 같다. 따라서 다음이 성립한다.

: $a \lesssim b \quad \text{ if and only if } \quad a \lt b \; \text{ or } \; a \sim b.$

전순서 $\,\lesssim\,$ 가 반대칭 관계이면, 동치 $\,\sim\,$ 는 동일성이 되며, 이 경우 $\,<\,$ 의 정의는 다음과 같이 다시 표현될 수 있다.

: $a \lt b \quad \text{ if and only if } \quad a \lesssim b \; \text{ and } \; a \neq b \quad\quad (\text{assuming } \lesssim \text{ is antisymmetric}).$

전순서가 반대칭적이면, 즉, $a \lesssim b$ 이고 $b \lesssim a$ 이면 $a = b$ 이면, 이는 부분 순서이다.

반면에, 대칭적이면, 즉, $a \lesssim b$ 이면 $b \lesssim a$ 이면, 이는 동치 관계이다.

전순서는 모든 $a, b \in P$ 에 대해 $a \lesssim b$ 또는 $b \lesssim a$ 이면 전체이다.

6. 구성

원순서 집합 $\,\lesssim\,$ 이 $S$ 에 주어지면, 다음과 같은 동치 관계 $\,\sim\,$ 를 $S$ 에서 정의할 수 있다.

: $a \sim b \quad \text{ if and only if } \quad a \lesssim b \; \text{ and } \; b \lesssim a.$

결과적인 관계 $\,\sim\,$ 는 원순서 $\,\lesssim\,$ 가 반사적이므로 반사적이며, $\,\lesssim\,$ 의 추이성을 두 번 적용하여 추이적이며, 정의에 의해 대칭적이다.

이 관계를 사용하여 동치류의 몫집합 $S / \sim,$ 즉 $\,\sim.$ 의 모든 동치류 집합에 부분 순서를 구성할 수 있다. 원순서가 $R^{+=}$ 로 표시되면, $S / \sim$ 은 $R$ -사이클 동치류의 집합이다.

: $x \in [y]$ iff $x = y$ or $x$ is in an $R$ -cycle with $y$ .

어떤 경우든, $S / \sim$ 에서 $[x] \leq [y]$ 를 $x \lesssim y.$ 일 때 정의할 수 있다. 이것이 잘 정의되어 있다는 것은, 즉 정의 조건이 $[x]$ 와 $[y]$ 의 대표를 선택하는 것에 의존하지 않는다는 것은 $\,\sim.\,$ 의 정의에서 따른다. 이것이 부분 순서 집합을 산출한다는 것은 쉽게 확인된다.

반대로, 집합 $S$ 의 분할에 대한 임의의 부분 순서로부터, $S$ 자체에 대한 원순서를 구성할 수 있다. 원순서와 (분할, 부분 순서) 쌍 사이에는 일대일 대응이 있다.

'''예시'''

$S$ 를 어떤 속성을 가진 형식적 이론으로 하자. 예를 들어, $S$ 는 1차 이론 (예: 체르멜로-프렝켈 집합론) 또는 더 간단한 0차 이론일 수 있다. $S$ 의 많은 속성 중 하나는 논리적 결과에 대해 닫혀 있다는 것이다. 예를 들어, 명제 $A \in S$ 가 어떤 명제 $B$ 를 논리적으로 함축하는 경우, 이는 $A \Rightarrow B$ 로 작성되며, $B \Leftarrow A,$ 로도 작성된다면, 반드시 $B \in S$ 이다 (''전건 긍정식'').

관계 $\,\Leftarrow\,$ 는 $S$ 에 대한 원순서이며, $A \Leftarrow A$ 가 항상 성립하고 $A \Leftarrow B$ 와 $B \Leftarrow C$ 가 모두 성립할 때마다 $A \Leftarrow C$ 도 성립하기 때문이다.

또한, 임의의 $A, B \in S,$ 에 대해, $A \sim B$ iff $A \Leftarrow B \text{ and } B \Leftarrow A$ 이다. 즉, 두 개의 명제가 $\,\Leftarrow\,$ 에 대해 동치인 경우는 두 명제가 논리적 동치일 때뿐이다. 이 특정 동치 관계 $A \sim B$ 는 일반적으로 자체 특수 기호 $A \iff B,$ 로 표시되므로, 이 기호 $\,\iff\,$ 는 $\,\sim.$ 대신 사용될 수 있다. 명제 $A$ 의 동치류는 $[A]$ 로 표시되며, $A$ 와 논리적으로 동치인 모든 명제 $B \in S$ 로 구성된다. (즉, $A \iff B$ 인 모든 $B \in S$ ).

$\,\Leftarrow,\,$ 에 의해 유도된 $S / \sim$ 에 대한 부분 순서는 동일한 기호 $\,\Leftarrow,\,$ 로 표시되며, $[A] \Leftarrow [B]$ iff $A \Leftarrow B,$ 로 특징지어진다. 여기서 우변의 조건은 동치류의 대표 $A \in [A]$ 와 $B \in [B]$ 의 선택에 독립적이다.

지금까지 $\,\Leftarrow\,$ 에 대해 말한 모든 것은 역관계 $\,\Rightarrow.\,$ 에 대해서도 말할 수 있다.

원순서 집합 $(S, \Leftarrow)$ 는 $A, B \in S$ 이고 $C := A \wedge B$ 가 논리적 접속 $\,\wedge,\,$ 에 의해 형성된 명제를 나타내면 $A \Leftarrow C$ 와 $B \Leftarrow C$ 가 성립하는 유향 집합이다. 여기서 $C \in S.$ 따라서 부분 순서 집합 $\left(S / \sim, \Leftarrow\right)$ 도 유향 집합이다.

관련된 예는 린덴바움-타르스키 대수를 참조하라.

집합 $S$ 에 대한 모든 이진 관계 $R$ 은 추이적 폐포 및 반사적 폐포 $R^{+=}$ 를 취함으로써 $S$ 에 대한 전순서로 확장될 수 있다. 추이적 폐포는 $R$ 에서 경로 연결을 나타낸다. 즉, $x R^+ y$ 는 $x$ 에서 $y$ 까지의 $R$ -경로가 있는 경우에만 해당한다.

'''이진 관계에 의해 유도된 좌측 잔여 전순서'''

이진 관계 $R$ 이 주어지면, 보완된 합성 $R \backslash R = \overline{R^\textsf{T} \circ \overline{R}}$ 은 좌측 잔여라고 하는 전순서를 형성하며,^[4] 여기서 $R^\textsf{T}$ 는 $R$ 의 역관계를 나타내고, $\overline{R}$ 는 $R$ 의 여집합 관계를 나타내며, $\circ$ 는 관계 합성을 나타낸다.

7. 구간

구간 $[a, b]$ 는 $a \lesssim x$ 및 $x \lesssim b$ 를 만족하는 점 ''x''의 집합이며, $a \lesssim x \lesssim b$ 로도 표기한다. 이 집합은 적어도 점 ''a''와 ''b''를 포함한다. 이 정의를 모든 쌍 $(a, b)$ 로 확장할 수도 있으며, 이렇게 확장된 구간들은 모두 공집합이다.

이에 상응하는 엄격한 관계 " $<$ "를 사용하여 구간 $(a, b)$ 를 $a < x$ 및 $x < b$ 를 만족하는 점 ''x''의 집합으로 정의할 수 있으며, $a < x < b$ 로도 표기한다. 열린 구간은 $a < b$ 일지라도 공집합일 수 있다.

$[a, b)$ 와 $(a, b]$ 도 유사하게 정의할 수 있다.

참조

_[1] 논문 Generalized Cauchy spaces
_[2] 서적 Types and Programming Languages The MIT Press 2002
_[3] 간행물 A machine-oriented logic based on the resolution principle
_[4] 문서 In this context, " $\backslash$ " does not mean "set difference".
_[5] 서적 Set Theory, An Introduction to Independence Proofs Elsevier

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

문의하기 : help@durumis.com