분배 격자

expanded=격자 순서론에서 **분배 격자**(分配格子, distributive lattice)는 만남과 이음이 서로 분배 법칙을 따르는 격자이다. 모든 분배 격자는 항상 집합들의 포함 관계에 따른 격자로 나타낼 수 있다.
# 정의
**오각형 격자**(pentagon lattice)는 다음과 같은 유계 격자이다. :N_5=\\{\bot,a,b,c,\top\\} :\bot\le a\le b\le\top :\bot\le c\le\top **다이아몬드 격자**(diamond lattice)는 다음과 같은 유계 격자이다. :M_5=\\{\bot,a,b,c,\top\\} :\bot\le a,b,c\le\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.6zbl=1002.0600189, Theorem 4.10(ii) 증명 조건 (A) ⇒ 조건 (A’). 임의의 a,b,c\in L에 대하여, :\begin{align} (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{align} (두 번째 등호는 흡수 법칙 (a\vee b)\wedge a=a를 사용한다.) 조건 (A’) ⇒ 조건 (A). 위 증명과 유사하다. 조건 (A) ⇒ 조건 (B). 임의의 a,b,c\in L에 대하여, :\begin{align} (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{align} 조건 (B) ⇒ 조건 (A). 임의의 a,b,c\in L에 대하여, 만약 a\le c라면, :\begin{align} 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{align} 이다. 따라서 L은 모듈러 격자이다. 이제, 임의의 a,b,c\in L에 대하여, :\begin{align} 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{align} 이다. (세 번째 등호는 모듈러 법칙을 사용한다.) 조건 (A) ⇒ 조건 (D). 임의의 a,b,c\in L에 대하여, 만약 a\le 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라고 가정하였을 때, 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{align}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{align} 증명 끝
# 성질
임의의 집합 S에 대하여, 그 멱집합의 격자 (\mathcal P(S),\subseteq)는 분배 격자이며, 이 격자의 모든 부분 격자도 분배 격자이다. 반대로, 선택 공리를 가정한다면, 모든 분배 격자는 멱집합 격자의 부분 격자와 동형이다.
## 함의 관계
모든 분배 격자는 모듈러 격자이다. 모든 헤이팅 대수는 분배 격자이다. 불 대수는 헤이팅 대수의 특수한 경우이므로 역시 분배 격자이다. 모든 전순서 집합 (T,\le)은 분배 격자이며, 이와 동형인 집합 격자는 \\{\\{s\le t|s\in S\\}|t\in T\\}\subset\mathcal P(T)이다.
## 보편 대수학적 성질
분배 격자의 부분 격자 위의 합동 관계는 전체 격자 위의 합동 관계로 확대될 수 있다.lccn=2011921250141, 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보존날짜=2022-07-2479 일반적인 대수 구조의 합동 관계 격자는 분배 격자일 필요가 없다.
## 반례
파일:Smallest nonmodular lattice 격자의 하세 도형 파일:Diamond 격자의 하세 도형 오각형 격자는 모듈러 격자가 아닌 가장 작은 격자이다. 특히, 오각형 격자는 분배 격자가 아니다. 다이아몬드 격자는 모듈러 격자이지만 분배 격자는 아닌 가장 작은 격자이다. 분배 격자는 이 두 격자를 부분 격자로 포함할 수 없지만, 부분 순서 집합으로 포함할 수는 있다.
## 자유 분배 격자
생성원의 크기가 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\ne\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, … A7153 **자유 유계 분배 격자**의 경우, 원소들은 위와 마찬가지이지만, 마지막 조건이 적용되지 않는다. 즉, :\varnothing=\bigvee\varnothing=\bot 과 :\\{\varnothing\\}=\bigwedge\varnothing=\top 이 존재한다. 즉, 같은 수의 생성원들을 갖는 자유 분배 격자보다 원소가 두 개 더 많다. 따라서 이들의 크기는 다음과 같다. :2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, … A372