전순서 집합

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

1. 개요

전순서 집합은 임의의 두 원소 간의 비교가 가능한 원순서 집합으로 정의되며, 부분 순서 집합이면서 이항 관계가 추이성, 반대칭성, 완전성을 만족한다. 전순서 집합은 원전순서 집합, 전순서 집합, 강 전순서 집합 등으로 세분화되며, 순서합, 사전식 순서와 같은 연산을 통해 새로운 전순서 집합을 만들 수 있다. 전순서 집합은 순서 위상을 부여하여 위상 공간으로 취급할 수 있으며, 완비 전순서 집합은 콤팩트 공간이다. 유한 전순서 집합은 정렬 집합이며, 가산 조밀 전순서 집합은 유리수 집합 또는 그 변형과 순서 동형이다. 완비 분해 가능 조밀 전순서 집합은 확장된 실수 집합 또는 그 변형과 순서 동형이다. 주요 예시로는 순서체, 실수, 정수, 유리수 등이 있으며, 아론샤인 직선과 컨트리먼 직선은 전순서 집합의 특수한 예시이다.

더 읽어볼만한 페이지

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

전순서 집합
정의
설명	어떤 집합의 모든 원소 쌍이 비교 가능한 관계를 가지는 순서 관계이다. 즉, 집합 내의 모든 원소가 '줄'을 따라 정렬될 수 있는 관계이다.
관련 개념
반대 개념	반순서 집합
상위 개념	순서론
하위 개념	전순서 집합은 정렬 집합의 특수한 경우이다.
성질
비교 가능성	집합 내 임의의 두 원소 a, b에 대해 a ≤ b 또는 b ≤ a 중 적어도 하나가 성립한다.
전이성	a ≤ b 이고 b ≤ c 이면 a ≤ c 이다.
반대칭성	a ≤ b 이고 b ≤ a 이면 a = b 이다.
반사성	a ≤ a 이다.
예시
수의 집합	실수 집합, 유리수 집합, 정수 집합 등은 일반적인 크기 비교(≤)에 대해 전순서 집합이다.
사전식 순서	문자열의 사전식 순서는 전순서 관계를 정의한다.
활용
정렬 알고리즘	데이터 정렬의 기본 개념으로 활용된다.
데이터베이스	데이터베이스 인덱싱 및 검색에 사용된다.
컴퓨터 과학	컴퓨터 과학 분야에서 자료 구조 및 알고리즘 설계에 중요한 역할을 한다.

2. 정의

원순서 집합, 전순서 집합, 강 전순서의 정의가 제시된다.

전순서 집합 $(X,\le)$ 의 '''도약'''(跳躍, jump^영어) $(a,b)\in X^2$ 은 다음 두 조건을 만족시키는 순서쌍이다.

$a 이다.$
$a 인 c\in X 가 존재하지 않는다.$

도약이 없는 전순서를 조밀 순서라고 한다.

임의의 (광의) 전순서 관계 ≤에 대해, 이에 부속하는 비대칭 (따라서 비반사적)인 '''협의 전순서''' (strict total order)라고 불리는 관계

<

가 존재한다. 이는 다음의 서로 동치인 두 종류의 방식으로 정의할 수 있다.

$a < b \Leftrightarrow a \le b$ 이고 $a \ne b$
$a < b \Leftrightarrow b \le a$ 가 아님

후자는 관계

<

가

\le

의 보관계의 역관계임을 의미한다.

협의 전순서의 성질은 다음과 같다.

추이율: $a < b$ 이고 $b < c$ 이면 $a < c$
삼분율: $a < b$ 또는 $b < a$ 또는 $a = b$ 중 어느 하나만 성립한다.
항등성을 부속하는 동치 관계로 하는 협의 약순서이다.

추이적이고 삼분적인 이항 관계

<

가 처음에 주어졌을 때, 거기에서 (광의) 전순서 ≤를 정하는 것도 다음의 동치인 두 종류의 방법으로 가능하다.

$a \le b \Leftrightarrow a < b$ 또는 $a = b$
$a \le b \Leftrightarrow b < a$ 가 아님

그 외에도 두 가지, 이들의 보관계

\ge

와

>

를 생각할 수 있으며, 네 짝

{\{<, >, \le, \ge\}}

는 어느 것으로부터라도 다른 세 종류를 도출할 수 있으므로, 집합이 전순서화됨을 말하는데 어떤 관계를 사용하여 정의·기술해도 좋다(특히 광의인지 협의인지는 기호로 구별할 수 있다).^[3]^[4]

2. 1. 원전순서 집합

