격자 (순서론)

순서론에서, 격자(格子, 영어: lattice)는 두 원소 부분집합의 상한(이음, 영어: join 조인[ *])과 하한(만남, 영어: meet 미트[ *])이 항상 존재하는 부분 순서 집합이다. 다시 말해, 임의의 에 대해, 인 최소 원소 과 최대 원소 가 항상 존재하는 부분 순서 집합 이다.

정의

(유계) 격자의 개념은 추상대수학적으로, 순서론적으로, 또는 범주론적으로 정의할 수 있으며, 이 세 정의는 서로 동치이다.

대수학적 정의

유계 격자(有界格子, 영어: bounded lattice) 는 두 개의 이항 연산 및 두 상수 가 주어지고, 다음 공리들을 만족시키는 대수 구조이다.

  • 가환 모노이드를 이룬다. 즉, 임의의 에 대하여 이며 이며 이다.
  • 가환 모노이드를 이룬다. 즉, 임의의 에 대하여 이며 이며 이다.
  • (흡수성) 임의의 에 대하여,

이로부터 다음 성질을 증명할 수 있다.

  • (흡수성) 이며
  • (멱등성)

여기서 이항 연산 이음, 만남이라고 하며, 최대 원소, 최소 원소라고 한다.

유계 격자의 정의에서 모노이드반군으로 약화시킨다면 (즉, 항등원의 존재를 생략한다면) 격자의 개념을 얻는다. 즉, 격자 는 다음 세 공리들을 만족시키는 이항 연산 이 주어진 대수 구조이다. 모든 에 대하여, 다음이 성립한다.

  • 가환 반군을 이룬다. 즉, 임의의 에 대하여 이며 이다.
  • 가환 반군을 이룬다. 즉, 임의의 에 대하여 이며 이다.
  • (흡수성) 임의의 에 대하여,

이로부터 다음을 증명할 수 있다.

격자 에 다음과 같은 부분 순서 를 줄 수 있다.

(이 두 성질은 흡수 법칙에 따라 동등하다.)

순서론적 정의

원순서 집합 이 다음 조건을 만족시킨다면, 유계 원격자(有界原格子, 영어: bounded prelattice)라고 한다.

원순서 집합 이 다음 조건을 만족시킨다면, 원격자(原格子, 영어: prelattice)라고 한다.

(유계) 원격자에서 상한·하한은 일반적으로 유일하지 않지만, 만약 여럿이 존재한다면 이들은 서로 동치이다. 즉, 그 동치류를 취할 수 있다. 이 개념은을 대수적으로 정의하려면 연산이 유일하게 정의되어야 하므로, 원순서 집합 대신 부분 순서 집합을 사용하면 (유계) 격자( 영어: (bounded) lattice)의 개념을 얻는다. 즉, (유계) 원격자인 부분 순서 집합(유계) 격자라고 한다.

범주론적 정의

원순서 집합작은 얇은 범주로 간주할 수 있으며, 따라서 격자의 순서론적 정의를 범주론의 언어로 재해석할 수 있다.

원순서 집합( 작은 얇은 범주) 가 다음 두 조건을 만족시키면, 원격자(原格子, 영어: prelattice)라고 한다.

원순서 집합( 작은 얇은 범주) 가 다음 두 조건을 만족시키면, 유계 원격자(有界原格子, 영어: bounded prelattice)라고 한다.

  • 모든 유한 을 갖는다.
  • 모든 유한 쌍대곱을 갖는다.

(유계) 원격자 속에서, 만약 서로 동형인 두 대상이 항상 같다면, 이를 (유계) 격자라고 한다.

이 경우, 세 정의들은 각각 다음과 같이 대응한다.

대수적 정의 순서론적 정의 범주론적 정의
원소 원소 대상
두 원소의 이음 두 원소의 상한 두 대상의 쌍대곱
두 원소의 만남 두 원소의 하한 두 대상의
또는 부분 순서 사상 의 존재
이음의 항등원 최소 원소 시작 대상
만남의 항등원 최대 원소 끝 대상

격자 준동형

격자 준동형이 아닌 증가 함수. 이지만, 이다.

두 유계 격자 사이의 유계 격자 준동형( 영어: bounded lattice homomorphism)은 유한 이음과 만남을 보존하는 함수 이다. 즉, 다음 성질을 만족시키는 함수이다. 임의의 유한 부분 집합 에 대하여,

이 경우, 만약 라면 마찬가지로 임을 쉽게 보일 수 있다. 따라서, 유계 격자 준동형은 증가 함수이다. 반면, 증가 함수이지만 격자 준동형이 아닌 함수도 존재한다.

두 유계 격자 사이의 격자 준동형( 영어: lattice homomorphism)은 공집합이 아닌 유한 이음과 만남을 보존하는 함수 이다. 즉, 다음 성질을 만족시키는 함수이다. 임의의 유한 부분 집합 에 대하여, 만약 공집합이 아니라면,

모든 유계 격자 준동형은 격자 준동형이지만, 그 역은 성립하지 않는다.

반대 격자

주어진 격자 에 대하여, 그 반대 격자( 영어: opposite lattice) 는 집합 에 다음과 같은 격자 연산을 부여한 격자이다. 모든 에 대하여,

즉, 부분 순서가 반대 방향이 되고, 만남과 이음이 서로 치환된다.