유한분배격자의 기본정리 (Fundamental Theorem of Finite Distributive Lattices)

Poset (partially ordered set) Theory에서 중요한 정리인 유한분배격자의 기본정리(Fundamental Theorem of Finite Distributive Lattices)에 대해 설명하고자 한다. 이 정리는 Birkhoff's Theorem으로도 불린다.

 

정의 1. 집합 \(P\)와 그 위에 정의된 order relation \(\le\)의 순서쌍 \((P, \le)\)를 Poset이라고 한다. \(P\)가 유한집합인 경우 \((P, \le)\)를 Finite Poset이라고 한다.

 

정의 2. Poset \(P\)의 임의의 두 원소가 유일하게 정해지는 Meet \(x\vee y\) 및 Join \(x\wedge y\)를 갖는 경우, \(P\)를 격자(Lattice)라고 한다.

 

정의 3. 격자 \(L\)이 아래 성질을 만족하는 경우 분배격자(distributive lattice)라고 한다.

$$ \begin{aligned} \text{For any } x,y,z\in L\text{, }\;\; x\wedge(y\vee z) = (x\wedge y)\vee(x\wedge z) \\ \text{For any } x,y,z\in L\text{, }\;\; x\vee(y\wedge z) = (x\vee y)\wedge(x\vee z) \end{aligned} $$

 

정리 4. 위 두 성질은 서로 동등하다.

(증명) We can derive one properties using the other properties. Details are left to the reader.

 

정의 5. Poset \(P\)의 부분집합 \(I\)가 다음 성질을 만족하는 경우 \(I\)를 \(P\)의 Order-Ideal이라고 한다.

$$ \text{For any } y\in I \text{ and } x\in P \text{ s.t. } x\le y \;\;\Longrightarrow\;\; x\in I. $$

즉, Order-Ideal은 각 원소에 대해 그 원소 이하인 모든 원소를 포함하는 집합이다.

 

Poset \(P\)의 모든 Order-Ideal의 집합을 \(J(P)\)로 나타내기로 하자. 그리고, \(J(P)\)에 대해 set-inclusion order를 부여한 Poset을 (모호할 수 있지만) 똑같이 \(J(P)\)로 쓸 것이다.

 

정리 6. Poset \(P\)에 대해 \(J(P)\)는 격자이다.

(증명) \(I, J \in J(P)\)라고 하자. 우선, \( I \vee J = I \cup J \in J(P) \)임을 보이자.

$$ \begin{aligned} x &\in I\cup J \text{ and } y \le x \\ &\rightarrow (x\in I \text{ or } x\in J) \text{ and } y\le x \\ &\rightarrow (x\in I \text{ and } y\le x) \text{ or } (x\in J \text{ and } y\le x) \\ &\rightarrow y\in I \text{ or } y\in J \\ &\rightarrow y\in I\cup J. \end{aligned} $$

즉, \(I\vee J = I\cup J\)는 Order-Ideal이므로 \(J(P)\)의 원소이다. 마찬가지로,

$$ \begin{aligned} x &\in I\cap J \text{ and } y \le x \\ &\rightarrow (x\in I \text{ and } x\in J) \text{ and } y\le x \\ &\rightarrow (x\in I \text{ and } y\le x) \text{ and } (x\in J \text{ and } y\le x) \\ &\rightarrow y\in I \text{ and } y\in J \\ &\rightarrow y\in I\cap J. \end{aligned} $$

즉, \(I\wedge J = I\cap J\)는 Order-Ideal이므로 \(J(P)\)의 원소이다. 따라서, 임의의 \(I, J\in P\)에 대해 \(I\vee J\) 및 \(I\wedge J\)가 유일하게 존재하므로 \(J(P)\)는 격자이다.

 

정리 7. Poset \(P\)에 대해 \(J(P)\)는 분배격자이다.

(증명) 정리 6에 의해 \(J(P)\)는 격자이다. 그런데 \(J(P)\)의 순서인 set-inclusion order에 의한 Meet과 Join은 각각 교집합과 합집합 연산에 해당하므로, 자명하게 분배법칙을 만족한다. 따라서 \(J(P)\)는 분배격자이다.

 

정의 8. 분배격자 \(L\)의 원소 \(x\)에 대해 \(x = y \vee z\)를 만족하는 \(y < x\), \(z < x\)인 \(y, z \in L\)이 존재하지 않는 경우, \(x\)를 Join-irreducible이라고 한다. \((\Leftrightarrow)\) \(y,z\in L\)이 \(x = y \vee z\)을 만족할 경우 항상 \(x = y\) 또는 \(x = z\)가 성립한다면 \(x\)를 Join-irreducible이라고 한다.

 