원순서 집합

(X,\lesssim)

이 다음 조건을 만족시킨다면, '''원전순서 집합'''(pretotally ordered set|프리토털리 오더드 셋^영어)이라고 한다.

임의의 $x,y\in X$ 에 대하여, $x\lesssim y$ 이거나 $y\lesssim x$ 이다.

즉, 두 원소가 항상 비교 가능한 원순서 집합이다.

2. 2. 전순서 집합

'''전순서 집합'''(全順序集合, totally ordered set|토털리 오더드 셋^영어)은 원전순서 집합인 부분 순서 집합

(X,\le)

이다. 이항 관계

\le

는 다음 세 조건을 만족시킨다.

(추이성) 만약 $x\le y\le z$ 라면 $x\le z$ 이다.
(반대칭성) 임의의 $x,y\in X$ 에 대하여, 만약 $x\le y$ 이며 $y\le x$ 라면 $x=y$ 이다.
(완전성) 항상 $x\le y$ 이거나 $y\le x$ 이다.

2. 3. 강 전순서

집합

X

에 대한 '''강 전순서'''는

X

에 대한 강 부분 순서이며, 서로 다른 임의의 두 원소가 비교 가능한 관계이다. 즉, 강 전순서는 다음 성질들을 만족하는 이항 관계

<

이다. 여기서

X

는 어떤 집합이고,

a, b, c

는

X

의 원소이다.

#

a < a

가 아니다. (비반사성)

# 만약

a < b

이면,

b < a

가 아니다. (비대칭성)

# 만약

a < b

이고

b < c

이면,

a < c

이다. (추이성)

# 만약

a \neq b

이면,

a < b

또는

b < a

이다. (연결성)

비대칭성은 추이성과 비반사성으로부터 유도되며,^[3] 비반사성은 비대칭성으로부터 유도된다.^[4]

(비강) 전순서

\leq

가 주어졌을 때, 이와 관련된 "강 전순서"

<

는 다음 두 가지 방법으로 정의할 수 있다.

$a < b$ 는 $a \leq b$ 이고 $a \neq b$ 인 경우이다. (반사 축소)
$a < b$ 는 $b \leq a$ 가 아닌 경우이다. (즉, $<$ 는 $\leq$ 의 보수의 역이다.)

반대로, 강 전순서

<

의 반사적 폐포는 (비강) 전순서가 된다.

3. 성질

전순서 집합은 다음과 같은 성질을 갖는다.

함의 관계:

전순서 집합	⇒	원전순서 집합
⇓		⇓
부분 순서 집합	⇒	원순서 집합

연산: 전순서 집합은 순서합, 사전식 순서 등의 연산을 통해 새로운 전순서 집합을 만들 수 있다.

위상수학적 성질: 전순서 집합은 순서 위상을 통해 위상 공간으로 다룰 수 있으며, 완비 정규 공간, 하우스도르프 공간 등 위상적 성질을 갖는다. 또한, 연결 공간인지 여부와 선형 연속체인지 여부가 동치이다. 완비 격자인 전순서 집합은 콤팩트 공간이다.

범주론적 성질: 전순서 집합과 증가 함수는 구체적 범주를 이루며, 이는 작은 범주 범주의 충만한 부분 범주이다.

3. 1. 함의 관계

전순서 집합	⇒	원전순서 집합
⇓		⇓
부분 순서 집합	⇒	원순서 집합

3. 2. 연산

"체인"은 때때로 전순서 집합의 동의어로 정의되지만, 일반적으로는 유도된 순서에 대해 전순서를 갖는 부분 순서 집합의 부분 집합을 가리킨다.^[6] 부분 순서 집합은 보통 포함 관계에 의해 정렬된, 주어진 집합의 부분 집합들의 집합이며, 체인은 이러한 집합의 속성을 설명하는 데 사용된다.

초른의 보조정리는 전순서 부분 집합을 지칭하는 데 '체인'을 사용하는 대표적인 예이다. 초른의 보조정리에 따르면, 부분 순서 집합 P의 모든 체인이 P에서 상계를 가지면 P는 적어도 하나의 극대 원소를 포함한다.^[7]

어떤 경우에는 체인이 일반적인 순서 또는 역순서를 갖는 자연수와 순서 동형이다. 이때 체인은 단조 수열과 동일시될 수 있으며, 수열의 증가/감소 여부에 따라 '''상승 체인''' 또는 '''하강 체인'''이라고 부른다.^[8]

