반사슬

1. 개요

반사슬은 원순서 집합의 부분 집합으로, 집합 내 임의의 두 원소가 비교 불가능한 경우를 말한다. 사슬과 반대되는 개념으로, 사슬은 전순서 집합인 부분 집합을 의미한다. 반사슬의 개념은 부분 순서 집합의 높이와 너비를 정의하는 데 사용되며, 딜워스 정리, 미르스키 정리, 그린-클라이트먼 정리, 히라구치 정리 등과 같은 정리에 중요한 역할을 한다. 반사슬은 멱집합, 대수 구조 등 다양한 수학 분야에서 활용되며, 최대 반사슬의 크기(너비)는 다항 시간 내에 찾을 수 있지만, 반사슬의 수를 세는 것은 #P-완전 문제로 알려져 있다.

2. 정의

원순서 집합 $(P,\backslash lesssim)$에서, 반사슬(antichain^영어)은 서로 비교 불가능한 원소들로 이루어진 부분 집합 $A\; \backslash subseteq\; P$를 말한다. 즉, 반사슬에 속하는 서로 다른 두 원소 $a,\; a\text{'}\; \backslash in\; A$에 대해서는 $a\; \backslash lesssim\; a\text{'}$ 관계도, $a\text{'}\; \backslash lesssim\; a$ 관계도 성립하지 않는다.

반대로, 사슬(chain^영어)은 전순서 집합을 이루는 부분 집합 $C\; \backslash subseteq\; P$를 의미하며, 사슬에 속하는 임의의 두 원소 $c,\; c\text{'}\; \backslash in\; C$는 항상 비교 가능하다. 즉, $c\; \backslash lesssim\; c\text{'}$이거나 $c\text{'}\; \backslash lesssim\; c$이다.

간단히 말해, 반사슬 속의 서로 다른 두 원소는 비교할 수 없고, 사슬 속의 서로 다른 두 원소는 항상 비교할 수 있다.

이러한 반사슬과 사슬의 개념은 부분 순서 집합 이론의 기본적인 구성 요소이며, 집합의 구조를 분석하는 데 중요한 도구로 사용된다. 관련된 주요 개념으로는 특정 조건을 만족하는 가장 큰 (반)사슬을 의미하는 극대 (반)사슬(maximal (anti-)chain^영어), 그리고 부분 순서 집합의 구조적 크기를 나타내는 높이(height^영어)와 너비(width^영어) 등이 있다.

2.1. 반사슬과 사슬

원순서 집합 $(P,\backslash lesssim)$에서 반사슬(Antichain)은 다음 조건을 만족시키는 부분 집합 $A\backslash subseteq\; P$를 의미한다.
* 임의의 $a,a\text{'}\backslash in\; A$에 대하여, $a\backslash lesssim\; a\text{'}$라면 $a=a\text{'}$이다.
이는 반사슬에 속하는 서로 다른 두 원소는 항상 비교 불가능함을 의미한다. 즉, 서로 다른 $a,\; a\text{'}\; \backslash in\; A$에 대해 $a\; \backslash not\backslash lesssim\; a\text{'}$이고 $a\text{'}\; \backslash not\backslash lesssim\; a$이다.

원순서 집합 $(P,\backslash lesssim)$에서 사슬(Chain)은 전순서 집합을 이루는 부분 집합 $C\backslash subseteq\; P$를 의미한다. 즉, 다음 조건을 만족시키는 부분 집합 $C\backslash subseteq\; P$이다.
* 임의의 두 원소 $c,c\text{'}\backslash in\; C$에 대하여, $c\backslash lesssim\; c\text{'}$이거나 $c\text{'}\backslash lesssim\; c$이다. 즉, 사슬에 속하는 임의의 두 원소는 항상 비교 가능하다.

부분 순서 집합 $(S,\; \backslash le)$가 주어졌을 때, 두 원소 $a,\; b\; \backslash in\; S$는 $a\; \backslash le\; b\; 또는$ b\; \backslash le\; a$일\; 경우$비교 가능하다고 한다. 만약 $a\; \backslash not\backslash le\; b이고$ b\; \backslash not\backslash le\; a이면,\; 두\; 원소는$$비교 불가능하다고 한다.

따라서 부분 순서 집합 $S$의 사슬은 모든 원소 쌍이 비교 가능한 부분 집합 $C\; \backslash subseteq\; S$이며, 반사슬은 모든 서로 다른 원소 쌍이 비교 불가능한 부분 집합 $A\; \backslash subseteq\; S$이다.

(참고: 일부 문헌에서는 '반사슬'이라는 용어를 강한 반사슬을 의미하는 데 사용하기도 하는데, 강한 반사슬은 반사슬의 서로 다른 두 원소보다 작은 poset의 원소가 없는 부분 집합을 의미한다.)

2.2. 극대 사슬과 극대 반사슬

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

부분 순서 집합 $S$가 주어졌을 때, 두 원소 $a$와 $b$가 $a\; \backslash leq\; b\; \backslash text\{\; 또는\; \}\; b\; \backslash leq\; a$ 관계를 만족하면 비교 가능하다고 한다. 반대로, $x\; \backslash leq\; y$도 아니고 $y\; \backslash leq\; x$도 아닌 경우, 원소 $x$와 $y$는 비교 불가능하다고 한다.

$S$의 사슬(chain)은 임의의 두 원소가 서로 비교 가능한 부분 집합 $C\; \backslash subseteq\; S$이다. 즉, 사슬 $C$는 그 자체로 전순서 집합이다. 반면, $S$의 반사슬(antichain)은 임의의 서로 다른 두 원소가 서로 비교 불가능한 부분 집합 $A\; \backslash subseteq\; S$이다. 즉, 반사슬 $A$ 내의 서로 다른 두 원소 사이에는 순서 관계가 존재하지 않는다. (일부 문헌에서는 "반사슬"이라는 용어를 강한 반사슬을 지칭하는 데 사용하기도 하는데, 이는 반사슬 내 서로 다른 두 원소보다 작은 원소가 부분 순서 집합 내에 존재하지 않는 특별한 경우를 의미한다.)

극대 반사슬은 다른 어떤 반사슬의 진부분집합도 되지 않는 반사슬을 말한다. 최대 반사슬은 그 크기(원소의 개수)가 다른 어떤 반사슬보다 크거나 같은 반사슬이다. 부분 순서 집합의 너비(width)는 최대 반사슬의 크기로 정의된다. 모든 반사슬은 어떤 사슬과도 최대 하나의 원소만을 공유할 수 있다. 따라서 만약 어떤 부분 순서 집합의 원소들을 $k$개의 사슬로 분할할 수 있다면, 그 집합의 너비는 최대 $k$이다. 만약 너비가 $k$보다 큰 반사슬이 존재한다면, 비둘기집 원리에 의해 적어도 두 개의 원소가 같은 사슬에 속하게 되어 모순이 발생하기 때문이다. Dilworth의 정리는 이 상한선이 항상 달성 가능함을 보여준다. 즉, 항상 사슬의 개수가 최대 반사슬의 크기(너비)와 같도록 원소들을 사슬로 분할하는 방법이 존재한다.

유사하게, 부분 순서 집합의 높이(height)는 가장 긴 사슬의 크기로 정의할 수 있다. Mirsky의 정리에 따르면, 유한한 높이를 갖는 모든 부분 순서 집합에서, 높이는 그 집합을 분할할 수 있는 가장 작은 반사슬의 개수와 같다.

2.3. 높이와 너비

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

부분 순서 집합 $S$가 주어졌을 때, 부분 순서 집합의 두 원소 $a$와 $b$는 $a\; \backslash leq\; b\; \backslash text\{\; 또는\; \}\; b\; \backslash leq\; a$일 경우 비교 가능하다고 한다. 두 원소가 비교 가능하지 않으면 비교 불가능하다고 한다. 즉, $x$와 $y$는 $x\; \backslash leq\; y\; \backslash text\{\; 도\; 아니고\; \}\; y\; \backslash leq\; x$도 아닌 경우 비교 불가능하다.

$S$의 사슬(chain^영어)은 각 원소 쌍이 비교 가능한 부분 집합 $C\; \backslash subseteq\; S$이다. 즉, $C$는 전순서 집합이다. $S$의 반사슬(antichain^영어)은 서로 다른 각 원소 쌍이 비교 불가능한 $S$의 부분 집합 $A$이다. 즉, $A$의 서로 다른 두 원소 사이에는 순서 관계가 없다. (그러나 일부 저자는 "반사슬"이라는 용어를 강한 반사슬을 의미하는 데 사용하는데, 강한 반사슬은 반사슬의 서로 다른 두 원소보다 작은 poset의 원소가 없는 부분 집합을 의미한다.)

극대 반사슬은 다른 어떤 반사슬의 진부분집합이 아닌 반사슬이다. 최대 반사슬은 다른 모든 반사슬보다 크거나 같은 기수를 갖는 반사슬이다. 부분 순서 집합의 너비는 최대 반사슬의 기수이다. 모든 반사슬은 어떤 사슬과도 최대 하나의 원소에서 교차할 수 있으므로, 순서의 원소를 $k$개의 사슬로 분할할 수 있다면, 순서의 너비는 최대 $k$여야 한다(만약 반사슬이 $k$개 이상의 원소를 갖는다면, 비둘기집 원리에 의해 같은 사슬에 속하는 2개의 원소가 존재하게 되므로 모순). Dilworth의 정리에 따르면 이 경계는 항상 도달할 수 있다. 즉, 반사슬과 원소를 사슬로 분할하는 방법이 항상 존재하여, 사슬의 개수가 반사슬의 원소 개수와 같고, 따라서 너비와 같아야 한다. 마찬가지로 부분 순서의 높이를 사슬의 최대 기수로 정의할 수 있다. Mirsky의 정리에 따르면, 유한한 높이를 갖는 모든 부분 순서에서, 높이는 순서를 분할할 수 있는 가장 작은 반사슬의 개수와 같다.

3. 성질

부분 순서 집합에서 사슬과 반사슬은 중요한 개념이다. 어떤 부분 순서 집합 $P$가 주어졌을 때, 이 집합을 여러 개의 사슬 또는 반사슬로 분할하는 방법을 고려할 수 있다. 이때, 집합의 구조적 특징을 나타내는 여러 성질들이 존재한다.

대표적으로 딜워스의 정리는 부분 순서 집합의 너비(width^영어, 가장 큰 반사슬의 크기)가 유한할 경우, 그 너비는 해당 집합을 분할하는 데 필요한 최소 사슬의 개수와 같다는 것을 말한다. 반대로, 미르스키 정리는 부분 순서 집합의 높이(height^영어, 가장 큰 사슬의 크기)가 유한할 경우, 그 높이는 해당 집합을 분할하는 데 필요한 최소 반사슬의 개수와 같다는 정리이다. 이 두 정리는 유한한 너비 또는 높이를 가진 부분 순서 집합의 기본적인 관계를 설명하지만, 무한 집합에 대해서는 성립하지 않을 수 있다.

이러한 관계는 그린-클라이트먼 정리(Greene–Kleitman theorem^영어)를 통해 더 일반화될 수 있다. 이 정리는 유한 부분 순서 집합에서 여러 개의 사슬 또는 반사슬의 합집합 크기와 관련된 복잡한 관계를 다루며, 딜워스 정리와 미르스키 정리는 이 정리의 특수한 경우($n=1$)로 볼 수 있다.

또한, 부분 순서 집합의 차원(dimension^영어) 개념과 관련된 히라구치 정리가 있다. 이 정리는 부분 순서 집합의 차원이 특정 조건(최소 사슬 분할 크기)보다 작거나 같음을 보여준다. 특히 너비가 유한한 부분 순서 집합의 경우, 딜워스 정리를 이용하면 차원이 너비보다 크지 않다는 결론을 얻을 수 있다($\backslash dim\; P\backslash le\backslash operatorname\{width\}P$).

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

임의의 부분 순서 집합 $P$에 대하여, $P$를 사슬들로 분할할 수 있으며, 이러한 분할의 최소 크기를 $c(P)$라고 하자. 또 $P$를 반사슬들로도 분할할 수 있으며, 이러한 분할의 최소 크기를 $a(P)$라고 하자. 한원소 집합은 사슬이자 반사슬이므로, 자명하게
:$c(P)\backslash le|P|$
:$a(P)\backslash le|P|$
이다. 부분 순서 집합 $(P,\backslash le)$ 속의 사슬 $C\backslash subseteq\; P$ 및 반사슬 $A\backslash subseteq\; P$에 대하여 $|A\backslash cap\; C|\backslash le1$이다. 따라서, 만약 $P$를 사슬 $\backslash \{C\_i\backslash \}\_\{i\backslash in\; I\}$들로 분할하였을 때, 각 반사슬 $A\backslash subseteq\; P$에 대하여 $|C\_i\backslash cap\; A|\backslash le\; 1$이므로 $|A|\backslash le|I|$이며, 즉
:$\backslash operatorname\{width\}P\backslash le\; c(P)$
이다. 반대로, 만약 $P$를 반사슬 $\backslash \{A\_j\backslash \}\_\{j\backslash in\; J\}$들로 분할하였을 때, 각 사슬 $C\backslash subseteq\; P$에 대하여 $|C\backslash cap\; A\_j|\backslash le\; 1$이므로 $|C|\backslash le|J|$이며, 즉
:$\backslash operatorname\{height\}P\backslash le\; a(P)$
이다.

딜워스 정리(Dilworth’s theorem^영어) 및 미르스키 정리(Mirsky’s theorem^영어)에 따르면, 만약 $P$의 너비 또는 높이가 유한하다면 위 부등식들이 등식이 된다. 즉, 딜워스 정리에 따르면, 만약 부분 순서 집합 $(P,\backslash le)$의 너비가 유한하다면, 이는 $c(P)$와 같다. 반대로, 미르스키 정리에 따르면, 만약 $P$의 높이가 유한하다면, 이는 $a(P)$와 같다.
:
:

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

극대 반사슬은 다른 어떤 반사슬의 진부분집합이 아닌 반사슬이다. 최대 반사슬은 다른 모든 반사슬보다 크거나 같은 기수를 갖는 반사슬이다. 부분 순서 집합의 너비는 최대 반사슬의 기수이다. 모든 반사슬은 어떤 사슬과도 최대 하나의 원소에서 교차할 수 있으므로, 순서의 원소를 $k$개의 사슬로 분할할 수 있다면, 순서의 너비는 최대 $k$여야 한다(만약 반사슬이 $k$개 이상의 원소를 갖는다면, 비둘기집 원리에 의해 같은 사슬에 속하는 2개의 원소가 존재하게 되므로 모순이다). 딜워스의 정리에 따르면 이 경계는 항상 도달할 수 있다. 즉, 반사슬과 원소를 사슬로 분할하는 방법이 항상 존재하여, 사슬의 개수가 반사슬의 원소 개수와 같고, 따라서 너비와 같아야 한다. 마찬가지로 부분 순서의 높이를 사슬의 최대 기수로 정의할 수 있다. 미르스키 정리에 따르면, 유한한 높이를 갖는 모든 부분 순서에서, 높이는 순서를 분할할 수 있는 가장 작은 반사슬의 개수와 같다.

3.2. 그린-클라이트먼 정리

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

부분 순서 집합 $P$를 사슬로 다음과 같이 분할하였다고 하자.
:$P=\backslash bigsqcup\_\{C\backslash in\backslash mathcal\; C\}C$
또한, $P$ 위에 $n$개의 반사슬 $A\_1,\backslash dots,A\_n$이 주어졌다고 하자. (이들이 서로소일 필요는 없다.) 그렇다면, 각 $C\backslash in\backslash mathcal\; C$에 대하여 다음 식이 성립한다.
:$C\backslash cap\backslash left(A\_1\backslash cup\; A\_2\backslash cup\backslash cdots\backslash cup\; A\_n\backslash right)\backslash le\; \backslash min\backslash \{|C|,n\backslash \}$
따라서, 다음과 같은 부등식이 자명하게 성립한다.
:$|A\_1\backslash cup\; A\_2\backslash cup\backslash cdots\backslash cup\; A\_n|\backslash le\backslash sum\_\{C\backslash in\backslash mathcal\; C\}\backslash min\backslash \{|C|,n\backslash \}$

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

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

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

3.3. 히라구치 정리

부분 순서 집합 $(P,\backslash le)$의 전순서 확대(totally ordered extension^영어)는 $P$ 위에 주어진 다음과 같은 전순서 $\backslash le\text{'}$이다.
:$\backslash forall\; a,b\backslash in\; P\backslash colon\; a\backslash le\; b\backslash implies\; a\backslash le\text{'}b$
즉, $P$에 순서 관계를 추가하여 전순서로 만드는 것이다. 부분 순서 집합 $(P,\backslash le)$의 차원(dimension^영어) $\backslash dim\; P$는 다음 조건을 만족시키는 전순서 확대의 집합 $\backslash \{\backslash le\_1,\backslash dots,\backslash le\_k\backslash \}$의 최소 크기이다.
:$\backslash forall\; a,b\backslash in\; P\backslash colon\; a\backslash le\; b\backslash iff\; (a\backslash le\_1b\backslash land\; a\backslash le\_2b\backslash land\backslash cdots\backslash land\; a\backslash le\_kb)$
(여기서 $\backslash land$는 논리곱이다.) 모든 부분 순서 집합은 하나 이상의 전순서 확대를 갖는다.

히라구치 정리에 의하면, 모든 부분 순서 집합 $P$에 대하여 그 차원은 비교 불가능한 원소 쌍의 수 $c(P)$보다 작거나 같다. 즉, $\backslash dim\; P\backslash le\; c(P)$이다. 만약 $P$의 너비가 유한하다면, 딜워스 정리에 의하여 $\backslash dim\; P\backslash le\backslash operatorname\{width\}P$가 된다.

4. 예시

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

전순서 집합의 경우, 반사슬은 공집합이거나 원소 하나만을 포함하는 집합이다. 이는 전순서 집합의 모든 원소 쌍은 서로 비교 가능하기 때문이다.

어떤 집합의 멱집합은 포함 관계를 순서 관계로 가질 때 부분 순서 집합을 이루며, 여기서의 반사슬(특히 슈페르너 족)은 조합론적으로 중요한 의미를 가진다. 예를 들어, 크기가 $n$인 유한 집합의 멱집합에서 서로 다른 반사슬(슈페르너 족)의 개수는 데데킨트 수(Dedekind number^영어)라고 한다. $n=0,\; 1,\; 2,\; \backslash dots$에 대한 데데킨트 수는 다음과 같다.
:2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, …

4.1. 전순서 집합

전순서 집합에서 반사슬은 공집합이거나 하나의 원소만을 갖는 집합이다. 이는 전순서 집합의 모든 원소 쌍은 서로 비교 가능하기 때문이다.

부분 순서 집합 $(P,\backslash le)$에 대하여 다음 세 조건은 서로 동치이다. 즉, 하나가 참이면 나머지 둘도 반드시 참이 된다.
* $P$는 전순서 집합이다.
* $P$는 스스로 사슬을 이룬다. (집합 내의 모든 원소가 서로 비교 가능하다는 의미이다.)
* $P$의 너비(가장 큰 반사슬의 크기)는 $\backslash operatorname\{width\}P=\backslash min\backslash \{1,|P|\backslash \}$이다. (집합에 원소가 하나라도 있다면 너비는 1이라는 의미이다.)

만약 $P$가 유한 부분 순서 집합이라면, 다음 두 조건 역시 서로 동치이다.
* $P$는 전순서 집합이다.
* $P$의 높이(가장 긴 사슬의 길이)는 $\backslash operatorname\{height\}P=|P|$이다. (집합의 모든 원소가 하나의 사슬을 이룬다는 의미이다.)

4.2. 멱집합

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

크기가 $n$인 유한 집합의 슈페르너 족의 수는 데데킨트 수(Dedekind number^영어)라고 하며, $n=0,1,2,\backslash dots$에 대해 다음과 같다.
:2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, …

$S$의 멱집합 $\backslash mathcal\; P(S)$의 높이는 $S$의 크기와 같다.
:$\backslash operatorname\{height\}\backslash mathcal\; P(S)=|S|$
슈페르너의 정리에 따르면, 만약 $S$가 유한 집합일 때, $\backslash mathcal\; P(S)$의 너비는 다음과 같다.
:$\backslash operatorname\{width\}\backslash mathcal\; P(S)=\backslash binom$