Well-order

Transitive binary relations

	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
			Total, Semiconnex					Anti- reflexive
Equivalence relation	Y	✗	✗	✗	✗	✗	Y	✗	✗
Preorder (Quasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Partial order	✗	Y	✗	✗	✗	✗	Y	✗	✗
Total preorder	✗	✗	Y	✗	✗	✗	Y	✗	✗
Total order	✗	Y	Y	✗	✗	✗	Y	✗	✗
Prewellordering	✗	✗	Y	Y	✗	✗	Y	✗	✗
Well-quasi-ordering	✗	✗	✗	Y	✗	✗	Y	✗	✗
Well-ordering	✗	Y	Y	Y	✗	✗	Y	✗	✗
Lattice	✗	Y	✗	✗	Y	Y	Y	✗	✗
Join-semilattice	✗	Y	✗	✗	Y	✗	Y	✗	✗
Meet-semilattice	✗	Y	✗	✗	✗	Y	Y	✗	✗
Strict partial order	✗	✗	✗	✗	✗	✗	✗	Y	Y
Strict weak order	✗	✗	✗	✗	✗	✗	✗	Y	Y
Strict total order	✗	✗	Y	✗	✗	✗	✗	Y	Y
	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
Definitions, for all $a,b$ and $S\neq \varnothing :$	${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$	${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$	${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$	${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$	$aRa$	${\text{not }}aRa$	${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$

indicates that the column's property is required by the definition of the row's term (at the very left). For example, the definition of an equivalence relation requires it to be symmetric. ✗ indicates that the property may, or may not hold. All definitions tacitly require the homogeneous relation

R

be transitive: for all

a,b,c,

if

aRb

and

bRc

then

aRc,

and there are additional properties that a homogeneous relation may satisfy.

수학에서, 집합(set) S에 대한 바른-순서(well-order:정렬) (또는 바른-순서화(well-ordering) 또는 바른-순서 관계(well-order relation))는 S의 모든 비어있지 않은(non-empty:비-공) 부분 집합(subset)이 이런 순서화에서 최소 원소(least element)를 가지는 속성과 함께 S에 대한 전체 순서(total order:전순서)입니다. 집합 '바른-순서 관계와 함께 집합 S는 바른-순서화된 집합(well-ordered set)이라고 불립니다. 일부 학술 기사 및 교재에서, 이러한 용어가 wellorder, wellordered, 그리고 wellordering 또는 well order, well ordered, 및 well ordering으로 대신 쓰입니다.

모든 비어 있지 않은 바른-순서화된 집합은 최소 원소를 가집니다. 가능한 가장 큰 원소(greatest element:최대 원소)를 제외하고, 바른-순서화된 집합의 모든 원소 s는 고유한 후임 원소 (다음 원소), 즉 s보다 큰 모든 원소의 부분 집합의 최소 원소를 가집니다. 전임이 없는 최소 원소 이외의 원소가 있을 수 있습니다 (예를 들어 아래의 자연수(Natural numbers)를 참조하십시오). 바른-순서화된 집합 S에서, 상한을 가진 모든 부분 집합 T는 최소 위쪽 경계(least upper bound), 즉 S에서 T의 모든 상한의 부분 집합의 최소 원소를 가집니다.

만약 ≤ 가 비-엄격한(non-strict:비-절대) 바른 순서화이면, < 는 엄격한 바른 순서화입니다. 관계가 엄격한 바른 순서화인 것과 그것이 바른-토대(well-founded:정초) 엄격한 전체 순서(strict total order:절대 전순서)인 것은 필요충분 조건입니다. 엄격한 및 비-엄격한 바른 순서 사이의 구분은 쉽게 상호-전환될 수 있기 때문에 종종 무시됩니다.

모든 바른-순서화된 집합은, 바른-순서화된 집합의 순서 유형(order type)이라고 불리는, 고유한 순서-숫자(ordinal number)에 대한 고유한 순서 동형(order isomorphic)입니다. 선택의 공리(axiom of choice)와 동등한, 바른-순서화 정리(well-ordering theorem)는 모든 집합이 바른 순서화될 수 있다고 말합니다. 만약 집합이 바른 순서화되면 (또는 심지어 그것이 바른-토대 관계(well-founded relation)를 단지 인정할지라도), 초월유한 귀납법(transfinite induction)의 증명 기법은, 주어진 명제가 집합의 모든 원소에 대해 사실임을 입증하기 위해서 사용될 수 있습니다.

자연수가 보통 덜한 관계에 의해 바른 순서화된 것이라는 관찰은 (자연수에 대해) 바른-순서화 원리(well-ordering principle)라고 공통적으로 불립니다.

Ordinal numbers

모든 각 바른-순서화된 집합은 바른-순서화된 집합의 순서 유형(order type)이라고 불리는 고유한 순서 숫자(ordinal number)에 대해 고유하게 순서 동형적(order isomorphic)입니다. 순서화된 집합 내 각 원소의 위치는 역시 순서 숫자에 의해 제공됩니다. 유한 집합의 경우에서, 특정한 대상의 순서 숫자를 찾거나, 특정한 순서 숫자를 갖는 대상을 찾기 위한 세는 것(counting)의 기본 연산은 대상에 순서 숫자를 하나씩 할당하는 것에 해당합니다. 유한 집합의 크기 (원소의 개수, 세는 숫자(cardinal number))는 순서 유형과 같습니다. 일상적인 의미에서 셈은 전형적으로 하나에서 시작하므로, 각 대상에 해당 대상을 마지막 원소로 갖는 초기 세그먼트의 크기를 할당합니다. 이들 숫자는 동형 순서에 따른 형식적 순서 숫자보다 하나 더 많다는 점에 유의해야 하는데, 왜냐하면 이것들은 이전 대상의 숫자 (0부터 세는 것에 해당)와 같기 때문입니다. 따라서 유한 n에 대해, 바른-순서화된 집합의 "n-번째 원소"라는 표현은 이것이 0부터 계산되는지 아니면 1부터 계산되는지를 알기 위한 문맥을 요구합니다. β가 무한 순서 숫자일 수도 있는 "β-번째 원소" 표기법에서, 그것은 전형적으로 0부터 셀 것입니다.

무한 집합에 대해 순서 유형이 카디널리티(cardinality)를 결정하지만, 그 반대는 아닙니다: 특정 카디널리티의 바른-순서화된 집합은 다양한 순서 유형을 가질 수 있으며, 간단한 예제에 대해 섹션 #Natural numbers을 참조하십시오. 셀-수-있는 무한(countably infinite) 집합에 대해, 가능한 순서 유형의 집합은 심지어 셀-수-없는 것입니다.

Examples and counterexamples

Natural numbers

자연수(natural number)의 표준 순서화 ≤는 바른 순서화되고 모든 각 비-영 자연수는 고유한 직전수를 가진다는 추가 속성이 있습니다.

자연수의 또 다른 바른 순서화는 모든 짝수가 모든 홀수보다 작음을 정의함으로써 주어지고, 보통의 순서화는 짝수와 확률 내에서 적용됩니다:

0 2 4 6 8 ... 1 3 5 7 9 ...

이것은 ω + ω 순서 유형의 바른-순서화된 집합입니다. 모든 각 원소는 다음수를 가집니다 (가장 큰 원소는 없습니다). 두 원소: 0과 1은 직전수가 없습니다.

Integers

자연수(natural number)의 표준 순서화 ≤와 달리, 정수(integer)의 표준 순서화 ≤는 바른 순서화가 아닌데, 왜냐하면, 예를 들어, 음의(negative) 정수 집합은 최소 원소를 포함하고 있지 않기 때문입니다.

다음 관계 R은 정수의 바른 순서화의 예제입니다: x R y와 다음 조건 중 하나가 유지되는 것은 필요충분(iff) 조건입니다:

x = 0
x는 양수이고, y는 음수입니다.
x와 y는 둘 다 양수이고, x ≤ y입니다.
x와 y는 둘 다 음수이고, |x| ≤ |y|입니다.

이 관계 R은 다음처럼 시각화될 수 있습니다:

0 1 2 3 4 ... −1 −2 −3 ...

R은 순서 숫자(ordinal number) ω + ω에 동형적입니다.

정수를 바른 순서화하기 위한 또 다른 관계는 다음 정의입니다: x ≤_z y인 것과 (|x| < |y| 또는 (|x| = |y| 및 x ≤ y))인 것은 필요충분 조건입니다. 이 바른 순서는 다음과 같이 시각화될 수 있습니다:

0 −1 1 −2 2 −3 3 −4 4 ...

이것은 순서 유형(order type) ω를 가집니다.

Reals

임의의 실수 구간(real interval)의 표준 순서화 ≤는 바른 순서화가 아닌데, 왜냐하면, 예를 들어, 열린 구간(open interval) (0, 1) ⊆ [0,1]은 최소 요소를 포함하지 않기 때문입니다. 집합 이론의 ZFC 공리 (선택의 공리(axiom of choice) 포함)에서, 우리는 실수의 바른 순서가 있음을 보일 수 있습니다. 역시 Wacław Sierpiński는 ZF + GCH (일반화된 연속체 가설(generalized continuum hypothesis))가 선택의 공리 및 따라서 실수의 바른 순서를 의미함을 입증했습니다. 그럼에도 불구하고, ZFC+GCH 공리 단독으로 실수의 정의-가능한 (공식에 의해) 바른 순서의 존재를 입증하기 위한 것이 충분하지 않다는 것을 보여줄 수 있습니다.^[1] 어쨌든 실수의 정의-가능한 바른 순서가 존재한다는 것은 ZFC와 일치합니다–예를 들어, V=L인 ZFC와 일치하고, 특정 공식이 실수, 또는 실제로 임의의 집합을 바른 순서화하는 것이 ZFC+V=L에서 비롯됩니다.

표준 순서가 ≤를 갖는 실수의 셀-수-없는 부분집합은 바른 순서가 될 수 없습니다: X가 ≤에 의해 바른 순서화된 R의 부분집합이라고 가정합니다. X에서 각 x에 대해, s(x)를 X에 대한 ≤ 순서화에서 x의 다음수로 놓습니다 (x가 X의 마지막 원소가 아닌 한). A = { (x, s(x)) | x ∈ X }를 그것의 원소가 비-빈이고 서로소 구간이라고 놓습니다. 그러한 각 구간은 적어도 하나의 유리수를 포함하고 있으므로, A에서 Q로 단사 함수(injective function)가 있습니다. X에서 A로의 단사가 있습니다 (나중에 영으로 매핑될 수 있는 아마도 X의 마지막 원소는 제외). 그리고 Q에서 자연수로의 단사가 있다는 것은 잘 알려져 있습니다 (영에 도달하지 않도록 선택될 수 있습니다). 따라서 X에서 자연수로의 단사가 있으며 이것은 X가 셀-수-있음을 의미합니다. 다른 한편으로, 실수의 셀-수-있는 무한 부분집합은 표준 "≤"을 갖는 바른 순서일 수도 있고 아닐 수도 있습니다. 예를 들어,

자연수는 표준 순서화 ≤ 아래에서 바른 순서입니다.
집합 {1/n : n =1,2,3,...}은 최소 원소를 가지지 않고 따라서 표준 순서화 ≤ 아래에서 바른 순서가 아닙니다.

바른 순서의 예제:

숫자의 집합 { − 2⁻ⁿ | 0 ≤ n < ω }은 순서 유형 ω를 가집니다.
숫자의 집합 { − 2⁻ⁿ − 2^−m−n | 0 ≤ m,n < ω }은 순서 유형 ω²을 가집니다. 이전 집합은 집합 내에 극한 점(limit point)의 집합입니다. 실수의 집합 내에, 보통 토폴로지 또는 순서 토폴로지에서, 0은 역시 집합의 극한 점입니다. 그것은 역시 극한 점의 집합의 극한 점입니다.
숫자의 집합 { − 2⁻ⁿ | 0 ≤ n < ω } ∪ { 1 }은 순서 유형 ω + 1을 가집니다. 이 집합의 순서 토폴로지(order topology) 내에, 1은 집합의 극한 점입니다. 실수의 보통 토폴로지 (또는 동등하게, 순서 토폴로지)에서는 그렇지 않습니다.

Equivalent formulations

만약 집합이 전체적으로 순서화(totally ordered)되었으면, 다음은 서로 동등합니다:

집합이 바른 순서화되었습니다. 즉, 모든 각 비-빈 부분집합은 최소 원소를 가집니다.
초월유한 귀납법(Transfinite induction)은 전체 순서화된 집합에 대해 작동합니다.
집합의 원소의 모든 각 엄격하게 감소하는 수열은 반드시 오직 유한하게 많은 단계 후에 종료되어야 합니다 (종속 선택의 공리(axiom of dependent choice)를 가정합니다).
모든 각 부분-순서화는 초기 세그먼트에 동형적입니다.

Order topology

모든 각 바른-순서화된 집합은 순서 토폴로지(order topology)를 부여함으로써 토폴로지 공간(topological space)으로 만들 수 있습니다.

이 토폴로지와 관련하여 두 가지 종류의 원소가 있을 수 있습니다:

고립된 점(isolated point) — 이것들은 최솟값과 직전수를 갖는 원소입니다.
극한 점(limit point) — 이 유형은 유한 집합에서 발생하지 않고, 무한 집합에서 발생하거나 발생하지 않을 수 있습니다; 극한 점없이 무한 집합은 순서 유형 ω, 예를 들어 N의 집합입니다.

부분집합에 대해 우리는 다음을 구별할 수 있습니다:

최솟값을 갖는 부분집합 (즉, 자체에 의해 경계진(bounded) 부분집합); 이것은 고립된 점 또는 전체 집합의 극한 점이 될 수 있습니다; 후자의 경우에서, 그것은 역시 부분집합의 극한 점일 수도 있고 아닐 수도 있습니다.
자체에 의해 경계지지 않았지만 전체 집합에서 경계진 부분집합; 그것들은 최솟값을 가지지 않지만, 부분집합 밖에 상한을 가집니다; 만약 부분집합은 비-빈이면 이 상한은 부분집합의 극한 점이고 따라서 역시 전체 집합의 극한 점입니다; 만약 부분집합이 빈 것이면 이 상한은 전체 집합의 최솟값입니다.
전체 집합에서 경계지지 않은 부분집합.

부분 집합은 전체 집합에서 공끝(cofinal)인 것과 그것이 전체 집합에서 경계지지 않았거나 그것이 역시 전체 집합의 최댓값인 최댓값을 가지는 것은 필요충분 조건입니다.

토폴로지적 공간으로서 바른-순서화된 집합이 첫 번째-셀-수-있는 공간(first-countable space)인 것과 그것이 순서 유형이 ω₁ (오메가-일)보다 작거나 같은 것은 필요충분 조건, 즉, 그 집합이 셀-수-있거나(countable) 가장 작은 셀-수-없는(uncountable) 순서 유형인 것은 필요충분 조건입니다.

References

^ Feferman, S. (1964). "Some Applications of the Notions of Forcing and Generic Sets". Fundamenta Mathematicae. 56 (3): 325–345. doi:10.4064/fm-56-3-325-345.

Folland, Gerald B. (1999). Real Analysis: Modern Techniques and Their Applications. Pure and applied mathematics (2nd ed.). Wiley. pp. 4–6, 9. ISBN 978-0-471-31716-6.

[1] Feferman, S. (1964). "Some Applications of the Notions of Forcing and Generic Sets". Fundamenta Mathematicae. 56 (3): 325–345. doi:10.4064/fm-56-3-325-345.

[1]