반사슬

순서론에서 반사슬(反사슬, 영어: antichain 앤티체인^[*])은 서로 다른 두 원소가 비교될 수 없는, 원순서 집합의 부분 집합이며, 사슬(영어: chain 체인^[*])은 서로 두 원소가 항상 비교될 수 있는, 원순서 집합의 부분 집합이다.

정의

원순서 집합 $(P,\lesssim )$의 반사슬은 다음 조건을 만족시키는 부분 집합 $A\subseteq P$이다.

• 임의의 $a,a'\in A$에 대하여, $a\lesssim a'$라면 $a=a'$이다.

원순서 집합 $(P,\leq )$의 사슬은 원전순서 집합인 부분 집합 $C\subset P$이다. 즉, 다음 조건을 만족시키는 부분 집합 $C\subseteq P$이다.

• 임의의 $c,c'\in C$에 대하여, $c\lesssim c'$이거나 $c\gtrsim c'$이다.

즉, 반사슬 속의 서로 다른 두 원소는 항상 비교 불가능하며, 사슬 속의 서로 다른 두 원소는 항상 비교 가능하다.

극대 사슬과 극대 반사슬

원순서 집합 $(P,\lesssim )$의 사슬들의 집합과 반사슬들의 집합은 각각 부분 집합 관계에 따라 부분 순서 집합을 이룬다. 이에 대하여 극대인 (반)사슬 (즉, 더 큰 반사슬에 포함되지 않는 (반)사슬)을 극대 (반)사슬(極大(反)사슬, 영어: maximal (anti-) chain)이라고 한다.

높이와 너비

원순서 집합 $(P,\lesssim )$의 높이(영어: height) $\operatorname {height} P$는 $P$ 속의 사슬의 크기의 상한이다. 마찬가지로, 원순서 집합 $(P,\lesssim )$의 너비(영어: width) $\operatorname {width} P$는 $P$ 속의 반사슬의 크기의 상한이다.

성질

딜워스 정리와 미르스키 정리

 이 부분의 본문은 딜워스의 정리입니다.

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

$c(P)\leq |P|$

$a(P)\leq |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)$

이다.

딜워스 정리(Dilworth定理, 영어: Dilworth’s theorem) 및 미르스키 정리(Мирский定理, 영어: Mirsky’s theorem)에 따르면, 만약 $P$의 너비 또는 높이가 유한하다면 위 부등식들이 포화된다. 즉, 딜워스 정리에 따르면, 만약 부분 순서 집합 $(P,\leq )$의 너비가 유한하다면, 이는 $c(P)$와 같다.^:303 반대로, 미르스키 정리에 따르면, 만약 $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)$

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

그린-클라이트먼 정리

딜워스 정리와 미르스키 정리는 다음과 같이 그린-클라이트먼 정리(Greene-Kleitman定理, 영어: Greene–Kleitman theorem)로 일반화된다.

부분 순서 집합 $P$를 사슬로 다음과 같이 분할하였다고 하자.

$P=\bigsqcup _{C\in {\mathcal {C}}}C$

또한, $P$ 위에 $n$개의 반사슬 $A_{1},\dots ,A_{n}$이 주어졌다고 하자. (이들이 서로소일 필요는 없다.) 그렇다면, 각 $C\in {\mathcal {C}}$에 대하여

$C\cap \left(A_{1}\cup A_{2}\cup \cdots \cup A_{n}\right)\leq \min\{|C|,n\}$

이므로, 자명하게

$|A_{1}\cup A_{2}\cup \cdots \cup A_{n}|\leq \sum _{C\in {\mathcal {C}}}\min\{|C|,n\}$

가 성립한다. $P$의 $n$-너비(영어: $n$-width) $\operatorname {width} _{n}(P)$를 $n$개의 반사슬의 합집합의 크기의 상한으로 정의하고, $P$의 $n$-높이(영어: $n$-height) $\operatorname {height} _{n}(P)$를 $n$개의 사슬의 합집합의 크기의 상한으로 정의하자. 마찬가지로, $c_{n}(P)$를 $P$의 사슬 분할 ${\mathcal {C}}$에 대한 $\textstyle \sum _{C\in {\mathcal {C}}}\min\{|C|,n\}$의 하한으로, $a_{n}(P)$를 $P$의 반사슬 분할 ${\mathcal {A}}$에 대한 $\textstyle \sum _{A\in {\mathcal {A}}}\min\{|A|,n\}$의 하한으로 정의하자. 그렇다면 위 논리에 의하여 자명하게

$\operatorname {width} _{n}P\leq c_{n}(P)$

$\operatorname {height} _{n}P\leq a_{n}(P)$

가 성립한다.

그린-클라이트먼 정리에 따르면, 만약 $P$가 유한 부분 순서 집합이라면, 위 두 부등식들이 항상 포화된다.

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

히라구치 정리

