딜워스의 정리

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

정의

부분 순서 집합 $(P,\leq )$의 높이(영어: height)는 $P$ 속의 사슬(부분 전순서 집합)의 크기의 상한이다. 즉, 다음과 같다.

$\operatorname {height} P=\sup \left\{n\colon x_{1}<\cdots <x_{n},\;\{x_{0},\dots ,x_{n}\}\subseteq P\right\}$

부분 순서 집합 $(P,\leq )$의 너비(영어: width)는 $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)\leq |P|$

$a(P)\leq |P|$

이다.

딜워스의 정리에 따르면, 만약 부분 순서 집합 $(P,\leq )$의 너비가 유한하다면, 이는 $c(P)$와 같다.^:303 반대로, 미르스키의 정리(영어: Mirsky’s theorem)에 따르면, 만약 $P$의 높이가 유한하다면, 이는 $a(P)$와 같다.

$\operatorname {width} P<\aleph _{0}\implies \operatorname {width} P=c(P)$

$\operatorname {height} P<\aleph _{0}\implies \operatorname {height} P=a(P)$

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

증명

부분 순서 집합 $(P,\leq )$ 속의 사슬 $C\subseteq P$ 및 반사슬 $A\subseteq P$에 대하여 $|A\cap C|\leq 1$이다. 따라서, 만약 $P$를 사슬 $\{C_{i}\}_{i\in I}$들로 분할하였을 때, 각 반사슬 $A\subseteq P$에 대하여 $|C_{i}\cap A|\leq 1$이므로 $|A|\leq |I|$이며, 즉

$\operatorname {width} P\leq c(P)$

이다.^:303 반대로, 만약 $P$를 반사슬 $\{A_{j}\}_{j\in J}$들로 분할하였을 때, 각 사슬 $C\subseteq P$에 대하여 $|C\cap A_{j}|\leq 1$이므로 $|C|\leq |J|$이며, 즉

$\operatorname {height} P\leq a(P)$

이다.

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

딜워스의 정리

딜워스의 정리의 증명은 쾨니그의 정리를 이용한 기법 등 여러 방법이 있다. 만약 $P$가 유한 집합일 경우, 미카 아셰르 페를레스(히브리어: מִיכָה אָשֵׁר פרלס, 1936~)는 다음과 같은 간단한 증명을 제시하였다.^:303–304

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

집합의 크기에 대한 수학적 귀납법을 사용하자. 우선, 딜워스의 정리는 한원소 집합인 부분 순서 집합에 대하여 자명하게 성립한다. 이제 딜워스의 정리가 크기 $|P|$ 미만의 모든 부분 순서 집합에 대하여 대해 성립한다고 가정하자. 그렇다면, 다음과 같이 두 가지 경우로 나눌 수 있다.

1. 크기 $\operatorname {width} P$의 반사슬은 모두 $\operatorname {max\,elem} (P)$과 같거나, $\operatorname {min\,elem} (P)$와 같다.
2. $\operatorname {max\,elem} (P)$ 및 $\operatorname {min\,elem} (P)$와 같지 않은, 크기 $\operatorname {width} P$의 반사슬 $A\subseteq P$가 존재한다.

1의 경우, $a\leq 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)\leq 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\geq a\}$

$A_{-}=\{x\in P\colon \exists a\in A\colon x\leq 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)\leq |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)\leq \operatorname {height} (P)$이다.

역사

딜워스의 정리는 미국의 수학자 로버트 파머 딜워스(영어: Robert Palmer Dilworth, 1914~1993)가 1950년 논문에서 처음 제시하였다.^:303

미르스키의 정리는 러시아 태생의 영국 수학자 레오니트 미르스키(러시아어: Леонид Мирский, 영어: Leonid Mirsky, 1918~1983)가 1971년에 증명하였다.

외부 링크

• “Length of a partially ordered set”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Width of a partially ordered set”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Dimension of a partially ordered set”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Greene-Kleitman theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Dilworth's lemma”. 《Wolfram MathWorld》 (영어). Wolfram Research. 

같이 보기

• 쾨니그의 정리