개요
순서쌍 (a,b)에 대해서 관계를 정의하고, 그 관계를 통해서 나온
관계
집합 [math]X[/math] 위의 이항 관계 [math]\le[/math]가 다음 관계가 있다.
- Reflexive: 임의의 [math]x\in X[/math]에 대하여, [math]x\le x[/math]
- Anit-Reflexive: 임의의 [math]x\in X[/math]에 대하여, [math]x\not\lt x[/math]
- Transitive: 임의의 [math]x,y,z\in X[/math]에 대하여, [math]x\le y\le z[/math]라면 [math]x\le z[/math]
- Symmetric: 임의의 [math]x,y\in X[/math]에 대하여, [math]x\le y[/math]라면 [math]y\le x[/math]
- Anti-Symmetric: 임의의 [math]x,y\in X[/math]에 대하여, [math]x\le y\le x[/math]라면 [math]x=y[/math]
Equivalence (동치)
어떤것이 같다고 정의하는 가.
동치에서는 Reflexive, Trasitive, 그리고 Sysmmetric이 성립된다. 예를 들어서 a==b mod(10)관계는 동치이다. 이 경우 Anti-Symmetric은 만족하지 못한다. 예) mod 12 <= mod 22 <= mod 12 이지만, 12 == 22가 아니다.
Partial Order
어떻게 순서를 정의할 것인가.
Partial Order에서는 약한 부분 순서(weak partial order)와, 강한 부분 순서(strict partial order)가 있다. 둘다 Anti-Symmetric과 Transitive를 만족하지만, Reflexive의 정의에서 다른데, 약한 부분 순서는 반사(Reflexive)를 허용하지만 강한 부분 순서는 비반사(Anti-Reflexive)를 허용한다. 즉 부분 순서 집합은 (Anti)Relexive, Anti-Symmetric, 그리고 Transitive를 만족하는 집합이다.
Poset
집합 D가 Partial order이면 partial order set (D, <)라고 하거나 단순히 poset이라고 한다.
Least Upper Bound
Partial order set D 그리고 D의 부분집합 X에 대해서, 만약 d [math]\in[/math]가 모든 X의 원소 x에 대해서 x < d이면 d를 upperbound라고 하며, Least upper bound는 모든 Upper bound중에서 제일 작은 원소를 말한다. 즉 자연수의 집합 [1, 10]에서 Upper bound는 11, 12 ...가 될 수 있지만, Least upper bound는 11하나 뿐이다.
Total Order
Total order는 Partial order에 모든 원소는 서로 비교 가능하다는 조건인 Connectivity가 추가된 Order를 의미한다.
예를 들어서 {0, 1}의 subset인 공집합, {0}, {1}, 그리고 {0, 1}을 생각 해보자. Order을 원소의 개수라고 작은 순서라고 해보자. 공집합 < {0} 그리고 {1} < {0, 1}처럼 <라는 명령어를 정의할 수 있다. 이 명령어 "<"는 Partial Order이지만 Total Order는 아닌데, 이는 {0} < {1}이 정의되지 않기 때문이다.
Chain
Partial ordered set D에 대해서 D의 부분집합 X가 Total order set이면 X를 Chain이라고 한다.
예를 들어서 0->1->2->3->4->5 ...인 0을 포함한 양의 정수 집합이 있다고 하자. 이떄 (0) (0,1) (0,1,3)과 같은 집합들은 이 poset의 chain이다.
Complete partial order
poset D에 대해서 D의 모든 chain X가 least upper bound를 가지고 있으면 D를 Complete partial order집합이라고 한다.
Lemma: 만약 poset이 CPO면 poset은 least element를 가지며, 만약 공집합이 least element을 가지고 있다면, CPO의 least element는 공집합의 least element와 같다.
예를 들어서, N을 100 이하의 자연수의 집합으로 정의하고 <를 보통의 비교 연산자로 정의하자. 이 집합 N은 CPO인데, 왜냐하면 모든 N의 부분 집합 X는 least upper bound를 가지고 있기 때문이다. 예를 들어서 {2, 4, 6}은 6을 Least upper bound를 가지고 있다. 제시된 Lemma는 공집합이 되며, 공집합의 Least element는 반드시 모든 자연수 집합의 부분집합의 least element이기 때문에 이 CPO는 또한 반드시 Lemma를 만족시킨다. 그러나 N을 자연수의 집합으로 간주하면 CPO가 아닌데, 짝수의 집합은 N의 부분집합으로 Partial order이지만, Upper bound가 없기 때문에, 집합 N은 CPO가 이경우 아니다.
Continuous Function
연속 함수에 대한 많은 정의가 있을 수 있지만, Partial order로도 Continouous를 정의할 수 있다. 두 poset D1 D2에 대해서 F: D1 -> D2가 모든 체인들에 대해서 least upper bound가 보존되면 이 함수를 연속이다 라고 한다.