격자 (순서론)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

순서론에서, 격자(格子, 영어: lattice)는 유한 집합의 만남과 이음이 존재하는 부분순서집합이다.

정의[편집]

격자의 개념은 추상대수학적으로 또는 순서론적으로 정의할 수 있으며, 이 두 정의는 서로 동치이다.

대수학적 정의[편집]

격자 (L,\vee,\wedge)는 다음 세 공리들을 만족시키는 이항연산 \vee,\wedge\colon L\times L\to L이 주어진 대수 구조이다. 여기서 \vee이음(영어: join 조임[*]), \wedge만남(영어: meet 미트[*])이라고 한다. 모든 a,b,c\in L에 대하여, 다음이 성립한다.

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

  • (멱등성) a\wedge a=a\vee a=a

격자 (L,\vee,\wedge)에 다음과 같은 부분순서 \le를 줄 수 있다.

a\le b\iff a=a\wedge b\iff b=a\vee b

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

순서론적 정의[편집]

다음 성질을 만족시키는 부분순서집합 (L,\le)격자라고 한다.

  • (이음의 존재) 모든 a,b\in L에 대하여, \{a,b\}상한 a\vee b\in L이 존재하며, 이를 이음(영어: join 조인[*])이라고 한다. 즉, 이는 다음을 만족시킨다.
    • a,b\le a\vee b
    • a,b\le c\implies a\vee b\le c
  • (이음의 존재) 모든 a,b\in L에 대하여, \{a,b\}하한 a\wedge b\in L이 존재하며, 이를 만남(영어: meet 미트[*])이라고 한다. 즉, 이는 다음을 만족시킨다.
    • a\wedge b\le a,b
    • c\le a,b\implies c\le a\wedge b

이음과 만남이 유일함을 쉽게 보일 수 있다.

[편집]

세 원소를 가진 집합의 멱집합은 격자를 이룬다.

집합 S멱집합 \mathcal P(S)=\{A\subset S\}은 부분집합 관계 \subset을 통해 부분순서집합을 이룬다. 이 부분순서집합은 격자를 이루며, 이 경우 이음과 만남은 각각 합집합교집합이다.

A\subset B\iff A\le B
A\cup B=A\vee B
A\cap B=A\wedge B

마찬가지로, S의 유한부분집합들의 집합 \{A\subset S\colon |A|<\aleph_0\} 또한 격자를 이룬다.

참고 문헌[편집]

  • (영어) Donnellan, Thomas (1968년). 《Lattice Theory》. Pergamon
  • (영어) Grätzer, G. (1971년). 《Lattice Theory: First concepts and distributive lattices》. W. H. Freeman
  • (영어) Davey, B.A., H. A. Priestley (2002년). 《Introduction to Lattices and Order》. Cambridge University Press. ISBN 978-0-521-78451-1
  • (영어) Birkhoff, Garrett (1967년). 《Lattice Theory》, AMS Colloquium Publications 25, 3판, American Mathematical Society
  • (영어) Dilworth, Robert P., Peter Crawley (1973년). 《Algebraic Theory of Lattices》. Prentice-Hall. ISBN 978-0-13-022269-5
  • (영어) Bilová, Štĕpánka (2001년). Eduard Fuchs: 《Lattice theory — its birth and life》. Prometheus, 250–257쪽

바깥 고리[편집]