최근 수정 시각 : 2024-08-25 17:32:38

순서 관계

수학기초론
Foundations of Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		다루는 대상과 주요 토픽
수리논리학 논리 · 논증{ 귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{ 증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론
집합론 집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한 · 모임
범주론 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리( 괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리
기타
예비사항( 약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학
틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 }}}}}}}}}



1. 개요2. 준순서
2.1. 부분순서
2.1.1. 순부분순서
3. 준전순서
3.1. 전순서
4. 정렬 순서5. 나무 순서6. 용어7. 예시8. 순서동형
8.1. 재미있는 결과

1. 개요

順 序 關 係 / Order Relation

순서 관계는 수학에서의 관계의 일종이다. 보통 어떤 관계를 순서 관계라고 보는 범위는 반사성과 추이성을, 또는 비반사성과 추이성 만족시키는 것이다. 전자인 순서 관계를 처음에 소개할 '준순서'라고 부르기도 한다. 집합론에서 관계를 나타낼 때 보통 기호로 [math( R )]이나 [math( f )]같은 문자들을 사용하는 것과 달리, 순서 관계는 관례적으로 [math( \leq )]나 [math( < )]같은 기호들을 사용한다. 또는 구부러진 기호 [math( \preceq )]나 [math( \prec )]를 사용하는 경우도 적지 않다. 이는 특히 아주 일반적인 순서인 '준순서'같은 순서들을 표기할 때 쓰이는 경우가 많다.

또한 집합 [math( X )]위의 순서 관계 [math( \leq )]가 주어지면 [math( (X , \leq) )]를 순서 집합(Ordered set)이라고 한다.

2. 준순서

집합 [math(A)]에서 다음 두 조건을 만족하는 이항 관계 [math(\leq)][1]를 준순서(quasi-order) 혹은 원순서(preorder)라 한다.
  1. [math(\forall x \in A \,(x \le x))] (반사관계)
  2. [math(\forall x, y, z \in A \,((x \le y \wedge y \le z) \to x \leq z))] (추이관계)

일반적으로 순서관계라고 하면 준순서가 아닌, 아래의 부분순서 관계를 뜻한다.

2.1. 부분순서

집합 [math(A)]에서 다음 세 조건을 만족하는 이항 관계 [math(\leq)]를 부분 순서(partial order)라고 하고 [math(\left(A, \leq \right))]를 부분 순서 집합(partially ordered set, poset)이라고 한다:
  1. [math(\forall x \in A \left(x\leq x \right))] (반사관계)
  2. [math(\forall x, y \in A \left(\left(x\leq y \wedge y\leq x \right) \to x = y \right))] (반대칭관계)
  3. [math(\forall x, y, z \in A ((x\leq y \wedge y\leq z) \to x\leq z))] (추이관계)

부분순서가 주어진 유한 집합에 대해 하세 다이어그램이라는 그래프로 나타내는 방법이 있다.

2.1.1. 순부분순서

집합 [math(A)]에서 정의된 이항 관계 [math(<)]가 다음을 만족할 때, 이를 A의 순부분순서(strict partial order)라고 한다:
  1. [math(\forall x \in A \left(\neg(x<x)\right))] (비반사관계)
  2. [math(\forall x, y, z \in A ((x<y \wedge y<z) \to x<z))] (추이관계)

사실상 순부분순서와 부분순서는 거의 같은 것이다. 즉, <를 정의하면 [math(\le)]를 자연스럽게 정의할 수 있고, 반대도 마찬가지다.
[math( \left(x<y\right) \overset{\mathrm{def}}{\Longleftrightarrow} \left( x\leq y \wedge x\neq y \right))]

3. 준전순서

집합 [math(A)]에서의 이항 관계 [math(\leq)]가 다음을 만족하면, 이를 준전순서 또는 원전순서(pretotal order)라 하고, [math(\left(A, \leq \right))]를 준전순서 집합 또는 원전순서 집합(pretotally ordered set)이라 한다:
  1. [math(\forall x, y \in A \left(x\leq y \lor y \leq x \right))] (항상 비교 가능)
  2. [math(\forall x, y \in A \left(\left(x\leq y \wedge y\leq x \right) \to x = y \right))] (반사관계)
  3. [math(\forall x, y, z \in A ((x\leq y \wedge y\leq z) \to x\leq z))] (추이관계)

