분배 격자 문서 원본 보기

{{위키데이터 속성 추적}}
{{대수 구조|expanded=격자}}
[[순서론]]에서 '''분배 격자'''(分配格子, {{llang|en|distributive lattice}})는 만남과 이음이 서로 [[분배 법칙]]을 따르는 [[격자 (순서론)|격자]]이다. 모든 분배 격자는 항상 집합들의 포함 관계에 따른 격자로 나타낼 수 있다.

== 정의 ==
'''오각형 격자'''({{llang|en|pentagon lattice}})는 다음과 같은 [[유계 격자]]이다.
:<math>N_5=\{\bot,a,b,c,\top\}</math>
:<math>\bot\le a\le b\le\top</math>
:<math>\bot\le c\le\top</math>
'''다이아몬드 격자'''({{llang|en|diamond lattice}})는 다음과 같은 [[유계 격자]]이다.
:<math>M_5=\{\bot,a,b,c,\top\}</math>
:<math>\bot\le a,b,c\le\top</math>
임의의 [[격자 (순서론)|격자]] <math>(L,\wedge,\vee)</math>에 대하여, 다음 조건들은 서로 [[동치]]이며, 이 조건을 만족시키는 격자를 '''분배 격자'''라고 한다.
* (A) 모든 <math>a,b,c\in L</math>에 대하여, <math>a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c)</math>
* (A’) 모든 <math>a,b,c\in L</math>에 대하여, <math>a\vee(b\wedge c)=(a\vee b)\wedge(a\vee c)</math>
* (B) 모든 <math>a,b,c\in L</math>에 대하여, <math>(a\wedge b)\vee(b\wedge c)\vee(c\wedge a)=(a\vee b)\wedge(b\vee c)\wedge(c\vee a)</math><ref name="Grätzer" />{{rp|73, Exercise 4.7}}
* (C) 모든 <math>a,b,c\in L</math>에 대하여, 만약 <math>a\wedge c=b\wedge c</math>이며 <math>a\vee c=b\vee c</math>라면 <math>a=b</math>이다.
* (D) 오각형 격자를 부분 격자로 하지 않으며, 다이아몬드 격자를 부분 격자로 하지 않는다.<ref name="Burris" />{{rp|12, Theorem 3.6}}<ref name="DaveyPriestley">{{서적 인용
|이름1=Brian A.
|성1=Davey
|이름2=Hilary A.
|성2=Priestley
|제목=Introduction to lattices and order
|언어=en
|판=2
|출판사=Cambridge University Press
|위치=Cambridge
|날짜=2002
|isbn=978-0-521-78451-1
|mr=1902334
|zbl=1002.06001
}}</ref>{{rp|89, Theorem 4.10(ii)}}
{{증명}}
조건 (A) ⇒ 조건 (A’). 임의의 <math>a,b,c\in L</math>에 대하여,
:<math>\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}</math>
(두 번째 등호는 흡수 법칙 <math>(a\vee b)\wedge a=a</math>를 사용한다.)

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

조건 (A) ⇒ 조건 (B). 임의의 <math>a,b,c\in L</math>에 대하여,
:<math>\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}</math>

조건 (B) ⇒ 조건 (A). 임의의 <math>a,b,c\in L</math>에 대하여, 만약 <math>a\le c</math>라면,
:<math>\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}</math>
이다. 따라서 <math>L</math>은 [[모듈러 격자]]이다. 이제, 임의의 <math>a,b,c\in L</math>에 대하여,
:<math>\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}</math>
이다. (세 번째 등호는 모듈러 법칙을 사용한다.)

조건 (A) ⇒ 조건 (D). 임의의 <math>a,b,c\in L</math>에 대하여, 만약 <math>a\le c</math>라면,
:<math>a\vee(b\wedge c)=(a\wedge c)\vee(b\wedge c)=(a\vee b)\wedge c</math>
이다. 따라서 <math>L</math>은 [[모듈러 격자]]이다. 즉, <math>L</math>은 오각형 격자를 부분 격자로 하지 않는다. 다이아몬드 격자 <math>\{\bot,a,b,c,\top\}</math>에서, <math>a\wedge(b\vee c)=a\wedge\top=a</math>이지만, <math>(a\wedge b)\vee(a\wedge c)=\bot\vee\bot=\bot</math>이다. 따라서, <math>L</math>은 다이아몬드 격자를 부분 격자로 가질 수 없다.

