반사슬

위키백과, 우리 모두의 백과사전.
(딜워스의 정리에서 넘어옴)
이동: 둘러보기, 검색

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

정의[편집]

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

  • 임의의 a,a'\in A에 대하여, a\le a'라면 a=a'

부분 순서 집합 (P,\le)사슬(영어: chain)은 전순서 집합부분 집합 C\subset P이다. 즉, 다음 조건을 만족시키는 부분 집합 C\subseteq P이다.

  • 임의의 c,c'\in A에 대하여, c\le c'이거나 c\ge c'

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

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

강한 반사슬[편집]

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

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

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

높이와 너비[편집]

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

\operatorname{height}P=\sup\left\{n\colon x_1<\cdots<x_n,\;\{x_0,\dots,x_n\}\subseteq P\right\}

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

이다.[1]: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)와 같다.[1]: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)

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

딜워스 정리의 증명[편집]

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

유한 부분 순서 집합 (P,\le)가 주어졌다고 하자. 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\le ba\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)\le 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\ge a\}
A_-=\{x\in P\colon\exists a\in A\colon x\le 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)\le|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)\le\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)\le \min\{|C|,n\}

이므로, 자명하게

|A_1\cup A_2\cup\cdots\cup A_n|\le\sum_{C\in\mathcal C}\min\{|C|,n\}

가 성립한다. Pn-너비(영어: n-width) 
:<math>\operatorname{width}_n(P)n개의 반사슬의 합집합의 크기의 상한으로 정의하고, Pn-높이(영어: 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가 유한 부분 순서 집합이라면, 위 두 부등식들이 항상 포화된다.[4][5]

딜워스 정리 · 미르스키 정리는 그린-클라이트먼 정리에서 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)이다.[6]:82, (3.3) 만약 P의 너비가 유한하다면, 딜워스 정리에 의하여 \dim P\le\operatorname{width}P가 된다.

[편집]

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

전순서 집합[편집]

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

  • P전순서 집합이다.
  • P는 스스로 속의 사슬을 이룬다.
  • P의 너비는 \operatorname{width}P=\min\{1,|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년에 리하르트 데데킨트는 데데킨트 수를 정의하였다.[7] 이후 1928년에 에마누엘 슈페르너(영어: Emanuel Sperner)는 멱집합의 너비를 계산하였다 (슈페르너의 정리).[8]

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

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

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

참고 문헌[편집]

  1. 윤영진 (2007). 《새로운 조합수학》. 교우사. ISBN 978-89-8172-379-8. 
  2. Perles, Micha Asher (1963). “On Dilworth’s theorem in the infinite case”. 《Israel Journal of Mathematics》 (영어) 1 (2): 108–109. doi:10.1007/BF02759806. MR 0168497. Zbl 0115.01703. 
  3. Perles, Micha Asher (1963). “A proof of Dilworth’s theorem for partially ordered sets”. 《Israel Journal of Mathematics》 (영어) 1 (2): 105–107. doi:10.1007/BF02759805. Zbl 0115.01702. 
  4. Greene, Curtis; Kleitman, Daniel J. (1976). “The structure of Sperner k-families”. 《Journal of Combininatorial Theory, Series A》 (영어) 20: 41–68. doi:10.1016/0097-3165(76)90077-7. ISSN 0097-3165. 
  5. Greene, Curtis (1976). “Some partitions associated with a partially ordered set”. 《Journal of Combininatorial Theory, Series A》 (영어) 20: 69–79. doi:10.1016/0097-3165(76)90078-9. ISSN 0097-3165. 
  6. Hiraguchi, Toshio (1951년 6월). “On the dimension of partially ordered sets”. 《金沢大学理科報告》 (영어) 1: 77–94. 
  7. Dedekind, Richard (1897). “Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler”. 《Festschrift der Technischen Hochschule Braunschweig》 (독일어). 
  8. Sperner, Emanuel (1928). “Ein Satz über Untermengen einer endlichen Menge”. 《Mathematische Zeitschrift》 (독일어) 27 (1): 544–548. doi:10.1007/BF01171114. JFM 54.0090.06. 
  9. Dilworth, R. P. (1950년 1월). “A decomposition theorem for partially ordered sets”. 《Annals of Mathematics》 (영어) 51: 161–166. ISSN 0003-486X. JSTOR 1969503. Zbl 0038.02003. 
  10. Mirsky, Leon (1971). “A dual of Dilworth’s decomposition theorem”. 《American Mathematical Monthly》 (영어) 78 (8): 876–877. doi:10.2307/2316481. JSTOR 2316481. 

바깥 고리[편집]