분배 격자

순서론에서 분배 격자(分配格子, 영어: distributive lattice)는 만남과 이음이 서로 분배 법칙을 따르는 격자이다. 모든 분배 격자는 항상 집합들의 포함 관계에 따른 격자로 나타낼 수 있다.

정의

오각형 격자(영어: pentagon lattice)는 다음과 같은 유계 격자이다.

$N_{5}=\{\bot ,a,b,c,\top \}$

$\bot \leq a\leq b\leq \top$

$\bot \leq c\leq \top$

다이아몬드 격자(영어: diamond lattice)는 다음과 같은 유계 격자이다.

$M_{5}=\{\bot ,a,b,c,\top \}$

$\bot \leq a,b,c\leq \top$

임의의 격자 $(L,\wedge ,\vee )$에 대하여, 다음 조건들은 서로 동치이며, 이 조건을 만족시키는 격자를 분배 격자라고 한다.

• (A) 모든 $a,b,c\in L$에 대하여, $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$
• (A’) 모든 $a,b,c\in L$에 대하여, $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$
• (B) 모든 $a,b,c\in L$에 대하여, $(a\wedge b)\vee (b\wedge c)\vee (c\wedge a)=(a\vee b)\wedge (b\vee c)\wedge (c\vee a)$^{:73, Exercise 4.7}
• (C) 모든 $a,b,c\in L$에 대하여, 만약 $a\wedge c=b\wedge c$이며 $a\vee c=b\vee c$라면 $a=b$이다.
• (D) 오각형 격자를 부분 격자로 하지 않으며, 다이아몬드 격자를 부분 격자로 하지 않는다.^{:12, Theorem 3.6:89, Theorem 4.10(ii)}

증명:

조건 (A) ⇒ 조건 (A’). 임의의 $a,b,c\in L$에 대하여,

${\begin{aligned}(a\vee b)\wedge (a\vee c)&=((a\vee b)\wedge a)\vee ((a\vee b)\wedge c)\\&=a\vee ((a\wedge c)\vee (b\wedge c))\\&=(a\vee (a\wedge c))\vee (b\wedge c)\\&=a\vee (b\wedge c)\end{aligned}}$

(두 번째 등호는 흡수 법칙 $(a\vee b)\wedge a=a$를 사용한다.)

조건 (A’) ⇒ 조건 (A). 위 증명과 유사하다.

조건 (A) ⇒ 조건 (B). 임의의 $a,b,c\in L$에 대하여,

${\begin{aligned}(a\wedge b)\vee (b\wedge c)\vee (c\wedge a)&=((a\vee (b\wedge c))\wedge (b\vee (b\wedge c)))\vee (c\wedge a)\\&=((a\vee b)\wedge (a\vee c)\wedge b)\vee (c\wedge a)\\&=((a\vee c)\wedge b)\vee (c\wedge a)\\&=((a\vee c)\vee (c\wedge a))\wedge (b\vee (c\wedge a))\\&=(a\vee c)\wedge (b\vee c)\wedge (b\vee a)\end{aligned}}$

조건 (B) ⇒ 조건 (A). 임의의 $a,b,c\in L$에 대하여, 만약 $a\leq c$라면,

${\begin{aligned}a\vee (b\wedge c)&=(c\wedge a)\vee ((b\wedge c)\vee (a\wedge b))\\&=(a\wedge b)\vee (b\wedge c)\vee (c\wedge a)\\&=(a\vee b)\wedge (b\vee c)\wedge (c\vee a)\\&=((a\vee b)\wedge (b\vee c))\wedge (c\vee a)\\&=(a\vee b)\wedge c\end{aligned}}$

이다. 따라서 $L$은 모듈러 격자이다. 이제, 임의의 $a,b,c\in L$에 대하여,