부분 순서 집합에서 모든 하강 체인이 결국 안정되면 하강 체인 조건을 만족한다고 한다.^[9] 예를 들어, 순서가 잘 정렬되어 있으면 하강 체인 조건을 만족한다. 상승 체인 조건은 모든 상승 체인이 결국 안정되는 것을 의미하며, 뇌터 환은 아이디얼이 상승 체인 조건을 만족하는 환이다.

유한 집합인 체인만 고려하는 경우도 있는데, 이를 ''유한 체인''이라고 하며, 간단히 ''체인''으로 줄여 쓰기도 한다. 체인의 '''길이'''는 체인 내 연속적인 원소 사이의 부등식(또는 집합 포함)의 수, 즉 원소 개수에서 1을 뺀 값이다.^[10] 단일 집합은 길이가 0인 체인이고, 순서쌍은 길이가 1인 체인이다. 공간의 차원은 부분 공간 체인의 최대 길이로 정의되기도 한다. 예를 들어, 벡터 공간의 차원은 선형 부분 공간 체인의 최대 길이이며, 가환환의 크룰 차원은 소 아이디얼 체인의 최대 길이이다.

전순서 집합은 특정 종류의 격자로 정의할 수 있다. 즉, 임의의 ''a'', ''b''에 대해

\{a\vee b, a\wedge b\} = \{a, b\}

가 성립하고, ''a'' ≤ ''b'' ⇔

a = a\wedge b

로 정의한다. 이에 따라 전순서 집합은 분배 격자가 된다.

전순서 집합이 '''완비'''라는 것은 공집합이 아니고 상계를 갖는 임의의 부분 집합이 상한을 갖는다는 의미이다. 실수 전체의 집합은 완비이지만, 유리수 전체의 집합은 그렇지 않다.

집합 ''X''가 완비가 되는 순서 위상의 성질은 다음과 같다.

''X'' 위의 순서 위상이 연결되어 있다면 ''X''는 완비이다.
''X''가 순서 위상에 관해 연결되기 위한 필요충분조건은 완비이고 ''X''에 "갭"이 없는 것이다. 여기서 "갭"은 ''X''의 두 점 ''a'', ''b'' (a < b)에 대해 a < c < b를 만족하는 점 ''c''가 존재하지 않는 경우를 말한다.
''X''가 완비가 되기 위한 필요충분조건은 순서 위상에서 임의의 닫힌 유계 집합이 콤팩트가 되는 것이다.

완비 격자를 이루는 전순서 집합은 그 순서 위상에서 콤팩트하다. 실수로 이루어진 닫힌 구간(예: 단위 닫힌 구간)이나 확대 실수 직선이 그 예이다.

3. 2. 1. 순서합

원순서 집합들의 족

\{(X_i,\lesssim_i)\}_{i\in I}

가 주어졌고,

I

에 원순서

\lesssim_I

가 부여되었다고 하자. 그러면 분리합집합

X=\textstyle\bigsqcup_{i\in I}X_i

위에 다음과 같은 원순서를 정의할 수 있다.

:

x_i\lesssim y_j\iff \left((i\prec_Ij)\lor\left(i=j\land x_i\lesssim_iy_j\right)\right)\qquad(x_i\in X_i,\;y_j\in X_j)

이를

\{(X_i,\lesssim_i)\}_{i\in I}

들의 '''순서합'''(ordered sum^영어)이라고 한다. (여기서

i\prec_Ij

는

i\lesssim_Ij\not\lesssim_Ii

를 뜻하며,

i\sim_Ij

는

i\lesssim j\lesssim i

를 뜻한다.)

이에 대하여 다음이 성립한다.

만약 $(I,\lesssim_I)$ 가 전순서 집합이며, 모든 $(X_i,\lesssim_i)$ 가 원전순서 집합이라면, 그 순서합 $X$ 역시 원전순서 집합이다.
만약 $(I,\lesssim_I)$ 가 전순서 집합이며, 모든 $(X_i,\lesssim_i)$ 가 전순서 집합이라면, 그 순서합 $X$ 역시 전순서 집합이다.
만약 모든 $(X_i,\lesssim_i)$ 가 부분 순서 집합이라면, 그 순서합 $X$ 역시 부분 순서 집합이다.

임의의 서로소인 전순서 집합

(A_1,\le_1)

과

(A_2,\le_2)

에 대해, 두 순서의 합 또는 간단히

A_1+A_2

라고 하는, 집합

A_1\cup A_2

에 자연스러운 순서

\le_+

가 존재한다.^[1]

:

x,y\in A_1\cup A_2

에 대해, 다음 중 하나가 참일 경우에만