부분 순서 집합 $(P,\leq )$의 전순서 확대(영어: totally ordered extension)는 $P$ 위에 주어진 다음과 같은 전순서 $\leq '$이다.

$\forall a,b\in P\colon a\leq b\implies a\leq 'b$

즉, $P$에 순서 관계를 추가하여 전순서로 만드는 것이다. 부분 순서 집합 $(P,\leq )$의 차원(영어: dimension) $\dim P$는 다음 조건을 만족시키는 전순서 확대의 집합 $\{\leq _{1},\dots ,\leq _{k}\}$의 최소 크기이다.

$\forall a,b\in P\colon a\leq b\iff (a\leq _{1}b\land a\leq _{2}b\land \cdots \land a\leq _{k}b)$

(여기서 $\land$는 논리합이다.) 모든 부분 순서 집합은 하나 이상의 전순서 확대를 갖는다.

히라구치 정리에 의하면, $\dim P\leq c(P)$이다.^{:82, (3.3)} 만약 $P$의 너비가 유한하다면, 딜워스 정리에 의하여 $\dim P\leq \operatorname {width} P$가 된다.

예

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

전순서 집합

전순서 집합의 반사슬은 공집합이거나 아니면 하나의 원소만을 갖는 집합이다. 부분 순서 집합 $(P,\leq )$에 대하여 다음 세 조건이 서로 동치이다.

• $P$는 전순서 집합이다.
• $P$는 스스로 속의 사슬을 이룬다.
• $P$의 너비는 $\operatorname {width} P=\min\{1,|P|\}$이다.

만약 $P$가 유한 부분 순서 집합이라면 다음 두 조건이 서로 동치이다.

• $P$는 전순서 집합이다.
• $P$의 높이는 $\operatorname {height} P=|P|$이다.

멱집합

 이 부분의 본문은 슈페르너의 정리입니다.

집합 $S$의 멱집합 ${\mathcal {P}}(S)$은 포함 관계에 대하여 부분 순서 집합(사실 불 대수)를 이룬다. ${\mathcal {P}}(S)$ 속의 반사슬을 슈페르너 족(Sperner族, 영어: Sperner family)이라고 한다.

크기가 $n$인 유한 집합의 슈페르너 족의 수는 데데킨트 수(영어: Dedekind number)라고 하며, 다음과 같다. ($n=0,1,2,\dots$)

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, … (OEIS의 수열 A372)

$S$의 멱집합 ${\mathcal {P}}(S)$의 높이는 $S$의 크기와 같다.

$\operatorname {height} {\mathcal {P}}(S)=|S|$

슈페르너의 정리에 따르면, 만약 $S$가 유한 집합일 때, ${\mathcal {P}}(S)$의 너비는 다음과 같다.

$\operatorname {width} {\mathcal {P}}(S)={\binom {|S|}{\lfloor |S|/2\rfloor }}$

대수 구조

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

환론에서, 가군 $M$의 부분 가군 격자 $\operatorname {Sub} (M)$의 높이 빼기 1은 $M$의 길이 $\operatorname {length} M$라고 한다.

$\operatorname {length} M=\operatorname {height} (\operatorname {Sub} (M))-1$

가환환 $R$의 소 아이디얼들의 부분 순서 집합 $(\operatorname {Spec} R,\subseteq )$의 높이 빼기 1은 $R$의 크룰 차원 $\dim R$이라고 한다.

$\dim R=\operatorname {height} (\operatorname {Spec} R,\subseteq )-1$

가환환 $R$의 소 아이디얼 ${\mathfrak {p}}$ 속에 포함된 소 아이디얼들의 부분 순서 집합

$\operatorname {Spec} R_{\mathfrak {p}}\cong \{{\mathfrak {p}}'\in \operatorname {Spec} R\colon p'\subseteq {\mathfrak {p}}\}$

의 높이 빼기 1은 ${\mathfrak {p}}$의 높이 $\operatorname {ht} {\mathfrak {p}}$라고 한다.

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

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

역사

1897년에 리하르트 데데킨트는 데데킨트 수를 정의하였다. 이후 1928년에 에마누엘 슈페르너(영어: Emanuel Sperner)는 멱집합의 너비를 계산하였다 (슈페르너의 정리).

딜워스 정리는 미국의 수학자 로버트 파머 딜워스(영어: Robert Palmer Dilworth, 1914~1993)가 1950년 논문에서 처음 제시하였다.^:303 히라구치 정리는 히라구치 도시오(일본어: 平口 俊夫)가 1951년에 증명하였다.^{:82, (3.3)}

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

그린-클라이트먼 정리는 커티스 그린(영어: Curtis Greene)과 대니얼 클라이트먼(영어: Daniel J. Kleitman)이 증명하였다.

외부 링크

• “Chain”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Anti-chain”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “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. 
• “Sperner property”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Antichain”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Chain”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Partial order width”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Partial order length”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Dilworth's lemma”. 《Wolfram MathWorld》 (영어). Wolfram Research.