정렬 원순서 집합

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

1. 개요

정렬 원순서 집합은 원순서 집합의 일종으로, 무한 열에 무한 증가 부분열이 존재하거나, 모든 반사슬이 유한 집합이며 내림 사슬 조건을 만족하는 등의 여러 동치 조건을 만족하는 집합을 의미한다. 정렬 전순서 집합, 정렬 부분 순서 집합, 정렬 집합 등이 있으며, 시뮬레이션과 순서형 개념을 통해 분석된다. 모든 집합이 정렬 전순서를 갖는다는 정렬 정리는 선택 공리, 초른 보조정리와 동치 관계에 있다. 자연수, 순서수, 유한 집합 등은 정렬 원순서 집합의 예시이며, 순서체나 약수 관계는 반례에 해당한다. 정렬 집합은 순서 위상을 부여하여 위상 공간으로 만들 수 있으며, 칸토어에 의해 개념이 도입되었고, 정렬 정리 증명을 둘러싼 역사적 논쟁이 있었다.

더 읽어볼만한 페이지

기초관계 - 정렬 원리
정렬 원리는 자연수의 부분집합이 항상 최소 원소를 갖는다는 속성으로, 수학적 귀납법과 동치이며 다양한 수학적 증명에 활용된다.
기초관계 - 전체집합
전체집합은 특정 맥락에서 고려되는 모든 객체를 포함하는 집합을 의미하나, 집합론에서는 모순을 피하기 위해 존재가 인정되지 않으며, 공리적 집합론에서는 고유 클래스 개념을 사용해 전체성을 표현한다.
순서론 - 스콧 위상
스콧 위상은 부분 순서 집합 위에 정의되는 위상으로, 하향 집합과 directed set의 상한에 대해 닫혀있는 집합을 닫힌 집합으로 정의하며, 컴퓨터 과학, 특히 프로그램 의미론에서 연속 함수의 개념을 일반화하고 프로그램의 계산 과정을 모델링하는 데 사용된다.
순서론 - 사전식 순서
사전식 순서는 정렬된 집합의 순서를 일반화하여 곱집합의 순서를 정의하는 데 사용되며, 단어 순서 정렬 방식과 유사하게 다양한 분야에 응용되는 수학적 개념이다.
집합론 - 퍼지 집합
퍼지 집합은 각 원소가 0과 1 사이의 소속도를 가지며, 소속 함수를 통해 정의되고, 여집합, 합집합, 교집합 등의 연산을 수행하며, 퍼지 논리, 퍼지 수, 엔트로피 등의 개념과 L-퍼지 집합, 직관적 퍼지 집합 등으로 확장된다.
집합론 - 무한 집합
무한 집합은 유한 집합이 아니며, 자연수보다 큰 크기를 가지고 자신의 진부분집합과 일대일 대응을 가지며, 가산 무한 집합과 비가산 무한 집합으로 나뉜다.

정렬 원순서 집합
정의
한국어	정렬 집합, 전순서 집합
영어	Well-ordered set
일본어	整列集合 (Seiretsu shūgō)
수학적 정의	모든 공집합이 아닌 부분집합이 최소 원소를 가지는 전순서 집합
대안적 정의	순서 아이소모픽이 순서수인 전순서 집합
성질
정렬 원순서 집합	well preordered set, well quasiordered set
기타 명칭	well (totally) ordered set, woset

2. 정의

원순서 집합 $(X,\lesssim)$ 에 대하여 다음 다섯 조건들이 서로 동치이며, 이를 만족시키는 원순서 집합을 '''정렬 원순서 집합'''(整列原順序集合, well preordered set^영어)이라고 한다.^[5]

