반사슬
"오늘의AI위키" 는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다."오늘의AI위키" 의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차 보기/숨기기
2. 정의
원순서 집합 (P,\lesssim) 에서, 반사슬 (antichain영어 )은 서로 비교 불가능한 원소들로 이루어진 부분 집합 A \subseteq P 를 말한다. 즉, 반사슬에 속하는 서로 다른 두 원소 a, a' \in A 에 대해서는 a \lesssim a' 관계도, a' \lesssim a 관계도 성립하지 않는다.사슬 (chain영어 )은 전순서 집합 을 이루는 부분 집합 C \subseteq P 를 의미하며, 사슬에 속하는 임의의 두 원소 c, c' \in C 는 항상 비교 가능하다. 즉, c \lesssim c' 이거나 c' \lesssim c 이다.부분 순서 집합 이론의 기본적인 구성 요소이며, 집합의 구조를 분석하는 데 중요한 도구로 사용된다. 관련된 주요 개념으로는 특정 조건을 만족하는 가장 큰 (반)사슬을 의미하는 '''극대 (반)사슬'''(maximal (anti-)chain영어 ), 그리고 부분 순서 집합의 구조적 크기를 나타내는 '''높이'''(height영어 )와 '''너비'''(width영어 ) 등이 있다.
2. 1. 반사슬과 사슬
원순서 집합 (P,\lesssim) 에서 반사슬 (Antichain)은 다음 조건을 만족시키는 부분 집합 A\subseteq P 를 의미한다.임의의 a,a'\in A 에 대하여, a\lesssim a' 라면 a=a' 이다. a, a' \in A 에 대해 a \not\lesssim a' 이고 a' \not\lesssim a 이다.원순서 집합 (P,\lesssim) 에서 사슬 (Chain)은 전순서 집합 을 이루는 부분 집합 C\subseteq P 를 의미한다. 즉, 다음 조건을 만족시키는 부분 집합 C\subseteq P 이다.임의의 두 원소 c,c'\in C 에 대하여, c\lesssim c' 이거나 c'\lesssim c 이다. 즉, 사슬에 속하는 임의의 두 원소는 항상 비교 가능하다. 부분 순서 집합 (S, \le) 가 주어졌을 때, 두 원소 a, b \in S 는 a \le b 또는 b \le a 일 경우 비교 가능 하다고 한다. 만약 a \not\le b이고 b \not\le a이면, 두 원소는 비교 불가능 하다고 한다.S 의 사슬은 모든 원소 쌍이 비교 가능한 부분 집합 C \subseteq S 이며, 반사슬은 모든 서로 다른 원소 쌍이 비교 불가능한 부분 집합 A \subseteq S 이다.poset 의 원소가 없는 부분 집합을 의미한다.)2. 2. 극대 사슬과 극대 반사슬
원순서 집합 (P,\lesssim) 에서 사슬들의 집합과 반사슬들의 집합은 각각 부분 집합 관계에 따라 부분 순서 집합 을 이룬다. 이 중에서 극대 원소, 즉 다른 더 큰 (반)사슬에 포함되지 않는 (반)사슬을 '''극대 (반)사슬'''(maximal (anti-) chain영어 )이라고 한다.S 가 주어졌을 때, 두 원소 a 와 b 가 a \leq b \text{ 또는 } b \leq a 관계를 만족하면 비교 가능하다고 한다. 반대로, x \leq y 도 아니고 y \leq x 도 아닌 경우, 원소 x 와 y 는 비교 불가능하다고 한다.S 의 사슬(chain)은 임의의 두 원소가 서로 비교 가능한 부분 집합 C \subseteq S 이다. 즉, 사슬 C 는 그 자체로 전순서 집합 이다. 반면, S 의 반사슬(antichain)은 임의의 서로 다른 두 원소가 서로 비교 불가능한 부분 집합 A \subseteq S 이다. 즉, 반사슬 A 내의 서로 다른 두 원소 사이에는 순서 관계가 존재하지 않는다. (일부 문헌에서는 "반사슬"이라는 용어를 강한 반사슬을 지칭하는 데 사용하기도 하는데, 이는 반사슬 내 서로 다른 두 원소보다 작은 원소가 부분 순서 집합 내에 존재하지 않는 특별한 경우를 의미한다.)크기 (원소의 개수)가 다른 어떤 반사슬보다 크거나 같은 반사슬이다. 부분 순서 집합의 너비(width)는 최대 반사슬의 크기로 정의된다. 모든 반사슬은 어떤 사슬과도 최대 하나의 원소만을 공유할 수 있다. 따라서 만약 어떤 부분 순서 집합의 원소들을 k 개의 사슬로 분할할 수 있다면, 그 집합의 너비는 최대 k 이다. 만약 너비가 k 보다 큰 반사슬이 존재한다면, 비둘기집 원리 에 의해 적어도 두 개의 원소가 같은 사슬에 속하게 되어 모순이 발생하기 때문이다. Dilworth의 정리 는 이 상한선이 항상 달성 가능함을 보여준다. 즉, 항상 사슬의 개수가 최대 반사슬의 크기(너비)와 같도록 원소들을 사슬로 분할하는 방법이 존재한다.2. 3. 높이와 너비
원순서 집합 (P,\lesssim) 의 '''높이'''(height영어 ) \operatorname{height}P 는 P 속의 사슬의 크기 의 상한이다. 마찬가지로, 원순서 집합 (P,\lesssim) 의 '''너비'''(width영어 ) \operatorname{width}P 는 P 속의 반사슬의 크기 의 상한이다.부분 순서 집합 S 가 주어졌을 때, 부분 순서 집합의 두 원소 a 와 b 는 a \leq b \text{ 또는 } b \leq a 일 경우 '''비교 가능'''하다고 한다. 두 원소가 비교 가능하지 않으면 '''비교 불가능'''하다고 한다. 즉, x 와 y 는 x \leq y \text{ 도 아니고 } y \leq x 도 아닌 경우 비교 불가능하다.S 의 '''사슬'''(chain영어 )은 각 원소 쌍이 비교 가능한 부분 집합 C \subseteq S 이다. 즉, C 는 전순서 집합 이다. S 의 '''반사슬'''(antichain영어 )은 서로 다른 각 원소 쌍이 비교 불가능한 S 의 부분 집합 A 이다. 즉, A 의 서로 다른 두 원소 사이에는 순서 관계가 없다. (그러나 일부 저자는 "반사슬"이라는 용어를 강한 반사슬을 의미하는 데 사용하는데, 강한 반사슬은 반사슬의 서로 다른 두 원소보다 작은 poset 의 원소가 없는 부분 집합을 의미한다.)기수 를 갖는 반사슬이다. 부분 순서 집합의 '''너비'''는 최대 반사슬의 기수이다. 모든 반사슬은 어떤 사슬과도 최대 하나의 원소에서 교차할 수 있으므로, 순서의 원소를 k 개의 사슬로 분할할 수 있다면, 순서의 너비는 최대 k 여야 한다(만약 반사슬이 k 개 이상의 원소를 갖는다면, 비둘기집 원리 에 의해 같은 사슬에 속하는 2개의 원소가 존재하게 되므로 모순). Dilworth의 정리에 따르면 이 경계는 항상 도달할 수 있다. 즉, 반사슬과 원소를 사슬로 분할하는 방법이 항상 존재하여, 사슬의 개수가 반사슬의 원소 개수와 같고, 따라서 너비와 같아야 한다. 마찬가지로 부분 순서의 '''높이'''를 사슬의 최대 기수로 정의할 수 있다. Mirsky의 정리에 따르면, 유한한 높이를 갖는 모든 부분 순서에서, 높이는 순서를 분할할 수 있는 가장 작은 반사슬의 개수와 같다.
3. 성질
부분 순서 집합 에서 사슬과 반사슬은 중요한 개념이다. 어떤 부분 순서 집합 P 가 주어졌을 때, 이 집합을 여러 개의 사슬 또는 반사슬로 분할 하는 방법을 고려할 수 있다. 이때, 집합의 구조적 특징을 나타내는 여러 성질들이 존재한다.딜워스의 정리 는 부분 순서 집합의 너비 (width영어 , 가장 큰 반사슬의 크기)가 유한할 경우, 그 너비는 해당 집합을 분할하는 데 필요한 최소 사슬의 개수와 같다는 것을 말한다.높이 (height영어 , 가장 큰 사슬의 크기)가 유한할 경우, 그 높이는 해당 집합을 분할하는 데 필요한 최소 반사슬의 개수와 같다는 정리이다. 이 두 정리는 유한한 너비 또는 높이를 가진 부분 순서 집합의 기본적인 관계를 설명하지만, 무한 집합에 대해서는 성립하지 않을 수 있다.영어 )를 통해 더 일반화될 수 있다.n=1 )로 볼 수 있다.영어 ) 개념과 관련된 '''히라구치 정리'''가 있다. 이 정리는 부분 순서 집합의 차원이 특정 조건(최소 사슬 분할 크기)보다 작거나 같음을 보여준다.\dim P\le\operatorname{width}P ).
3. 1. 딜워스 정리와 미르스키 정리
임의의 부분 순서 집합 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) 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’s theorem영어 ) 및 '''미르스키 정리'''(Mirsky’s theorem영어 )에 따르면, 만약 P 의 너비 또는 높이가 유한하다면 위 부등식들이 등식이 된다. 즉, '''딜워스 정리'''에 따르면, 만약 부분 순서 집합 (P,\le) 의 너비가 유한하다면, 이는 c(P) 와 같다.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) 기수 로서 성립하지 않는다.너비 는 최대 반사슬의 기수이다. 모든 반사슬은 어떤 사슬과도 최대 하나의 원소에서 교차할 수 있으므로, 순서의 원소를 k 개의 사슬로 분할할 수 있다면, 순서의 너비는 최대 k 여야 한다(만약 반사슬이 k 개 이상의 원소를 갖는다면, 비둘기집 원리 에 의해 같은 사슬에 속하는 2개의 원소가 존재하게 되므로 모순이다). 딜워스의 정리 에 따르면 이 경계는 항상 도달할 수 있다. 즉, 반사슬과 원소를 사슬로 분할하는 방법이 항상 존재하여, 사슬의 개수가 반사슬의 원소 개수와 같고, 따라서 너비와 같아야 한다. 마찬가지로 부분 순서의 높이 를 사슬의 최대 기수로 정의할 수 있다. 미르스키 정리에 따르면, 유한한 높이를 갖는 모든 부분 순서에서, 높이는 순서를 분할할 수 있는 가장 작은 반사슬의 개수와 같다.3. 2. 그린-클라이트먼 정리
딜워스 정리와 미르스키 정리는 다음과 같이 '''그린-클라이트먼 정리'''(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\3. 3. 히라구치 정리
부분 순서 집합 (P,\le) 의 '''전순서 확대'''(totally ordered extension|eng )는 P 위에 주어진 다음과 같은 전순서 \le' 이다.\forall a,b\in P\colon a\le b\implies a\le'b P 에 순서 관계를 추가하여 전순서로 만드는 것이다. 부분 순서 집합 (P,\le) 의 '''차원'''(dimension|eng ) \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 는 논리곱 이다.) 모든 부분 순서 집합은 하나 이상의 전순서 확대를 갖는다.P 에 대하여 그 차원은 비교 불가능한 원소 쌍의 수 c(P) 보다 작거나 같다. 즉, \dim P\le c(P) 이다.P 의 너비가 유한하다면, 딜워스 정리 에 의하여 \dim P\le\operatorname{width}P 가 된다.
4. 예시
공집합 은 항상 자명하게 사슬이자 반사슬이다.전순서 집합 의 경우, 반사슬은 공집합 이거나 원소 하나만을 포함하는 집합이다. 이는 전순서 집합의 모든 원소 쌍은 서로 비교 가능하기 때문이다.멱집합 은 포함 관계를 순서 관계로 가질 때 부분 순서 집합 을 이루며, 여기서의 반사슬(특히 슈페르너 족)은 조합론적으로 중요한 의미를 가진다. 예를 들어, 크기가 n 인 유한 집합 의 멱집합에서 서로 다른 반사슬(슈페르너 족)의 개수는 '''데데킨트 수'''(Dedekind number|데데킨트 수eng )라고 한다. n=0, 1, 2, \dots 에 대한 데데킨트 수는 다음과 같다.
4. 1. 전순서 집합
전순서 집합 에서 반사슬은 공집합 이거나 하나의 원소만을 갖는 집합이다. 이는 전순서 집합의 모든 원소 쌍은 서로 비교 가능하기 때문이다.부분 순서 집합 (P,\le) 에 대하여 다음 세 조건은 서로 동치 이다. 즉, 하나가 참이면 나머지 둘도 반드시 참이 된다.P 는 전순서 집합 이다.P 는 스스로 사슬을 이룬다. (집합 내의 모든 원소가 서로 비교 가능하다는 의미이다.)P 의 너비(가장 큰 반사슬의 크기)는 \operatorname{width}P=\min\{1,|P|\} 이다. (집합에 원소가 하나라도 있다면 너비는 1이라는 의미이다.)P 가 유한 부분 순서 집합 이라면, 다음 두 조건 역시 서로 동치 이다.P 는 전순서 집합 이다.P 의 높이(가장 긴 사슬의 길이)는 \operatorname{height}P=|P| 이다. (집합의 모든 원소가 하나의 사슬을 이룬다는 의미이다.)4. 2. 멱집합
집합 S 의 멱집합 \mathcal P(S) 은 포함 관계에 대하여 부분 순서 집합 (사실 불 대수 )을 이룬다. \mathcal P(S) 속의 반사슬을 '''슈페르너 족'''(Sperner family영어 )이라고 한다.n 인 유한 집합 의 슈페르너 족의 수는 '''데데킨트 수'''(Dedekind number영어 )라고 하며, n=0,1,2,\dots 에 대해 다음과 같다.S 의 멱집합 \mathcal P(S) 의 높이는 S 의 크기 와 같다.\operatorname{height}\mathcal P(S)=|S| 슈페르너의 정리 '''에 따르면, 만약 S 가 유한 집합 일 때, \mathcal P(S) 의 너비 는 다음과 같다.\operatorname{width}\mathcal P(S)=\binom{\lfloor|S|/2\rfloor}S 가 주어졌을 때, 부분 순서 집합의 두 원소 a 와 b 는 a \leq b \text{ 또는 } b \leq a 일 경우 비교 가능하다고 한다. 두 원소가 비교 가능하지 않으면 비교 불가능하다고 한다. 즉, x 와 y 는 x \leq y \text{ 도 아니고 } y \leq x 도 아닌 경우 비교 불가능하다.S 의 사슬(chain)은 각 원소 쌍이 비교 가능한 부분 집합 C \subseteq S 이다. 즉, C 는 전순서 집합이다. S 의 반사슬(antichain)은 서로 다른 각 원소 쌍이 비교 불가능한 S 의 부분 집합 A 이다. 즉, A 의 서로 다른 두 원소 사이에는 순서 관계가 없다. (그러나 일부 저자는 "반사슬"이라는 용어를 강한 반사슬을 의미하는 데 사용하는데, 강한 반사슬은 반사슬의 서로 다른 두 원소보다 작은 poset 의 원소가 없는 부분 집합을 의미한다.)기수 를 갖는 반사슬이다. 부분 순서 집합의 너비 는 최대 반사슬의 기수이다. 모든 반사슬은 어떤 사슬과도 최대 하나의 원소에서 교차할 수 있으므로, 순서의 원소를 k 개의 사슬로 분할할 수 있다면, 순서의 너비는 최대 k 여야 한다(만약 반사슬이 k 개 이상의 원소를 갖는다면, 비둘기집 원리 에 의해 같은 사슬에 속하는 2개의 원소가 존재하게 되므로 모순). Dilworth의 정리에 따르면 이 경계는 항상 도달할 수 있다. 즉, 너비는 순서를 분할할 수 있는 최소 사슬의 개수와 같다. 마찬가지로 부분 순서의 높이 를 사슬의 최대 기수로 정의할 수 있다. Mirsky의 정리에 따르면, 유한한 높이를 갖는 모든 부분 순서에서, 높이는 순서를 분할할 수 있는 가장 작은 반사슬의 개수와 같다.n 개의 원소를 가진 집합의 부분 집합 포함 관계에서 반사슬은 스페르너 집합으로 알려져 있다. 공집합의 멱집합조차도 두 개의 반사슬을 갖는다. 하나는 공집합 자체만을 원소로 갖는 집합({∅})이고, 다른 하나는 원소가 없는 집합(∅)이다.4. 3. 대수 구조
추상대수학 에서는 다양한 대수 구조 로부터 정의되는 부분 순서 집합 의 높이 개념이 중요하게 활용된다.환론 에서, 가군 M 의 부분 가군들이 이루는 격자 \operatorname{Sub}(M) 의 높이에서 1을 뺀 값은 M 의 '''길이 '''(length) \operatorname{length}M 라고 정의한다.\operatorname{length}M = \operatorname{height}(\operatorname{Sub}(M)) - 1 가환환 R 의 소 아이디얼 들의 부분 순서 집합 (\operatorname{Spec}R, \subseteq) 의 높이에서 1을 뺀 값은 R 의 '''크룰 차원 '''(Krull dimension) \dim R 이라고 한다. 여기서 \operatorname{Spec}R 은 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 \mathfrak p' \subseteq \mathfrak p\} \mathfrak p 의 '''높이'''(height) \operatorname{ht}\mathfrak p 라고 정의한다. 이는 \mathfrak p 아래에 얼마나 많은 소 아이디얼들이 연쇄적으로 포함될 수 있는지를 나타낸다.\operatorname{ht}\mathfrak p = \operatorname{height}(\operatorname{Spec}R_{\mathfrak p}) - 1 = \operatorname{height}\{\mathfrak p' \in \operatorname{Spec}R \colon \mathfrak p' \subsetneq \mathfrak p\} 유한 집합 일 때 이 부분 순서 집합은 '''오름 사슬 조건'''(ascending chain condition, ACC)을 만족시킨다고 한다. 반대로, 최대 원소를 갖는 모든 사슬이 항상 유한 집합 일 때 '''내림 사슬 조건'''(descending chain condition, DCC)을 만족시킨다고 한다. 이 두 조건은 각각 뇌터 환 과 아르틴 환 과 같은 중요한 대수적 구조를 정의하는 데 핵심적인 역할을 한다.
5. 역사
1897년에 리하르트 데데킨트 는 데데킨트 수를 정의하였다.eng )는 멱집합 의 너비를 계산하였다 (슈페르너의 정리 ).미국 의 수학자 로버트 파머 딜워스(Robert Palmer Dilwortheng , 1914~1993)가 1950년 논문에서 처음 제시하였다.jpn )가 1951년에 증명하였다.rus , Leonid Mirskyeng , 1918~1983)가 1971년에 증명하였다.eng )과 대니얼 클라이트먼(Daniel J. Kleitmaneng )이 증명하였다.
6. 계산 복잡도
주어진 부분 순서 집합 에서 가장 큰 반사슬(최대 반사슬)을 찾는 문제, 그리고 그 크기(부분 순서 집합의 너비)를 알아내는 문제는 다항 시간 안에 해결할 수 있다. 반면, 주어진 부분 순서 집합에 포함된 모든 반사슬의 개수를 세는 문제는 #P-완전 문제로 알려져 있어 계산적으로 훨씬 더 어렵다.
참조
[1]
저널
On Dilworth’s theorem in the infinite case
1963
[2]
저널
1976
[3]
저널
1976
[4]
저널
http://hdl.handle.ne[...]
1951-06
[5]
저널
1897
[6]
저널
Ein Satz über Untermengen einer endlichen Menge
1928
[7]
서적
http://www.kyowoo.co[...]
2007
[8]
저널
1950-01
[9]
저널
A dual of Dilworth’s decomposition theorem
1971
CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.help@durumis.com