분배 격자

3. 성질

분배 격자는 몇 가지 동치적인 정의를 가진다. 예를 들어, 어떤 격자 ''L''이 분배 격자라는 것은 ''L''의 임의의 원소 ''x, y, z''에 대해, 만약 두 원소 ''x'', ''y''에 대해 어떤 원소 ''z''와의 만남(∧) 결과와 결합(∨) 결과가 각각 같다면 (즉, ''x'' ∧ ''z'' = ''y'' ∧ ''z'' 이고 ''x'' ∨ ''z'' = ''y'' ∨ ''z'' 이면), 반드시 ''x''와 ''y''는 같다는 조건과 동치이다.

가장 간단한 비분배 격자로는 "다이아몬드 격자" ''M''₃와 "오각형 격자" ''N''₅가 알려져 있다. 어떤 격자가 분배 격자인지 판별하는 중요한 기준 중 하나는, 그 격자가 부분 격자로서 ''M''₃나 ''N''₅와 동형인 것을 포함하지 않아야 한다는 것이다. 여기서 부분 격자는 원래 격자의 만남(∧) 및 결합(∨) 연산을 그대로 보존하는 부분 집합을 의미한다.

모든 분배 격자는 모듈러 격자의 성질도 만족한다. 또한 분배성은 몇 가지 다른 유용한 속성들을 수반하는데, 예를 들어 분배 격자에서는 만남-소수 원소와 만남-기약가능 원소가 동치이며, 마찬가지로 결합-소수 원소와 결합-기약가능 원소도 동치이다.^[7] 분배 격자의 피복 관계는 중앙 그래프를 형성하기도 한다.^[8]

3. 1. 모듈러 격자와의 관계

3. 2. 다른 격자와의 관계

• $L$의 모든 원소 $x,\; y,\; z$에 대해 다음 등식이 성립한다:

• 모든 원소 $x,\; y,\; z$에 대해, $x\; \backslash wedge\; z\; =\; y\; \backslash wedge\; z$ 이고 $x\; \backslash vee\; z\; =\; y\; \backslash vee\; z$ 이면 항상 $x\; =\; y$ 이다.

3. 3. 표현 정리

4. 예시

분배 격자는 여러 수학적 구조에서 자연스럽게 등장하는 중요한 개념이다. 예를 들어, 양의 정수 전체의 집합에 약수 관계를 부여한 격자 $(\backslash mathbb\; Z^+,\backslash mid)$는 분배 격자이다. 이 격자는 특정 집합 격자와 동형 관계를 가진다.

또한, 임의의 격자 $L$이 주어졌을 때, 그 합동 관계들의 격자인 $\backslash operatorname\{Cong\}(L)$는 항상 분배 격자가 된다는 중요한 성질이 있다.^[10][11] 이는 일반적인 대수 구조의 합동 관계 격자가 반드시 분배 격자일 필요는 없다는 점과 대비된다.

이 외에도 집합론, 논리학, 순서론 등 다양한 분야에서 분배 격자의 예를 찾아볼 수 있다. (자세한 내용은 하위 섹션 참고)

4. 1. 집합 격자

4. 2. 논리 연산

4. 3. 자연수 격자

4. 4. 정수 분할

4. 5. 기타

• 린덴바움-타르스키 대수는 대부분의 논리에서 결합(and)과 분리(or) 연산을 지원하며, 이는 분배 격자를 이룬다. 즉, 결합은 분리에 대해 분배 법칙을 만족하고, 그 반대도 성립한다.
• 모든 부울 대수는 분배 격자이다.
• 모든 헤이팅 대수는 분배 격자이다. 특히, 모든 지역과 모든 위상 공간의 열린 집합 격자가 여기에 포함된다. 또한 헤이팅 대수는 직관 논리의 린덴바움 대수로 볼 수 있어, 첫 번째 예시의 특별한 경우이기도 하다.
• 모든 전순서 집합은 최댓값을 합집합(join)으로, 최솟값을 교집합(meet)으로 하는 분배 격자이다.
• 자연수의 집합은 최대 공약수를 교집합으로, 최소 공배수를 합집합으로 하여 (조건부 완비) 분배 격자를 형성한다. 이 격자는 최소 원소인 1을 가지며, 이는 합집합 연산의 항등원 역할을 한다.
• 양의 정수 ''n''에 대해, ''n''의 모든 양의 약수 집합은 최대 공약수를 교집합으로, 최소 공배수를 합집합으로 하는 분배 격자를 형성한다. 이 격자는 ''n''이 제곱 인수가 없는 정수일 때, 그리고 오직 그때만 부울 대수가 된다.
• 격자 정렬 벡터 공간은 분배 격자이다.
• 정수 분할을 나타내는 영 격자는 영 다이어그램의 포함 관계 순서에 따라 분배 격자를 이룬다.
• 분배 다면체의 점들(좌표별 최솟값 및 최댓값 연산에 닫힌 볼록 다면체)은 이 두 연산을 각각 격자의 교집합과 합집합 연산으로 삼아 분배 격자를 형성한다.^[2]

