딜워스의 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''딜워스의 정리'''(Dilworth의定理, {{llang|en|Dilworth’s theorem}})는 [[부분 순서 집합]]의 [[반사슬]]의 최대 크기에 대한 정리다.

== 정의 ==
[[부분 순서 집합]] <math>(P,\le)</math>의 '''높이'''({{llang|en|height}})는 <math>P</math> 속의 사슬(부분 [[전순서 집합]])의 [[집합의 크기|크기]]의 [[상한]]이다. 즉, 다음과 같다.
:<math>\operatorname{height}P=\sup\left\{n\colon x_1<\cdots<x_n,\;\{x_1,\dots,x_n\}\subseteq P\right\}</math>
[[부분 순서 집합]] <math>(P,\le)</math>의 '''너비'''({{llang|en|width}})는 <math>P</math> 속의 [[반사슬]]의 [[집합의 크기|크기]]의 [[상한]]이다. 즉, 다음과 같다.
:<math>\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\}</math>
(여기서 <math>s\parallel s'</math>은 두 원소가 비교 불가능임을 뜻한다.)

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

'''딜워스의 정리'''에 따르면, 만약 [[부분 순서 집합]] <math>(P,\le)</math>의 너비가 유한하다면, 이는 <math>c(P)</math>와 같다.<ref name="윤영진"/>{{rp|303}} 반대로, '''미르스키의 정리'''({{llang|en|Mirsky’s theorem}})에 따르면, 만약 <math>P</math>의 높이가 유한하다면, 이는 <math>a(P)</math>와 같다.
:<math>\operatorname{width}P<\aleph_0\implies \operatorname{width}P=c(P)</math>
:<math>\operatorname{height}P<\aleph_0\implies \operatorname{height}P=a(P)</math>

이 정리들은 무한한 너비 또는 높이의 부분 순서 집합에 대하여 [[기수 (수학)|기수]]로서 성립하지 않는다.<ref>{{저널 인용
 | last = Perles | first = Micha Asher
 | title = On Dilworth’s theorem in the infinite case
 | mr = 0168497
 | journal=Israel Journal of Mathematics
 | 날짜 = 1963  | volume = 1 | pages = 108–109
 | doi=10.1007/BF02759806
 | issue = 2 | zbl =  0115.01703 | 언어=en}}</ref>

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

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

=== 딜워스의 정리 ===
딜워스의 정리의 증명은 [[쾨니그의 정리]]를 이용한 기법 등 여러 방법이 있다. 만약 <math>P</math>가 [[유한 집합]]일 경우, 미카 아셰르 페를레스({{llang|he|<bdi>מִיכָה אָשֵׁר פרלס</bdi>}}, 1936~)는 다음과 같은 간단한 증명을 제시하였다.<ref>{{저널 인용
 | last = Perles | first = Micha Asher
 | title = A proof of Dilworth’s theorem for partially ordered sets
 | journal=Israel Journal of Mathematics
 | 날짜 = 1963  | volume = 1 | pages = 105–107
 | doi=10.1007/BF02759805
 | issue = 2 | zbl = 0115.01702 | 언어=en}}</ref><ref name="윤영진"/>{{rp|303–304}}

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

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

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

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

== 역사 ==
딜워스의 정리는 [[미국]]의 수학자 로버트 파머 딜워스({{llang|en|Robert Palmer Dilworth}}, 1914~1993)가 1950년 논문에서 처음 제시하였다.<ref name="윤영진">{{서적 인용|저자=윤영진|제목=새로운 조합수학|출판사=교우사|날짜=2007|isbn=978-89-8172-379-8|url=http://www.kyowoo.co.kr/02_sub/view.php?p_idx=334|언어=ko}}</ref>{{rp|303}}<ref>{{저널 인용|이름=R. P.|성=Dilworth|제목=A decomposition theorem for partially ordered sets|저널=Annals of Mathematics|권=51|날짜=1950-01|쪽=161–166|jstor=1969503|zbl=0038.02003|issn=0003-486X|언어=en}}</ref>

미르스키의 정리는 러시아 태생의 영국 수학자 레오니트 미르스키({{llang|ru|Леонид Мирский}}, {{llang|en|Leonid Mirsky}}, 1918~1983)가 1971년에 증명하였다.<ref>{{저널 인용
 | last = Mirsky | first = Leon
 | title = A dual of Dilworth’s decomposition theorem
 | url = https://archive.org/details/sim_american-mathematical-monthly_1971-10_78_8/page/n45 | jstor = 2316481
 | journal = American Mathematical Monthly
 | volume = 78
 | issue = 8 | year = 1971 | pages = 876–877
 | doi = 10.2307/2316481|언어=en}}</ref>

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Length of a partially ordered set}}
* {{eom|title=Width of a partially ordered set}}
* {{eom|title=Dimension of a partially ordered set}}
* {{eom|title=Greene-Kleitman theorem}}
* {{매스월드|id=DilworthsLemma|title=Dilworth's lemma}}

== 같이 보기 ==
* [[쾨니그의 정리]]

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