임의의 무한 열 $(x_i)_{i\in\mathbb N}\subseteq X$ 에 대하여, $i 이자 x_i\lesssim x_j 인 i,j\in\mathbb N 이 존재한다.$
임의의 무한 열은 무한 증가 부분열을 갖는다. 즉, $(x_i)_{i\in\mathbb N}\subseteq X$ 에 대하여, $x_{f(0)}\lesssim x_{f(1)}\lesssim x_{f(2)}\lesssim\cdots$ 가 되는 증가 함수 $f\colon\mathbb N\to\mathbb N$ 가 존재한다.^[5]^[3]
(유한 개의 극소 원소의 존재) 임의의 부분 집합 $S\subseteq X$ 에 대하여, 만약 $S\ne\varnothing$ 이라면, $S$ 는 (하나 이상의) 극소 원소들을 가지며, $S$ 의 극소 원소들의 동치류의 수는 유한하다.
$\mathcal P(X)$ 위의 원순서 $S\lesssim^\star T\iff S\subseteq\downarrow T$ 를 정의하였을 때, 이항 관계 $S\prec^\star T\iff S\lesssim^\star T\not\lesssim^\star S$ 는 정초 관계이다.^[2] (여기서 $\downarrow$ 는 하폐포를 뜻한다.)
다음 두 조건이 성립한다.^[5]^[3]
* $X$ 속의 모든 반사슬은 유한 집합이다.
* (내림 사슬 조건) $X$ 속의 모든 감소열 $x_0\gtrsim x_1\gtrsim x_2\gtrsim\cdots$ 에 대하여, 모든 $i,j\ge N$ 에 대하여 $x_i\sim x_j$ 가 되는 $N\in\mathbb N$ 이 존재한다.

여기서

x\sim y

는

x\lesssim y\lesssim x

를 뜻한다.

정렬 원순서 집합인 부분 순서 집합을 '''정렬 부분 순서 집합'''(整列部分順序集合, well partially ordered set^영어)이라고 한다. 정렬 원순서 집합인 전순서 집합을 '''정렬 전순서 집합'''(整列全順序集合, well totally ordered set^영어) 또는 '''정렬 집합'''(well ordered set^영어)이라고 한다.

전순서 집합

(X,\le)

에 대해서 '''정렬 전순서 집합'''이 되기 위한 조건들은 다음과 같다.

임의의 열 $(x_i)_{i\in\mathbb N}\subseteq X$ 에 대하여, $i 이자 x_i\le x_j 인 i,j\in\mathbb N 이 존재한다.$
임의의 열 $(x_i)_{i\in\mathbb N}\subseteq X$ 은 증가 부분열을 갖는다.
(최소 원소의 존재) 임의의 부분 집합 $S\subseteq X$ 에 대하여, 만약 $S\ne\varnothing$ 이라면, $S$ 는 최소 원소를 갖는다.
(내림 사슬 조건) $X$ 속의 모든 감소열 $x_0\ge x_1\ge x_2\ge\cdots$ 에 대하여, 모든 $i,j\ge N$ 에 대하여 $x_i\sim x_j$ 가 되는 $N\in\mathbb N$ 이 존재한다.
집합론적 나무를 이룬다.
어떤 순서수와 순서 동형이다.

2. 1. 정렬 원순서 집합

원순서 집합

(X,\lesssim)