${\begin{aligned}a\wedge (b\vee c)&=a\wedge ((a\vee b)\wedge (b\vee c)\wedge (c\vee a))\\&=a\wedge ((a\wedge b)\vee (b\wedge c)\vee (c\wedge a))\\&=(a\wedge b)\vee (c\wedge a)\vee (a\wedge (b\wedge c))\\&=(a\wedge b)\vee (a\wedge c)\end{aligned}}$

이다. (세 번째 등호는 모듈러 법칙을 사용한다.)

조건 (A) ⇒ 조건 (D). 임의의 $a,b,c\in L$에 대하여, 만약 $a\leq c$라면,

$a\vee (b\wedge c)=(a\wedge c)\vee (b\wedge c)=(a\vee b)\wedge c$

이다. 따라서 $L$은 모듈러 격자이다. 즉, $L$은 오각형 격자를 부분 격자로 하지 않는다. 다이아몬드 격자 $\{\bot ,a,b,c,\top \}$에서, $a\wedge (b\vee c)=a\wedge \top =a$이지만, $(a\wedge b)\vee (a\wedge c)=\bot \vee \bot =\bot$이다. 따라서, $L$은 다이아몬드 격자를 부분 격자로 가질 수 없다.

조건 (D) ⇒ 조건 (B). $L$이 오각형 격자를 부분 격자로 하지 않으며, 어떤 $a,b,c\in L$ 및 $d=(a\wedge b)\vee (b\wedge c)\vee (c\wedge a)$, $e=(a\vee b)\wedge (b\vee c)\wedge (c\vee a)$에 대하여 $d<e$라고 가정하였을 때, $L$의 다이아몬드 부분 격자를 찾는 것으로 족하다.

$a'=(a\vee d)\wedge e=(a\wedge e)\vee d$

$b'=(b\vee d)\wedge e=(b\wedge e)\vee d$

$c'=(c\vee d)\wedge e=(c\wedge e)\vee d$