x\le_+ y

가 성립한다.

:#

x,y\in A_1

이고

x\le_1 y

:#

x,y\in A_2

이고

x\le_2 y

:#

x\in A_1

이고

y\in A_2

직관적으로 이것은 두 번째 집합의 원소가 첫 번째 집합의 원소 위에 추가된다는 것을 의미한다.

더 일반적으로,

(I,\le)

가 전순서 인덱스 집합이고, 각

i\in I

에 대해 구조

(A_i,\le_i)

가 선형 순서이며, 집합

A_i

가 쌍별로 서로소인 경우,

\bigcup_i A_i

에 대한 자연적인 전순서는 다음과 같이 정의된다.^[2]

:

x,y\in \bigcup_{i\in I} A_i

에 대해, 다음 중 하나가 참일 경우

x\le y

가 성립한다.

:# 어떤

i\in I

에 대해

x\le_i y

가 성립한다.

:# 또는

I

에

x\in A_i

,

y\in A_j

이고

i 인 어떤 i, j 가 존재한다.

3. 2. 2. 사전식 순서

원순서 집합들의 족

\{(X_i,\lesssim_i)\}_{i\in I}

가 주어졌으며,

I

에 역시 원순서

\lesssim_I

가 부여되었다고 하자. 그렇다면, 분리합집합

X=\textstyle\bigsqcup_{i\in I}X_i

위에 다음과 같은 원순서를 정의할 수 있다.

:

x_i\lesssim y_j\iff \left((i\prec_Ij)\lor\left(i=j\land x_i\lesssim_iy_j\right)\right)\qquad(x_i\in X_i,\;y_j\in X_j)

이를

\{(X_i,\lesssim_i)\}_{i\in I}

들의 '''순서합'''(ordered sum^영어)이라고 한다. (여기서

i\prec_Ij

는

i\lesssim_Ij\not\lesssim_Ii

를 뜻하며,

i\sim_Ij

는

i\lesssim j\lesssim i

를 뜻한다.)

이에 대하여 다음이 성립한다.

만약 $(I,\lesssim_I)$ 가 전순서 집합이며, 모든 $(X_i,\lesssim_i)$ 가 원전순서 집합이라면, 그 순서합 $X$ 역시 원전순서 집합이다.
만약 $(I,\lesssim_I)$ 가 전순서 집합이며, 모든 $(X_i,\lesssim_i)$ 가 전순서 집합이라면, 그 순서합 $X$ 역시 전순서 집합이다.
만약 모든 $(X_i,\lesssim_i)$ 가 부분 순서 집합이라면, 그 순서합 $X$ 역시 부분 순서 집합이다.

3. 3. 위상수학적 성질

순서 위상을 갖춘 전순서 집합은 위상 공간으로 다룰 수 있다.

모든 원전순서 집합은 (순서 위상에서) 완비 정규 공간이며, 모든 전순서 집합은 하우스도르프 완비 정규 공간이다.^[17]

전순서 집합에 대해 다음 두 조건은 서로 동치이다.

선형 연속체이다.
순서 위상을 부여했을 때, 연결 공간이다.

완비 전순서 집합은 항상 콤팩트 공간이다.

전순서 집합의 부분 공간은 항상 직교 콤팩트 공간이자 가산 파라콤팩트 공간이다. 전순서 집합이 메타콤팩트 공간이면, 파라콤팩트 공간이다.

모든 분해 가능 전순서 집합은 항상 사전식 순서를 부여한

\mathbb R\times2

의 부분 집합과 순서 동형이다.^[17]

전순서 집합의 순서 위상은 정규 공간이다.

상한을 갖는 모든 공집합이 아닌 집합이 최소 상한을 가질 경우, 전순서 집합은 '''완비'''라고 한다. 예를 들어 실수 집합 '''R'''은 완비이지만, 유리수 집합 '''Q'''는 완비가 아니다.

순서 위상의 속성과 X의 완비성과 관련된 결과는 다음과 같다.

''X''의 순서 위상이 연결되어 있으면 ''X''는 완비이다.
''X''는 순서 위상에서 연결되어 있을 필요충분조건은 완비이고 ''X''에 ''갭''이 없을 때이다(갭은 ''a'' < ''b''를 만족하는 ''a''와 ''b'' 두 점으로, ''a'' < ''c'' < ''b''를 만족하는 ''c''가 없다).
''X''는 순서 위상에서 닫힌 유계 집합이 콤팩트일 때 필요충분조건으로 완비이다.