조건 2.와 3.을 만족하므로 앞의 준순서 관계이면서 임의의 두 원소가 항상 비교 가능한 순서이다.

3.1. 전순서

집합 [math(A)]에서의 이항 관계 [math(\leq)]가 다음을 만족하면, 이를 전순서(total order) 또는 선형순서(linear order)라 하고, [math(\left(A, \leq \right))]를 전순서 집합(totally ordered set, toset) 또는 선형 순서 집합(linearly ordered set)이라 한다:
  1. [math(\forall x, y \in A \left(x\leq y \lor y \leq x \right))] (항상 비교 가능)
  2. [math(\forall x, y \in A \left(\left(x\leq y \wedge y\leq x \right) \to x = y \right))] (반대칭관계)
  3. [math(\forall x, y, z \in A \,((x \le y \wedge y \le z) \to x \leq z))] (추이관계)

앞의 모든 순서들에게 있던 조건인 반사관계가 빠진 이유는 조건 1.로부터 아래와 같이 유도할 수 있기 때문이다.

[math(\begin{aligned}
\forall x&\in A(x \leq x \lor x \leq x) \\
\therefore\forall x&\in A(x \leq x) \\
\end{aligned})]

따라서 이것을 포함하여 전순서의 조건을 나열하면, (항상 비교 가능), (반사관계, 반대칭관계, 추이관계) 만족하는 순서가 된다. 이를 통해 전순서는 준전순서이면서 부분 순서인 순서임을 알 수 있다.

전순서는 부분 순서이기도 하므로 전순서의 하세 다이어그램을 그려보면, 원소들을 일렬로 배치하는 모양을 생각할 수 있다. 이런 점에서 부분순서 집합의 부분집합인 전순서 집합을 사슬(chain)이라고 부르기도 한다. 이와 비슷하게 부분순서 집합을 그물이라 부르는 경우도 있다.

4. 정렬 순서

전순서 집합 [math(A)]의 임의의 부분집합이 최소원소를 가지면, [math(A)]를 정렬집합(well-ordered set)이라 하고, 그 전순서를 정렬 순서(well-ordering)이라 한다.

정렬 집합은 어떤 서수(ordinal)에 대해 순서 동형이다. 즉, [math(ON)]을 서수의 고유 모임이라고 하면, 임의의 정렬 집합 [math(A)]에 대하여 [math(x,\:y\in A,\:\:x<y\iff f(x)<f(y))]인 전단사함수 [math(f:A\to\alpha)]가 존재하는 서수 [math(\alpha\in ON)]가 존재한다.

선택공리를 가정하면, 임의의 집합에 정렬순서를 줄 수 있는게 보장된다. 이를 정렬 정리(well-ordering theorem)라고 하는데, ZF 하에서 선택공리와 동치인 대표적인 명제이다.

5. 나무 순서

파일:상세 내용 아이콘.svg   자세한 내용은 나무(순서론) 문서
를
의 번 문단을
의 부분을
참고하십시오.

