전순서 집합
전순서 집합 (totally ordered set, linearly ordered set)은 집합과 그 집합의 모든 원소 쌍에 대해 정의된 전순서 관계를 함께 묶어 부르는 말이다. 다시 말해, 집합 S와 S 위의 이항 관계 ≤가 다음 세 가지 조건을 만족하면 (S, ≤)를 전순서 집합이라고 한다.
- 반사성 (Reflexivity): 모든 a ∈ S에 대해 a ≤ a이다.
- 반대칭성 (Antisymmetry): 모든 a, b ∈ S에 대해 a ≤ b이고 b ≤ a이면 a = b이다.
- 전이성 (Transitivity): 모든 a, b, c ∈ S에 대해 a ≤ b이고 b ≤ c이면 a ≤ c이다.
- 전순서성 (Totality 또는 Completeness): 모든 a, b ∈ S에 대해 a ≤ b 또는 b ≤ a이다.
이러한 조건을 만족하는 관계 ≤를 전순서 관계 (total order, linear order)라고 한다. 전순서 관계는 집합의 모든 원소들을 '선형'으로 배열할 수 있게 해준다. 즉, 임의의 두 원소를 비교하여 어느 것이 '앞'에 있는지 결정할 수 있다.
전순서 집합의 예로는 다음과 같은 것들이 있다.
- 실수 집합 ℝ와 일반적인 부등호 관계 ≤.
- 자연수 집합 ℕ와 일반적인 부등호 관계 ≤.
- 사전식 순서가 부여된 단어들의 집합.
- 부분집합 관계 ⊆ 하에서의 집합족 (다만, 모든 집합족이 부분집합 관계에 대해 전순서 집합을 이루는 것은 아니다. 예를 들어, {a, b, c}의 모든 부분집합의 집합은 ⊆ 관계에 대해 전순서 집합이 아니다.).
전순서 집합은 수학, 컴퓨터 과학, 논리학 등 다양한 분야에서 중요한 개념으로 활용된다. 특히 정렬 알고리즘, 데이터베이스, 의사 결정 이론 등에서 그 중요성이 부각된다.