* 편의상 \(L\)의 Bottom 원소는 Join-irreducible이 아닌 것으로 생각한다. 하지만, 이렇게 하든지 하지 않든지 이후의 증명에는 큰 차이가 없다. 모든 Order-Ideal은 Bottom 원소를 포함하므로, 그것이 없다고 해도 별 상관이 없기 때문이다.

 

분배격자 \(L\)의 모든 Join-irreducible 원소의 집합을 \(\text{Irr}(L)\)로 나타내기로 하자.

 

예제 9. 다음 Finite Poset \(P\)를 생각하자.

A poset \(P\) with 4 elements

\(P\)는 격자가 아니다. 하지만 \(J(P)\)는 다음과 같은 분배격자가 됨을 확인할 수 있다.

\(J(P)\): The poset of the order-ideals of \(P\)

\(\text{Irr}(J(P))\)는 무엇인가 살펴보자.

그림에서 \(P \simeq \text{Irr}(J(P))\)임을 알 수 있다. 즉, \(P\)의 각 원소는 \(J(P)\)의 Join-irreducible 원소들의 subposet과 순서동형이다.

 

여기서 순서동형은 두 Poset 간에 순서가 보존되는 bijection이 존재한다는 뜻이다. 즉 다음과 같이 정의한다.

 

정의 10. 두 Poset \(P, Q\)가 순서동형(order-isomorphism) \(\Leftrightarrow\) bijection \(\phi: P \rightarrow Q\)가 존재하여 \( x,y\in P \)에 대해 \( x\le y \Leftrightarrow \phi(x) \le \phi(y) \).

 

위 그림의 결과는 일반적으로 성립하는 것이다. 이를 표현하면 다음 정리가 된다.

 

정리 11. Finite Poset \(P\)에 대하여, \(P \simeq \text{Irr}(J(P))\).

(증명) \(\phi: P \rightarrow \text{Irr}(J(P))\)를 다음과 같이 정의하자.

$$ \text{For } x \in P\text{, define } \phi: x \mapsto \Lambda_x = \left\lbrace s\in P | s \le x\right\rbrace. $$

 

Step 1: \(\phi(x) \in \text{Irr}(J(P))\)임을 보이자.

증명) \(\Lambda_x = E\vee F = E\cup F\)로 표현될 수 있다고 가정하자. (\(E,F \in J(P)\)). 그러면 \(x\in E\)이거나 \(x\in F\)이다. 일반성을 잃지 않고 \(x\in E\)라고 하자. \(E\)가 Order-Ideal이므로 \(x\) 이하인 모든 원소를 포함하게 되어 \(\Lambda_x \subseteq E\)가 된다. 그런데 \(\Lambda_x = E\vee F = E\cup F\)에서 \(E\subseteq \Lambda_x\)이므로 \(E = \Lambda_x\)이다. 따라서 \(\Lambda_x\)는 \(J(P)\)의 Join-irreducible 원소이다.

 

Step 2: \(\phi\)가 surjective임을 보이자.

증명) 먼저, 증명의 편의를 위해 임의의 \(Q \subseteq P\)에 대해 \(\langle Q\rangle = \lbrace s\in P|s\le t \text{ for some } t\in Q\rbrace\)로 약속하자. 그러면 \(\langle Q \rangle\)는 Order-Ideal이다. 또한, 임의의 \(I\in \text{Irr}(J(P))\)에 대해, \(I\)의 maximal 원소들의 집합을 \(A\)라고 하자. 그러면 \(I = \langle A \rangle\)이다. (증명: 우선 \(\langle A\rangle \subseteq I\)임은 자명하다. 한편, \(I\)의 각 원소는 maximal이거나, maximal이 아니다. maximal인 원소는 정의상 \(\langle A\rangle\)에 속하고, maximal이 아닌 원소 \(x\)는 어떤 maximal 원소 \(y \in A\) 이하이므로 \(\langle\rangle\)의 정의에 의해 \(\langle A\rangle\)에 속한다.)

 

만약 \(|A| \ge 2\)라면, 어떤 \(a\in A\)에 대해 다음과 같은 집합을 정의할 수 있다.

$$ B = \lbrace a \rbrace \;\;\text{ and }\;\; C = A - \lbrace a \rbrace $$

