순서론적 정의

${ (L,\le) }$가 poset이라고 하자. 이때, ${ \forall a,b \in L }$에 대해,

\[\inf \{ a,b \}, \quad\sup\{ a,b \}\]

가 모두 존재하는 ${ L=(L,\le) }$을 lattice라고 한다.

대수적 정의

Universal Algebra

더 자세한 내용은 Universal Algebra 참조

${ A }$가 nonempty set이라고 하자,

  • (${ n }$-ary) operation은 함수 ${ f: A^{n} \to A }$
  • ${ F }$는 operation들의 sequence

순서쌍 ${ \mathfrak{A}=(A;F) }$를 algebra라고 한다.

이 문서에서는 lattice만 다루므로 ${ F }$가 유한인 경우만 생각하도록 하자.

\(F = (f_{0},f_{1}, \dots , f_{n-1})\) 이고 ${ f_{i} }$가 각각 ${ A }$의 ${ k_{i} }$-ary operation일 때 squence

\[\tau = (k_{0},k_{1}, \dots ,k_{n-1})\]

을 type of algebra ${ \mathfrak{A} }$라고 한다.

Semilattice

${(A, \circ)}$를 binary operation ${ \circ }$이 주어진 algebra라고 하자. 이것이 조건을 만족하면 semilattice라고 한다.

\[\begin{gather} \mbox{(Idem) } & a \circ a=a \\ \mbox{(Comm) } & a \circ b = b\circ a \\ \mbox{(Assoc) } & (a\circ b) \circ c = a \circ (b \circ c) \end{gather}\]

위 조건들은 각각

  • (Idem) = idempotency,
  • (Comm) = commutativity,
  • (Assoc) = associativity 라고 한다.

Lattice

nonempty set ${ L }$에 주어진 type (2,2)1 algebra ${ (L,\wedge,\vee) }$가 다음 조건을 만족하면 lattice라고 한다.

  1. ${ (L, \wedge) }$는 semilattice
  2. ${ (L,\vee) }$는 semilattice
  3. (Absorp) ${ a \vee ( a \wedge b ) = a}$ 이고 ${ a \wedge (a \vee b ) = a}$

조건 3 (Absorp) = Absorption이라고 한다.

기호 읽는법: ${ \wedge }$를 meet, ${ \vee }$를 join이라고 읽는다.

어렵게 생각하지 말고 Boolean logic을 생각하면 된다. 실제로 Boole algebra는 distribution lattice라는 종류의 lattice이다. meet를 and, join을 or로 생각하면 대강 맞다.

두 정의의 동등성

앞에서 우리는 lattice를 poset ${ (L,\le) }$와 algebra ${ (L;\wedge, \vee) }$에 대해서 각각 정의했다. 두 정의가 동등함을 보이는 것은 연습문제로 남기겠다.

poset과 algebra에서 정의한 lattice를 ${ \mathfrak{L}^{\mathrm{ord}} }$, ${ \mathfrak{L}^{\mathrm{alg}} }$ 로 각각 표기하자

Exercise 1. poset ${ (L,\le) }$에

\[\begin{eqnarray} a \wedge b &=& \inf \{ a,b \}\\ a\vee b &=& \sup \{ a,b \} \end{eqnarray}\]

라는 binary operation을 주면 ${ (L;\wedge,\vee) }$는 ${ \mathfrak{L}^{\mathrm{alg}} }$이다.

Hint: absorption을 너무 복잡하게 생각하지 말자.

${\sup { a,b } }$는 ${ a }$와 ${ b }$ 중 큰 것이므로 ${ \inf\{a,\sup\{ a,b \}\} =a }$ 이다.

Exercise 2. algebra ${ (L;\wedge,\vee) }$에 다음과 같은 순서를 주자.

\[a \le b \mbox{ if } a \vee b = b\]

${ (L,\le) }$는 ${ \mathfrak{L}^{\mathrm{ord}} }$이다.

Hint: transitivity는 다음과 같이 보일 수 있다.

\[a \vee c = a \vee (b \vee c) =(a \vee b) \vee c=b \vee c = c\]

함께보기

참고문헌

  1. Grätzer (2011). Lattice Theory: Foundation, Birkhäuser.

  1. 즉, ${ \wedge }$와 ${ \vee }$ 모두 binary operation on ${ L }$ ↩