격자
- 순서 구조
격자(lattice)는 만남과 이음을 가지는 순서 구조이다.
만남과 이음
부분 순서 집합 \(P\)와 그 부분집합 \(S\)가 주어졌을 때, 다음의 두 성질을 만족하는 \(m \in P\)를 \(S\)의 만남(meet)이라고 하고 \(\bigwedge S\)로 나타낸다.
- \(\forall x \in S, m \leq x\)
- \(\forall w \in P, (\forall x \in S, w \leq x) \to w \leq m\)
쌍대적으로, 다음의 두 성질을 만족하는 \(m \in P\)를 \(S\)의 이음(join)이라고 하고 \(\bigvee S\)로 나타낸다.
- \(\forall x \in S, x \leq m\)
- \(\forall w \in P, (\forall x \in S, x \leq w) \to m \leq w\)
만남은 최대하계(greatest lower bound), 이음은 최소상계(least upper bound)와 같은 개념이다. 부분 순서 집합에서 만남과 이음은 존재성이 보장되지 않지만, 존재한다면 각각 유일하다. 두 원소의 만남과 이음 \(\bigwedge \{x,y\}\), \(\bigvee \{x,y\}\)는 각각 \(x \wedge y\), \(x \vee y\)로 줄여 쓴다.
격자
부분 순서 집합의 임의의 두 원소의 만남이 존재하는 경우 만남 반격자(meet semilattice), 임의의 두 원소의 이음이 존재하는 경우 이음 반격자(join semilattice)라고 부른다. 임의의 두 원소의 만남과 이음이 모두 존재하는 경우에는 격자(lattice)라고 부른다.
완비 격자
부분 순서 집합의 임의의 부분집합에 대해 만남과 이음이 존재한다면 완비 격자(complete lattice)라고 부른다.
완비 반격자, 즉 임의의 부분집합에 대해 만남만이, 혹은 이음만이 존재하는 부분 순서 집합을 가리키는 개념은 별도로 정의하지 않는데, 이는 그러한 개념이 곧 완비 격자와 동치이기 때문이다.