조건 (D) ⇒ 조건 (B). <math>L</math>이 오각형 격자를 부분 격자로 하지 않으며, 어떤 <math>a,b,c\in L</math> 및 <math>d=(a\wedge b)\vee(b\wedge c)\vee(c\wedge a)</math>, <math>e=(a\vee b)\wedge(b\vee c)\wedge(c\vee a)</math>에 대하여 <math>d<e</math>라고 가정하였을 때, <math>L</math>의 다이아몬드 부분 격자를 찾는 것으로 족하다.
:<math>a'=(a\vee d)\wedge e=(a\wedge e)\vee d</math>
:<math>b'=(b\vee d)\wedge e=(b\wedge e)\vee d</math>
:<math>c'=(c\vee d)\wedge e=(c\wedge e)\vee d</math>
라고 하자. (각 식의 두 번째 등호는 모듈러 법칙에 따른다.) <math>\{d,a',b',c',e\}</math>가 다이아몬드 부분 격자임을 증명하자. 즉,
:<math>a'\wedge b'=b'\wedge c'=c'\wedge a'=d</math>
:<math>a'\vee b'=b'\vee c'=c'\vee a'=e</math>
를 보여야 한다. 쌍대성 및 대칭성에 따라, <math>a'\wedge b'=d</math>만을 보여도 좋다. 이는 다음과 같이 보일 수 있다.
:<math>\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}</math>
{{증명 끝}}

== 성질 ==
임의의 집합 <math>S</math>에 대하여, 그 [[멱집합]]의 격자 <math>(\mathcal P(S),\subseteq)</math>는 분배 격자이며, 이 격자의 모든 부분 격자도 분배 격자이다. 반대로, [[선택 공리]]를 가정한다면, 모든 분배 격자는 멱집합 격자의 부분 격자와 [[동형]]이다.

=== 함의 관계 ===
모든 분배 격자는 [[모듈러 격자]]이다.

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

=== 보편 대수학적 성질 ===
분배 격자의 부분 격자 위의 [[합동 관계]]는 전체 격자 위의 [[합동 관계]]로 확대될 수 있다.<ref name="Grätzer">{{서적 인용
|이름1=George
|성1=Grätzer
|제목=Lattice Theory: Foundation
|언어=en
|출판사=Springer
|위치=Basel
|날짜=2011
|isbn=978-3-0348-0017-4
|doi=10.1007/978-3-0348-0018-1
|mr=2768581
|zbl=1233.06001
|lccn=2011921250
}}</ref>{{rp|141, Theorem 144}} 즉, 분배 격자 <math>L</math>의 부분 격자 <math>M\subseteq L</math> 위의 [[합동 관계]] <math>\sim</math>에 대하여, 항상
:<math>\forall a,b\in M\colon a\sim'b\iff a\sim b</math>
인 <math>L</math> 위의 합동 관계 <math>\sim'</math>를 찾을 수 있다.

== 예 ==
양의 정수의 [[약수]] 관계에 대한 격자 <math>(\mathbb Z^+,\mid)</math>는 분배 격자이다. 이 경우, 각 자연수
:<math>n=\prod_{p\in\mathbb P}p^{n_p}</math>
를
:<math>\{p^i\colon p\in\mathbb P,\;i=0,1,\dots,n_p\}</math>
로 대응시키면, 이 격자와 [[동형]]인 집합 격자를 얻는다.

