부분 순서 관계 편집하기

'''부분 순서 관계'''(Partial Order Relation)는 집합 내 원소들 사이의 순서를 정의하는 이항 관계(Binary Relation) 중 하나로, 반사성(reflexivity), 반대칭성(antisymmetry), 이행성(transitivity)의 세 가지 성질을 만족하는 관계이다.
==정의==
집합 '''X''' 위의 이항 관계 '''≤'''가 다음 세 가지 성질을 만족하면, 이를 '''부분 순서 관계'''라고 한다.
*'''반사성 (Reflexivity)'''
**모든 원소 x에 대해 '''x ≤ x'''가 성립한다.
**즉, 모든 원소는 자기 자신과 비교될 수 있다.

*'''반대칭성 (Antisymmetry)'''
**두 원소 x, y가 있을 때, '''x ≤ y'''이고 '''y ≤ x'''라면 반드시 '''x = y'''이어야 한다.
**즉, 서로 다른 두 원소가 동시에 순서 관계를 가질 수 없다.

*'''이행성 (Transitivity)'''
**세 원소 x, y, z가 있을 때, '''x ≤ y'''이고 '''y ≤ z'''라면 반드시 '''x ≤ z'''이어야 한다.
**즉, 순서 관계가 연속적으로 유지된다.
이러한 조건을 만족하는 집합 (X, ≤)을 '''부분 순서 집합'''(Partially Ordered Set, Poset)이라고 한다.
==예제==
===부분 순서 관계 예시===
*'''자연수의 나눗셈 관계'''
**집합 X = {1, 2, 4, 8}에서 관계 '''x ≤ y'''를 '''x가 y를 나눈다'''로 정의하면 부분 순서 관계가 된다.
**예: 1 ≤ 2, 2 ≤ 4, 4 ≤ 8

*'''부분 집합 관계 (⊆)'''
**임의의 집합 S의 부분 집합들 사이에서 포함 관계(⊆)는 부분 순서 관계를 이룬다.
**예: {1, 2} ⊆ {1, 2, 3}, {1} ⊆ {1, 2}
===부분 순서가 아닌 관계 예시===
*'''"이상함" 관계'''
**예를 들어, x와 y가 "서로 이상하다고 생각한다"는 관계는 반대칭성을 만족하지 않으므로 부분 순서 관계가 아니다.

*'''"친밀도" 관계'''
**사람 사이의 친밀도를 수치화하고, "더 친한 관계"를 정의한다고 하더라도, 이행성이 성립하지 않을 수 있다.
**즉, A가 B보다 친하고, B가 C보다 친하다고 해서 A가 C보다 친하다고 단정할 수 없다.
==전순서 관계와의 차이==
부분 순서 관계는 '''모든 원소 쌍이 비교될 필요가 없다.'''  반면, **전순서 관계(Total Order Relation)** 는 **모든 원소가 비교될 수 있는 순서 관계**이다.
*예: 실수 집합 ℝ에서 일반적인 크기 비교(≤)는 전순서 관계이다.
*예: 부분 집합 관계(⊆)는 부분 순서 관계이지만, 모든 집합이 서로 포함 관계에 있지 않으므로 전순서 관계는 아니다.
==하세 다이어그램 (Hasse Diagram)==
부분 순서 집합을 시각적으로 표현하는 방법 중 하나가 **하세 다이어그램(Hasse Diagram)** 이다.  하세 다이어그램은 다음 원칙을 따른다.
#각 원소를 점(node)으로 나타낸다.
#관계가 있는 두 원소 (x ≤ y)에 대해 x에서 y로 선(edge)을 연결한다.
#불필요한 선(이행성에 의해 유도될 수 있는 관계)은 생략한다.
예제:  집합 X = {1, 2, 4, 8}에서 나눗셈 관계를 하세 다이어그램으로 표현하면 다음과 같다.<pre>
    8
    |
    4
    |
    2
    |
    1
</pre>또는:<syntaxhighlight lang="text">
    8
    |
    4
    |
    2
    |
    1
</syntaxhighlight>
==응용==
부분 순서 관계는 수학 및 컴퓨터 과학에서 여러 가지 응용이 있다.
*'''자료 구조'''
**힙(heap), 트리(tree)와 같은 자료 구조에서 우선순위 관계를 정의하는 데 사용된다.

*'''스케줄링 문제'''
**작업 간의 의존 관계를 나타낼 때 사용되며, DAG(Directed Acyclic Graph)로 모델링할 수 있다.

*'''논리 회로 최적화'''
**게이트 간의 연산 순서를 최적화하는 데 사용된다.
==같이 보기==
*[[전순서 관계]]
*[[부분 집합]]
*[[격자 이론]]
*[[위상 정렬]]
==참고 문헌==
*D. Knuth, ''Concrete Mathematics'', Addison-Wesley, 1994.
*Birkhoff, G., ''Lattice Theory'', American Mathematical Society, 1995.
*[https://mathworld.wolfram.com/PartialOrder.html Wolfram MathWorld - Partial Order]
[[분류:알고리즘]]