격자 (순서론)

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

순서론에서, 격자(格子, 영어: lattice)는 부분 순서 집합의 하나로, 해당 집합의 임의의 두 원소로 이루어진 부분집합에 대해 항상 상한과 하한이 존재하는 부분 순서 집합이다. 다시 말해서, 부분 순서 집합 (S, \le)의 임의의 두 원소 a, b에 대해, a\leu, b\leu, l\lea, l\leb를 만족하는 최소 원소 u와 최대 원소 l이 항상 존재한다면 이 부분 순서 집합은 격자이다. 이때 상한(u)은 이음(join), 하한(l)은 만남(meet)이라고 부른다.

정의[편집]

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

대수학적 정의[편집]

격자 (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을 통해 부분 순서 집합을 이룬다. 이 부분 순서 집합은 격자를 이루며, 이 경우 집합 S의 어떤 두 부분 집합의 이음과 만남은 각각 두 부분 집합의 합집합교집합이다.

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. Zbl 0194.32503. 
  • Grätzer, G. (1971년). 《Lattice theory: first concepts and distributive lattices》 (영어). A Series of Books in Mathematics. W. H. Freeman. Zbl 0232.06001. 
  • Davey, B.A.; H. A. Priestley (2002년). 《Introduction to lattices and order》 (영어) 2판. Cambridge University Press. doi:10.1017/CBO9780511809088. ISBN 978-0-521-78451-1. Zbl 1002.06001. 
  • 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. ISBN 978-052123893-9. MR 0698074. Zbl 0499.54001. 
  • 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쪽. ISBN 80-7196-219-8. Zbl 1009.01014. 
  • Rota, Gian-Carlo (1977년 12월). “The Many Lives of Lattice Theory” (영어). 《Notices of the American Mathematical Society》 44 (11): 1440–1445. Zbl 0908.06001. 

바깥 고리[편집]