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