그러면 \(\langle B \rangle \cup \langle C \rangle = \langle A \rangle = I\). (증명: \(\langle\rangle\)의 정의 이용.) 그런데 \(B\not\subseteq \langle C\rangle\)이고 \(C\not\subseteq \langle B \rangle\)이므로 \(\langle B\rangle, \langle C\rangle \neq I\)이다. (증명: 만약 \(a\in \langle C\rangle\)이라면, \(a\)는 \(C\)의 어떤 원소 이하여야 한다. 이는 \(a\)가 maximal임에 모순이다. \(C\)에 대한 증명도 비슷하다.) 이는 \(I\)가 \(J(P)\)에서 Join-irreducible임에 모순이다.

 

따라서 \(|A| = 1\)이어야 한다. 하나뿐인 \(A\)의 원소를 \(x\)라고 하면, \(A = \Lambda_x\)가 된다. 그러므로, \(\phi\)는 surjective이다.

 

Step 3: \(\phi\)가 injective임을 보이자.

증명) \(x, y\in P\)에 대해 \(\Lambda_x = \Lambda_y\)라고 하자. 그러면 \(y \le x\)이고 \(x\le y\)이므로 \(x = y\). 따라서 \(\phi\)는 injective이다.

 

Step 4: \(\phi\)가 order-preserving임을 보이자.

증명) \(x,y \in P\)가 \(x\le y\)를 만족한다면, 임의의 \(z\in \Lambda_x\)에 대해

$$ z\le x\le y \;\;\Rightarrow \;\; z\in \Lambda_y. $$

따라서 \(\Lambda_x \subseteq \Lambda_y\)이므로 \(\phi\)는 order-preserving이다.

 

Step 5: \(\phi^{-1}\)가 order-preserving임을 보이자.

증명) \(x,y \in P\)에 대해 \(\Lambda_x \subseteq \Lambda_y\)가 성립한다고 하자. 그러면

$$ x\in\Lambda_x\;\;\Rightarrow\;\; x\in\Lambda_y \;\;\Rightarrow\;\; x\le y. $$

따라서 \(x\le y\)이므로 \(\phi^{-1}\)는 order-preserving이다.

 

결론적으로 Step 1~5에 의해 \(\phi\)는 order-preserving bijection이고, 그 정의역과 공역인 \(P\)와 \(\text{Irr}(J(P))\)는 서로 순서동형이다.

 

한편, 이와 유사하게 다음 정리가 성립한다.

 

정리 12. 유한분배격자 \(L\)에 대하여, \(L \simeq J(\text{Irr}(L))\).

 

(증명) \(\phi: L \rightarrow J(\text{Irr}(L))\)를 다음과 같이 정의하자.

$$ \text{For } t\in L\text{, define } \phi: t \mapsto I_t = \lbrace s \in \text{Irr}(L) | s\le t \rbrace $$

 

Step 1: \(\phi(t) \in J(\text{Irr}(L))\)임을 보이자.

증명) 만약 \( x\in\phi(t) \)이고 \(y \in \text{Irr}(L)\)이 \(y\le x\)를 만족한다면 \(y\le x\le t\)이므로 \(y \in \phi(t)\)이다. 따라서 \(\phi(t)\)는 Order-Ideal이므로 \(\phi(t) \in J(\text{Irr}(L)\)이다.

 

Step 2: \(\phi\)가 surjective임을 보이자.

증명) 임의의 \(I \in J(\text{Irr}(L))\)을 택하자. \(t = \vee_{s\in I} s\)로 놓으면 \(I_t = I\)가 됨을 보일 것이다.

 

(\(\Rightarrow\)) \(I \subseteq I_t \)임을 보이자. 각 \(x \in I\)에 대하여,

$$ x \le x \vee \left( \vee_{s\in I, s\neq x} s \right) = \vee_{s\in I} s = t.$$

따라서 \(I_t\)의 정의에 의해 \(x \in I_t\)이다. 그러므로, \(I \subseteq I_t\).

 

(\(\Leftarrow\)) \(I_t \subseteq I\)임을 보이자. 먼저, 다음을 관찰하자.

 

• \(I \subseteq I_t\); Hence, \(t = \vee_{s\in I} s \le \vee_{s\in I_t} s\).
• \(s \le t\) for any \(s \in I_t\) by definition; Hence, \(\vee_{s\in I_t} s \le \vee_{s\in I_t} t = t\).

따라서 \(\vee_{s\in I_t} s = \vee_{s\in I} s\)가 성립한다. 이제 임의의 \(x\in I_t\)를 택하면, 분배법칙에 의해

$$ \begin{aligned} x\wedge \left(\vee_{s\in I_t} s\right) &= x\wedge \left(\vee_{s\in I} s\right) \\ x &= \vee_{s\in I} (x\wedge s) \end{aligned} $$

