반사슬 문서 원본 보기

{{위키데이터 속성 추적}}
[[순서론]]에서 '''반사슬'''(反사슬, {{llang|en|antichain|앤티체인}})은 서로 다른 두 원소가 비교될 수 없는, [[원순서 집합]]의 [[부분 집합]]이며, '''사슬'''({{llang|en|chain|체인}})은 서로 두 원소가 항상 비교될 수 있는, [[원순서 집합]]의 [[부분 집합]]이다.

== 정의 ==
[[원순서 집합]] <math>(P,\lesssim)</math>의 '''반사슬'''은 다음 조건을 만족시키는 [[부분 집합]] <math>A\subseteq P</math>이다.
* 임의의 <math>a,a'\in A</math>에 대하여, <math>a\lesssim a'</math>라면 <math>a=a'</math>이다.
[[원순서 집합]] <math>(P,\le)</math>의 '''사슬'''은 [[전순서 집합|원전순서 집합]]인 [[부분 집합]] <math>C\subset P</math>이다. 즉, 다음 조건을 만족시키는 [[부분 집합]] <math>C\subseteq P</math>이다.
* 임의의 <math>c,c'\in C</math>에 대하여, <math>c\lesssim c'</math>이거나 <math>c\gtrsim c'</math>이다.
즉, 반사슬 속의 서로 다른 두 원소는 항상 비교 불가능하며, 사슬 속의 서로 다른 두 원소는 항상 비교 가능하다.

=== 극대 사슬과 극대 반사슬 ===
[[원순서 집합]] <math>(P,\lesssim)</math>의 사슬들의 집합과 반사슬들의 집합은 각각 [[부분 집합]] 관계에 따라 [[부분 순서 집합]]을 이룬다. 이에 대하여 극대인 (반)사슬 (즉, 더 큰 반사슬에 포함되지 않는 (반)사슬)을 '''극대 (반)사슬'''(極大(反)사슬, {{llang|en|maximal (anti-) chain}})이라고 한다.

=== 높이와 너비 ===
[[원순서 집합]] <math>(P,\lesssim)</math>의 '''높이'''({{llang|en|height}}) <math>\operatorname{height}P</math>는 <math>P</math> 속의 사슬의 [[집합의 크기|크기]]의 [[상한]]이다. 마찬가지로, [[원순서 집합]] <math>(P,\lesssim)</math>의 '''너비'''({{llang|en|width}}) <math>\operatorname{width}P</math>는 <math>P</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\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>
이다.

'''딜워스 정리'''(Dilworth定理, {{llang|en|Dilworth’s theorem}}) 및 '''미르스키 정리'''(Мирский定理, {{llang|en|Mirsky’s theorem}})에 따르면, 만약 <math>P</math>의 너비 또는 높이가 유한하다면 위 부등식들이 포화된다. 즉, '''딜워스 정리'''에 따르면, 만약 [[부분 순서 집합]] <math>(P,\le)</math>의 너비가 유한하다면, 이는 <math>c(P)</math>와 같다.<ref name="윤영진"/>{{rp|303}} 반대로,  '''미르스키 정리'''에 따르면, 만약 <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>

=== 그린-클라이트먼 정리 ===
딜워스 정리와 미르스키 정리는 다음과 같이 '''그린-클라이트먼 정리'''(Greene-Kleitman定理, {{llang|en|Greene–Kleitman theorem}})로 일반화된다.

[[부분 순서 집합]] <math>P</math>를 사슬로 다음과 같이 [[집합의 분할|분할]]하였다고 하자.
:<math>P=\bigsqcup_{C\in\mathcal C}C</math>
또한, <math>P</math> 위에 <math>n</math>개의 반사슬 <math>A_1,\dots,A_n</math>이 주어졌다고 하자. (이들이 [[서로소 집합|서로소]]일 필요는 없다.) 그렇다면, 각 <math>C\in\mathcal C</math>에 대하여
:<math>C\cap\left(A_1\cup A_2\cup\cdots\cup A_n\right)\le \min\{|C|,n\}</math>
이므로, 자명하게
:<math>|A_1\cup A_2\cup\cdots\cup A_n|\le\sum_{C\in\mathcal C}\min\{|C|,n\}</math>
가 성립한다. <math>P</math>의 '''<math>n</math>-너비'''({{llang|en|<math>n</math>-width}}) <math>\operatorname{width}_n(P)</math>를 <math>n</math>개의 반사슬의 [[합집합]]의 크기의 상한으로 정의하고, <math>P</math>의 '''<math>n</math>-높이'''({{llang|en|<math>n</math>-height}}) <math>\operatorname{height}_n(P)</math>를 <math>n</math>개의 사슬의 [[합집합]]의 크기의 [[상한]]으로 정의하자. 마찬가지로, <math>c_n(P)</math>를 <math>P</math>의 사슬 분할 <math>\mathcal C</math>에 대한 <math>\textstyle\sum_{C\in\mathcal C}\min\{|C|,n\}</math>의 [[하한]]으로, <math>a_n(P)</math>를 <math>P</math>의 반사슬 분할 <math>\mathcal A</math>에 대한 <math>\textstyle\sum_{A\in\mathcal A}\min\{|A|,n\}</math>의 [[하한]]으로 정의하자. 그렇다면 위 논리에 의하여 자명하게
:<math>\operatorname{width}_nP\le c_n(P)</math>
:<math>\operatorname{height}_nP\le a_n(P)</math>
가 성립한다.

