딜워스의 정리

조합론에서 **딜워스의 정리**(Dilworth의定理, )는 부분 순서 집합의 반사슬의 최대 크기에 대한 정리다.

## 정의
부분 순서 집합 (P,\le)의 **높이**()는 P 속의 사슬(부분 전순서 집합)의 크기의 상한이다. 즉, 다음과 같다.
:\operatorname{height}P=\sup\left\{n\colon x_1
부분 순서 집합 (P,\le)의 **너비**()는 P 속의 반사슬의 크기의 상한이다. 즉, 다음과 같다.
:\operatorname{width}P=\sup\left\{|S|\colon S\subseteq P,\;s\parallel s'\forall s,s'\in S\right\}\in\mathbb Z^+\cup\{0,\infty\}
(여기서 s\parallel s'은 두 원소가 비교 불가능임을 뜻한다.)

임의의 부분 순서 집합 P에 대하여, P를 사슬들로 분할할 수 있으며, 이러한 분할의 최소 크기를 c(P)라고 하자. 또 P를 반사슬들로도 분할할 수 있으며, 이러한 분할의 최소 크기를 a(P)라고 하자. 한원소 집합은 사슬이자 반사슬이므로, 자명하게
:c(P)\le|P|
:a(P)\le|P|
이다.

**딜워스의 정리**에 따르면, 만약 부분 순서 집합 (P,\le)의 너비가 유한하다면, 이는 c(P)와 같다. 반대로, **미르스키의 정리**()에 따르면, 만약 P의 높이가 유한하다면, 이는 a(P)와 같다.
:\operatorname{width}P
:\operatorname{height}P

이 정리들은 무한한 너비 또는 높이의 부분 순서 집합에 대하여 기수로서 성립하지 않는다.

## 증명
부분 순서 집합 (P,\le) 속의 사슬 C\subseteq P 및 반사슬 A\subseteq P에 대하여 |A\cap C|\le1이다. 따라서, 만약 P를 사슬 \{C_i\}_{i\in I}들로 분할하였을 때, 각 반사슬 A\subseteq P에 대하여 |C_i\cap A|\le 1이므로 |A|\le|I|이며, 즉
:\operatorname{width}P\le c(P)
이다. 반대로, 만약 P를 반사슬 \{A_j\}_{j\in J}들로 분할하였을 때, 각 사슬 C\subseteq P에 대하여 |C\cap A_j|\le 1이므로 |C|\le|J|이며, 즉
:\operatorname{height}P\le a(P)
이다.

따라서, 딜워스의 정리와 미르스키의 정리에서 자명하지 않은 것은 반대 방향의 부등식이다. 이 경우, 두 정리의 증명은 매우 다르다.

### 딜워스의 정리
딜워스의 정리의 증명은 쾨니그의 정리를 이용한 기법 등 여러 방법이 있다. 만약 P가 유한 집합일 경우, 미카 아셰르 페를레스(, 1936~)는 다음과 같은 간단한 증명을 제시하였다.

유한 부분 순서 집합 (P,\le)가 주어졌다고 하자. P의 극대 원소들의 집합을 \operatorname{max\,elem}(P), 극소 원소들의 집합을 \operatorname{min\,elem}(P)라고 하자. 이들은 각각 반사슬을 이룬다.

집합의 크기에 대한 수학적 귀납법을 사용하자. 우선, 딜워스의 정리는 한원소 집합인 부분 순서 집합에 대하여 자명하게 성립한다. 이제 딜워스의 정리가 크기 |P| 미만의 모든 부분 순서 집합에 대하여 대해 성립한다고 가정하자. 그렇다면, 다음과 같이 두 가지 경우로 나눌 수 있다.
# 크기 \operatorname{width}P의 반사슬은 모두 \operatorname{max\,elem}(P)과 같거나, \operatorname{min\,elem}(P)와 같다.
# \operatorname{max\,elem}(P) 및 \operatorname{min\,elem}(P)와 같지 않은, 크기 \operatorname{width}P의 반사슬 A\subseteq P가 존재한다.
1의 경우, a\le b인 a\in\operatorname{min\,elem}(P)와 b\in\operatorname{max\,elem}(P)를 찾을 수 있다. (그렇지 아니하다면 크기가 \operatorname{width}P보다 더 큰 반사슬이 존재하게 되기 때문이다.) P\setminus\{a,b\}의 최소 사슬 분할
:P\setminus\{a,b\}=\bigsqcup_{i=1}^{c(P\setminus\{a,b\})}C_i
이 주어졌을 때
:P=\{a,b\}\sqcup \bigsqcup_{i=1}^{c(P\setminus\{a,b\})}C_i
는 P의 사슬 분할이므로, P\setminus\{a,b\}에 딜워스의 정리를 적용하면
:c(P)\le c(P\setminus\{a,b\})+1=\operatorname{width}(P\setminus\{a,b\})+1=\operatorname{width}P
이다.

2의 경우, 다음과 같은 두 부분 집합 A_\pm\subsetneq P를 정의하자.
:A_+=\{x\in P\colon\exists a\in A\colon x\ge a\}
:A_-=\{x\in P\colon\exists a\in A\colon x\le a\}
:\operatorname{width}(A_+)=\operatorname{width}(A_-)=|A|=\operatorname{width}P
:A_+\subsetneq P\supsetneq A_-
:A_+\cap A_-=A
A_\pm에 딜워스의 정리를 적용하여 다음과 같은 사슬 분해를 얻는다고 하자.
:A_\pm=\bigsqcup_{a\in A}C_\pm(a)
:\max C_-(a)=a=\min C_+(a)
그렇다면 P의 사슬 분해
:P=\bigsqcup_{a\in A}(C_+(a)\cup C_-(a))
를 얻는다. 즉,
:c(P)\le|A|=\operatorname{width}P
가 된다.

### 미르스키의 정리
미르스키의 정리의 증명은 딜워스의 정리의 증명보다 더 간단하다. P가 유한한 높이의 부분 순서 집합이라고 하자. 원소 x\in P에 대하여, N(x)가 x를 최대 원소로 하는 사슬의 길이의 최댓값이라고 하자. 이는 함수 N\colon P\to\mathbb N을 정의한다.
그렇다면, 각 자연수 n\in\mathbb N의 원상 N^{-1}(n)\subseteq P은 반사슬을 이루며, 이들은 P의 분할을 이룬다.
:P=\bigsqcup_{n=0}^\infty N^{-1}(n)
따라서 a(P)\le\operatorname{height}(P)이다.

## 역사
딜워스의 정리는 미국의 수학자 로버트 파머 딜워스(, 1914~1993)가 1950년 논문에서 처음 제시하였다.

미르스키의 정리는 러시아 태생의 영국 수학자 레오니트 미르스키(, , 1918~1983)가 1971년에 증명하였다.

## 각주

## 외부 링크
* 
* 
* 
* 
* 

## 같이 보기
* 쾨니그의 정리

분류:순서론
분류:조합적 집합론
분류:조합론 정리
분류:완벽 그래프