(+)분류 : 가져온 문서/오메가
半順序集合 / Partially ordered set, Poset
반순서가 주어진 집합을 말한다.
1. 정의 ✎ ⊖
P가 집합이고 P 위의 순서 \\preceq가
1. (반사성) 임의의 x\\in P에 대해 x\\preceq x
2. (반대칭성) 임의의 x,y\\in P에 대해 x\\preceq y이고 y\\preceq x이면 x=y
3. (추이성) 임의의 x,y,z\\in P에 대해 x\\preceq y이고 y\\preceq z이면 x\\preceq z
를 만족하면 \\preceq를 반순서(Partial order)라 하고, (P,\\preceq)를 반순서집합이라 한다. 이 때 반순서집합은 그 기반 집합 P뿐 아니라 반순서 \\preceq에도 의존한다. 주어진 순서가 명백한 경우(가령, 실수 집합 위에 대소관계로 자연스럽게 순서가 주어진 경우)에는 집합만을 언급하기도 한다.
1. (반사성) 임의의 x\\in P에 대해 x\\preceq x
2. (반대칭성) 임의의 x,y\\in P에 대해 x\\preceq y이고 y\\preceq x이면 x=y
3. (추이성) 임의의 x,y,z\\in P에 대해 x\\preceq y이고 y\\preceq z이면 x\\preceq z
를 만족하면 \\preceq를 반순서(Partial order)라 하고, (P,\\preceq)를 반순서집합이라 한다. 이 때 반순서집합은 그 기반 집합 P뿐 아니라 반순서 \\preceq에도 의존한다. 주어진 순서가 명백한 경우(가령, 실수 집합 위에 대소관계로 자연스럽게 순서가 주어진 경우)에는 집합만을 언급하기도 한다.
2. 예시 ✎ ⊖
- 임의의 전순서집합
- 자연수 집합 위에 나눠떨어짐 관계를 반순서로 준 집합.
- 임의의 집합 X에 대해, 그 멱집합 위에 포함관계를 순서로 준 집합.
- x\\le y\\ \\text{iff}\\ \\lnot x\\lor y=1인 순서를 준 임의의 불 대수.
3. 사슬 조건 ✎ ⊖
3.1. 오름 사슬 조건 ✎ ⊖
반순서 집합 S가 다음 조건을 만족하면 S는 오름 사슬 조건(ascending chain condition, a.c.c.)을 만족한다고 한다.
- (오름 사슬 조건) 모든 오름 사슬은 결국 멈춘다. 즉, 증가하는 원소들의 사슬 x_1\\preceq x_2\\preceq \\cdots \\preceq x_n \\preceq \\cdots (n\\in \\mathbb{N})에 대해 x_n=x_{n+1}을 만족하는 n이 존재한다.
- (극대 원소 조건) 공집합이 아닌 임의의 S의 부분집합은 극대원소를 가진다.
3.2. 내림 사슬 조건 ✎ ⊖
마찬가지로 S가 다음 조건을 만족하면 S는 내림 사슬 조건(descending chain condition, d.c.c.)을 만족한다고 한다.
전순서집합이 극소 원소 조건을 만족하면 이 집합을 정렬 가능하다(well-ordered)라고 한다. 자연수 집합은 대표적인 정렬 가능한 전순서집합이다.
- (내림 사슬 조건) 모든 내림 사슬은 결국 멈춘다. 즉, 감소하는 원소들의 사슬 x_1\\succeq x_2\\succeq \\cdots \\succeq x_n \\succeq \\cdots (n\\in \\mathbb{N})에 대해 x_n=x_{n+1}을 만족하는 n이 존재한다.
- (극소 원소 조건) 공집합이 아닌 임의의 S의 부분집합은 극소원소를 가진다.
전순서집합이 극소 원소 조건을 만족하면 이 집합을 정렬 가능하다(well-ordered)라고 한다. 자연수 집합은 대표적인 정렬 가능한 전순서집합이다.