'''그린-클라이트먼 정리'''에 따르면, 만약 <math>P</math>가 유한 부분 순서 집합이라면, 위 두 부등식들이 항상 포화된다.<ref name="GK">{{저널 인용|이름=Curtis|성=Greene|이름2=Daniel J.|성2=Kleitman|제목=The structure of Sperner ''k''-families|저널=Journal of Combininatorial Theory, Series A|권=20|날짜=1976|쪽=41–68|issn=0097-3165|doi=10.1016/0097-3165(76)90077-7|언어=en}}</ref><ref name="Greene">{{저널 인용|이름=Curtis|성=Greene|제목=Some partitions associated with a partially ordered set|저널=Journal of Combininatorial Theory, Series A|권=20|날짜=1976|쪽=69–79|issn=0097-3165|doi=10.1016/0097-3165(76)90078-9|언어=en}}</ref>

딜워스 정리 · 미르스키 정리는 그린-클라이트먼 정리에서 <math>n=1</math>인 특수한 경우이다.

=== 히라구치 정리 ===
[[부분 순서 집합]] <math>(P,\le)</math>의 '''전순서 확대'''({{llang|en|totally ordered extension}})는 <math>P</math> 위에 주어진 다음과 같은 [[전순서]] <math>\le'</math>이다.
:<math>\forall a,b\in P\colon a\le b\implies a\le'b</math>
즉, <math>P</math>에 순서 관계를 추가하여 전순서로 만드는 것이다. [[부분 순서 집합]] <math>(P,\le)</math>의 '''차원'''({{llang|en|dimension}}) <math>\dim P</math>는 다음 조건을 만족시키는 전순서 확대의 집합 <math>\{\le_1,\dots,\le_k\}</math>의 최소 크기이다.
:<math>\forall a,b\in P\colon a\le b\iff (a\le_1b\land a\le_2b\land\cdots\land a\le_kb)</math>
(여기서 <math>\land</math>는 [[논리합]]이다.) 모든 부분 순서 집합은 하나 이상의 전순서 확대를 갖는다.