라고 하자. (각 식의 두 번째 등호는 모듈러 법칙에 따른다.) $\{d,a',b',c',e\}$가 다이아몬드 부분 격자임을 증명하자. 즉,

$a'\wedge b'=b'\wedge c'=c'\wedge a'=d$

$a'\vee b'=b'\vee c'=c'\vee a'=e$

를 보여야 한다. 쌍대성 및 대칭성에 따라, $a'\wedge b'=d$만을 보여도 좋다. 이는 다음과 같이 보일 수 있다.

${\begin{aligned}a'\wedge b'&=((a\wedge e)\vee d)\wedge ((b\wedge e)\vee d)\\&=((a\wedge e)\wedge ((b\wedge e)\vee d))\vee d\\&=((a\wedge e)\wedge ((b\vee d)\wedge e))\vee d\\&=((a\wedge e)\wedge (b\vee d))\vee d\\&=((a\wedge (a\vee b)\wedge (b\vee c)\wedge (c\vee a))\wedge (b\vee (a\vee b)\wedge (b\vee c)\wedge (c\vee a)))\vee d\\&=(a\wedge (b\vee c)\wedge (b\vee (c\wedge a)))\vee d\\&=(a\wedge (b\vee ((b\vee c)\wedge (c\wedge a))))\vee d\\&=(a\wedge (b\vee (c\wedge a))\vee d\\&=((a\wedge b)\vee (c\wedge a))\vee d\\&=d\end{aligned}}$

성질

임의의 집합 $S$에 대하여, 그 멱집합의 격자 $({\mathcal {P}}(S),\subseteq )$는 분배 격자이며, 이 격자의 모든 부분 격자도 분배 격자이다. 반대로, 선택 공리를 가정한다면, 모든 분배 격자는 멱집합 격자의 부분 격자와 동형이다.

함의 관계

모든 분배 격자는 모듈러 격자이다.

모든 헤이팅 대수는 분배 격자이다. 불 대수는 헤이팅 대수의 특수한 경우이므로 역시 분배 격자이다. 모든 전순서 집합 $(T,\leq )$은 분배 격자이며, 이와 동형인 집합 격자는 $\{\{s\leq t|s\in S\}|t\in T\}\subset {\mathcal {P}}(T)$이다.

보편 대수학적 성질

분배 격자의 부분 격자 위의 합동 관계는 전체 격자 위의 합동 관계로 확대될 수 있다.^{:141, Theorem 144} 즉, 분배 격자 $L$의 부분 격자 $M\subseteq L$ 위의 합동 관계 $\sim$에 대하여, 항상

$\forall a,b\in M\colon a\sim 'b\iff a\sim b$

인 $L$ 위의 합동 관계 $\sim '$를 찾을 수 있다.

예

양의 정수의 약수 관계에 대한 격자 $(\mathbb {Z} ^{+},\mid )$는 분배 격자이다. 이 경우, 각 자연수

$n=\prod _{p\in \mathbb {P} }p^{n_{p}}$

를

$\{p^{i}\colon p\in \mathbb {P} ,\;i=0,1,\dots ,n_{p}\}$

로 대응시키면, 이 격자와 동형인 집합 격자를 얻는다.

임의의 격자 $L$의 합동 관계들의 격자 $\operatorname {Cong} (L)$는 분배 격자이다.^{:145, Theorem 149:79} 일반적인 대수 구조의 합동 관계 격자는 분배 격자일 필요가 없다.

반례

• 
  오각형 격자의 하세 도형
• 
  다이아몬드 격자의 하세 도형

오각형 격자는 모듈러 격자가 아닌 가장 작은 격자이다. 특히, 오각형 격자는 분배 격자가 아니다. 다이아몬드 격자는 모듈러 격자이지만 분배 격자는 아닌 가장 작은 격자이다. 분배 격자는 이 두 격자를 부분 격자로 포함할 수 없지만, 부분 순서 집합으로 포함할 수는 있다.

자유 분배 격자

생성원의 크기가 0, 1, 2, 3인 자유 유계 분배 격자. 자유 분배 격자의 경우 0과 1을 포함하지 않는다.

(유계) 분배 격자들은 대수 구조 다양체를 이루므로, 이에 대한 자유 대수를 정의할 수 있다. 즉, 자유 분배 격자(영어: free distributive lattice) 및 자유 유계 분배 격자(영어: free bounded distributed lattice)의 개념이 존재하며, 이는 자유 격자와 다르다. 일반적으로, 자유 격자는 구체적으로 묘사하기 힘들지만, 자유 분배 격자는 간단히 묘사할 수 있다.

생성원들의 집합 $A=a_{i}$가 주어졌다고 하자. 그렇다면, 이들로부터 생성되는 자유 분배 격자 $\langle A\rangle$는 다음과 같은 꼴의 원소들로 구성된다.

$\{M_{1},M_{2},\dots ,M_{n}\}$

여기서

• 모든 $i$에 대하여 $M_{i}\subset A$는 유한 집합이다.
• 모든 $i,j=1,\dots ,n$에 대하여 만약 $M_{i}\subset M_{j}$라면 $i=j$이다.
• $n>0$이며, $M_{i}\neq \varnothing$인 $i$가 존재한다.

이러한 원소는

$\bigvee _{i}\left(\bigwedge M_{i}\right)$

로 해석된다. $n$개의 원소로 생성되는 자유 분배 격자의 크기는 데데킨트 수(영어: Dedekind number)라고 하며, 다음과 같다 ($n=0,1,2,\dots$).

0, 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786, … (OEIS의 수열 A7153)

자유 유계 분배 격자의 경우, 원소들은 위와 마찬가지이지만, 마지막 조건이 적용되지 않는다. 즉,

$\varnothing =\bigvee \varnothing =\bot$

과

$\{\varnothing \}=\bigwedge \varnothing =\top$

이 존재한다. 즉, 같은 수의 생성원들을 갖는 자유 분배 격자보다 원소가 두 개 더 많다. 따라서 이들의 크기는 다음과 같다.

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, … (OEIS의 수열 A372)

외부 링크

• “Distributive lattice”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Distributive lattice”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Distributive lattice”. 《nLab》 (영어).