격자 (순서론)

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

순서론에서, 격자(格子, 영어: 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

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

격자 준동형사상[편집]

격자 준동형사상이 아닌 증가함수. u\vee v=1이지만, u'\vee u'=u'\ne1'이다.

두 격자 L,L' 사이의 격자 준동형사상(영어: lattice homomorphism)은 이음과 만남을 보존하는 사상 \phi\colon L\to L'이다. 즉, 다음 성질을 만족시키는 함수이다. 임의의 a,b\in L에 대하여,

\phi(a)\wedge\phi(b)=\phi(a\wedge b)
\phi(a)\vee\phi(b)=\phi(a\vee b)

이 경우, 만약 a\le b라면 마찬가지로 \phi(a)\le\phi(b)임을 쉽게 보일 수 있다. 따라서, 격자 준동형사상은 증가함수이다. 반면, 증가함수이지만 격자 준동형사상이 아닌 함수도 존재한다.

반대 격자[편집]

주어진 격자 (L,\le_L,\wedge_L,\vee_L)에 대하여, 그 반대 격자(영어: opposite lattice) L^{\operatorname{op}}는 집합 L에 다음과 같은 격자 연산을 부여한 격자이다. 모든 a,b\in L에 대하여,

a\vee_{L^{\operatorname{op}}}b=a\wedge_Lb
a\wedge_{L^{\operatorname{op}}}b=a\vee_Lb
a\le_{L^{\operatorname{op}}}b=a\ge_Lb

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

[편집]

전순서[편집]

전순서 집합 (T,\le)은 격자를 이룬다. 이 경우

a\vee b=\max\{a,b\}
a\wedge b=\min\{a,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\} 또한 격자를 이룬다.

약수의 격자[편집]

60의 약수들의 격자

양의 정수 n에 대하여, n의 (양의 정수인) 약수들은 격자를 이룬다. 마찬가지로, 모든 양의 정수의 격자 \mathbb Z^+ 역시 격자를 이룬다. 이 경우, 격자 연산은 다음과 같다.

정수론 격자
a\mid b (약수 관계) a\le b
\operatorname{lcm}(a,b) (최소공배수) a\vee b
\gcd(a,b) (최대공약수) a\wedge b

이는 환 \mathbb Z/n 또는 \mathbb Z의 아이디얼들의 격자의 특수한 경우이다.

분할 격자[편집]

집합 S분할 P\subset\mathcal P(S)들의 집합은 격자를 이룬다.

분할 격자
분할의 세분 \forall p\in P\colon\exists q\subset Q\colon p\subset q P\le Q
공통 세분 \{p\cap q|p\in Q,q\in Q\} P\wedge Q
공통 역세분 \max\{R|R\ge P,Q\} P\vee Q

열린 집합의 격자[편집]

위상공간 X의 열린 부분집합들은 포함 관계에 대하여 격자를 이룬다. 이 격자는 완비 헤이팅 대수이다.

대수학에서의 격자[편집]

대칭군 S_4의 부분군의 격자

G의 부분군들의 집합은 유계 완비 격자를 이룬다.

부분군 격자
H\subset H' H\le H'
H\cap H' H\wedge H'
\langle H\cup H'\rangle (H\cup H'으로 생성되는 부분군) H\vee H'
1 (자명군) \bot
G \top

마찬가지로, 주어진 군의 정규부분군들 역시 완비 모듈러 격자를 이룬다.

유사환 R아이디얼들의 집합 \operatorname{Ideal}(R)은 유계 완비 격자를 이룬다.

아이디얼 격자
\mathfrak a\subset\mathfrak b \mathfrak a\le\mathfrak b
\mathfrak a\cap\mathfrak b \mathfrak a\wedge\mathfrak b
\mathfrak a+\mathfrak b \mathfrak a\vee\mathfrak b
\{0\} \bot
R \top

벡터 공간 V의 부분공간들의 집합은 완비 격자를 이룬다. 이 격자는 양자 논리의 기반을 이룬다.

벡터 공간 격자
A\subset B A\le B
A\cap B A\wedge B
\operatorname{span}(A,B) A\vee B
\{0\} \bot
V \top

참고 문헌[편집]

  • (영어) 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》, 2판, Cambridge University Press. doi:10.1017/CBO9780511809088. Zbl 1002.06001. 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
  • (영어) Johnstone, Peter T. (1983년 4월). 《Stone spaces》, Cambridge Studies in Advanced Mathematics 3. Cambridge University Press. MR0698074. Zbl 0499.54001. ISBN 978-052123893-9
  • (영어) Bilová, Štěpánka (2001년). 〈Lattice theory — its birth and life〉, Eduard Fuchs: 《Mathematics throughout the ages. Contributions from the summer school and seminars on the history of mathematics and from the 10th and 11th Novembertagung on the history and philosophy of mathematics, Holbaek, Denmark, October 28-31, 1999, and Brno, the Czech Republic, November 2-5, 2000》. Prometheus, 250–257쪽. Zbl 1009.01014. ISBN 80-7196-219-8
  • (영어) Rota, Gian-Carlo (1977년 12월). The Many Lives of Lattice Theory. 《Notices of the American Mathematical Society》 44 (11): 1440–1445. Zbl 0908.06001.

바깥 고리[편집]