'''히라구치 정리'''에 의하면, <math>\dim P\le c(P)</math>이다.<ref name="Hiraguchi">{{저널 인용|이름=Toshio|성=Hiraguchi|제목=On the dimension of partially ordered sets|저널=金沢大学理科報告|권=1|날짜=1951-06|쪽= 77–94|url=http://hdl.handle.net/2297/33696|언어=en}}</ref>{{rp|82, (3.3)}} 만약 <math>P</math>의 너비가 유한하다면, 딜워스 정리에 의하여 <math>\dim P\le\operatorname{width}P</math>가 된다.

== 예 ==
[[공집합]]은 항상 자명하게 사슬이자 반사슬이다.

=== 전순서 집합 ===
[[전순서 집합]]의 반사슬은 [[공집합]]이거나 아니면 하나의 원소만을 갖는 집합이다. [[부분 순서 집합]] <math>(P,\le)</math>에 대하여 다음 세 조건이 서로 [[동치]]이다.
* <math>P</math>는 [[전순서 집합]]이다.
* <math>P</math>는 스스로 속의 사슬을 이룬다.
* <math>P</math>의 너비는 <math>\operatorname{width}P=\min\{1,|P|\}</math>이다.
만약 <math>P</math>가 유한 부분 순서 집합이라면 다음 두 조건이 서로 [[동치]]이다.
* <math>P</math>는 [[전순서 집합]]이다.
* <math>P</math>의 높이는 <math>\operatorname{height}P=|P|</math>이다.

=== 멱집합 ===
{{본문|슈페르너의 정리}}
[[집합]] <math>S</math>의 [[멱집합]] <math>\mathcal P(S)</math>은 포함 관계에 대하여 [[부분 순서 집합]](사실 [[불 대수]])를 이룬다. <math>\mathcal P(S)</math> 속의 반사슬을 '''슈페르너 족'''(Sperner族, {{llang|en|Sperner family}})이라고 한다.

크기가 <math>n</math>인 [[유한 집합]]의 슈페르너 족의 수는 '''데데킨트 수'''({{llang|en|Dedekind number}})라고 하며, 다음과 같다. (<math>n=0,1,2,\dots</math>)
:2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, … {{OEIS|A372}}

<math>S</math>의 [[멱집합]] <math>\mathcal P(S)</math>의 높이는 <math>S</math>의 [[집합의 크기|크기]]와 같다.
:<math>\operatorname{height}\mathcal P(S)=|S|</math>
'''[[슈페르너의 정리]]'''에 따르면, 만약 <math>S</math>가 [[유한 집합]]일 때, <math>\mathcal P(S)</math>의 너비는 다음과 같다.
:<math>\operatorname{width}\mathcal P(S)=\binom{|S|}{\lfloor|S|/2\rfloor}</math>

=== 대수 구조 ===
[[추상대수학]]에서는 각종 [[대수 구조]]로부터 정의되는 [[부분 순서 집합]]의 높이가 널리 사용된다.

[[환론]]에서, [[가군]] <math>M</math>의 [[부분 가군]] [[격자 (순서론)|격자]] <Math>\operatorname{Sub}(M)</math>의 높이 빼기 1은 <math>M</math>의 '''[[가군의 길이|길이]]''' <math>\operatorname{length}M</math>라고 한다.
:<math>\operatorname{length}M=\operatorname{height}(\operatorname{Sub}(M))-1</math>

[[가환환]] <math>R</math>의 [[소 아이디얼]]들의 [[부분 순서 집합]] <math>(\operatorname{Spec}R,\subseteq)</math>의 높이 빼기 1은 <math>R</math>의 '''[[크룰 차원]]''' <math>\dim R</math>이라고 한다.
:<math>\dim R=\operatorname{height}(\operatorname{Spec}R,\subseteq)-1</math>
[[가환환]] <math>R</math>의 [[소 아이디얼]] <math>\mathfrak p</math> 속에 포함된 소 아이디얼들의 [[부분 순서 집합]]
:<math>\operatorname{Spec}R_{\mathfrak p}\cong\{\mathfrak p'\in\operatorname{Spec}R\colon p'\subseteq\mathfrak p\}</math>
의 높이 빼기 1은 <math>\mathfrak p</math>의 '''[[아이디얼의 높이|높이]]''' <math>\operatorname{ht}\mathfrak p</math>라고 한다.
:<math>\operatorname{ht}\mathfrak p=\operatorname{height}(\operatorname{Spec}R_{\mathfrak p})-1=\operatorname{height}\{\mathfrak p'\in\operatorname{Spec}R\colon p'\subsetneq\mathfrak p\}</math>

[[최소 원소]]를 갖는 사슬이 항상 [[유한 집합]]인 [[부분 순서 집합]]은 '''[[오름 사슬 조건]]'''을 만족시킨다고 하고, 반대로 [[최대 원소]]를 갖는 사슬이 항상 [[유한 집합]]인 [[부분 순서 집합]]은 '''[[내림 사슬 조건]]'''을 만족시킨다고 한다. 이 조건들은 [[뇌터 환]] · [[아르틴 환]]과 같은 중요한 개념들을 정의하는 데 쓰인다.

== 역사 ==
1897년에 [[리하르트 데데킨트]]는 데데킨트 수를 정의하였다.<ref>{{저널 인용
 | last = Dedekind | first = Richard | author-link = 리하르트 데데킨트
 | 제목 = Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler
 | 저널=Festschrift der Technischen Hochschule Braunschweig | 날짜 = 1897|언어=de}}</ref> 이후 1928년에 에마누엘 슈페르너({{llang|en|Emanuel Sperner}})는 [[멱집합]]의 너비를 계산하였다 ([[슈페르너의 정리]]).<ref>{{저널 인용
 | last = Sperner | first = Emanuel
 | title =  Ein Satz über Untermengen einer endlichen Menge
 | journal = Mathematische Zeitschrift
 | volume = 27 | issue = 1 | 날짜 = 1928
 | doi = 10.1007/BF01171114
 | pages = 544–548 | jfm = 54.0090.06 |언어=de}}</ref>

딜워스 정리는 [[미국]]의 수학자 로버트 파머 딜워스({{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|ja|平口 俊夫}})가 1951년에 증명하였다.<ref name="Hiraguchi"/>{{rp|82, (3.3)}}

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

그린-클라이트먼 정리는 커티스 그린({{llang|en|Curtis Greene}})과 대니얼 클라이트먼({{llang|en|Daniel J. Kleitman}})이 증명하였다.<ref name="GK"/><ref name="Greene"/>

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

== 외부 링크 ==
* {{eom|title=Chain}}
* {{eom|title=Anti-chain}}
* {{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}}
* {{eom|title=Sperner property}}
* {{매스월드|id=Antichain|title=Antichain}}
* {{매스월드|id=Chain|title=Chain}}
* {{매스월드|id=PartialOrderWidth|title=Partial order width}}
* {{매스월드|id=PartialOrderLength|title=Partial order length}}
* {{매스월드|id=DilworthsLemma|title=Dilworth's lemma}}

[[분류:순서론]]
[[분류:조합적 집합론]]