딜워스의 정리

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

정의

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

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

부분 순서 집합 ${\displaystyle (P,\leq )}$의 너비(영어: width)는 ${\displaystyle P}$ 속의 반사슬의 크기의 상한이다. 즉, 다음과 같다.

${\displaystyle \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 \}}$

(여기서 ${\displaystyle s\parallel s'}$은 두 원소가 비교 불가능임을 뜻한다.)

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

${\displaystyle c(P)\leq |P|}$

${\displaystyle a(P)\leq |P|}$

이다.

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

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

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

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

증명

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

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

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

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

이다.

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

딜워스의 정리

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

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

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

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

1의 경우, ${\displaystyle a\leq b}$인 ${\displaystyle a\in \operatorname {min\,elem} (P)}$와 ${\displaystyle b\in \operatorname {max\,elem} (P)}$를 찾을 수 있다. (그렇지 아니하다면 크기가 ${\displaystyle \operatorname {width} P}$보다 더 큰 반사슬이 존재하게 되기 때문이다.) ${\displaystyle P\setminus \{a,b\}}$의 최소 사슬 분할

${\displaystyle P\setminus \{a,b\}=\bigsqcup _{i=1}^{c(P\setminus \{a,b\})}C_{i}}$

이 주어졌을 때

${\displaystyle P=\{a,b\}\sqcup \bigsqcup _{i=1}^{c(P\setminus \{a,b\})}C_{i}}$

는 ${\displaystyle P}$의 사슬 분할이므로, ${\displaystyle P\setminus \{a,b\}}$에 딜워스의 정리를 적용하면

${\displaystyle c(P)\leq c(P\setminus \{a,b\})+1=\operatorname {width} (P\setminus \{a,b\})+1=\operatorname {width} P}$

이다.

2의 경우, 다음과 같은 두 부분 집합 ${\displaystyle A_{\pm }\subsetneq P}$를 정의하자.

${\displaystyle A_{+}=\{x\in P\colon \exists a\in A\colon x\geq a\}}$

${\displaystyle A_{-}=\{x\in P\colon \exists a\in A\colon x\leq a\}}$

${\displaystyle \operatorname {width} (A_{+})=\operatorname {width} (A_{-})=|A|=\operatorname {width} P}$

${\displaystyle A_{+}\subsetneq P\supsetneq A_{-}}$

${\displaystyle A_{+}\cap A_{-}=A}$

${\displaystyle A_{\pm }}$에 딜워스의 정리를 적용하여 다음과 같은 사슬 분해를 얻는다고 하자.

${\displaystyle A_{\pm }=\bigsqcup _{a\in A}C_{\pm }(a)}$

${\displaystyle \max C_{-}(a)=a=\min C_{+}(a)}$

그렇다면 ${\displaystyle P}$의 사슬 분해

${\displaystyle P=\bigsqcup _{a\in A}(C_{+}(a)\cup C_{-}(a))}$

를 얻는다. 즉,

${\displaystyle c(P)\leq |A|=\operatorname {width} P}$

가 된다.

미르스키의 정리

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

${\displaystyle P=\bigsqcup _{n=0}^{\infty }N^{-1}(n)}$

따라서 ${\displaystyle a(P)\leq \operatorname {height} (P)}$이다.

역사

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

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