집합론, 그 열한 번째 이야기 | 순서관계

순서관계란, 어떤 집합의 원소들 간의 크기를 비교하는 이항관계를 말하며, 구체적으로는 다음과 같이 다양한 종류가 있으며, 우리가 생각하는 일반적인 순서 관계와는 거리가 좀 있다.

 

1. 준순서 :      원순서라고도 하며, 집합 $A$에서 다음 두 조건을 만족하는 이항관계 $\leq$를 준순서라고 부른다.      1) 반사성 : $\forall x\in A,\;x\leq x$      2) 추이성 : $\forall x,y,z\in A,\;x\leq y\land y\leq z\Rightarrow x\leq z$      준순서에서는 $x\not=y$이어도 $x\leq y$이면서 동시에 $y\leq x$일 수 있다.      일반적으로 순서관계라고 하면 준순서가 아닌, 아래의 부분순서 관계를 뜻한다.      2. 부분순서(Partially Order) :      집합 $A$에서 다음 세 조건을 만족하는 이항관계 $\leq$를 부분순서라고 부른다.      또한, $(A,\leq)$를 부분순서집합이라고 부른다.      1) 반사성 : $\forall x\in A,\;x\leq x$      2) 반대칭성 : $\forall x,y\in A,\;x\leq y\land y\leq x\Rightarrow x=y$      3) 추이성 : $\forall x,y,z\in A,\;x\leq y\land y\leq z\Rightarrow x\leq z$      3. 순부분순서 :      집합 $A$에서 다음 두 조건을 만족하는 이항관계 $<$를 순부분순서라고 부른다.      1) 비반사성 : $\forall x\in A,\;\neg(x<x)$      2) 추이성 : $\forall x,y,z\in A,\;x<y\land y<z\Rightarrow x<z$      사실상 순부분순서와 부분순서는 거의 같은 것이다.      즉, $<$를 정의하면 $\leq$를 자연스럽게 정의할 수 있고, 반대도 마찬가지다.      4. 전순서(Totally Order) :      집합 $A$에서 다음 두 조건을 만족하는 이항관계 $\leq$를 전순서라고 부른다.      또한, $(A,\leq)$를 전순서집합이라고 부른다.      1) 완전성(코넥스 성질) : $\forall x,y\in A,\;x\leq y\lor y\leq x$      2) 반대칭성 : $\forall x,y\in A,\;x\leq y\land y\leq x\Rightarrow x=y$      3) 추이성 : $\forall x,y,z\in A,\;x\leq y\land y\leq z\Rightarrow x\leq z$      부분순서집합과의 차이점은 1번 조건에 따라 모든 원소들이 서로 비교가능하다는 것이다.      즉, 원소들을 일렬로 배치하는 모형을 생각할 수 있고, 그렇기 때문에 부분순서 집합의 부분집합인      전순서집합을 사슬(chain)이라고 부르기도 한다.      5. 정렬순서(Well-Order) :      전순서집합 $A$의 임의의 부분집합이 최소원소를 가지면, $A$를 정렬순서집합이라고 부르며,      전순서 $\leq$를 정렬순서라고 한다. 또한, ZFC 집합론 하에서 임의의 집합에 정렬순서를      부여할 수 있음이 보장된다. 이를 정렬 정리라고 한다.

 

추가적으로, 순서관계에는 다음과 같은 용어를 정의한다.

 

1. 비교 가능성 :      부분순서집합 $(A,\leq)$가 주어졌을 때, $A$의 두 원소 $a$, $b$가 $a\leq b\lor b\leq a$를 만족할 때,      $a$와 $b$가 비교 가능하다고 하며, 그렇지 않은 경우, $a$와 $b$가 비교 불가능하다고 한다.      2. 극대 원소, 극소 원소 :      부분순서집합 $(A,\leq)$가 주어졌을 때, $\forall x\in A,\;M\leq x\Rightarrow x=M$인 $M\in A$를      $A$의 극대 원소라고 하며, $\forall x\in A,\;x\leq m\Rightarrow x=m$인 $m\in A$를 $A$의 극소 원소라고 한다.      3. 최대 원소, 최소 원소 :      부분순서집합 $(A,\leq)$가 주어졌을 때, $\forall x\in A,\;x\leq M$을 만족하는 $M\in A$를      $A$의 최대 원소라고 하며, $\forall x\in A,\;m\leq x$를 만족하는 $m\in A$를 $A$의 최소 원소라고 한다.      4. 상계, 하계, 상한, 하한 :      부분순서집합 $(A,\leq)$가 주어졌을 때, $A$의 부분집합 $E$에 대해 $\forall x\in E,\;x\leq M$을 만족하는      $M\in A$를 $E$의 상계라고 부르며, $\forall x\in E,\;m\leq x$를 만족하는 $m\in A$를 $E$의 하계라고 한다.      또한, $E$의 상계집합의 최소원소를 상한이라고 하며 $E$의 하계집합의 최대원소를 하한이라고 한다.      어떤 부분집합이 상계를 가진다고 해서 상한을 가짐이 보장되는 것은 아니며,      반대로 하계를 가진다고 해서 하한을 가짐이 보장되는 것 또한 아니다.      5. 유계 :      부분순서집합 $(A,\leq)$가 주어졌을 때, $A$의 부분집합 $E$에 대해 $E$의 상계와 하계가 동시에 존재할 때,      $E$를 유계집합이라고 한다.