가 성립한다. 그런데, \(x\)는 Join-irreducible이므로 위 Join식의 어떤 항이 반드시 \(x\)와 같아야 한다. 즉, 어떤 \(s^\prime\in I\)에 대해 다음이 성립한다.

$$ x \le s^\prime $$

그런데 \(I\)는 Order-Ideal이므로 \(x \in I\). 그러므로, \(I_t \subseteq I\)이다.

따라서 \(I_t = I\)이므로 모든 \(I \in J(\text{Irr}(L))\)는 그에 상응하는 어떤 \(t=t(I)\)가 존재하여 \(\phi(t) = I\)를 만족한다. 그러므로, \(\phi\)는 surjective이다.

 

Step 3. \(\phi\)가 injective임을 보이자.

증명) \(t,u\in L\)이라고 하자. Step 2의 증명과정에서 다음을 알고 있다.

$$ t = \vee_{s\in I_t}s, \;\;\;\;u = \vee_{s\in I_u}s. $$

따라서, 만약 \(I_t = I_u\)라고 한다면

$$ t = \vee_{s\in I_t}s = \vee_{s\in I_u}s = u. $$

그러므로 \(\phi\)는 injective이다.

 

Step 4. \(\phi\)가 order-preserving임을 보이자.

증명) \(t,u\in L\)에 대하여, \(t\le u\)라고 하자. 만약 \(x\in I_t\)이면, 정의에 의해

$$ x\le t\le u \;\;\Rightarrow \;\; x \in I_u. $$

즉 \(I_t \subseteq I_u\)이므로 \(\phi\)는 order-preserving이다.

 

Step 5. \(\phi^{-1}\)가 order-preserving임을 보이자.

증명) \(t,u\in L\)이라고 하자. Step 2의 증명과정에서 다음을 알고 있다.

$$ t = \vee_{s\in I_t}s, \;\;\;\;u = \vee_{s\in I_u}s. $$

따라서, 만약 \(I_t \subseteq I_u\)라고 한다면

$$ t = \vee_{s\in I_t}s \le \left(\vee_{s\in I_t} s\right) \wedge \left(\vee_{s\in (I_u-I_t)}s\right) = \vee_{s\in I_u} s = u. $$

그러므로 \(\phi^{-1}\)는 order-preserving이다.

 

결론적으로 Step 1~5에 의해 \(\phi\)는 order-preserving bijection이고, 그 정의역과 공역인 \(L\)과 \(J(\text{Irr}(L))\)은 서로 순서동형이다.

 

이제 이 두 가지 결과를 합쳐서 멋지게 써 보자.

 

정리 13. 유한분배격자의 기본정리 (Fundamental Theorem of Finite Distributive Lattices)

유한분배격자 \(L\)에 대해, \(L \simeq J(P)\)를 만족하는 Poset \(P\)는 유일하게 존재한다. (즉, 모두 서로 순서동형)

 

(증명) 존재성: \(P = \text{Irr}(L)\)로 택하면, 정리 12에 의해 \(L \simeq J(P)\)를 만족한다.

유일성: 만약 어떤 Poset \(Q\)가 \(L \simeq J(Q)\)를 만족한다면, 정리 11에 의해 \(Q \simeq \text{Irr}(J(Q)) \simeq \text{Irr}(L)\)로 항상 \(\text{Irr}(L)\)과 동형이다.

 

* 유한성이 어디서 오는지 생각해보자. 증명과정 어딘가에서 사용하고 있다.

 

정리 13이 의미하는 것은 무엇일까? 어떤 유한분배격자 \(L\)을 생각하더라도 그에 대응하는 Poset \(P = P(L)\)이 존재하여 \(L \simeq J(P)\)를 만족하므로, 결국 우리는 \(L\)의 Meet과 Join을 각각 합집합과 교집합으로 해석할 수 있는 것이다. 어떤 집합에 대한 합집합과 교집합인가? 앞서 살펴본 대로 \(P = \text{Irr}(L)\) 내에서의 합집합과 교집합이다.

 

참고 문헌

Earnshaw, B.A. (2005). Combinatorial aspects of partially ordered sets. Retrieved from https://users.math.msu.edu/users/Earnshaw/research/poset.pdf

 

Martin, J. (2008). Birkhoff's Theorem (Lecture notes for MATH796-S08). Retrieved from http://jlmartin.faculty.ku.edu/~jlmartin/courses/math796-S08/notes0128.pdf

 

Stanley, R. P. (2011). Enumerative Combinatorics (Cambridge Studies in Advanced Mathematics), 2nd ed. Cambridge (England): Cambridge University Press.