수학(mathematics)에서, 전체(total) 또는 선형 순서(linear order)는 임의의 두 원소가 비교-가능인 부분 순서(partial order)입니다. 즉, 전체 순서는 \(X\)에서 모든 \(a, b\), 및 \(c\)에 대해 다음을 만족시키는 어떤 집합 \(X\)에 대한 이항 관계(binary relation) \(\leq\)입니다:
- \(a \leq a\) (반사적(reflexive)).
- 만약 \(a \leq b\)이고 \(b \leq c\)이면 \(a \leq c\)이다 (전이적(transitive)).
- 만약 \(a \leq b\)이고 \(b \leq a\)이면 \(a = b\)이다 (반-대칭적(antisymmetric)).
- \(a \leq b\) 또는 \(b \leq a\) (강하게 연결된(strongly connected), 이전에 전체라고 했음).
전체 순서는 때때로 단순(simple), 연결(connex), 또는 완전 순서(full orders)이라고도 합니다.
전체 순서를 갖춘 집합은 전체적으로 순서화된 집합(totally ordered set)입니다; 단순 순서화된 집합(simply ordered set), 선형적으로 순서화된 집합(linearly ordered set), 및 로셋(loset)이라는 용어도 사용됩니다. 체인(chain)이라는 용어는 때때로 전체적으로 정렬된 집합의 동의어로 정의되지만, 일반적으로 주어진 부분적으로 정렬된 집합의 일종의 전체적으로 순서화된 부분집합을 참조합니다.
주어진 부분 순서를 전체 순서로 확장하는 것을 해당 부분 순서의 선형 확장(linear extension)이라고 불립니다.
Strict and non-strict total orders
집합 \(X\) 위에 엄격한 전체 순서(strict total order)는 임의의 둘의 구별되는 원소가 비교-가능인 \(X\) 위에 엄격한 부분 순서(strict partial order)입니다. 즉, 전체 순서는 \(X\)에서 모든 \(a, b\), 및 \(c\)에 대해 다음을 만족시키는 어떤 집합 \(X\) 위에 이항 관계(binary relation) \(<\)입니다.
- \(a < a\)가 아니다 (비-반사적(irreflexive)).
- 만약 \(a < b\)이고 \(b < c\)이면 \(a < c\)이다 (전이적(transitive)).
- 만약 \(a \neq b\)이면, \(a < b\) 또는 \(b < a\)이다 (연결된(connected)).
각각의 (비-엄격한) 전체 순서 \(\leq\)에 대해 결합된 관계 \(<\)가 있으며, 다음 두 가지 동등한 방법에서 정의될 수 있는 \(\leq\)와 결합된 엄격한 전체 순서(strict total order)라고 불립니다:
- 만약 \(a \leq b\)이고 \(a \neq b\)이면, \(a < b\)이다 (반사적 축소(reflexive reduction)).
- 만약 \(b \leq a\)가 아니면 \(a < b\)이다 (즉, \(<\)는 \(\leq\)의 전환(converse)의 여관계(complement)입니다).
반대로, 엄격한 전체 순서 \(<\)의 반사적 클로저(reflexive closure)는 (비-엄격한) 전체 순서입니다.
Examples
- 전체적으로 순서화된 집합 X의 임의의 부분집합(subset)은 X 위에 순서의 제한에 대해 전체적으로 순서화됩니다.
- 진 집합, ∅ 위에 고유한 순서는 전체 순서입니다.
- 세는 숫자(cardinal numbers) 또는 순서 숫자(ordinal numbers)의 임의의 집합 (보다 강하게, 이것들은 바른-순서(well-orders)입니다).
- 만약 X가 임의의 집합이고 f가 X에서 전체적으로 순서화된 집합으로의 단사 함수(injective function)이면, f가 \(x_1 \le x_2\)를 설정함으로써 전체 순서화를 유도하는 것과 \(f(x_1) \le f(x_2)\)인 것은 필요충분 조건입니다.
- 바른-순서화된 집합(well ordered set)에 의해 인덱스된(indexed), 전체 순서화된 집합의 가족의 데카르트 곱(Cartesian product) 위에 사전식 순서(lexicographical order)는 자체로 전체 순서입니다.
- 보통의 "작거나 같음" (≤) 또는 "크거나 같음"(≥) 관계에 의해 순서화된 실수(real numbers)의 집합은 전체적으로 순서화됩니다. 따라서 실수의 각 부분-집합은 자연수(natural numbers), 정수(integers), 및 유리수(rational numbers)와 같이 전체적으로 순서화됩니다. 이들 각각은 특정 속성을 갖는 전체적으로 순서화된 집합의 (순서 동형(order isomorphism)까지) 고유한 "초기 예제"로 표시될 수 있습니다 (여기서, 전체 순서 A는 만약, B가 속성을 가질 때마다, A에서 B의 부분-집합으로 순서 동형이 있으면, 속성에 대해 초기값(initial)입니다):
- 자연수는 위쪽 경계(upper bound)가 없는 초기 비-빈 전체적으로 순서화된 집합을 형성합니다.
- 정수는 위쪽 경계도 없고 아래쪽 경계(lower bound)도 없는 초기 비-빈 전체적으로 순서화된 초기 집합을 형성합니다.
- 유리수는 실수에서 조밀한(dense) 초기 전체적으로 순서화된 집합을 형성합니다. 더욱이, 반사적 축소 <는 유리수 위에 조밀한 순서(dense order)입니다.
- 실수는 순서 토폴로지(order topology, 아래에 정의됨)에서 연결된(connected) 초기 무-경계진 전체적으로 순서화된 집합을 형성합니다.
- 순서화된 필드(ordered fields)는 정의에 의해 전체적으로 순서화됩니다. 그것들은 유리수와 실수를 포함합니다. 모든 각 순서화된 필드는 유리수와 동형적인 순서화된 부분-필드를 포함합니다. 임의의 데데킨트-완비(Dedekind-complete) 순서화된 필드는 실수와 동형적입니다.
- 표준 사전 순서(dictionary order), 예를 들어, A < B < C 등에 의해 순서화된 알파벳 문자는 엄격한 전체 순서입니다.
Chains
체인(chain)이라는 용어는 때때로 전체적으로 순서화된 집합에 대한 동의어로 정의되지만, 일반적으로 유도된 순서에 대해 전체적으로 순서화된 것인 부분적으로 순서화된 집합(partially ordered set)의 부분-집합(subset)을 참조하는 데 사용됩니다. 전형적으로, 부분적으로 순서화된 집합은 포함에 의해 순서화된 주어진 집합의 부분-집합 집합이고, 그 용어는 체인의 집합의 속성을 나타내는 데 사용됩니다. 이렇게 많은 수의 중첩된 집합의 수준은 그 용어의 유용성을 설명합니다.
전체적으로 순서화된 부분-집합을 참조하는 데 체인(chain)의 사용의 공통적인 예제는 만약 부분적으로 순서화된 집합 X의 모든 각 체인이 X에서 위쪽 경계를 가지면, X가 적어도 하나의 최대 원소를 포함한다고 주장하는 조온의 보조정리(Zorn's lemma)입니다. 조온의 보조정리는 공통적으로 X가 부분-집합의 집합임과 함께 사용됩니다; 이 경우에서, 위쪽-경계는 X에서 체인의 원소들의 합집합이 X에 있음을 입증함으로써 얻습니다. 이것은 일반적으로 벡터 공간(vector space)이 하멜 기저(Hamel bases)를 가지고 링(ring)이 최대 아이디얼(maximal ideals)을 가진다는 것을 증명하기 위해 사용되는 방법입니다.
어떤 맥락에서, 고려되는 체인은 자연수에 대해 그것들의 보통의 순서 또는 그것의 반대 순서(opposite order)와 순서 동형적입니다. 이 경우에서, 체인은 단조 수열(monotone sequence)로 식별될 수 있고, 수열이 증가하는지 감소하는지에 따라 오름 체인(ascending chain) 또는 내려가는 체인(descending chain)이라고 불립니다.
부분적으로 순서화된 집합은 만약 모든 각 내려가는 체인이 결국 안정화되면 내려가는 체인 조건(descending chain condition)을 가집니다. 예를 들어, 순서가 만약 그것이 내려가는 체인 조건을 가지면 바른 토대된 것입니다. 유사하게, 오름 체인 조건(ascending chain condition)은 모든 각 오름 체인이 결국 안정화된다는 것을 의미합니다. 예를 들어, 뇌터 링(Noetherian ring)은 그것의 아이디얼(ideals)이 오름 체인 조건을 만족시키는 링입니다.
다른 문맥에서, 유한 집합(finite sets)인 체인만 고려됩니다. 이 경우에서, 종종 체인(chain)으로 축약되는 유한 체인(finite chain)에 대해 이야기합니다. 이 경우에서, 체인의 길이(length)는 체인의 연속 원소 사이의 부등식 (또는 집합 포함)의 숫자입니다; 즉, 숫자에서 사슬의 원소 중 하나를 뺀 것입니다. 따라서 한원소 집합(singleton set)은 길이 영의 체인이고, 순서 쌍(ordered pair)은 길이 일의 체인입니다. 공간의 차원(dimension)은 종종 부분-공간의 체인의 최대 길이로 정의되거나 특성화됩니다. 예를 들어, 벡터 공간의 차원(dimension of a vector space)은 선형 부분-공간(prime ideals)의 체인의 최대 길이이고, 교환 링(commutative ring)의 크룰 차원(Krull dimension)은 주요 아이디얼(prime ideals)의 체인의 최대 길이입니다.
"체인"은 부분적으로 순서화된 집합이 아닌 구조(structures)의 일부 전체적으로 순서화된 부분-집합에도 사용될 수 있습니다. 예제는 다항식의 정규 체인(regular chains)에 의해 제공됩니다. 또 다른 예제는 그래프(graph)에서 걸음(walk)에 대해 동의어로 "체인"을 사용하는 것입니다.
Further concepts
Lattice theory
전체적으로 순서화된 집합을 특정 종류의 격자(lattice)로 정의할 수 있습니다. 즉, 우리가 다음을 가진다는 격자:
\(\quad \{a\vee b, a\wedge b\} = \{a, b\}\) for all a, b.
그런 다음 a ≤ b를 쓰는 것과 \(a = a\wedge b\)인 것은 필요충분 조건입니다. 따라서 전체적으로 순서화된 집합은 분배 격자(distributive lattice)입니다.
Finite total orders
간단한 세는(counting) 논증은 임의의 비-빈 유한 전체적으로 순서화된 집합 (및 따라서 그것으로부터 임의의 비-빈 부분-집합)이 최소 원소를 가진다고 검증할 것입니다. 따라서 모든 각 유한 전체 순서는 사실 바른 순서(well order)입니다. 직접 증명에 의해 또는 모든 각 바른 순서가 순서-숫자와 순서 동형적(order isomorphic)임을 관찰함으로써, 모든 각 유한 전체 순서가 <에 의해 순서화된 자연수의 초기 세그먼트(initial segment)와 순서 동형적(order isomorphic)임을 보여줄 수 있습니다. 다시 말해, k 개의 원소를 갖는 집합 위에 전체 순서는 처음 k 개의 자연수와 전단사를 유도합니다. 따라서 (영 또는 일로 시작하는) 순서화를 존중하는 방식으로 자연수에 의한 순서 유형 유한(order type) ω를 갖는 유한 전체 순서 또는 바른 순서를 인덱싱하는 것이 공통적입니다.
Category theory
전체적으로 순서화된 집합은 부분적으로 순서화된 집합(partially ordered sets)의 카테고리(category)의 전체 부분카테고리(full subcategory)를 형성하며, 사상은 순서를 존중하는 맵입니다. 즉, a ≤ b이면 f(a) ≤ f(b)임을 만족하는 맵 f입니다.
두 개의 순서를 존중하는 두 개의 전체적으로 순서화된 집합 사이의 전단사(bijective) 맵은 이 카테고리에서 동형(isomorphism)입니다.
Order topology
임의의 전체적으로 순서화된 집합 X에 대해 열린 구간(open intervals) (a, b) = {x : a < x and x < b}, (−∞, b) = {x : x < b}, (a, ∞) = {x : a < x}, 및 (−∞, ∞) = X를 정의할 수 있습니다. 이들 열린 구간을 순서화된 집합 위에 토폴로지(topology), 순서 토폴로지(order topology)를 정의하기 위해 사용할 수 있습니다.
둘 이상의 순서가 한 집합 위에 사용되는 것일 때, 특정 순서에 의해 유도된 순서 토폴로지에 대해 이야기합니다. 예를 들어 만약 N이 자연수가, <는 보다 작다이고 >가 보다 크다이면, <에 의해 유도된 N 위에 순서 토폴로지와 >에 의해 유도된 N 위에 순서 토폴로지를 참조할 수 있습니다 (이 경우에서 그것들은 동일하게 발생하지만 일반적으로 발생하지 않을 것입니다).
전체 순서에 의해 유도된 순서 토폴로지는 유전적으로 정규(normal)인 것으로 표시될 수 있습니다.
Completeness
전체적으로 순서화된 집합은 만약 위쪽 경계(upper bound)를 가지는 모든 각 비-빈 부분-집합이 최소 위쪽 경계(least upper bound)를 가지면 완비(complete)라고 말합니다. 예를 들어, 실수 집합 R은 완비이지만 유리수 집합 Q는 완비가 아닙니다. 다시 말해서, 완비성(completeness)의 다양한 개념 ("전체(total)"와 혼동하지 말 것)은 제한(restrictions)으로 이월하지 않습니다. 예를 들어, 실수에 걸쳐 관계 ≤의 속성은 R에서 위쪽 경계를 갖는 R의 모든 각 비-빈(non-empty) 부분-집합 S가 R에서 최소 위쪽 경계 (또한 상한이라고도 함)을 가진다는 것입니다. 어쨌든, 유리수에 대해 이 상한은 반드시 유리할 필요는 없으므로, 같은 속성은 유리수로의 관계 ≤의 제한을 유지하지 않습니다.
순서 토폴로지의 속성을 X의 완비성과 관련된 여러 결과가 있습니다:
- 만약 X 위에 순서 토폴로지가 연결된 것이며, X는 완비입니다.
- X가 순서 토폴로지 아래에서 연결된 것과 그것이 완비이고 X에서 틈이 없는 것은 필요충분 조건입니다 (틈은 어떤 c도 a < c < b를 만족시키지 못함을 만족하는 a < b를 갖는 X에서 두 점 a와 b입니다.)
- X가 완비인 것과 순서 토폴로지에서 닫혀 있는 모든 각 경계진 집합이 컴팩트인 것은 필요충분 조건입니다.
완비 격자(complete lattice)인 전체적으로 순서화된 집합 (그것의 순서 토폴로지와 함께)은 컴팩트(compact)입니다. 예제는 실수의 닫힌 구간, 예를 들어 단위 구간(unit interval) [0,1], 및 아핀적으로 확장된 실수 시스템(affinely extended real number system, 확장된 실수 직선)입니다. 이들 예제 사이에는 순서-보존하는 위상-동형(homeomorphisms)이 있습니다.
Sums of orders
임의의 두 개의 서로소 전체 차수 \((A_1,\le_1)\)와 \((A_2,\le_2)\)에 대해, 집합 \(A_1\cup A_2\) 위에 자연스러운 순서 \(\le_+\)가 있으며, 이는 두 순서의 합 또는 때때로 단지 \(A_1+A_2\)라고 불립니다:
\(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\) 위에 자연스러운 전체 순서는 다음에 의해 정의됩니다:
\(x,y\in \bigcup_{i\in I} A_i\)에 대해, \(x\le y\)는 만약 다음 중 하나이면 유지됩니다:
- \( x\le_i y \)를 갖는 일부 \(i\in I\)가 있습니다
- \( x\in A_i\), \( y\in A_j\)를 갖는 \(I\)에서 일부 \(i<j\)가 있습니다
Orders on the Cartesian product of totally ordered sets
증가하는 강도의 순서, 즉 감소하는 쌍의 집합의 순서에서, 두 개의 전체적으로 순서화된 집합의 데카르트 곱(Cartesian product) 위에 가능한 순서 3개는 다음입니다:
- 사전식 순서(Lexicographical order): (a,b) ≤ (c,d)인 것과 a < c 또는 (a = c 그리고 b ≤ d)인 것은 필요충분 조건입니다. 이것은 전체 순서입니다.
- (a,b) ≤ (c,d)인 것과 a ≤ c 그리고 b ≤ d (곱 순서(product order))인 것은 필요충분 조건입니다. 이것은 부분 순서입니다.
- (a,b) ≤ (c,d)인 것과 (a < c 그리고 b < d) 또는 (a = c 그리고 b = d) (대응하는 엄격한 전체 순서의 직접 곱(direct product)의 반사적 클로저)인 것은 필요충분 조건입니다. 이것은 역시 부분 순서입니다.
모든 셋은 둘 보다 많은 집합의 데카르트 곱에 대해 유사하게 정의될 수 있습니다.
벡터 공간(vector space) \(\mathbf{R}^n\)에 적용된, 이들의 각각은 그것을 순서화된 벡터 공간(ordered vector space)으로 만듭니다.
역시 부분적으로 순서화된 집합의 예제(examples of partially ordered sets)를 참조하십시오.
\(\mathbf{R}^n\)의 부분-집합 위에 정의된 n 개의 실수 변수의 실수 함수는 해당 부분-집합 위에 엄격하게 약한 순서와 대응하는 전체 이전-순서를 정의합니다.
Related structures
반대칭적, 전이적, 및 반사적 (그러나 반드시 전체는 아님)인 이항 관계는 부분 순서(partial order)입니다.
호환-가능 전체 순서를 갖는 그룹(group)은 전체적으로 순서화된 그룹(totally ordered group)입니다.
전체 순서의 감소(로 서로 정의할 수 있는)인 몇 가지 비-자명한 구조가 있습니다. 방향을 잊어버리면 사이성 관계(betweenness relation)가 발생합니다. 끝의 위치를 잊어버리면 순환 순서(cyclic order)가 발생합니다. 두 데이터를 모두 잊어버리면 분리 관계(separation relation)가 발생합니다.
See also
References
- Garrett Birkhoff (1967). Lattice Theory. Colloquium Publications. Vol. 25. Providence: Am. Math. Soc.
- Brian A. Davey; Hilary Ann Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN 89009753.
- Fuchs, L (1963). Partially Ordered Algebraic Systems. Pergamon Press.
- George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co. ISBN 0-7167-0442-0
- John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988. ISBN 0-486-65676-4
- Rosenstein, Joseph G. (1982). Linear orderings. New York: Academic Press.
- Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer-Verlag. ISBN 978-3-642-77970-1.
External links
- "Totally ordered set", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