완비 격자인 전순서 집합(순서 위상 포함)은 콤팩트이다. 예시로는 실수의 닫힌 구간, 예를 들어 단위 구간 [0,1]과 아핀 확장 실수 체계(확장된 실수선)가 있다.

3. 4. 범주론적 성질

전순서 집합과 증가 함수는 구체적 범주를 이룬다. 이는 작은 범주의 범주의 충만한 부분 범주이다.

공집합이 아닌 유한 전순서 집합들의 범주는 '''단체 범주'''(simplex category^영어)라고 하며, 그 위의 준층 범주는 '''단체 집합'''이라고 한다. 이는 호모토피 이론에서 매우 중요하게 사용된다.

전순서 집합은 모든 ''a'', ''b''에 대해

: {''a''∨''b'', ''a''∧''b''} = {''a'', ''b''}

를 만족하는 격자로 정의할 수 있다.

이때 ''a'' ≤ ''b'' 는 ''a'' = ''a''∧''b''로 표기한다. 따라서 전순서 집합은 분배 격자이다.

전순서 집합은 부분 순서 집합의 범주의 충만 부분 범주를 형성하며, 사상은 순서를 존중하는 함수, 즉 ''a'' ≤ ''b''이면 ''f''(''a'') ≤ ''f''(''b'')인 함수 ''f''이다.

두 전순서 집합 간의 순서를 존중하는 전단사 함수는 이 범주에서 동형 사상이다. 순서를 보존하는 사상 ''f''(''a'' ≤ ''b'' 이면 ''f''(''a'') ≤ ''f''(''b''))를 사상으로 하여, 전순서 집합 전체는 반순서 집합의 범주의 충만 부분 범주가 된다.

이때, 두 전순서 집합 사이의 전단사 사상은 이 범주에서의 동형 사상이 된다.

4. 분류

선택 공리를 추가한 체르멜로-프렝켈 집합론에서는 모든 전순서 집합의 분류가 불가능하다. 예를 들어, 수슬린 가설은 비교적 간단한 분류 문제임에도 불구하고 증명하거나 반증할 수 없다. 그러나 특수한 경우에는 다음과 같은 분류가 가능하다.

가산 조밀 전순서 집합
완비 분해 가능 조밀 전순서 집합
유한 집합 위의 (원)전순서

전순서 집합은 임의의 ''a'', ''b''에 대해

\{a\vee b, a\wedge b\} = \{a, b\}

가 성립하고, ''a'' ≤ ''b'' ⇔

a = a\wedge b

로 정의되는 분배 격자의 일종으로 볼 수도 있다.

4. 1. 가산 조밀 전순서 집합

조밀 가산 전순서 집합

(X,\le)

은 다음 여섯 전순서 집합 가운데 정확히 하나와 순서 동형이다.

공집합
한원소 집합
$\mathbb Q$ (유리수의 전순서 집합)
$\{-\infty\}\sqcup\mathbb Q$ . 이는 $\mathbb Q_{\ge0}$ 과 순서 동형이다.
$\mathbb Q\sqcup\{+\infty\}$ . 이는 $\mathbb Q_{\le0}$ 과 순서 동형이다.
$\mathbb Q\sqcup\{-\infty,+\infty\}$ . 이는 $\mathbb Q\cap[0,1]$ 과 순서 동형이다.

특히, 최대 원소와 최소 원소를 갖지 않는 분해 가능 조밀 가산 전순서 집합

(X,\le)

은 항상

\mathbb Q

와 순서 동형이다.

4. 2. 완비 분해 가능 조밀 전순서 집합

전순서 집합

(X,\le)

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

$X$ 는 조밀 순서이다.
$X$ 에 순서 위상을 가하면, $X$ 는 분해 가능 공간이다.
(완비성) 상계와 하계를 갖는 임의의 부분 집합 $A\subseteq X$ 는 (만약 $A\ne\varnothing$ 이라면) 상한과 하한을 갖는다.

그렇다면,

X

는 다음 여섯 전순서 집합 가운데 정확히 하나와 순서 동형이다.

공집합
한원소 집합
$\mathbb R$ (실수의 전순서 집합). 이는 $(0,1)$ 과 순서 동형이다.
$\mathbb R\sqcup\{+\infty\}$ . 이는 $(0,1]$ 과 순서 동형이다.
$\mathbb R\sqcup\{-\infty\}$ . 이는 $[0,1)$ 과 순서 동형이다.
$\bar{\mathbb R}=\mathbb R\sqcup\{+\infty,-\infty\}$ (확장된 실수). 이는 $[0,1]$ 과 순서 동형이다.

