순서 관계

 


1. 준순서
2. 부분순서
3. 순부분순서
4. 전순서
5. 정렬 순서
6. 용어
7. 예시
8. Similar
8.1. 재미있는 결과


1. 준순서

집합 $$A$$에서 다음 두 조건을 만족하는 이항 관계 $$\leq$$를 준순서 혹은 원순서(quasi-order, preorder)라 한다.
  1. $$\forall x \in A \left(x\leq x \right)$$ (reflexivity)
  2. $$\forall x, y, z \in A ((x\leq y \wedge y\leq z) \to x\leq z)$$ (transitivity)
일반적으로 순서관계라고 하면 준순서가 아닌, 아래의 부분순서 관계를 뜻한다.

2. 부분순서

집합 $$A$$에서 다음 세 조건을 만족하는 이항 관계 $$\leq$$를 부분 순서(partial order)라고 하고 $$\left(A, \leq \right)$$를 부분 순서 집합(partially ordered set, poset)이라고 한다:
  1. $$\forall x \in A \left(x\leq x \right)$$ (reflexivity)
  2. $$\forall x, y \in A \left(\left(x\leq y \wedge y\leq x \right) \to x = y \right)$$ (antisymmetry)
  3. $$\forall x, y, z \in A ((x\leq y \wedge y\leq z) \to x\leq z)$$ (transitivity)
부분순서가 주어진 유한 집합에 대해 하세 다이어그램이라는 그래프로 나타내는 방법이 있다.

3. 순부분순서

집합 $$A$$에서 정의된 이항 관계 $$<$$가 다음을 만족할 때, 이를 A의 순부분순서(strict partial order)라고 한다:
  1. $$\forall x \in A \left(\neg(x
  2. $$\forall x, y, z \in A ((x
사실상 순부분순서와 부분순서는 거의 같은 것이다. 즉, <를 정의하면 $$\le$$를 자연스럽게 정의할 수 있고, 반대도 마찬가지다.
$$ \left(x

4. 전순서

집합 $$A$$에서의 이항 관계 $$\leq$$가 다음을 만족하면, 이를 전순서(total order) 또는 선형순서(linear order)라 하고, $$\left(A, \leq \right)$$를 전순서 집합(totally ordered set, toset) 또는 선형 순서 집합(linearly ordered set)이라 한다:
  1. $$\forall x, y \in A \left(x\leq y \lor y \leq x \right)$$ (totality)
  2. $$\forall x, y \in A \left(\left(x\leq y \wedge y\leq x \right) \to x = y \right)$$ (antisymmetry)
  3. $$\forall x, y, z \in A ((x\leq y \wedge y\leq z) \to x\leq z)$$ (transitivity)
부분순서 집합과의 차이점은 1번 조건에 따라 모든 원소들이 서로 비교가능하다는 것이다. 따라서 원소들을 일렬로 배치하는 모형을 생각할 수 있고, 이런 점에서 부분순서 집합의 부분집합인 전순서 집합을 사슬(chain)이라고 부르기도 한다. 이와 비슷하게 부분순서 집합을 그물이라 부르는 경우도 있다.

5. 정렬 순서

전순서 집합 $$A$$가 임의의 부분집합이 극소원소를 가지면, $$A$$를 정렬집합(well-ordered set)이라 하고, 그 전순서를 정렬 순서(well-ordering)이라 한다.
정렬 집합은 어떤 서수(ordinal)에 대해 순서 동형이다. 즉, $$ON$$을 서수의 고유 모임이라고 하면, 임의의 정렬 집합 $$A$$에 대하여 $$x,\:y\in A,\:\:x<y\iff f(x)<f(y)$$인 전단사함수 $$f:A\to\alpha$$가 존재하는 서수 $$\alpha\in ON$$가 존재한다.
선택공리를 가정하면, 임의의 집합에 정렬순서를 줄 수 있는게 보장 된다. 이를 정렬 정리(well-ordering theorem)라고 하는데, ZF하에서 선택공리와 동치인 대표적인 명제이다.

6. 용어

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

7. 예시

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

8. Similar

$$\forall x, y \in A (x <_1 y \leftrightarrow f(x) <_2 f(y))$$를 만족하는 bijective function $$f:A \to B$$가 존재할 때 두 순서집합 $$(A, <_1)$$, $$(B, <_2)$$가 similar하다고 한다.

8.1. 재미있는 결과

  • 끝점이 없는 모든 countable dense linearly ordered set은 similar하다. (따라서 유리수만 보면 된다.)
  • 모든 countable linearly ordered set은 유리수의 부분 집합과 similar하다.

[1] 정수로 범위를 확장할 경우 반대칭성을 만족하지 못해 부분순서관계가 되지 못한다.[2] 정수의 범위로 확장시킬 경우, 반대칭성을 만족하지 못하는 반례로 2와 -2를 들 수 있다. 둘은 서로를 나누어떨어뜨리지만 $$2 \neq -2$$이다.

분류