Mirsky's theorem

Mirsky's theorem은 POSET에 관련된 기초적인(?) 정리 중 하나인데, 어디 심층 문제에 대뜸 나왔다길래 포스팅해본다.

이에 완전히 대응되는 정리로 Dilworth's theorem이 있지만 증명이 복잡해서 일단은 Mirsky만 증명하기로 한다.

POSET(PreOrder SET)의 형식적인 정의는 다음과 같다. 직관적으로는 두 정수 간의 약배수 관계를 생각하면 된다.

- 집합 \(P\)의 원소들에 대해서, 관계 \(\preccurlyeq\)가 다음을 만족한다.

- 반사율 (reflexivity) : 임의의 \(a \in P\)에 대해 \(a \preccurlyeq a\).

- 추이율 (transitivity) : \(a, b, c \in P\)에 대해 \(a \preccurlyeq b \ \wedge \ b \preccurlyeq c \implies a \preccurlyeq c\).

반드시 모든 두 원소 \(a, b \in P\)에 대해 \(a \preccurlyeq b\) 또는 \(b \preccurlyeq a\)가 성립할 필요는 없다.

정수의 약배수 관계에 대입해보면 약배수 관계가 두 조건을 충족한다는 것을 알 수 있다.

Mirsky's theorem을 이해하기 위해선 chain, antichain이라는 개념이 필요하다. 전혀 어렵지 않은 개념이지만 명쾌하면서도 엄밀한 설명을 쓰기는 언제나 어렵다.

Chain은 \(P\)의 부분집합 중 임의의 두 원소를 비교할 수 있는 것을 말한다. 약배수 관계를 생각했을 때 \(\{1, 2, 2^{2}, 2^{3}, \ldots 2^{k}, \ldots \}\)는 \(\mathbb{N}\)의 chain을 이룬다.

Antichain은 반대로, 임의의 두 원소 간에 순서관계가 성립하지 않는 부분집합을 말한다. 약배수 관계로 생각했을 때 소수의 집합 \(\{2,3,5,7,\ldots\}\)은 \(\mathbb{N}\)의 antichain을 이룬다. 형식적으로는 이렇게 쓰는데 별로 유용하지는 않은 것 같으니 너무 얽매이지는 말자.

- Antichain \(A\)의 원소 \(a,b\)에 대해, \(a \preccurlyeq b \implies a = b\).

원소 1개짜리 집합(singleton)은 자명하게 chain이자 antichain이므로, 집합 \(P\)를 chain, 혹은 antichain들로 분할할 수 있다. Mirsky's theorem은 이 분할의 크기와 관련된 정리이다.

Thms.

- Mirsky's theorem: \(C(P) = \left|\text{maximal_chain}(P)\right|\)가 finite할 때, \(C(P) = \left|\text{minimal_antichain_partition}(P)\right| = \text{ap}(P)\).

- Dilworth's theorem: \(A(P) = \left|\text{maximal_antichain}(P)\right|\)가 finite할 때, \(A(P) = \left|\text{minimal_chain_partition}(P)\right| = \text{cp}(P)\).

각각 \(C(P)\)와 \(A(P)\)가 infinite한 경우에는 성립하지 않는다고 한다. 이건 생각해보고 추가할 예정.

\(C(P)\)랑 \(A(P)\)를 실제로는 \(\text{height}(P)\)와 \(\text{width}(P)\)라고 쓰는데 맨날 둘이 헷갈려서 별로 좋아하지 않는다.

Proof of Mirsky's theorem

1. \(C(P) \le \text{ap}(P)\)

\(P\)를 분할하는 반사슬들을 \(A_{1}, A_{2}, \ldots, A_{k}\)라고 하자. (\(k \ge \text{ap}(P)\))

이 때 임의의 사슬 \(C\)에 대해서 \(\left| C \cap A_{i} \right| \le 1\)이 성립하므로 \(|C| \le k\)이다.

임의의 (사슬, 반사슬 분할)에 대해서 다음이 성립하므로 \(C(P) \le \text{ap}(P)\)이다.

2. \(C(P) \ge \text{ap}(P)\)

이 부분이 간단하지만 tricky하다. 아이디어는 크기 \(C(P)\) 이하의 antichain partition을 실제로 construct하는 것이다.

\(x \in P\)에 대해, \(f(x)\)를 "\(x\)를 극대 원소로 하는 chain의 최대 크기"로 정의하자. 

극대 원소는 생각하는 그거 맞다. \(x \preccurlyeq y\)인 \(y\)가 없는 원소.

가령 \(\mathbb{N}\)에서 \(f(8) = 4 = |\{1,2,4,8\}|\)이다.

이 때 임의의 \(n\)에 대해 \(n\)의 preimage \(f^{-1}(n) = \{ x \in P | f(x) = n \}\)은 antichain을 이룬다. 만약 \(x \preccurlyeq y, x \neq y\)인 \(x, y \in f^{-1}(n)\)이 존재한다면 \(f(y) > n\)이기 때문.

이때 \(f(x)\)의 범위가 \([1, C(P)]\)이고, \(f^{-1}(1), \ldots, f^{-1}\left( C(P) \right) \)가 \(P\)의 분할을 이루므로 증명이 끝난다.

Corollary.

이걸 Chain - Antichain이라고 불렀던 것 같은데 왜 찾으면 안 나오는지 모르겠다.

- \(C(P), A(P)\)가 finite할 때, \(C(P) \cdot A(P) \ge |P|\).

증명은 한줄이다. \(C(P) \cdot A(P) = \text{ap}(P) \cdot A(P) \ge |P|._{\blacksquare}\)

언젠가 Dilworth's theorem도 추가해야겠다. 신기한 증명법이 있다고 해서 연구해보려고 한다.