특히, 완비 분해 가능 조밀 무한 전순서 집합은 (순서 동형 아래) 확장된 실수의 전순서 집합

(\overline{\mathbb R},\le)

밖에 없다.

X

가 위 성질들을 만족시킨다고 할때, 분해 가능 공간의 정의에 의하여, 가산 조밀 집합

D\subseteq X

을 찾을 수 있으며,

D

위의 순서는 조밀 순서임을 쉽게 알 수 있다. 따라서

D

는 위와 같이 6개의 순서형 가운데 하나와 동형이며,

X

는

D

의 데데킨트 완비화와 순서 동형이다.

마지막 조건을 약화시킬 경우, 이들의 분류는 수슬린 가설에 의하여 좌우되는데, 이는 선택 공리를 추가한 체르멜로-프렝켈 집합론과 독립적인 명제이다.

어떤 전순서 집합

(X,\le)

에 대하여, 다음 네 조건이 동치이다.^[17]

$X$ 는 분해 가능 공간이며, 가산 개의 도약을 갖는다.
다음 조건을 만족시키는 가산 집합 $D\subseteq X$ 가 존재한다.
임의의 $x\in X$ 에 대하여, $x=\sup\{d\in D\colon d\le x\}$
다음 조건을 만족시키는 가산 집합 $D\subseteq X$ 가 존재한다.
임의의 $x\in X$ 에 대하여, $x=\inf\{d\in D\colon d\ge x\}$
$X$ 는 $\mathbb R$ 의 부분 집합과 순서 동형이다. 즉, 단사 단조 함수 $f\colon X\to\mathbb R$ 가 존재한다.

4. 3. 유한 집합 위의 (원)전순서

크기 3의 집합 $\{a,b,c\}$ 위에 존재할 수 있는 13개의 원전순서. 여기서 $a 는 a\lesssim b\not\lesssim a 를 뜻한다. 이 가운데 맨 밖의, 검은 색 글씨의 6개는 전순서이다. 중간의, 푸른 색 글씨의 6개는 2개의 동치류들을 갖는 원전순서이다. 가운데의, 붉은 색 글씨의 1개는 1개의 동치류를 갖는 비이산 원순서이다.$

유한 전순서 집합은 항상 정렬 집합이며, 따라서 그 크기에 따라 완전히 분류된다.

크기

n

의 유한 집합 위의 원전순서들의 수는 '''푸비니 수'''(Fubini number^영어)

F_n

이라고 한다.^[18] 크기

n

의 유한 집합 위의 전순서들의 수는 계승

n!

이다. 이들의 값은 다음과 같다.

$n$	0	1	2	3	4	5	6	7
$F_n$	1	1	3	13	75	541	4683	47293
$n!$	1	1	2	6	24	120	720	5040

단순한 셈 논증을 통해, 공집합이 아닌 유한 전순서 집합(따라서 그 부분 집합)은 최소 원소를 가짐을 확인할 수 있다. 따라서 모든 유한 전순서는 사실 정렬 순서이다. 직접 증명하거나, 모든 정렬 순서가 순서 동형인 서수임을 관찰하여, 모든 유한 전순서가 자연수를 < 로 정렬한 초기 세그먼트와 순서 동형임을 보일 수 있다. 즉, ''k''개의 원소를 가진 집합에 대한 전순서는 처음 ''k''개의 자연수와 전단사 함수를 유도한다. 따라서 순서를 존중하는 방식으로 (0 또는 1부터 시작) 유한 전순서 또는 정렬 순서를 순서 유형 ω로 자연수로 색인화하는 것이 일반적이다.

5. 예

모든 순서체는 전순서 집합이다.
정수환 $\mathbb Z$ 나 자연수의 모노이드 $\mathbb N$ 역시 전순서 집합이다. 이들 집합 가운데, 자연수의 집합을 제외한 나머지는 정렬 집합이 아니다.
원순서 집합들의 족 $(X,\lesssim)_{i\in I}$ 이 주어졌을 때, 곱집합 $\textstyle\prod_{i\in I}X_i$ 위에 원순서

:

x\lesssim y\iff\forall i\in I\colon x_i\lesssim y_i

를 줄 수 있다. 마찬가지로, 분리합집합

\textstyle\bigsqcup_{i\in I}X_I

위에 원순서

:

x\lesssim y\iff\exists i\in I\colon x\in X_i\ni y\land x\lesssim_iy

를 줄 수 있다.

