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

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

 

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

 

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

 

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