딜워스의 정리

조합론에서 **딜워스의 정리**(Dilworth의定理, Dilworth’s theorem)는 부분 순서 집합의 반사슬의 최대 크기에 대한 정리다.
# 정의
부분 순서 집합 (P,\le)의 **높이**(height)는 P 속의 사슬(부분 전순서 집합)의 크기의 상한이다. 즉, 다음과 같다. :\operatorname{height}P=\sup\left\\{n\colon x_1<\cdots 부분 순서 집합 (P,\le)의 **너비**(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)\le|P| :a(P)\le|P| 이다. **딜워스의 정리**에 따르면, 만약 부분 순서 집합 (P,\le)의 너비가 유한하다면, 이는 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) 이 정리들은 무한한 너비 또는 높이의 부분 순서 집합에 대하여 기수로서 성립하지 않는다.언어=en
# 증명
부분 순서 집합 (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) 이다.303 반대로, 만약 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~)는 다음과 같은 간단한 증명을 제시하였다.언어=en303–304 유한 부분 순서 집합 (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)이다.
# 역사
딜워스의 정리는 미국의 수학자 로버트 파머 딜워스(Robert Palmer Dilworth, 1914~1993)가 1950년 논문에서 처음 제시하였다.언어=ko303언어=en 미르스키의 정리는 러시아 태생의 영국 수학자 레오니트 미르스키(Леонид Мирский, Leonid Mirsky, 1918~1983)가 1971년에 증명하였다.언어=en