격자 (순서론)

순서론에서 격자(格子, 영어: lattice)는 두 원소의 상한(이음, 영어: join 조인^[*])과 하한(만남, 영어: meet 미트^[*])이 항상 존재하는 부분 순서 집합이다.

정의

(유계) 격자의 개념은 추상대수학적으로, 순서론적으로, 또는 범주론적으로 정의할 수 있으며, 이 세 정의는 서로 동치이다.

대수학적 정의

유계 격자(有界格子, 영어: bounded lattice) $(L,\vee ,\wedge ,\bot ,\top )$는 두 개의 이항 연산 $\land ,\lor \colon L^{2}\to L$ 및 두 상수 $\bot ,\top \in L$가 주어지고, 다음 공리들을 만족시키는 대수 구조이다.

• $(L,\land ,\top )$는 가환 모노이드를 이룬다. 즉, 임의의 $a,b,c\in L$에 대하여 $(a\land b)\land c=a\land (b\land c)$이며 $a\land b=b\land a$이며 $a\land \top =a$이다.
• $(L,\lor ,\bot )$는 가환 모노이드를 이룬다. 즉, 임의의 $a,b,c\in L$에 대하여 $(a\lor b)\lor c=a\lor (b\lor c)$이며 $a\lor b=b\lor a$이며 $a\lor \bot =a$이다.
• (흡수성) 임의의 $a,b\in L$에 대하여, $a\vee (a\wedge b)=a\wedge (a\vee b)=a$

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

• (흡수성) $a\lor \top =\top$이며 $a\land \bot =\bot$
• (멱등성) $a\land a=a\lor a=a$

증명

흡수성:

$a\lor \top =(a\land \top )\lor \top =\top$

$a\land \bot =(a\lor \bot )\land \bot =\bot$

멱등성:

$a\wedge a=a\wedge (a\vee (a\wedge a))=a$

$a\vee a=a\vee (a\wedge (a\vee a))=a$

여기서 이항 연산 $\vee$를 이음, $\wedge$를 만남이라고 하며, $\top$은 최대 원소, $\bot$은 최소 원소라고 한다.

유계 격자의 정의에서 모노이드를 반군으로 약화시킨다면 (즉, 항등원의 존재를 생략한다면) 격자의 개념을 얻는다. 즉, 격자 $(L,\vee ,\wedge )$는 다음 세 공리들을 만족시키는 이항 연산 $\vee ,\wedge \colon L\times L\to L$이 주어진 대수 구조이다. 모든 $a,b,c\in L$에 대하여, 다음이 성립한다.

• $(L,\land )$는 가환 반군을 이룬다. 즉, 임의의 $a,b,c\in L$에 대하여 $(a\land b)\land c=a\land (b\land c)$이며 $a\land b=b\land a$이다.
• $(L,\lor )$는 가환 반군을 이룬다. 즉, 임의의 $a,b,c\in L$에 대하여 $(a\lor b)\lor c=a\lor (b\lor c)$이며 $a\lor b=b\lor a$이다.
• (흡수성) 임의의 $a,b\in L$에 대하여, $a\vee (a\wedge b)=a\wedge (a\vee b)=a$

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

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

$a\leq b\iff a=a\wedge b\iff b=a\vee b$

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

순서론적 정의

원순서 집합 $(L,\lesssim )$이 다음 조건을 만족시킨다면, 유계 원격자(有界原格子, 영어: bounded prelattice)라고 한다.

• 모든 유한 집합은 상한을 갖는다. (특히, 공집합의 경우, $L$은 최대 원소를 갖는다.)
• 모든 유한 집합은 하한을 갖는다. (특히, 공집합의 경우, $L$은 최소 원소를 갖는다.)

원순서 집합 $(L,\lesssim )$이 다음 조건을 만족시킨다면, 원격자(原格子, 영어: prelattice)라고 한다.

• 공집합이 아닌 모든 유한 집합은 상한을 갖는다.
• 공집합이 아닌 모든 유한 집합은 하한을 갖는다.

(유계) 원격자에서 상한·하한은 일반적으로 유일하지 않지만, 만약 여럿이 존재한다면 이들은 서로 동치이다. 즉, 그 동치류를 취할 수 있다. 이 개념을 대수적으로 정의하려면 연산이 유일하게 정의되어야 하므로, 원순서 집합 대신 부분 순서 집합을 사용하면 (유계) 격자(영어: (bounded) lattice)의 개념을 얻는다. 즉, (유계) 원격자인 부분 순서 집합을 (유계) 격자라고 한다.

범주론적 정의

원순서 집합은 작은 얇은 범주로 간주할 수 있으며, 따라서 격자의 순서론적 정의를 범주론의 언어로 재해석할 수 있다.

원순서 집합(작은 얇은 범주) $(L,\lesssim )$가 다음 두 조건을 만족시키면, 원격자(原格子, 영어: prelattice)라고 한다.

• 시작 대상을 제외한 모든 유한 곱을 갖는다.
• 끝 대상을 제외한 모든 유한 쌍대곱을 갖는다.

원순서 집합(작은 얇은 범주) $(L,\lesssim )$가 다음 두 조건을 만족시키면, 유계 원격자(有界原格子, 영어: bounded prelattice)라고 한다.

