본문으로 이동

분배 격자

위키백과, 우리 모두의 백과사전.

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

정의

[편집]

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

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

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

  • (A) 모든 에 대하여,
  • (A’) 모든 에 대하여,
  • (B) 모든 에 대하여, [1]:73, Exercise 4.7
  • (C) 모든 에 대하여, 만약 이며 라면 이다.
  • (D) 오각형 격자를 부분 격자로 하지 않으며, 다이아몬드 격자를 부분 격자로 하지 않는다.[2]:12, Theorem 3.6[3]:89, Theorem 4.10(ii)

증명:

조건 (A) ⇒ 조건 (A’). 임의의 에 대하여,

(두 번째 등호는 흡수 법칙 를 사용한다.)

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

조건 (A) ⇒ 조건 (B). 임의의 에 대하여,

조건 (B) ⇒ 조건 (A). 임의의 에 대하여, 만약 라면,

이다. 따라서 모듈러 격자이다. 이제, 임의의 에 대하여,

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

조건 (A) ⇒ 조건 (D). 임의의 에 대하여, 만약 라면,

이다. 따라서 모듈러 격자이다. 즉, 은 오각형 격자를 부분 격자로 하지 않는다. 다이아몬드 격자 에서, 이지만, 이다. 따라서, 은 다이아몬드 격자를 부분 격자로 가질 수 없다.

조건 (D) ⇒ 조건 (B). 이 오각형 격자를 부분 격자로 하지 않으며, 어떤 , 에 대하여 라고 가정하였을 때, 의 다이아몬드 부분 격자를 찾는 것으로 족하다.

라고 하자. (각 식의 두 번째 등호는 모듈러 법칙에 따른다.) 가 다이아몬드 부분 격자임을 증명하자. 즉,

를 보여야 한다. 쌍대성 및 대칭성에 따라, 만을 보여도 좋다. 이는 다음과 같이 보일 수 있다.

성질

[편집]

임의의 집합 에 대하여, 그 멱집합의 격자 는 분배 격자이며, 이 격자의 모든 부분 격자도 분배 격자이다. 반대로, 선택 공리를 가정한다면, 모든 분배 격자는 멱집합 격자의 부분 격자와 동형이다.

함의 관계

[편집]

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

모든 헤이팅 대수는 분배 격자이다. 불 대수는 헤이팅 대수의 특수한 경우이므로 역시 분배 격자이다. 모든 전순서 집합 은 분배 격자이며, 이와 동형인 집합 격자는 이다.

보편 대수학적 성질

[편집]

분배 격자의 부분 격자 위의 합동 관계는 전체 격자 위의 합동 관계로 확대될 수 있다.[1]:141, Theorem 144 즉, 분배 격자 의 부분 격자 위의 합동 관계 에 대하여, 항상

위의 합동 관계 를 찾을 수 있다.

[편집]

양의 정수의 약수 관계에 대한 격자 는 분배 격자이다. 이 경우, 각 자연수

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

임의의 격자 합동 관계들의 격자 는 분배 격자이다.[1]:145, Theorem 149[2]:79 일반적인 대수 구조의 합동 관계 격자는 분배 격자일 필요가 없다.

반례

[편집]

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

자유 분배 격자

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

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

생성원들의 집합 가 주어졌다고 하자. 그렇다면, 이들로부터 생성되는 자유 분배 격자 는 다음과 같은 꼴의 원소들로 구성된다.

여기서

  • 모든 에 대하여 유한 집합이다.
  • 모든 에 대하여 만약 라면 이다.
  • 이며, 가 존재한다.

이러한 원소는

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

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

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

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

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

각주

[편집]
  1. Grätzer, George (2011). 《Lattice Theory: Foundation》 (영어). Basel: Springer. doi:10.1007/978-3-0348-0018-1. ISBN 978-3-0348-0017-4. LCCN 2011921250. MR 2768581. Zbl 1233.06001. 
  2. Burris, Stanley N.; Sankappanavar, Hanamantagouda P. (1981). 《A course in universal algebra》. Graduate Texts in Mathematics (영어) 78. Springer. ISBN 978-1-4613-8132-7. ISSN 0072-5285. MR 0648287. Zbl 0478.08001. 2022년 7월 24일에 원본 문서에서 보존된 문서. 2022년 8월 8일에 확인함. 
  3. Davey, Brian A.; Priestley, Hilary A. (2002). 《Introduction to lattices and order》 (영어) 2판. Cambridge: Cambridge University Press. ISBN 978-0-521-78451-1. MR 1902334. Zbl 1002.06001. 

외부 링크

[편집]