6. 용어

  • 비교 가능성(comparability)
    부분순서집합 [math(\left(A, \leq \right))]가 주어졌을 때, 집합 [math(A)]의 두 원소 [math(a, b)]가 [math(a \leq b)]이거나 [math(b \leq a)]이면 a와 b는 비교 가능하다(comparable)고 하며, 그렇지 않으면 a와 b는 비교 불가능하다(incomparable)고 한다.
  • 극대 원소, 극소 원소
    부분순서집합 [math(\left(A, \leq \right))]가 주어졌을 때, 집합 [math(A)]의 모든 원소 [math(x)]에 대하여 [math(M \leq x \implies x=M)]을 만족시키는 집합 [math(A)]의 원소 [math(M)]을 집합 [math(A)]의 극대 원소(Maximal element)라고 하며, 반대로 집합 [math(A)]의 모든 원소 [math(x)]에 대하여 [math(x \leq m \implies x=m)]을 만족시키는 집합 [math(A)]의 원소 [math(m)]을 집합 [math(A)]의 극소 원소(Minimal element)라고 한다.
    극대, 극소 원소는 한 부분순서집합 내에서 여러 개가 존재할 수도 있고, 아예 존재하지 않을 수도 있다.
  • 최대 원소, 최소 원소
    부분순서집합 [math(\left(A, \leq \right))]가 주어졌을 때, 집합 [math(A)]의 모든 원소 [math(x)]에 대하여 [math(x \leq M)]을 만족시키는 집합 [math(A)]의 원소 [math(M)]을 집합 [math(A)]의 최대 원소(Greatest element)라고 하며, 반대로 집합 [math(A)]의 모든 원소 [math(x)]에 대하여 [math(m \leq x)]를 만족시키는 집합 [math(A)]의 원소 [math(m)]을 집합 [math(A)]의 최소 원소(Least element)라고 한다.
    최대, 최소 원소의 개념의 핵심은 부분순서집합의 모든 원소가 그 원소에 대하여 비교 가능해야 한다는 것이다. 만약 비교 가능하지 않은 원소가 하나라도 존재한다면 최대, 최소 원소가 될 수 없다. 최대, 최소 원소는 아예 존재하지 않을 수도 있지만, 한 부분순서집합 내에서 둘 이상 존재할 수 없다. 또한 모든 최대, 최소 원소는 각각 극대, 극소 원소가 된다.
    한편 모든 유한한 전순서관계는 최대 원소와 최소 원소를 갖지만 어떤 부분순서집합이 최대, 최소 원소를 갖는다고 해서 반드시 전순서집합이 되는 것은 아니다. 왜냐하면 최대, 최소 원소를 제외한 다른 원소들 사이에 비교 가능하지 않은 원소의 쌍이 존재할 수 있기 때문이다.
  • 상계, 하계, 상한, 하한
    실수 체계에서의 정의와 유사하다. 부분순서집합 [math(\left(A, \leq \right))]와 집합 [math(A)]의 부분집합 [math(E)]가 주어졌을 때, 집합 [math(E)]의 모든 원소 [math(x)]에 대하여 [math(x \leq M)]을 만족시키는 집합 [math(A)]의 원소 [math(M)]을 집합 [math(E)]의 상계(Upper Bound)라고 하며, 반대로 집합 [math(E)]의 모든 원소 [math(x)]에 대하여 [math(m \leq x)]를 만족시키는 집합 [math(A)]의 원소 [math(m)]을 집합 [math(A)]의 하계(Lower Bound)라고 한다. 집합 [math(E)]의 상계 집합의 최소 원소를 집합 [math(E)]의 상한(Supremum) 또는 최소 상계(Least Upper Bound)라 하고, 하계 집합의 최대 원소를 하한(Infimum) 또는 최대 하계(Greatest Lower Bound)라 한다.
    실수 집합의 경우 완비성 공리(Completeness Axiom)에 의해서 상계(하계)를 가지면 상한(하한)을 반드시 가졌다. 하지만 일반적으로는 상계와 하계를 갖는다고 해서 상한과 하한이 반드시 존재하는 것은 아니다. 유리수 집합의 부분집합으로 '제곱이 2보다 작은 수의 집합'을 생각해 보자. 이 집합의 상계는 1.5, 2, 3, 100 등 수도 없이 많이 존재하지만, 상한은 없다.

