반사슬

순서론에서 **반사슬**(反사슬, 앤티체인)은 서로 다른 두 원소가 비교될 수 없는, 원순서 집합의 부분 집합이며, **사슬**(체인)은 서로 두 원소가 항상 비교될 수 있는, 원순서 집합의 부분 집합이다.
# 정의
원순서 집합 (P,\lesssim)의 **반사슬**은 다음 조건을 만족시키는 부분 집합 A\subseteq P이다. * 임의의 a,a'\in A에 대하여, a\lesssim a'라면 a=a'이다. 원순서 집합 (P,\le)의 **사슬**은 원전순서 집합인 부분 집합 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)\le|P| :a(P)\le|P| 이다. 부분 순서 집합 (P,\le) 속의 사슬 C\subseteq P 및 반사슬 A\subseteq P에 대하여 |A\cap C|\le1이다. 따라서, 만약 P를 사슬 \\{C_i\\}_{i\in I}들로 분할하였을 때, 각 반사슬 A\subseteq P에 대하여 |C_i\cap A|\le 1이므로 |A|\le|I|이며, 즉 :\operatorname{width}P\le c(P) 이다.303 반대로, 만약 P를 반사슬 \\{A_j\\}_{j\in J}들로 분할하였을 때, 각 사슬 C\subseteq P에 대하여 |C\cap A_j|\le 1이므로 |C|\le|J|이며, 즉 :\operatorname{height}P\le a(P) 이다. **딜워스 정리**(Dilworth定理, Dilworth’s theorem) 및 **미르스키 정리**(Мирский定理, Mirsky’s theorem)에 따르면, 만약 P의 너비 또는 높이가 유한하다면 위 부등식들이 포화된다. 즉, **딜워스 정리**에 따르면, 만약 부분 순서 집합 (P,\le)의 너비가 유한하다면, 이는 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) 이 정리들은 무한한 너비 또는 높이의 부분 순서 집합에 대하여 기수로서 성립하지 않는다.언어=en
## 그린-클라이트먼 정리
딜워스 정리와 미르스키 정리는 다음과 같이 **그린-클라이트먼 정리**(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)\le \min\\{|C|,n\\} 이므로, 자명하게 :|A_1\cup A_2\cup\cdots\cup A_n|\le\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}_nP\le c_n(P) :\operatorname{height}_nP\le a_n(P) 가 성립한다. **그린-클라이트먼 정리**에 따르면, 만약 P가 유한 부분 순서 집합이라면, 위 두 부등식들이 항상 포화된다.언어=en언어=en 딜워스 정리 · 미르스키 정리는 그린-클라이트먼 정리에서 n=1인 특수한 경우이다.
## 히라구치 정리
부분 순서 집합 (P,\le)의 **전순서 확대**(totally ordered extension)는 P 위에 주어진 다음과 같은 전순서 \le'이다. :\forall a,b\in P\colon a\le b\implies a\le'b 즉, P에 순서 관계를 추가하여 전순서로 만드는 것이다. 부분 순서 집합 (P,\le)의 **차원**(dimension) \dim P는 다음 조건을 만족시키는 전순서 확대의 집합 \\{\le_1,\dots,\le_k\\}의 최소 크기이다. :\forall a,b\in P\colon a\le b\iff (a\le_1b\land a\le_2b\land\cdots\land a\le_kb) (여기서 \land는 논리합이다.) 모든 부분 순서 집합은 하나 이상의 전순서 확대를 갖는다. **히라구치 정리**에 의하면, \dim P\le c(P)이다.언어=en82, (3.3) 만약 P의 너비가 유한하다면, 딜워스 정리에 의하여 \dim P\le\operatorname{width}P가 된다.
# 예
공집합은 항상 자명하게 사슬이자 반사슬이다.
## 전순서 집합
전순서 집합의 반사슬은 공집합이거나 아니면 하나의 원소만을 갖는 집합이다. 부분 순서 집합 (P,\le)에 대하여 다음 세 조건이 서로 동치이다. * 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, … 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년에 리하르트 데데킨트는 데데킨트 수를 정의하였다.언어=de 이후 1928년에 에마누엘 슈페르너(Emanuel Sperner)는 멱집합의 너비를 계산하였다 (슈페르너의 정리).언어=de 딜워스 정리는 미국의 수학자 로버트 파머 딜워스(Robert Palmer Dilworth, 1914~1993)가 1950년 논문에서 처음 제시하였다.언어=ko303언어=en 히라구치 정리는 히라구치 도시오(平口 俊夫)가 1951년에 증명하였다.82, (3.3) 미르스키 정리는 러시아 태생의 영국 수학자 레오니트 미르스키(Леони́д Ми́рский, Leonid Mirsky, 1918~1983)가 1971년에 증명하였다.언어=en 그린-클라이트먼 정리는 커티스 그린(Curtis Greene)과 대니얼 클라이트먼(Daniel J. Kleitman)이 증명하였다.