• 모든 유한 곱을 갖는다.
• 모든 유한 쌍대곱을 갖는다.

(유계) 원격자 $(L,\lesssim )$ 속에서, 만약 서로 동형인 두 대상이 항상 같다면, 이를 (유계) 격자라고 한다.

이 경우, 세 정의들은 각각 다음과 같이 대응한다.

대수적 정의	순서론적 정의	범주론적 정의
원소	원소	대상
두 원소의 이음 $a\lor b$	두 원소의 상한 $\sup\{a,b\}$	두 대상의 쌍대곱 $a\sqcup b$
두 원소의 만남 $a\land b$	두 원소의 하한 $\inf\{a,b\}$	두 대상의 곱 $a\times b$
$a=a\land b$ 또는 $b=a\lor b$	부분 순서 $a\leq b$	사상 $a\to b$의 존재
이음의 항등원 $\bot$	최소 원소 $\min L$	시작 대상 $0$
만남의 항등원 $\top$	최대 원소 $\max L$	끝 대상 $1$

격자 준동형

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

두 유계 격자 $L,L'$ 사이의 유계 격자 준동형(영어: bounded lattice homomorphism)은 유한 이음과 만남을 보존하는 함수 $\phi \colon L\to L'$이다. 즉, 다음 성질을 만족시키는 함수이다. 임의의 유한 부분 집합 $S\in L$에 대하여,

$\bigvee \phi (S)=\phi \left(\bigvee S\right)$

$\bigwedge \phi (S)=\phi \left(\bigwedge S\right)$

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

두 격자 $L,L'$ 사이의 격자 준동형(영어: lattice homomorphism)은 공집합이 아닌 유한 이음과 만남을 보존하는 함수 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \phi\colon L\to L'} 이다. 즉, 다음 성질을 만족시키는 함수이다. 임의의 유한 부분 집합 $S\in L$에 대하여, 만약 $S$가 공집합이 아니라면,

$\bigvee \phi (S)=\phi \left(\bigvee S\right)$

$\bigwedge \phi (S)=\phi \left(\bigwedge S\right)$

모든 유계 격자 준동형은 격자 준동형이지만, 그 역은 성립하지 않는다.

반대 격자

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

$a\vee _{L^{\operatorname {op} }}b=a\wedge _{L}b$

$a\wedge _{L^{\operatorname {op} }}b=a\vee _{L}b$

$a\leq _{L^{\operatorname {op} }}b=a\geq _{L}b$

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

예

전순서

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

$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\leq 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\leq 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\in Q\colon p\subset q$	$P\leq Q$
공통 세분 $\{p\cap q|p\in P,q\in Q\}$	$P\wedge Q$
공통 역세분 $\min\{R|R\geq P,Q\}$	$P\vee Q$

열린집합의 격자

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

대수학에서의 격자

대칭군 $S_{4}$의 부분군의 격자

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

부분군	격자
$H\subset H'$	$H\leq 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}}\leq {\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\leq B$
$A\cap B$	$A\wedge B$
$\operatorname {span} (A,B)$	$A\vee B$
$\{0\}$	$\bot$
$V$	$\top$

역사

19세기에 조지 불은 명제 논리의 분석을 위하여 1848년에 유계 격자의 일종인 불 대수를 도입하였다.^:252 이와 독자적으로, 리하르트 데데킨트는 19세기 말에 대수적 수론에서 "쌍대군"(독일어: Dualgruppe 두알그루페^[*])의 개념을 도입하였으며, 이는 오늘날의 격자의 개념과 유사하다. 그러나 데데킨트의 이 개념은 당시에 주목받지 못했다.^:253

이후 1920년대에 격자 이론은 다시 연구되기 시작하였다. 프리츠 클라인바르멘(독일어: Fritz Klein-Barmen, 1892~1961)은 이 개념을 독일어: Verband 페르반트^[*](조직, 기구, 군 부대)라고 명명하였고,^{:117:55, 주석 4} 이 용어는 오늘날 독일어에서 사용되고 있다.^:253 개릿 버코프(1911~1996)는 이를 추상대수학에 응용하였고, 영어: lattice 래티스^[*])(격자)라는 용어를 도입하였다.^{:55, 주석 4:254} 프랑스어 용어 프랑스어: treillis 트레이^[*](창살, 전투복)는 1945년에 마르셀폴 쉬첸베르제(프랑스어: Marcel-Paul Schützenberger, 1920~1996)가 도입하였다.^{:55, 주석 4}

참고 문헌

• 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.  CS1 관리 - 추가 문구 (링크)
• Birkhoff, Garrett (1967). 《Lattice theory》. AMS Colloquium Publications (영어) 25 3판. American Mathematical Society.  CS1 관리 - 추가 문구 (링크)
• 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. 
• Rota, Gian-Carlo (1977년 12월). “The Many Lives of Lattice Theory” (PDF). 《Notices of the American Mathematical Society》 (영어) 44 (11): 1440–1445. Zbl 0908.06001. 

외부 링크

• “Lattice”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Lattice”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Lattice theory”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Lattice automorphism”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Lattice homomorphism”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Lattice embedding”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Lattice endomorphism”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Lattice isomorphism”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Lattice”. 《nLab》 (영어). 
• “Lattice”. 《ProofWiki》 (영어).