5. 자유 분배 격자

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

자유 분배 격자는 주어진 생성원 집합으로부터 분배 법칙만을 만족하도록 자유롭게 생성된 격자 구조를 의미한다. 자유 유계 분배 격자는 여기에 추가로 최대 원소($\backslash top$)와 최소 원소($\backslash bot$)를 포함하는 구조이다. 생성원의 개수에 따른 자유 (유계) 분배 격자의 크기는 데데킨트 수와 밀접한 관련이 있다.

5. 1. 구성

• '''자유 분배 격자''': $G$의 유한 부분 집합들로 이루어진 모든 유한 반사슬들의 집합이다. 단, 여기서 공집합($\backslash varnothing$)인 반사슬($\backslash bigvee\; \backslash varnothing$, 즉 최소 원소 $\backslash bot$)과, 반사슬의 원소로서 공집합($\backslash bigwedge\; \backslash varnothing$, 즉 최대 원소 $\backslash top$)을 포함하는 경우는 제외된다. 즉, 반사슬 $\backslash \{N\_1,\; \backslash dots,\; N\_n\backslash \}$에서 $n>0$이고, 모든 $N\_i$는 공집합이 아니다.
• '''자유 유계 분배 격자''': 위와 동일하게 구성되지만, 최소 원소 $\backslash bot$ (공집합 반사슬 $\backslash varnothing$에 해당)와 최대 원소 $\backslash top$ (반사슬 $\backslash \{\backslash varnothing\backslash \}$에 해당)을 포함한다. 따라서 같은 수의 생성원을 갖는 자유 분배 격자보다 원소의 개수가 정확히 2개 더 많다.

• 결합($\backslash lor$): $S\; \backslash lor\; T$는 합집합 $S\; \backslash cup\; T$에서 부분 집합 관계에 있는 원소들을 제거하여 얻은 반사슬이다. (예: $N\_i\; \backslash subset\; M\_j$이면 $M\_j$ 제거)
• 만남($\backslash land$): $S\; \backslash land\; T$는 $\backslash \{N\_i\; \backslash cup\; M\_j\; \backslash mid\; N\_i\; \backslash in\; S,\; M\_j\; \backslash in\; T\backslash \}$로 구성된 집합족에서 부분 집합 관계에 있는 원소들을 제거하여 얻은 반사슬이다.

데데킨트 수는 매우 빠르게 증가하며, 현재 $n=9$까지의 값만 알려져 있다.

5. 2. 데데킨트 수

(OEIS의 수열 A007153)

만약 최소 원소($\backslash bot$, 빈 결합)와 최대 원소($\backslash top$, 빈 만남)를 포함하는 '''자유 유계 분배 격자'''를 고려하면, 원소의 개수는 위 데데킨트 수보다 2만큼 더 많다. 이 값들은 다음과 같다.

(OEIS의 수열 A000372)

참조

_[1] 서적 Lattice Theory https://archive.org/[...] American Mathematical Society
_[2] 간행물 Distributive lattices, polyhedra, and generalized flows
_[3] 간행물 Writings of Charles S. Peirce: 1879–1884 https://books.google[...] Indiana University Press
_[4] 학술지 On the Algebra of Logic
_[5] 학술지 Bemerkung zur Algebra der Logik http://gdz-lucene.tc[...]
_[6] 문서 Balbes and Dwinger (1975), p. 63 citing Birkhoff, G. "Subdirect unions in universal algebra", Bull. Amer. Math. Soc. SO (1944), 764-768.
_[7] 문서 See [[Birkhoff's representation theorem#The partial order of join-irreducibles]].
_[8] 간행물 A ternary operation in distributive lattices http://projecteuclid[...]
_[9] 서적
_[10] 서적
_[11] 서적 https://www.math.uwa[...] 2022-08-08