반사슬

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

정의

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

• 임의의 $a,a'\in A$에 대하여, $a\not <a'$

부분 순서 집합 $(P,\leq )$의 사슬(영어: chain)은 전순서 집합인 부분 집합 $C\subset P$이다.

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

부분 순서 집합 $(P,\leq )$의 강한 하향 반사슬(強한下向反사슬, 영어: strong downward antichain)은 다음 조건을 만족시키는 부분 집합 $A\subset P$이다.

• 임의의 $a,a'\in A$에 대하여, $p\leq a,a'$인 $p\in P$가 존재하지 않는다.

부분 순서 집합 $P$의 강한 상향 반사슬(強한上向反사슬, 영어: strong upward antichain)은 $P^{\operatorname {op} }$의 강한 하향 반사슬이다. 강한 하향 반사슬 및 강한 상향 반사슬은 반사슬이지만, 그 역은 성립하지 않는다.

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

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

부분 순서 집합 $(P,\leq )$의 너비(영어: 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)\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)$

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

딜워스 정리의 증명

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

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

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

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

1의 경우, $a\leq 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)\leq 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\geq a\}$

$A_{-}=\{x\in P\colon \exists a\in A\colon x\leq 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)\leq |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)\leq \operatorname {height} (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) $:<math>\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$가 된다.

예

공집합은 항상 강한 하향 반사슬이자 강한 상향 반사슬이다.

전순서 집합의 반사슬은 공집합이거나 아니면 하나의 원소만을 갖는 집합이다. 따라서, 전순서 집합 $(T,\leq )$에 대하여,

$\operatorname {height} T=|T|$

$\operatorname {width} T={\begin{cases}0&T=\varnothing \\1&T\neq \varnothing \end{cases}}$

이다.

멱집합

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

유한 집합 $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)

슈페르너의 정리에 따르면, ${\mathcal {P}}(S)$의 너비는 다음과 같다.

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

역사

1897년에 리하르트 데데킨트는 데데킨트 수를 발견하였다. 이후 1928년에 에마누엘 슈페르너(영어: Emanuel Sperner)는 멱집합의 너비가 데데킨트 수와 같다는 사실(슈페르너의 정리)을 증명하였다.

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

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

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

바깥 고리

• “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. 
• Weisstein, Eric Wolfgang. “Antichain”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Dilworth's lemma”. 《Wolfram MathWorld》 (영어). Wolfram Research.