에 대하여 다음 다섯 조건들이 서로 동치이며, 이를 만족시키는 원순서 집합을 '''정렬 원순서 집합'''(整列原順序集合, 202, Definition 2.3/well preordered set}})이라고 한다.^[5]{{rp^영어

임의의 무한 열 $(x_i)_{i\in\mathbb N}\subseteq X$ 에 대하여, $i 이자 x_i\lesssim x_j 인 i,j\in\mathbb N 이 존재한다.$
임의의 무한 열은 무한 증가 부분열을 갖는다. 즉, $(x_i)_{i\in\mathbb N}\subseteq X$ 에 대하여, $x_{f(0)}\lesssim x_{f(1)}\lesssim x_{f(2)}\lesssim\cdots$ 가 되는 증가 함수 $f\colon\mathbb N\to\mathbb N$ 가 존재한다.^[5]^[3]
(유한 개의 극소 원소의 존재) 임의의 부분 집합 $S\subseteq X$ 에 대하여, 만약 $S\ne\varnothing$ 이라면, $S$ 는 (하나 이상의) 극소 원소들을 가지며, $S$ 의 극소 원소들의 동치류의 수는 유한하다.
$\mathcal P(X)$ 위의 원순서 $S\lesssim^\star T\iff S\subseteq\downarrow T$ 를 정의하였을 때, 이항 관계 $S\prec^\star T\iff S\lesssim^\star T\not\lesssim^\star S$ 는 정초 관계이다.^[2] (여기서 $\downarrow$ 는 하폐포를 뜻한다.)
다음 두 조건이 성립한다.^[5]^[3]
* $X$ 속의 모든 반사슬은 유한 집합이다.
* (내림 사슬 조건) $X$ 속의 모든 감소열 $x_0\gtrsim x_1\gtrsim x_2\gtrsim\cdots$ 에 대하여, 모든 $i,j\ge N$ 에 대하여 $x_i\sim x_j$ 가 되는 $N\in\mathbb N$ 이 존재한다.

여기서

x\sim y

는

x\lesssim y\lesssim x

를 뜻한다.

정렬 원순서 집합인 부분 순서 집합을 '''정렬 부분 순서 집합'''(整列部分順序集合, well partially ordered set^영어)이라고 한다. 정렬 원순서 집합인 전순서 집합을 '''정렬 전순서 집합'''(整列全順序集合, well totally ordered set^영어) 또는 '''정렬 집합'''(well ordered set^영어)이라고 한다.

전순서 집합

(X,\le)

에 대해서 '''정렬 전순서 집합'''이 되기 위한 조건들은 다음과 같다.

임의의 열 $(x_i)_{i\in\mathbb N}\subseteq X$ 에 대하여, $i 이자 x_i\le x_j 인 i,j\in\mathbb N 이 존재한다.$
임의의 열 $(x_i)_{i\in\mathbb N}\subseteq X$ 은 증가 부분열을 갖는다.
(최소 원소의 존재) 임의의 부분 집합 $S\subseteq X$ 에 대하여, 만약 $S\ne\varnothing$ 이라면, $S$ 는 최소 원소를 갖는다.
(내림 사슬 조건) $X$ 속의 모든 감소열 $x_0\ge x_1\ge x_2\ge\cdots$ 에 대하여, 모든 $i,j\ge N$ 에 대하여 $x_i\sim x_j$ 가 되는 $N\in\mathbb N$ 이 존재한다.
집합론적 나무를 이룬다.
어떤 순서수와 순서 동형이다.

2. 2. 정렬 부분 순서 집합

2. 3. 정렬 전순서 집합 (정렬 집합)

전순서 집합 중에서 정렬 원순서 집합의 조건을 만족하는 집합을 정렬 전순서 집합(well-totally-ordered set) 또는 정렬 집합(well-ordered set)이라고 한다. 모든 유한 원순서 집합은 (자명하게) 정렬 원순서 집합을 이룬다.^[5] 특히, 자연수 집합의 표준적인 전순서는 정렬 전순서이다.

보다 일반적으로, 임의의 순서수

\alpha

보다 작은 순서수들의 집합

:

\alpha=\{\beta\in\operatorname{Ord}\colon\beta<\alpha\}

는 정렬 전순서 집합이다. 모든 순서수의 고유 모임

\operatorname{Ord}

(또는 그 임의의 부분 모임)의 표준적인 전순서는 정렬 전순서이다. 선택 공리를 가정할 경우, 기수의 고유 모임의 표준적인 전순서 역시 정렬 전순서이며, 이 사실은 알레프 수의 정의의 기반을 이룬다.

순서 집합

X

가 전순서 집합일 경우, 다음 조건들은 모두 서로 동치이다.

$X$ 는 정렬 집합이다. 즉, 공집합이 아닌 임의의 부분 집합이 최소 원소를 갖는다.
$X$ 전체에서 초한 귀납법이 유효하다.
$X$ 의 원소로 구성된 임의의 엄격 단조 감소 수열은 반드시 유한한 길이로 멈춘다(단, 종속 선택 공리를 가정한다).

2. 4. 시뮬레이션

두 정렬 원순서 집합

(S,\lesssim_S)

,

(T,\lesssim_T)

사이의 시뮬레이션(simulation^영어)

f\colon S\to T

는 다음 성질들을 만족시키는 함수이다.

(증가 함수) 만약 $s,s'\in S$ 에 대하여 $s\lesssim s'$ 라면, $f(s)\lesssim f(s')$ 이다.
$f(S)\subseteq T$ 는 하집합이다. 즉, 임의의 $s\in S$ 및 $t\in T$ 에 대하여, 만약 $t\lesssim f(s)$ 라면 $f(s')=t$ 인 $s'\in S$ 가 존재한다.

정렬 전순서 집합과 시뮬레이션들의 범주는 순서수의 얇은 범주와 동치이다.

정렬 전순서의 동형은 정렬 전순서와 시뮬레이션의 범주에서의 동형이다. 이 동형에 대한 동치류를 순서형(順序型, order type^영어)이라고 한다. 순서수는 각 순서형의 표준적인 대표원을 제공한다.

3. 성질

3. 1. 함의 관계

정렬 전순서 집합은 정렬 원전순서 집합이다. 전순서 집합은 정렬 원순서 집합의 특수한 경우이며, 부분 순서 집합 역시 정렬 원순서 집합의 특수한 경우이다. 정렬 부분 순서 집합은 정렬 원순서 집합이다. 이들 사이의 관계는 다음과 같이 나타낼 수 있다.

정렬 전순서 집합	⟹				정렬 원전순서 집합
	⇘	colspan=3 \|	⇙
		전순서 집합	⇒	원전순서 집합
⇓		⇓		⇓	⇓
		부분 순서 집합	⇒	원순서 집합
	⇗	colspan=3 \|	⇖
정렬 부분 순서 집합	⟹				정렬 원순서 집합

3. 2. 정렬 전순서 집합

정렬 전순서 집합

(S,\le)

의 부분 집합

A\subset S

이 주어졌을 때,

(A,\le)

역시 정렬 전순서 집합이다.

서로 동형인 두 정렬 전순서 집합은 같은 집합의 크기를 갖는다. 반대로, 집합의 크기가 같은 두 유한 정렬 전순서 집합은 서로 동형이다. 반면, 집합의 크기가 같지만 서로 다른 무한 정렬 전순서 집합이 존재한다. 예를 들어, 순서수

\omega

에 대응하는 정렬 전순서 집합과 순서수

\omega+1

에 대응하는 정렬 전순서 집합은 서로 동형이지 않다.

3. 3. 정렬 원순서 집합

정렬 원순서 집합들의 유한 족

(X_i,\lesssim_i)_{i=1}^n

이 주어졌을 때, 분리합집합

\textstyle\bigsqcup_{i=1}^nX_i

위에 순서

:

x\lesssim y\iff\exists i\in\{1,\dots,n\}\colon(x\in X_i\land y\in X_i\land x\lesssim_iy)

를 정의하면, 이 역시 정렬 원순서 집합이다.

정렬 원순서 집합들의 유한 족

(X_i,\lesssim_i)_{i=1}^n

이 주어졌을 때, 곱집합

\textstyle\prod_{i=1}^nX_i

위에 순서

:

(x_1,x_2,\dots,x_n)\lesssim(y_i,y_2,\dots,y_n)\iff\left(\forall i\in\{1,\dots,n\}\colon x_i\lesssim y_i\right)

를 주면,

\textstyle(\prod_{i=1}^nX_i,\lesssim)

역시 정렬 원순서 집합이다. 이를 '''딕슨 보조 정리'''(Dickson’s lemma^영어)라고 한다.^[4]^[5] 이 정리는 수학적 귀납법을 통해

n=2

인 경우를 증명하면 충분하다. (

n=0

은 자명하다.)

X\times Y

속의 점렬

(x_k,y_k)_{k=0}^\infty

이 주어졌다고 할 때,

:

(x_{f(k)})_{k=0}^\infty

가

(x_k)_{k=0}^\infty

의 증가 부분열이고,

:

(y_{f(g(k))})_{k=0}^\infty

가

(y_{f(k)})_{k=0}^\infty

의 증가 부분열이라면,

:

(x_{f(g(k))},y_{f(g(k))})_{k=0}^\infty

는

(x_k,y_k)_{k=0}^\infty

의 증가 부분열이 된다.

3. 4. 정렬 정리

'''정렬 정리'''(整列定理, well-ordering theorem^영어)에 따르면, 모든 집합은 적어도 하나 이상의 정렬 전순서를 갖는다. (다만, 이 정렬 전순서는 구체적으로 명시하지 못할 수 있다.) 다시 말해, 임의의 크기를 갖는 순서수가 존재한다. 이를 통해, 임의의 집합 위에 초한 귀납법을 적용할 수 있다. 사실, 1차 논리의 체르멜로-프렝켈 집합론에서, 정렬 정리는 선택 공리 및 초른 보조정리와 서로 동치이다. 즉, 체르멜로-프렝켈 집합론의 공리들로, 이 셋 가운데 하나가 주어지면 나머지 둘을 증명할 수 있다.

폰 노이만-베르나이스-괴델 집합론이나 모스-켈리 집합론과 같은, 모임을 다루는 이론에서는 모든 모임이 정렬 전순서를 갖는지에 대하여 생각할 수 있다. ( 선택 공리를 제외한) 이들 체계에서는 다음 두 조건이 서로 동치이다.

모든 모임은 정렬 전순서를 갖는다.
(대역적 선택 공리 axiom of global choice^영어) 공집합이 아닌 집합들을 원소로 하는 모든 모임은 선택 함수를 갖는다.

4. 순서수

임의의 정렬 집합은 그 정렬 집합의 순서형이라고 불리는 단 하나의 순서수에 순서 동형이다. 순서 집합의 각 원소의 위치는 순서 집합에 의해서도 주어진다. 유한 집합의 경우, 세는 것이라는 기본적인 조작에 의해서 대상 하나하나에 (몇 번째 원소인지를 의미하는) 순서수를 할당함으로써, 특정 대상의 순서수를 구할 수 있으며, 또는 특정 순서수를 가진 대상을 구할 수도 있다. 유한 집합에서는 그 크기, 즉 그 원소의 개수를 의미하는 기수와 그 순서형인 순서수는 일치한다고 생각할 수 있다. 이것은 일상적인 의미에서의 세는 것은 1부터 시작한다고 생각하지만, 그렇게 하면 유한 집합의 각 대상에 차례로 순서수를 매겨서 마지막 원소가 되는 대상에 매겨지는 순서수는 그 집합의 기수가 된다는 의미이다.

실제로는 여기서 말하는 순서수는 순서 동형에 따라 정의되는 엄밀한 의미에서의 순서수보다 1만큼 크다는 것에 주의해야 한다. 엄밀한 의미에서의 순서수는 그 대상보다 앞에 있는 대상의 수와 같다 (또는 이것은 0부터 세기 시작하는 것에 대응한다). 그러므로 유한한 ''n''에 대해 정렬 집합의 "번째 원소"라고 말할 때, 그 문맥에서는 0부터 세기 시작했는지 1부터 세기 시작했는지가 명확해야 한다. ''β''가 초한 순서수 (무한 순서수)일 때도 "번째 원소"와 같은 표기를 할 수 있으며, 이 경우 전형적으로 0부터 센다.

무한 집합에 대해서도 그 순서형은 거기에 속하는 기수를 유일하게 결정하지만, 역은 성립하지 않으며, 같은 기수를 가진 정렬 집합으로 서로 다른 순서형을 가진 것이 무수히 존재할 수 있다. 가산 무한 집합이라 하더라도, 그 집합의 순서형으로서 가능한 것의 수는 비가산이다.

5. 도입

정렬 집합 ''X''의 임의의 원소 ''s''는, 그것이 ''X''의 최대 원소가 아닌 한, 단 하나의 후자(successor; 후계, 다음 원소, 직후 원소)를 가진다. 이것은 즉, ''s''보다 큰 ''X''의 원소 전체가 이루는 부분 집합에서의 최소 원소로서 ''s''의 후자가 결정된다는 것이다. 또한, 정렬 집합 ''X'' 중에서 위로 유계인 임의의 부분 집합은 (그 상계 전체가 이루는 ''X''의 부분 집합에 최소 원소를 취할 수 있으므로) 반드시 상한을 가진다. 또는 정렬 집합 ''X''에는, 전자(predecessor; 직전 원소)를 가지지 않는 원소가 반드시 존재한다(그것은 물론, ''X'' 전체에서의 최소 원소이다).

집합에 정렬 순서가 주어지면, 거기에서는 집합의 모든 원소에 대한 명제의 초한 귀납법을 사용한 증명을 생각할 수 있다.

자연수 전체가 이루는 집합 이 통상의 크기 관계 ""에 관하여 정렬 집합이 된다는 사실은, 일반적으로 정렬 원리라고 불린다.

(선택 공리와 동치인) 정렬 가능 정리는, 임의의 집합이 정렬 순서화 가능함을 주장하는 것이다. 정렬 가능 정리는 또한 초른의 보조 정리와 동치이다.

6. 예

6. 1. 자연수의 집합

모든 유한 원순서 집합은 정렬 원순서 집합이다.^[5] 특히, 자연수 집합의 표준적인 전순서는 정렬 전순서이다.

임의의 순서수

\alpha

보다 작은 순서수들의 집합

:

\alpha=\{\beta\in\operatorname{Ord}\colon\beta<\alpha\}

는 정렬 전순서 집합이다. 모든 순서수의 고유 모임

\operatorname{Ord}

(또는 그 임의의 부분 모임)의 표준적인 전순서는 정렬 전순서이다. 선택 공리를 가정할 경우, 기수의 고유 모임의 표준적인 전순서 역시 정렬 전순서이며, 이는 알레프 수의 정의의 기반을 이룬다.^[5]

(0을 포함하는) 자연수 전체의 집합 은 통상적인 크고 작음 관계 ≤가 정렬 순서를 부여한다. 이 정렬 집합의 순서형은 ω로 표기된다. 또한, 0이 아닌 임의의 자연수는 유일한 직전 원소를 가진다.

에서의 다른 정렬 순서로서는, 예를 들어 모든 짝수가 어떤 홀수보다 작다고 하고, 짝수끼리 또는 홀수끼리는 통상적인 크고 작음 관계를 적용하는 경우가 있다.

: 0, 2, 4, 6, 8, …, 1, 3, 5, 7, 9, …

이 순서에 관한 정렬 집합의 순서형은 ω + ω이다. 임의의 원소가 직후의 원소를 가지지만 (따라서 최대 원소는 존재하지 않음), 직전 원소를 가지지 않는 원소가 0과 1의 두 개 존재한다.^[5]

6. 2. 정수의 집합

모든 유한 원순서 집합은 정렬 원순서 집합을 이룬다.^[5] 특히, 자연수 집합의 표준적인 전순서는 정렬 전순서이다.

정수 전체의 집합 '''Z'''에 통상적인 크고 작음 관계(≤)를 부여하면, 음의 정수 집합에는 최소 원소가 존재하지 않으므로 정렬 집합이 아니다.

하지만, 다음과 같은 이항 관계 ''R''을 통해 '''Z'''를 정렬 집합으로 만들 수 있다.

두 정수 ''x'', ''y''에 대해, ''xRy''는 다음 조건 중 하나를 만족하는 것이다.

''x'' = 0
''x''는 양수이고 ''y''는 음수
''x'', ''y''가 모두 양수이고, ''x'' ≤ ''y''
''x'', ''y''가 모두 음수이고 절댓값/absolute value^영어 ''x'' ≤ 절댓값/absolute value^영어 ''y''

이 관계 ''R''에 따라 정수를 나열하면 다음과 같다.

: 0, 1, 2, 3, 4, …, −1, −2, −3, …

이 정렬 순서 ''R''에 관한 정렬 집합 '''Z'''의 순서형은 순서수 ω + ω에 순서 동형이다.

'''Z'''의 또 다른 정렬 순서의 예시는 다음과 같다.

: ''x'' ≤_'''Z''' ''y'' ⇔ 절댓값/absolute value^영어 ''x'' < 절댓값/absolute value^영어 ''y'' 이거나 [절댓값/absolute value^영어 ''x'' = 절댓값/absolute value^영어 ''y'' 이고 ''x'' ≤ ''y'']

이 관계에 따라 정수를 나열하면 다음과 같다.

: 0, −1, 1, −2, 2, −3, 3, −4, 4, …

이것은 ω를 순서형으로 하는 정렬 순서이다.

6. 3. 실수의 집합

양의 실수 전체의 집합 ${\displaystyle \mathbb {R} ^{+}}$에 일반적인 크기 관계 ≤를 고려한 것은 정렬 순서가 아니다. 예를 들어 열린 구간 (0, 1)은 최소 원소를 갖지 않는다. 한편, 선택 공리를 포함하는 집합론의 ZFC 공리계로부터, 실수 전체의 집합 ${\displaystyle \mathbb {R} }$ 위의 정렬 순서가 존재함을 보일 수 있다. 그러나, ZFC나, 일반 연속체 가설을 더한 체계 ZFC+GCH에서는, ${\displaystyle \mathbb {R} }$ 위의 정렬 순서를 정의하는 논리식은 존재하지 않는다. 다만, ${\displaystyle \mathbb {R} }$ 위의 정의 가능한 정렬 순서의 존재는 ZFC와 (상대적으로) 무모순이다. 예를 들어 ''V''=''L''는 ZFC와 (상대적으로) 무모순이며, ZFC+''V''=''L''에서는 어떤 특정 논리식이 ${\displaystyle \mathbb {R} }$ (실제로는 임의의 집합)을 정렬 순서화하는 것이 따른다.

${\displaystyle \mathbb {R} }$의 비가산 부분 집합에 일반적인 크기 관계를 넣은 것이 정렬 집합이 되지 않는다는 것은, 실수 직선 ${\displaystyle \mathbb {R} }$을 서로 교차하지 않는 구간의 합으로 분할할 때, 그러한 구간의 수가 기껏해야 가산이라는 것으로부터 알 수 있다. 가산 무한 집합이라면, 일반적인 크기 관계 ≤가 정렬 순서가 될 수도, 되지 않을 수도 있다. 정렬 순서가 되는 예로는 집합 {−2^−''n'' | 0 ≤ ''n'' < ''ω''}는 순서형/order type^영어 ''ω''를 갖는다. 집합 {−2^−''n'' − 2^{−''m''−''n''} | 0 ≤ ''m'', ''n'' < ''ω''}는 순서형 ''ω''²를 갖는다. 앞선 예에서 언급한 집합은, 이 집합에 집적점의 집합으로 포함된다. 실수 전체의 집합 ${\displaystyle \mathbb {R} }$ 안에서는 (일반적인 위상에서도 순서 위상에서도) 0도 집적점에 포함된다 (이는 집적점 전체의 집합의 집적점이기도 하다). 집합 {−2^−''n'' | 0 ≤ ''n'' < ''ω''} ∪ {1}은 순서형 ''ω'' + 1이다. 이 집합에 순서 위상을 고려하면, 1은 집적점이지만, ${\displaystyle \mathbb {R} }$에 일반적인 위상 (순서 위상과 같지만)을 넣어도 1은 집적점이 되지 않는다.

6. 4. 문자열

원순서 집합

(\Sigma,\lesssim_\Sigma)

위의 유한 문자열 집합 (클레이니 스타)

\Sigma^*

위에 '''부분 문자열 관계'''를 정의할 수 있다.

s=s_0s_1\cdots s_{m-1}

과

t=t_0t_1\cdots t_{n-1}

에 대하여,

s\ll t

는 다음 조건을 만족시키는 것을 의미한다.

:

s_i\lesssim_\Sigma t_{f(i)}

가 되는 단사 증가 함수

:

f\colon\{0,1,\dots,m-1\}\to\{0,1,\dots,n-1\}

가 존재한다. 이는 원순서이며, 만약

\lesssim_\Sigma

가 부분 순서라면 부분 문자열 관계는 부분 순서가 된다. '''히그먼 보조 정리'''(Higman’s lemma^영어)에 따르면,

(\Sigma^*,\ll)

는 정렬 원순서 집합이다.^[11]^[5]

6. 5. 그래프

(무향) 유한 그래프들의 가산 무한 집합은 그래프 마이너 관계에 대하여 원순서 집합을 이룬다. '''로버트슨-시모어 정리'''(Robertson–Seymour theorem^영어)에 따르면, 이는 정렬 원순서 집합이다.^[6]

7. 반례

순서체 $K$ (예를 들어, 유리수체나 실수체)는 정렬 전순서 집합이 될 수 없다. 모든 순서체는 $\mathbb Z$ 를 부분환으로 포함하는데, 이 경우 $\mathbb Z$ 전체는 최소 원소를 갖지 않기 때문이다. 마찬가지로, 자명환이 아닌 순서환은 항상 정렬 전순서 집합이 될 수 없다.

순서체 $K$ 에서, 음이 아닌 원소들의 전순서 집합 $K_{\ge0}$ 역시 정렬 전순서 집합이 될 수 없다. 이는 $K_{\ge0}$ 는 양의 유리수들의 집합 $\mathbb Q^+$ 을 포함하는데, 이는 최소 원소를 갖지 않기 때문이다.

양의 정수의 집합에 약수 관계 $(\mathbb Z^+,\mid)$ 를 부여하면, 이는 부분 순서 집합이지만 정렬 부분 순서 집합이 아니다. 이는 소수의 집합은 무한 반사슬을 이루기 때문이다.

8. 동치인 정식화

전순서 집합인 순서 집합 $X$ 에 대해, 다음 조건들은 모두 서로 동치이다.

$X$ 는 정렬 집합이다. 즉, 공집합이 아닌 임의의 부분 집합이 최소 원소를 갖는다.
$X$ 전체에서 초한 귀납법이 유효하다.
$X$ 의 원소로 구성된 임의의 엄격 단조 감소 수열은 반드시 유한한 길이로 멈춘다(단, 종속 선택 공리를 가정한다).

9. 순서 위상

임의의 정렬 집합은 순서 위상을 부여하여 위상 공간으로 만들 수 있다. 순서 위상과 관련하여, 이 위상 공간의 원소는 고립점과 극한점 두 종류로 나눌 수 있다.

고립점: 최소원이나 바로 앞의 원소를 갖는 원소 등이 이 종류의 점이 된다.
극한점: 유한 정렬 집합에서는 이 종류의 원소가 존재할 수 없다. 또한, 무한 정렬 집합은 극한점을 가질 수도, 갖지 않을 수도 있다. 극한점을 갖지 않는 무한 정렬 집합(예를 들어, 자연수)은 순서형 ω를 갖는다.

또한, 이 위상 공간의 부분 집합에 대해서는 다음과 같이 구분할 수 있다.

최대원을 갖는 부분 집합(즉, 그 자체로 유계인 집합): 이러한 부분 집합의 최대원은 전체 집합의 고립점이 되는 경우도 있고 극한점이 되는 경우도 있다.
그 자체는 유계가 아니지만, 전체 집합 안에서는 유계인 부분 집합: 이러한 부분 집합은 최대원을 갖지 않지만, 부분 집합에 속하지 않는 상한을 갖는다. 이 부분 집합이 공집합이 아니라면, 이 상한은 이 부분 집합의 극한점이며, 따라서 전체 집합의 극한점이기도 하다. 한편, 공집합의 경우 상한은 전체 집합에서의 최소원이다.
전체 집합에서도 유계가 아닌 부분 집합.

부분 집합이 공종((''cofinal''))이기 위한 필요충분 조건은, 그것이 전체 집합 안에서 유계가 아니거나, 그것이 전체 집합에서도 최대원이 되는 최대원을 갖는 것이다.

위상 공간으로서의 정렬 집합이, 제1 가산 공간이 되기 위한 필요충분 조건은, 그것이 ω₁ 이하의 서수를 순서형으로 갖는 것이다. 이것은 즉, 그 집합이 가산이거나, 또는 최소의 비가산 순서형을 갖는다는 것을 말하고 있다.

10. 역사

정렬 전순서 집합의 용어 및 개념은 1883년에 게오르크 칸토어가 순서수를 도입하기 위하여 정의하였다.^[7] 칸토어는 정렬 정리가 증명이 필요없을 정도로 자명한 "사고 법칙"이라고 간주했지만, 이를 증명하지 않고 공리로 가정하였다.^[8] 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다.

1904년 8월 하이델베르크 세계 수학자 대회에서 쾨니그 줄러는 정렬 정리를 반증하였다고 발표하였으나,^[8] 몇 주 뒤 펠릭스 하우스도르프가 이 "반증"의 오류를 지적하였다. 같은 해, 에른스트 체르멜로는 선택 공리를 도입하여 정렬 정리를 증명하였다.^[9]

1937년에 주로 쿠레파가 "부분 정렬 순서 집합"이라는 용어를 사용하였으나, 쿠레파는 무한 반사슬의 부재를 가정하지 않았다.^[10]^[3] 1952년에 그레이엄 히그먼은 정렬 부분 순서와 동치인 개념을 "유한 기저 성질"이라는 이름으로 도입하였고, 히그먼 보조 정리를 증명하였다.^[11]^[3] 같은 해에 에르되시 팔과 리하르트 라도 역시 "부분 정렬 순서 집합"이라는 용어를 도입하였다.^[12]^[3]

현재까지도 많은 수학자들은 정렬 정리가 직관적이지 않다고 여긴다. 그러나 이와 동치인 선택 공리는 대체로 더 직관적이라고 여겨진다. 미국의 수학자 제리 로이드 보나는 1977년에 이에 대하여 다음과 같이 농담하였다.

선택 공리는 당연히 참이고, 정렬 정리는 당연히 거짓이고, 초른 보조정리는 글쎄……?

참조

_[1] 논문 Some Applications of the Notions of Forcing and Generic Sets 1964
_[2] 저널 Better-quasi-orderings and coinduction 2003
_[3] 저널 The theory of well-quasi-ordering: a frequently discovered concept 1972-11
_[4] 저널 Finiteness of the odd perfect and primitive abundant numbers with ''n'' distinct prime factors 1913-10
_[5] 저널 What’s so special about Kruskal’s theorem and the ordinal Γ₀? A survey of some results in proof theory 1991-09-19
_[6] 저널 Graph minors XX. Wagner’s conjecture 2004-11
_[7] 저널 Ueber unendliche, lineare Punktmannichfaltigkeiten 5 http://resolver.sub.[...] 1883
_[8] 서적 Zermelo’s axiom of choice: its origins, development, and influence Springer-Verlag 1982
_[9] 저널 Beweis, daß jede Menge wohlgeordnet werden kann. (Aus einem an Herrn Hilbert gerichteten Briefe) http://resolver.sub.[...] 1904
_[10] 저널 Théorie des ensembles http://gallica.bnf.f[...] 1937-12-13
_[11] 저널 Ordering by divisibility in abstract algebras 1952
_[12] 저널 Sets having a divisor property 1952-04
_[13] 서적 Handbook of analysis and its foundations http://www.math.vand[...] Academic Press 2016-07-14

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

문의하기 : help@durumis.com