전순서 집합의 임의의 부분 집합은 원래 집합의 순서를 그 부분 집합에 제한함으로써 전순서 집합이 된다.
공집합에 대한 유일한 순서는 전순서이다.
기수 또는 서수의 임의의 집합은 정렬 집합이다.
집합 X에 대해, X에서 전순서 집합으로의 단사 사상 f가 존재할 때, x₁ < x₂ ⇔ f(x₁) < f(x₂)로 X에서의 순서를 정하면, X는 전순서 집합이 된다.
잘 정렬 집합에 의해 색인된 전순서 집합족의 데카르트 곱에 대한 사전식 순서는 그 자체가 전순서이다.
일반적인 "이하" (≤) 또는 "이상" (≥) 관계에 의해 정렬된 실수 집합은 전순서 집합이다. 따라서 실수 집합의 각 부분 집합인 자연수, 정수, 유리수도 전순서 집합이다. 이들 각각은 특정 속성을 가진 전순서 집합의 유일한 (순서 동형까지) "초기 예시"임을 보여줄 수 있다. (여기서, 전순서 A는 속성에 대해 ''초기''인데, 만약 B가 그 속성을 가지면 A에서 B의 부분 집합으로의 순서 동형이 있기 때문이다):^[5]
자연수는 상한이 없는 초기 비어있지 않은 전순서 집합이다.
정수는 상한도 하한도 없는 초기 비어있지 않은 전순서 집합이다.
유리수는 실수에서 조밀한 초기 전순서 집합이다. 게다가 반사 감소 <는 유리수에 대한 조밀 순서이다.
실수는 (아래에 정의된) 순서 위상에서 연결된 초기 무제한 전순서 집합이다.
모든 ''데데킨트 완비'' 순서체는 실수와 동형이다.
표준 사전식 순서로 정렬된 알파벳의 문자(A < B < C)는 엄격한 전순서이다.
단순한 셈 논증을 통해, 공집합이 아닌 유한 전순서 집합(따라서 그 부분 집합)은 최소 원소를 가짐을 확인할 수 있다. 따라서 모든 유한 전순서는 정렬 순서이다.
모든 정렬 순서가 순서 동형인 서수임을 관찰하여, 모든 유한 전순서가 자연수를 <로 정렬한 초기 세그먼트와 순서 동형임을 보일 수 있다. 즉, ''k''개의 원소를 가진 집합에 대한 전순서는 처음 ''k''개의 자연수와 전단사 함수를 유도한다. 따라서 순서를 존중하는 방식으로 (0 또는 1부터 시작) 유한 전순서 또는 정렬 순서를 순서 유형 ω로 자연수로 색인화하는 것이 일반적이다.
실수 전체 집합 R은 일반적인 크고 작음 관계 ("<" 또는 ">")에 의해 전순서화된다. 따라서 그 부분 집합으로서, 자연수 전체 집합 N, 정수 전체 집합 Z, 유리수 전체 집합 Q 등도 전순서 집합이 된다.

N**은 상계를 갖지 않는 최소의 전순서 집합이다.
Z**는 상계도 하계도 갖지 않는 최소의 전순서 집합이다.
Q는 R** 중에서 조밀이 되는 최소의 전순서 집합이다. 여기서 말하는 조밀성은 a < b가 되는 임의의 실수 a, b에 대해, a < q < b가 되는 유리수 q가 반드시 존재한다는 것을 말한다.
R**은 순서 위상(후술)에 관해 연결이 되는 최소의 비유계 전순서 집합이다.

5. 1. 순서체

모든 순서체는 전순서 집합이다. 예를 들어, 실수체

\mathbb R

, 유리수체

\mathbb Q

등은 표준적인 순서를 부여하면 전순서 집합을 이룬다. 정수환

\mathbb Z

나 자연수의 모노이드

\mathbb N

역시 전순서 집합이다. 이들 집합 가운데, 자연수의 집합을 제외한 나머지는 정렬 집합이 아니다.

순서체는 정의에 의해 전순서 집합이다. 유리수체나 실수체가 여기에 포함된다.^[5]

5. 2. 아론샤인 직선

Aronszajn line^영어은 다음 조건들을 만족시키는 전순서 집합이다.^[19]

크기가 $\aleph_1$ 이다.
$\omega_1$ (최소 비가산 순서수)과 순서 동형인 부분 집합을 갖지 않는다.
$\omega_1^{\operatorname{op}}$ ( $\omega_1$ 의 반대 순서)와 순서 동형인 부분 집합을 갖지 않는다.
$\mathbb R$ 의 비가산 부분 집합과 순서 동형인 부분 집합을 갖지 않는다.

