| 수학기초론 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. 개요
partial order순서 관계의 일종으로, 임의의 두 원소 사이의 대소 관계가 항상 정의되는 것이 아닌 일부만 정의된 이항 관계를 의미한다. 전순서(total order) 집합을 배경으로 하는 해석학 등과 다르게 부분 순서는 집합론, 이산수학, 범주론에서 주로 등장한다.
2. 정의
집합 [math(X)] 위에 정의된 이항 관계 [math(\preceq)]에 대해- [math(\forall a\in X(a\preceq a))] (반사성)
- [math(\forall a,b\in X(a\preceq b\land b\preceq a\to a=b))] (반대칭성)
- [math(\forall a,b,c\in X(a\preceq b\land b\preceq c\to a\preceq c))] (추이성)
위 조건을 모두 만족한다면, [math(\preceq)]를 부분 순서(partial order) 또는 부분 순서 관계(partial order relation)라고 하고, [math((X,\preceq))]를 부분 순서 집합(partially ordered set), 또는 줄여서 poset이라고 한다.[1] 여느 관계와 마찬가지로, 가리키는 대상이 명확하다면 순서쌍 대신 [math(X)]를 부분 순서 집합이라 부르기도 한다.
3. 사슬
부분 순서 집합 [math(X)]의 부분집합 [math(C\subset X)]가 [math(X)]에서 정의된 순서 관계 [math(\prec)] 위에서 전순서 집합을 이룰 때, [math(C)]를 [math(X)]의 사슬(chain)이라 한다.선택공리와 동치인 명제 중 하우스도르프 극대 원리가 있는데, 이걸 사용하면 모든 부분 순서 집합이 극대 사슬을 가진다는 사실을 알 수 있다. 정확히는 부분 순서 집합의 사슬들을 모은 집합에 부분집합 관계를 순서로 정의했을 때, 극대(maximal) 원소가 존재한다는 뜻이다. 선택공리에서 초른의 보조정리와 극대 원리를 유도하고, 여기에서 정렬 원리(well-ordering principle)를 유도하면서 되돌아오는 게 일반적인 집합론 수업의 하이라이트 부분 중 하나.
4. 곱 부분 순서
두 집합의 곱집합(cartesian product)에서 파생되는 부분 순서 관계. [math((A,\preceq_A))]와 [math((B,\preceq_B))] 모두 부분 순서 집합이라고 가정하자. 이 둘의 곱집합 [math(A\times B)] 위의 이항관계 [math(\preceq_{A\times B})]를| [math(\forall a,a'\in A\forall b,b'\in B(a\preceq_A a'\land b\preceq_B b'\iff(a,b)\preceq_{A\times B}(a',b')))] |
와 같이 정의할 때, [math((A\times B,\preceq_{A\times B}))]는 부분 순서 집합을 이룬다. 증명은 다음과 같다. 우선 [math(\forall a\preceq a,\forall b\preceq b)]이므로 [math((a,b)\preceq(a,b))]는 자명하다. 또한 [math((a,b)\preceq(a',b'))]라는 것은 정의에 따라 [math(a\preceq a'\land b\preceq b')]이며 반대의 경우도 마찬가지로 [math((a',b')\preceq(a,b))]라면 [math(a'\preceq a\land b'\preceq b)]이다. 이 둘이 모두 참일 경우 [math((a\preceq a'\land a'\preceq a)\land(b\preceq b'\land b'\preceq b))] 따라서 [math(a=a'\land b=b')]이며, 이는 [math((a,b)=(b,b'))]과 같이 나타낼 수 있으므로 반대칭성 또한 성립한다. 마찬가지로 [math((a,b)\preceq(a',b')\land(a',b')\preceq(a,b))]일 경우 [math(a\preceq a'\land a'\preceq a\to a\preceq a)]이며, 이는 [math(b)]도 마찬가지다. 따라서 [math((a,b)\preceq(a,b))]이므로 추이성 역시 만족한다.
5. 표현
유한 부분 순서를 표현할 때 가장 널리 쓰이는 도표로 하세 다이어그램이 존재한다. 개별 원소의 반사는 자명하므로 모두 생략하고[2], 어떤 원소가 다른 원소보다 클 경우, 둘을 선분으로 연결하고 큰 원소를 위에 놓는다. 또한 복잡하지 않게끔 추이적으로 유도되는 선분은 생략한다.이산수학에서는 그래프나 트리 형태에 조건을 일부 수정해 표현하기도 하며, 범주론에서는 부분 순서 자체가 특수한 범주로 표현되는 것도 가능하다.
6. 예시
가장 유명한 예시 중 하나로, 집합의 부분집합 관계 [math(\subset)]은 부분 순서를 이룬다. 증명은 다음과 같다. 우선 모든 집합은 자기 자신의 부분집합이므로 반사성을 만족하며, 임의의 두 집합이 서로의 부분집합이라면 ZFC 공리계의 외연 공리(axiom of extensionality)에 의해 상등이다. [math(A)]가 [math(B)]의 부분집합일 것의 필요충분조건이 [math(\forall a\in A)]가 [math(a\in B)]일 것이므로, [math(A\subset B)]이고 [math(B\subset C)]라면 [math(\forall a\in A)]는 [math(a\in C)]이다. 따라서 추이성 역시 성립한다.또 다른 예시로 약수 관계가 있다. 기본적으로 모든 수는 자기 자신으로 나누어 떨어지며, [math(a|b\land b|a)]라는 것은 [math(a)]의 소인수가 모두 [math(b)]에 속하며, 동시에 [math(b)]의 소인수가 모두 [math(a)]에 속한다는 뜻이므로 [math(a=b)]이다. 비슷하게 [math(a|b|c)]라면 [math(a)]의 소인수가 [math(c)]에도 속한다는 뜻이므로 [math(a|c)]가 성립하며, 따라서 추이성 역시 만족한다.