반사슬

순서론에서 '''반사슬'''(反사슬, )은 서로 다른 두 원소가 비교될 수 없는, 원순서 집합의 부분 집합이며, '''사슬'''()은 서로 두 원소가 항상 비교될 수 있는, 원순서 집합의 부분 집합이다.
원순서 집합 의 '''반사슬'''은 다음 조건을 만족시키는 부분 집합 이다.
* 임의의 에 대하여, 라면 이다.
원순서 집합 의 '''사슬'''은 원전순서 집합인 부분 집합 이다. 즉, 다음 조건을 만족시키는 부분 집합 이다.
* 임의의 에 대하여, 이거나 이다.
즉, 반사슬 속의 서로 다른 두 원소는 항상 비교 불가능하며, 사슬 속의 서로 다른 두 원소는 항상 비교 가능하다.
=== 극대 사슬과 극대 반사슬 ===
원순서 집합 의 사슬들의 집합과 반사슬들의 집합은 각각 부분 집합 관계에 따라 부분 순서 집합을 이룬다. 이에 대하여 극대인 (반)사슬 (즉, 더 큰 반사슬에 포함되지 않는 (반)사슬)을 '''극대 (반)사슬'''(極大(反)사슬, )이라고 한다.
=== 높이와 너비 ===
원순서 집합 의 '''높이'''() 는  속의 사슬의 크기의 상한이다. 마찬가지로, 원순서 집합 의 '''너비'''() 는  속의 반사슬의 크기의 상한이다.
=== 딜워스 정리와 미르스키 정리 ===
임의의 부분 순서 집합 에 대하여, 를 사슬들로 분할할 수 있으며, 이러한 분할의 최소 크기를 라고 하자. 또 를 반사슬들로도 분할할 수 있으며, 이러한 분할의 최소 크기를 라고 하자. 한원소 집합은 사슬이자 반사슬이므로, 자명하게
:
:
이다. 부분 순서 집합  속의 사슬  및 반사슬 에 대하여 이다. 따라서, 만약 를 사슬 들로 분할하였을 때, 각 반사슬 에 대하여 이므로 이며, 즉
:
이다. 반대로, 만약 를 반사슬 들로 분할하였을 때, 각 사슬 에 대하여 이므로 이며, 즉
:
이다.
'''딜워스 정리'''(Dilworth定理, ) 및 '''미르스키 정리'''(Мирский定理, )에 따르면, 만약 의 너비 또는 높이가 유한하다면 위 부등식들이 포화된다. 즉, '''딜워스 정리'''에 따르면, 만약 부분 순서 집합 의 너비가 유한하다면, 이는 와 같다. 반대로,  '''미르스키 정리'''에 따르면, 만약 의 높이가 유한하다면, 이는 와 같다.
:
:
이 정리들은 무한한 너비 또는 높이의 부분 순서 집합에 대하여 기수로서 성립하지 않는다.
=== 그린-클라이트먼 정리 ===
딜워스 정리와 미르스키 정리는 다음과 같이 '''그린-클라이트먼 정리'''(Greene-Kleitman定理, )로 일반화된다.
부분 순서 집합 를 사슬로 다음과 같이 분할하였다고 하자.
:
또한,  위에 개의 반사슬 이 주어졌다고 하자. (이들이 서로소일 필요는 없다.) 그렇다면, 각 에 대하여
:
이므로, 자명하게
:
가 성립한다. 의 '''-너비'''() 를 개의 반사슬의 합집합의 크기의 상한으로 정의하고, 의 '''-높이'''() 를 개의 사슬의 합집합의 크기의 상한으로 정의하자. 마찬가지로, 를 의 사슬 분할 에 대한 의 하한으로, 를 의 반사슬 분할 에 대한 의 하한으로 정의하자. 그렇다면 위 논리에 의하여 자명하게
:
:
가 성립한다.
'''그린-클라이트먼 정리'''에 따르면, 만약 가 유한 부분 순서 집합이라면, 위 두 부등식들이 항상 포화된다.
딜워스 정리 · 미르스키 정리는 그린-클라이트먼 정리에서 인 특수한 경우이다.
=== 히라구치 정리 ===
부분 순서 집합 의 '''전순서 확대'''()는  위에 주어진 다음과 같은 전순서 이다.
:
즉, 에 순서 관계를 추가하여 전순서로 만드는 것이다. 부분 순서 집합 의 '''차원'''() 는 다음 조건을 만족시키는 전순서 확대의 집합 의 최소 크기이다.
:
(여기서 는 논리합이다.) 모든 부분 순서 집합은 하나 이상의 전순서 확대를 갖는다.
'''히라구치 정리'''에 의하면, 이다. 만약 의 너비가 유한하다면, 딜워스 정리에 의하여 가 된다.
공집합은 항상 자명하게 사슬이자 반사슬이다.
=== 전순서 집합 ===
전순서 집합의 반사슬은 공집합이거나 아니면 하나의 원소만을 갖는 집합이다. 부분 순서 집합 에 대하여 다음 세 조건이 서로 동치이다.
* 는 전순서 집합이다.
* 는 스스로 속의 사슬을 이룬다.
* 의 너비는 이다.
만약 가 유한 부분 순서 집합이라면 다음 두 조건이 서로 동치이다.
* 는 전순서 집합이다.
* 의 높이는 이다.
=== 멱집합 ===
집합 의 멱집합 은 포함 관계에 대하여 부분 순서 집합(사실 불 대수)를 이룬다.  속의 반사슬을 '''슈페르너 족'''(Sperner族, )이라고 한다.
크기가 인 유한 집합의 슈페르너 족의 수는 '''데데킨트 수'''()라고 하며, 다음과 같다. ()
:2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, … 
의 멱집합 의 높이는 의 크기와 같다.
:
'''슈페르너의 정리'''에 따르면, 만약 가 유한 집합일 때, 의 너비는 다음과 같다.
:
=== 대수 구조 ===
추상대수학에서는 각종 대수 구조로부터 정의되는 부분 순서 집합의 높이가 널리 사용된다.
환론에서, 가군 의 부분 가군 격자 \operatorname{Sub}(M)의 높이 빼기 1은 의 '''길이''' 라고 한다.
:
가환환 의 소 아이디얼들의 부분 순서 집합 의 높이 빼기 1은 의 '''크룰 차원''' 이라고 한다.
:
가환환 의 소 아이디얼  속에 포함된 소 아이디얼들의 부분 순서 집합
:
의 높이 빼기 1은 의 '''높이''' 라고 한다.
:
최소 원소를 갖는 사슬이 항상 유한 집합인 부분 순서 집합은 '''오름 사슬 조건'''을 만족시킨다고 하고, 반대로 최대 원소를 갖는 사슬이 항상 유한 집합인 부분 순서 집합은 '''내림 사슬 조건'''을 만족시킨다고 한다. 이 조건들은 뇌터 환 · 아르틴 환과 같은 중요한 개념들을 정의하는 데 쓰인다.
1897년에 리하르트 데데킨트는 데데킨트 수를 정의하였다. 이후 1928년에 에마누엘 슈페르너()는 멱집합의 너비를 계산하였다 (슈페르너의 정리).
딜워스 정리는 미국의 수학자 로버트 파머 딜워스(, 1914~1993)가 1950년 논문에서 처음 제시하였다.
히라구치 정리는 히라구치 도시오()가 1951년에 증명하였다.
미르스키 정리는 러시아 태생의 영국 수학자 레오니트 미르스키(, , 1918~1983)가 1971년에 증명하였다.
그린-클라이트먼 정리는 커티스 그린()과 대니얼 클라이트먼()이 증명하였다.
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
분류:순서론
분류:조합적 집합론