반사슬
순서론에서, 반사슬(反사슬, )은 서로 다른 두 원소가 비교될 수 없는, 원순서 집합의 부분 집합이며, 사슬()은 서로 두 원소가 항상 비교될 수 있는, 원순서 집합의 부분 집합이다.
원순서 집합 formula_1의 반사슬은 다음 조건을 만족시키는 부분 집합 formula_2이다.
원순서 집합 formula_6의 사슬은 원전순서 집합인 부분 집합 formula_7이다. 즉, 다음 조건을 만족시키는 부분 집합 formula_8이다.
즉, 반사슬 속의 서로 다른 두 원소는 항상 비교 불가능하며, 사슬 속의 서로 다른 두 원소는 항상 비교 가능하다.
원순서 집합 formula_1의 사슬들의 집합과 반사슬들의 집합은 각각 부분 집합 관계에 따라 부분 순서 집합을 이룬다. 이에 대하여 극대인 (반)사슬 (즉, 더 큰 반사슬에 포함되지 않는 (반)사슬)을 극대 (반)사슬(極大(反)사슬, )이라고 한다.
원순서 집합 formula_1의 높이() formula_14는 formula_15 속의 사슬의 크기의 상한이다. 마찬가지로, 원순서 집합 formula_1의 너비() formula_17는 formula_15 속의 반사슬의 크기의 상한이다.
임의의 부분 순서 집합 formula_15에 대하여, formula_15를 사슬들로 분할할 수 있으며, 이러한 분할의 최소 크기를 formula_21라고 하자. 또 formula_15를 반사슬들로도 분할할 수 있으며, 이러한 분할의 최소 크기를 formula_23라고 하자. 한원소 집합은 사슬이자 반사슬이므로, 자명하게
이다. 부분 순서 집합 formula_6 속의 사슬 formula_8 및 반사슬 formula_2에 대하여 formula_29이다. 따라서, 만약 formula_15를 사슬 formula_31들로 분할하였을 때, 각 반사슬 formula_2에 대하여 formula_33이므로 formula_34이며, 즉
이다. 반대로, 만약 formula_15를 반사슬 formula_37들로 분할하였을 때, 각 사슬 formula_8에 대하여 formula_39이므로 formula_40이며, 즉
이다.
딜워스 정리(Dilworth定理, ) 및 미르스키 정리(Мирский定理, )에 따르면, 만약 formula_15의 너비 또는 높이가 유한하다면 위 부등식들이 포화된다. 즉, 딜워스 정리에 따르면, 만약 부분 순서 집합 formula_6의 너비가 유한하다면, 이는 formula_21와 같다. 반대로, 미르스키 정리에 따르면, 만약 formula_15의 높이가 유한하다면, 이는 formula_23와 같다.
이 정리들은 무한한 너비 또는 높이의 부분 순서 집합에 대하여 기수로서 성립하지 않는다.
딜워스 정리의 증명은 쾨니그의 정리를 이용한 기법 등 여러 방법이 있다. 만약 formula_15가 유한 집합일 경우, 미카 아셰르 페를레스(, 1936~)는 다음과 같은 간단한 증명을 제시하였다.
유한 부분 순서 집합 formula_6가 주어졌다고 하자. formula_15의 극대 원소들의 집합을 formula_52, 극소 원소들의 집합을 formula_53라고 하자. 이들은 각각 반사슬을 이룬다.
집합의 크기에 대한 수학적 귀납법을 사용하자. 우선, 딜워스 정리는 한원소 집합인 부분 순서 집합에 대하여 자명하게 성립한다. 이제 딜워스 정리가 크기 formula_54 미만의 모든 부분 순서 집합에 대하여 대해 성립한다고 가정하자. 그렇다면, 다음과 같이 두 가지 경우로 나눌 수 있다.
1의 경우, formula_62인 formula_63와 formula_64를 찾을 수 있다. (그렇지 아니하다면 크기가 formula_17보다 더 큰 반사슬이 존재하게 되기 때문이다.) formula_66의 최소 사슬 분할
이 주어졌을 때
는 formula_15의 사슬 분할이므로, formula_66에 딜워스의 정리를 적용하면
이다.
2의 경우, 다음과 같은 두 부분 집합 formula_72를 정의하자.
formula_78에 딜워스 정리를 적용하여 다음과 같은 사슬 분해를 얻는다고 하자.
그렇다면 formula_15의 사슬 분해
를 얻는다. 즉,
가 된다.
미르스키 정리의 증명은 딜워스 정리의 증명보다 더 간단하다. formula_15가 유한한 높이의 부분 순서 집합이라고 하자. 원소 formula_85에 대하여, formula_86가 formula_87를 최대 원소로 하는 사슬의 길이의 최댓값이라고 하자. 이는 함수 formula_88을 정의한다.
그렇다면, 각 자연수 formula_89의 원상 formula_90은 반사슬을 이루며, 이들은 formula_15의 분할을 이룬다.
따라서 formula_93이다.
딜워스 정리와 미르스키 정리는 다음과 같이 그린-클라이트먼 정리(Greene-Kleitman定理, )로 일반화된다.
부분 순서 집합 formula_15를 사슬로 다음과 같이 분할하였다고 하자.
또한, formula_15 위에 formula_97개의 반사슬 formula_98이 주어졌다고 하자. (이들이 서로소일 필요는 없다.) 그렇다면, 각 formula_99에 대하여
추상대수학에서는 각종 대수 구조로부터 정의되는 부분 순서 집합의 높이가 널리 사용된다.
환론에서, 가군 formula_101의 부분 가군 격자 formula_102의 높이 빼기 1은 formula_101의 길이 formula_104라고 한다.
가환환 formula_106의 소 아이디얼들의 부분 순서 집합 formula_107의 높이 빼기 1은 formula_106의 크룰 차원 formula_109이라고 한다.
가환환 formula_106의 소 아이디얼 formula_112 속에 포함된 소 아이디얼들의 부분 순서 집합
의 높이 빼기 1은 formula_112의 높이 formula_115라고 한다.
최소 원소를 갖는 사슬이 항상 유한 집합인 부분 순서 집합은 오름 사슬 조건을 만족시킨다고 하고, 반대로 최대 원소를 갖는 사슬이 항상 유한 집합인 부분 순서 집합은 내림 사슬 조건을 만족시킨다고 한다. 이 조건들은 뇌터 환 · 아르틴 환과 같은 중요한 개념들을 정의하는 데 쓰인다.
1897년에 리하르트 데데킨트는 데데킨트 수를 정의하였다. 이후 1928년에 에마누엘 슈페르너()는 멱집합의 너비를 계산하였다 (슈페르너의 정리).
딜워스 정리는 미국의 수학자 로버트 파머 딜워스(, 1914~1993)가 1950년 논문에서 처음 제시하였다.
히라구치 정리는 히라구치 도시오()가 1951년에 증명하였다.
미르스키 정리는 러시아 태생의 영국 수학자 레오니트 미르스키(, , 1918~1983)가 1971년에 증명하였다.
그린-클라이트먼 정리는 커티스 그린()과 대니얼 클라이트먼()이 증명하였다.