격자
격자는 순서집합에 한 가지 성질을 더한 것이다. 격자의 어떤 두 원소에 대해서도 상한과 하한이 있어야 하고, 그 상한과 하한도 격자에 속해야 한다.
상집합과 하집합
먼저 어떤 순서 ≤를 정한 집합 M이 있다고 하자. 이 순서는 아무것이나 될 수 있지만 순서관계의 조건은 만족해야 한다.
다음으로 집합 M의 원소 a를 하나 잡는다. 집합 M에서 원소 a의 상집합(위 원뿔)은 a보다 크거나 같은, 즉 a ≤ x인 x ∈ M 전체로 정의한다.
집합으로 자연수를, 원소로 a = 7을 잡으면 상집합은 수의 집합 {7, 8, 9, …}이다. 실수에서라면 구간 [7, ∞)를 얻는다.
집합으로 M = 2ℕ을 잡아 보자. 이것은 멱집합, 즉 자연수의 집합의 모든 부분집합의 집합이다. 다시 말해 자연수로 만들 수 있는 모든 집합이다. 순서는 부분집합 관계로 정한다. 그러면 {3, 5} ≤ {3, 4, 5} 등이 성립한다.
집합 {1, 2, 3, 4}의 상집합은 원소 1, 2, 3, 4를 포함하는 모든 집합이다. 예를 들어 집합 {1, 2, 3, 4, 5, 6, 9}나 {1, 2, 3, 4, 2323, 454645}이다. 집합 {1, 2, 3, 4} 자신도 상집합에 들어간다.
하집합(아래 원뿔)도 비슷하게 정의한다. 원소 a보다 작거나 같은 원소들로 이루어진다. a = 7이고 M이 자연수의 집합이면 집합 {1, 2, 3, 4, 5, 6, 7}을 얻는다. 7보다 작거나 같은 자연수들이다.
집합 {1, 2, 3, 4}라면 이 집합의 모든 부분집합을 얻는다.
여러 원소의 상집합과 하집합
앞에서는 원소 하나에 대한 상집합과 하집합을 정의했다. 하지만 원소 여러 개에 대한 상집합과 하집합도 정의할 수 있다. 집합 M과 원소 a, b가 있으면 두 원소의 공통 상집합에는 a와 b 모두보다 크거나 같은 원소들이 들어 있다. 다시 말해 두 원소의 상집합을 각각 구하고 그 교집합을 구한다. 그러면 a보다 크고 동시에 b보다 큰 원소들을 얻는다.
자연수로 계속해 보자. a = 3, b = 5라고 하자. a보다 크거나 같은 원소 전체는 집합 {3, 4, 5, 6, …}이고, b보다 크거나 같은 원소 전체는 {5, 6, 7, 8, …}이다. 이제 교집합을 구하면 다시 집합 {5, 6, 7, 8, …}을 얻는다. 전순서집합이라면 두 원소 가운데 큰 쪽을 찾아 그 상집합을 구하기만 하면 된다.
집합이라면 이렇게 간단하지 않다. 집합 a = {1, 2, 3}과 b = {2, 3, 4}의 하집합을 구해 보자. a와 b 모두의 부분집합인 집합 전체이다. 예를 들어 집합 {1, 2, 3}은 a의 부분집합일까? 그렇다. b의 부분집합이기도 할까? 아니다. 이 집합은 하집합에 들어가지 않는다.
a와 b 모두의 부분집합 가운데 가장 큰 집합이 무엇인지 보자. 분명히 집합 {2, 3}이다. 이것은 두 집합의 교집합 a ∩ b이다. 이 집합은 하집합에 들어간다. 이 집합의 모든 부분집합도 들어간다. 예를 들어 ∅ ⊆ {2, 3}이고 동시에 {2, 3} ⊆ a ∧ {2, 3} ⊆ b이면 당연히 ∅ ⊆ a ∧ ∅ ⊆ b이기 때문이다. 이것은 추이성에서 나온다.
마지막으로 두 원소가 아니라 집합 전체에 대한 상집합과 하집합을 정의하자. 집합 M과, 상집합과 하집합을 구하려는 집합 A ⊆ M이 있다고 하자. 그러면 다음이 성립한다.
상한과 하한
상집합과 하집합을 이용하면 상한과 하한을 쉽게 정의할 수 있다. 집합 M과 원소 a ∈ M이 있으면 원소 a의 상한과 하한은 모두 같은 원소 a이다.
하지만 M의 두 원소 a, b의 상한을 구하려면 다르게 해야 한다. 원소 a, b의 상한은 a ∨ b 또는 sup(a, b)로 나타내는데, 원소 a, b의 상집합에서 최소 원소와 같다. 즉 원소 a, b보다 크거나 같은 원소를 모두 구하고 그 가운데 최소 원소를 고른다. 극소 원소가 아니라 최소 원소이다. 최소 원소는 일반적으로 없을 수도 있으므로 상한도 일반적으로 없을 수 있다.
하한을 구할 때는 먼저 두 원소의 하집합을 구하고 그 가운데 최대 원소를 찾는다.
예: 수 3과 5의 상집합은 집합 {5, 6, 7, …}이라는 것을 이미 안다. 최소 원소는 5이다. 따라서 sup(3, 5) = 5이다.
또 집합 a = {1, 2, 3}과 b = {2, 3, 4}의 하집합은 집합 {2, 3}의 모든 부분집합의 집합이라는 것도 안다. 즉 집합 {2, 3}, {2}, {3}, ∅이다. 이 가운데 가장 큰 집합은 {2, 3}이다. 그래서 이 집합이 집합 a, b의 하한이다. a ∧ b = {2, 3} 또는 inf(a, b) = {2, 3}으로 나타낸다.
격자의 정의
격자 S는 어떤 두 원소 a, b ∈ S에 대해서도 상한과 하한이 있고, 그 하한과 상한이 집합 S에 속하는 순서집합이다. 그래서 다음이 성립하면 순서집합 S는 격자라고 쓸 수 있다.
격자의 간단한 예로 보통의 순서를 준 실수가 있다. sup(a, b) = max(a, b)이고 inf(a, b) = min(a, b)인데, 이것은 언제나 실수이다.
앞에서 도입한, 부분집합 관계에 따른 순서를 준 집합족도 격자이다. sup(a, b) = a ∪ b이고 inf(a, b) = a ∩ b이다. 이것도 그 집합족에 속하는 집합이다.
집합족 S로 원소가 두 개인 자연수의 부분집합 전체(예: {1, 2}, {7, 19}, …)를 잡으면 이 집합족은 격자가 아니다. 예를 들어 sup({1, 2}, {3, 4}) = {1, 2, 3, 4}인데, 집합 {1, 2, 3, 4}는 원소가 두 개인 자연수의 부분집합이 아니므로 이 집합족에 속하지 않기 때문이다.