7. 예시

  • 수 체계의 부등호
    순서 관계 중에서도 전순서에 해당한다. 어찌 보면 순서 관계라는 개념 자체가 수 체계에서만 사용하던 원소들 간의 대소 비교를 모든 종류의 원소로 확장시킨 개념이라 말할 수 있다. a가 b보다 작다는 것을 a가 b에 대하여 순서상 앞에 위치한다(precede)고 해석할 수 있기 때문이다.
  • 집합 사이의 포함 관계
    반사성과 추이성을 만족하고, 반대칭성은 아예 집합의 상등의 정의와 동일하므로 부분순서관계에 해당한다. 하지만 완전한 포함 관계에 있지 않은 집합의 쌍이 존재하므로 전순서관계는 아니다. 최소 원소는 공집합([math(\emptyset)])이며, 최대 원소는 존재하지 않는다.
  • 자연수의 나누어떨어짐 관계([math(|)])
    나누어떨어짐 관계 역시 반사성, 반대칭성, 추이성을 모두 만족시키므로 부분순서관계에 해당한다. 최소 원소는 1이며, 최대 원소는 존재하지 않는다.
    • 모든 자연수는 자기 자신을 나누어떨어뜨릴 수 있으므로 반사성을 만족한다.
    • 어떤 두 자연수 [math(a, b)]에 대하여 [math(a|b)]이고 [math(b|a)]라 가정하자. 그러면 [math(b=am)], [math(a=bn)]을 만족시키는 두 정수 [math(m, n)]이 존재하며, [math(a, b)]가 자연수이므로 [math(m, n)] 역시 자연수이다. [math(a=bn=\left(am\right)n=a\left(mn\right))]이므로 [math(m=n=1)]이고, 결과적으로 [math(a=b)]라는 결론을 얻는다. 따라서 반대칭성도 만족한다.
    • 어떤 세 자연수 [math(a, b, c)]에 대하여 [math(a|b)]이고 [math(b|c)]라 가정하자. 그러면 [math(b=am)], [math(c=bn)]을 만족시키는 두 정수 [math(m, n)]이 존재한다. 그러면 [math(c=a\left(mn\right))]이므로 [math(a|c)]이다. 따라서 추이성도 만족한다.

    다만 이 관계 역시 8, 12처럼 서로 나누어떨어지지 않는 관계에 있는 자연수의 쌍이 존재하기 때문에 전순서관계가 아니다.
    만약에 수의 범위를 정수로 확장할 경우 반대칭성을 만족하지 못해 부분순서관계가 되지 못한다. 반대칭성을 만족하지 못하는 반례로 2와 -2를 들 수 있다. 둘은 서로를 나누어떨어뜨리지만 [math(2 \neq -2)]이다.
  • 양자역학에서 측정의 결과값들로 만들어지는 상태공간이 부분순서를 따른다고 설명하기도 한다. 고전적인 측정은 '예'와 '아니오'의 결과값이 나오며 결정론적인 명제 논리학을 따르지만 양자역학의 측정은 비결정론적 특성을 보였기 때문에 1936년 버크호프와 폰 노이만은 힐베르트 공간에서의 부분순서로 구성된 양자 논리학을 만들었다.
  • 족보가 개족보가 아니라면 부자 관계로 순서관계를 줄수 있다.

8. 순서동형

[math(\forall x, y \in A (x <_1 y \leftrightarrow f(x) <_2 f(y)))]를 만족하는 일대일대응 [math(f:A \to B)]가 존재할 때 [math(f)]를 순서동형사상이라 하고, 두 순서집합 [math((A, <_1))]과 [math((B, <_2))]는 순서동형이라고 한다.

8.1. 재미있는 결과

  • 끝점이 없고 가산이며 조밀한 모든 전순서집합은 서로 순서동형이다. (따라서 유리수만 보면 된다.)
  • 모든 가산인 전순서집합은 유리수의 부분집합과 순서동형이다.

[1] 본 문서에서는 초등학교 때부터 가르치는 평범한 부등호를 사용하였으나, 순서관계를 다루는 집합론, 해석학, 위상수학 등의 수학 기초과목 교과서에서는 흔히 쓰이는 부등호 대신 [math(\prec)], [math(\preceq)], [math(\succ)], [math(\succeq)]라는 살짝 휘어진 기호를 쓰기도 한다.

분류