아론샤인 직선의 존재는 선택 공리를 추가한 체르멜로-프렝켈 집합론만으로 보일 수 있다. 아론샤인 직선은 나흐만 아론샤인(Nachman Aronszajn^pl, 1907~1980)이 도입하였다.

5. 3. 컨트리먼 직선

'''컨트리먼 직선'''(Countryman line^영어)은 다음 조건을 만족시키는 전순서 집합

(X,\le)

이다.

$X$ 의 집합의 크기는 $\aleph_1$ 이다.
임의의 양의 정수 $n$ 에 대하여, $X^n$ 은 $\aleph_0$ 개의 전순서 집합들의 분리합집합과 순서 동형이다.

컨트리먼 직선의 존재는 선택 공리를 추가한 체르멜로-프렝켈 집합론만으로 보일 수 있으며, 이는 사하론 셸라흐가 증명하였다.^[20]

6. 데카르트 곱 위의 순서

두 전순서 집합의 데카르트 곱에 대한 순서를 확장하는 방법에는 여러 가지가 있지만, 결과적인 순서는 부분 순서일 수 있다. 다음은 가능한 세 가지 순서이며, 각 순서가 다음 순서보다 강한 순서로 나열되어 있다.

사전식 순서: ('a', 'b') ≤ ('c', 'd')는 a < c 또는 (a = c 및 b ≤ d)인 경우에만 해당된다. 이는 전순서이다.
('a', 'b') ≤ ('c', 'd')는 a ≤ c 및 b ≤ d인 경우에만 해당된다(곱 순서). 이는 부분 순서이다.
('a', 'b') ≤ ('c', 'd')는 (a < c 및 b < d) 또는 (a = c 및 b = d)인 경우에만 해당된다(해당 엄격한 전순서의 직접 곱의 반사적 폐포). 이것 역시 부분 순서이다.

각 순서는 곱 순서에서 x ≤ y를 만족하는 경우, 이 관계가 사전식 순서 등에서도 유지된다는 의미에서 다음 순서를 확장한다. 이 세 가지는 두 개 이상의 집합의 데카르트 곱에 대해서도 유사하게 정의될 수 있다.

벡터 공간 '''R'''^''n''에 적용하면, 이들은 각각 순서화된 벡터 공간을 만든다.

'''R'''^''n''의 부분 집합에서 정의된 n개의 실수 변수의 실수 함수는 해당 부분 집합에 대한 엄격한 약순서 및 해당 전순서를 정의한다.

7. 관련 개념

부분 순서는 반대칭적이고, 추이적이며, 반사적이지만, 반드시 완전하지는 않은 이항 관계이다.

호환 가능한 전순서를 갖는 군은 전순서군이다.

전순서의 축약으로 (상호 정의 가능한) 비자명한 구조는 몇 개 없다. 방향을 잊으면 중간성 관계가 된다. 끝점의 위치를 잊으면 순환 순서가 된다. 두 데이터를 모두 잊으면 분리 관계가 된다.^[12]

8. 역사

분해 가능 완비 전순서 집합의 분류 정리^[21]와 가산 조밀 전순서 집합의 분류 정리^[21]는 게오르크 칸토어가 1895년에 증명하였다.

참조

_[1] 학술지 Ordering of characters and strings 1990-08-01
_[2] 학술지 Maximal Elements and Upper Bounds in Posets 1992
_[3] 문서
_[4] 문서
_[5] 문서
_[6] 서적 Theory of Relations https://www.elsevier[...] Elsevier 2000-12
_[7] 서적 Introduction to Lattices and Order Cambridge University Press
_[8] 서적 Notes on set theory Birkhäuser
_[9] 문서
_[10] 문서
_[11] 서적 Automata, Logics, and Infinite Games Springer 2002
_[12] 간행물 A survey of homogeneous structures
_[13] 서적 Naive Set Theory Nostrand
_[14] 서적 Logical Reasoning: A First Course King's College Publications
_[15] 서적 Logical Reasoning: A First Course King's College Publications
_[16] 학술지 A survey of homogeneous structures https://www.scienced[...] 2024-03-03
_[17] 저널 Separable linear orders and universality 2016
_[18] 서적 Advanced combinatorics: The art of finite and infinite expansions 1974
_[19] 서적 Discovering modern set theory II: set-theoretic tools for every mathematician http://bookstore.ams[...] 1997
_[20] 저널 Decomposing uncountable squares to countably many chains 1976-07
_[21] 저널 Beiträge zur Begründung der transfiniten Mengenlehre (Erster Artikel) http://www.digizeits[...]

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

문의하기 : help@durumis.com