임의의 [[격자 (순서론)|격자]] <math>L</math>의 [[합동 관계]]들의 격자 <math>\operatorname{Cong}(L)</math>는 분배 격자이다.<ref name="Grätzer" />{{rp|145, Theorem 149}}<ref name="Burris">{{서적 인용
|이름1=Stanley N.
|성1=Burris
|이름2=Hanamantagouda P.
|성2=Sankappanavar
|제목=A course in universal algebra
|언어=en
|총서=Graduate Texts in Mathematics
|권=78
|출판사=Springer
|날짜=1981
|isbn=978-1-4613-8132-7
|issn=0072-5285
|mr=0648287
|zbl=0478.08001
|url=https://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html
|url-status=live
|확인날짜=2022-08-08
|보존url=https://web.archive.org/web/20220724132440/https://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html
|보존날짜=2022-07-24
}}</ref>{{rp|79}} 일반적인 [[대수 구조]]의 합동 관계 격자는 분배 격자일 필요가 없다.

=== 반례 ===
<gallery mode="packed" heights="220">
파일:Smallest nonmodular lattice 1.svg|오각형 격자의 [[하세 도형]]
파일:Diamond lattice.svg|다이아몬드 격자의 [[하세 도형]]
</gallery>
오각형 격자는 [[모듈러 격자]]가 아닌 가장 작은 격자이다. 특히, 오각형 격자는 분배 격자가 아니다. 다이아몬드 격자는 [[모듈러 격자]]이지만 분배 격자는 아닌 가장 작은 격자이다. 분배 격자는 이 두 격자를 부분 격자로 포함할 수 없지만, 부분 순서 집합으로 포함할 수는 있다.

=== 자유 분배 격자 ===
[[파일:Monotone Boolean functions.svg|섬네일|right|400px|생성원의 크기가 0, 1, 2, 3인 자유 유계 분배 격자. 자유 분배 격자의 경우 0과 1을 포함하지 않는다.]]
(유계) 분배 격자들은 [[대수 구조 다양체]]를 이루므로, 이에 대한 [[자유 대수]]를 정의할 수 있다. 즉, '''자유 분배 격자'''({{llang|en|free distributive lattice}}) 및 '''자유 유계 분배 격자'''({{llang|en|free bounded distributed lattice}})의 개념이 존재하며, 이는 자유 격자와 다르다. 일반적으로, 자유 격자는 구체적으로 묘사하기 힘들지만, 자유 분배 격자는 간단히 묘사할 수 있다.

생성원들의 집합 <math>A=a_i</math>가 주어졌다고 하자. 그렇다면, 이들로부터 생성되는 '''자유 분배 격자''' <math>\langle A\rangle</math>는 다음과 같은 꼴의 원소들로 구성된다.
:<math>\{M_1,M_2,\dots,M_n\}</math>
여기서
* 모든 <math>i</math>에 대하여 <math>M_i\subset A</math>는 [[유한 집합]]이다.
* 모든 <math>i,j=1,\dots, n</math>에 대하여 만약 <math>M_i\subset M_j</math>라면 <math>i=j</math>이다.
* <math>n>0</math>이며, <math>M_i\ne\varnothing</math>인 <math>i</math>가 존재한다.
이러한 원소는
:<math>\bigvee_i\left(\bigwedge M_i\right)</math>
로 해석된다. <math>n</math>개의 원소로 생성되는 자유 분배 격자의 크기는 '''데데킨트 수'''({{llang|en|Dedekind number}})라고 하며, 다음과 같다 (<math>n=0,1,2,\dots</math>).
:0, 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786, … {{OEIS|A7153}}

'''자유 유계 분배 격자'''의 경우, 원소들은 위와 마찬가지이지만, 마지막 조건이 적용되지 않는다. 즉,
:<math>\varnothing=\bigvee\varnothing=\bot</math>
과
:<math>\{\varnothing\}=\bigwedge\varnothing=\top</math>
이 존재한다. 즉, 같은 수의 생성원들을 갖는 자유 분배 격자보다 원소가 두 개 더 많다. 따라서 이들의 크기는 다음과 같다.
:2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, … {{OEIS|A372}}

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Distributive lattice}}
* {{매스월드|id=DistributiveLattice|title=Distributive lattice}}
* {{웹 인용|url=http://ncatlab.org/nlab/show/distributive+lattice|제목=Distributive lattice|웹사이트=nLab|언어=en}}

{{전거 통제}}

[[분류:격자 이론]]