半順序集合 / Partially ordered set, Poset
반순서가 주어진 집합을 말한다.
목차
1. 정의
2. 예시
3. 사슬 조건
3.1. 오름 사슬 조건
3.2. 내림 사슬 조건
4. 보기
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에도 의존한다. 주어진 순서가 명백한 경우(가령, 실수 집합 위에 대소관계로 자연스럽게 순서가 주어진 경우)에는 집합만을 언급하기도 한다.
- 임의의 전순서집합
- 자연수 집합 위에 나눠떨어짐 관계를 반순서로 준 집합.
- 임의의 집합
X에 대해, 그 멱집합 위에 포함관계를 순서로 준 집합. x\le y\ \text{iff}\ \lnot x\lor y=1인 순서를 준 임의의 불 대수.
3. 사슬 조건 ✎
반순서 집합
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의 부분집합은 극대원소를 가진다.
마찬가지로
S가 다음 조건을 만족하면
S는
내림 사슬 조건(descending chain condition, d.c.c.)을 만족한다고 한다.
- (내림 사슬 조건) 모든 내림 사슬은 결국 멈춘다. 즉, 감소하는 원소들의 사슬
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)라고 한다. 자연수 집합은 대표적인 정렬 가능한 전순서집합이다.
