부분 순서

위키백과, 우리 모두의 백과사전.
(부분순서에서 넘어옴)
이동: 둘러보기, 검색

순서론에서, 어떤 집합에 대해 정의된 이항 관계부분 순서(部分順序, 영어: partial order)라는 것은, 그 집합 내의 어떤 두 원소 사이에 그 이항 관계가 정의되어있다는 뜻이다.

정의[편집]

집합 S 위의 이항 관계 {\le}\subseteq S^2가 다음 조건을 만족시키면 이 이항 관계는 집합 S에 대해 부분 순서이다.

  • (반사성) 모든 s\in S에 대하여, s\le s
  • (추이성) 모든 s,t,u\in S에 대하여, 만약 s\le t이며 t\le u라면 s\le u
  • (반대칭성) 모든 s,t\in S에 대하여, 만약 s\le t이며 t\le s라면 s=t

집합과 그 집합에 대해 부분 순서인 이항 관계의 순서쌍 (S,\le)부분 순서 집합(部分順序集合, 영어: poset)이라고 한다.

범주론적으로, 부분 순서 집합 (S,\le)범주로 여길 수 있다. 이 경우

  • (S,\le)의 대상은 S의 원소이다.
  • (S,\le)사상\{(s,t)\in S^2\colon s\le t\}이다. (s,t)s에서 t로 가는 사상이다. 즉, \hom(s,t)는 0개 또는 1개의 원소만을 포함한다.
  • 대상 s\in S의 항등 사상은 (s,s)\in S^2이다.

모형 이론적으로, 부분 순서는 이항 관계 \le의 언어에 대한, 다음 1차 논리적 공리들로 구성되는 이론이다.

  • \forall a\colon a\le a
  • \forall a\forall b\forall c\colon(a\le b)\land(b\le c)\implies a\le c
  • \forall a\forall b\colon(a\le b)\land(b\le a)\implies a=b

부분 순서의 이론의 모형은 부분 순서 집합이다.

순서 보존 함수[편집]

두 부분 순서 집합 (S,\le_S), (T,\le_T) 사이의 순서 보존 함수(順序保存函數, 영어: order-preserving function) f\colon S\to T는 다음 성질을 만족시키는 함수이다.

  • 임의의 s,s'\in S에 대하여, 만약 s\le_Ss'이라면 f(s)\le_Tf(s')이다.

즉, 이는 이항 관계 \le에 대한 구조로서의 준동형이다.

순서 보존 함수인 전단사 함수순서 동형 사상(順序同型寫像, 영어: order isomorphism)이라고 하고, 순서 동형사상이 존재하는 두 부분 순서 집합을 순서 동형(順序同型, 영어: order-isomorphic)이라고 한다.

[편집]

집합 \{x,y,z\}의 멱집합 위의 포함 관계는 격자이므로, 부분 순서를 이룬다.

모든 전순서는 부분 순서이다. 예를 들어, 자연수 집합 \mathbb N이나 정수 집합 \mathbb Z, 유리수 집합 \mathbb Q, 실수 집합 \mathbb R 위의 표준적인 순서는 전순서이므로 부분 순서이다.

집합 S멱집합 \mathcal P(S) 위의, 포함 관계 \subseteq는 부분 순서이며, 만약 S가 두 개 이상의 원소를 갖는다면 이는 전순서가 아니다. 또한, 이를 \mathcal P(S)의 부분 집합에 국한시켜도 역시 부분 순서를 이룬다. 예를 들어,

등등은 특정한 부분 집합들의 집합이므로 포함 관계를 통해 부분 순서를 갖는다.

양의 정수의 집합 \mathbb Z^+ 위에, 약수 관계 \mid (a\mid b는 "ab의 약수")는 부분 순서이며, 이는 전순서가 아니다.

부분 순서의 수[편집]

크기가 n인 유한 집합 위의 부분 순서의 수는 다음과 같다. (n=0,1,2,\dots)

1, 1, 3, 19, 219, 4231, 130023, … (OEIS의 수열 A1035)

크기가 n인 유한 집합 위의 부분 순서의 동형류의 수는 다음과 같다. (n=0,1,2,\dots)

1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284, … (OEIS의 수열 A112)

바깥 고리[편집]

같이 보기[편집]