분배 격자

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

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

정의[편집]

임의의 격자 에 대하여, 다음 네 조건들은 서로 동치이다.

  • 모든 에 대하여,
  • 모든 에 대하여,
  • 모든 에 대하여,
  • 모든 에 대하여, 만약 이며 라면 이다.

이 조건을 만족시키는 격자를 분배 격자라고 한다.

분배 격자의 준동형사상은 격자로서의 준동형사상이다. 즉, 격자 준동형사상 조건은 자동적으로 분배 법칙을 만족시킨다.

성질[편집]

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

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

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

[편집]

임의의 집합 에 대하여, 그 멱집합의 격자 는 분배 격자이다.

양의 정수의 (인수 관계에 대한) 격자 는 분배 격자이다. 이 경우, 각 양의 정수를

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

다음 두 부분 순서 집합들은 (실선만을 포함하고 점선을 포함하지 않는다면) 격자를 이루지만, 분배 격자를 이루지 않는다. 반면, 점선을 추가하면 이들은 분배 격자가 된다. 즉, 분배 격자는 비분배 격자를 부분 순서 집합으로 포함할 수 있다.

Non-dstrbtive lattices-warning.svg

자유 분배 격자[편집]

생성원의 크기가 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)

참고 문헌[편집]

외부 링크[편집]