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도 추가해야겠다. 신기한 증명법이 있다고 해서 연구해보려고 한다.