격자 (순서론)

순서론에서 격자(格子, 영어: 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)은 공집합이 아닌 유한 이음과 만남을 보존하는 함수 $\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년에 유계 격자의 일종인 불 대수를 도입하였다.^[1]^:252 이와 독자적으로, 리하르트 데데킨트는 19세기 말에 대수적 수론에서 "쌍대군"(독일어: Dualgruppe 두알그루페^[*])의 개념을 도입하였으며,^[2]^[3] 이는 오늘날의 격자의 개념과 유사하다. 그러나 데데킨트의 이 개념은 당시에 주목받지 못했다.^[1]^:253

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

참고 문헌

위키미디어 공용에 관련된
미디어 분류가 있습니다.

격자

↑ ^가 ^나 ^다 ^라 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.
↑ Dedekind, Richard (1897). 〈Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler〉. 《Festschrift der Technische Hochschule》 (독일어). 브라운슈바이크: Vieweg. 1–40쪽.
↑ Dedekind, Richard (1900). “Über die von drei Moduln erzeugte Dualgruppe”. 《Mathematische Annalen》 (독일어) 53 (3): 371–403. doi:10.1007/BF01448979. ISSN 0025-5831.
↑ Klein, Fritz (1932). “Über einen Zerlegungssatz in der Theorie der abstrakten Verknüpfungen”. 《Mathematische Annalen》 (독일어) 106 (1): 114–130. doi:10.1007/BF01455881. ISSN 0025-5831.
↑ ^가 ^나 ^다 Hardouin Duparc, Olivier B. M. (2014년 6월). “Crystallography, group theory, etymology, and ’pataphysics”. 《The Mathematical Intelligencer》 (영어) 36 (2): 54–61. doi:10.1007/s00283-013-9426-0. ISSN 0343-6993.
↑ Birkhoff, Garrett (1933). “On the combination of subalgebra”. 《Proceedings of the Cambridge Philosophical Society》 (영어) 29: 441–464.
↑ Schützenberger, Marcel-Paul (1945). “Sur certains axiomes de la théorie des structures”. 《Comptes Rendus de l’Académie des Sciences》 (프랑스어) 221: 218-220.

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》 (영어).

[Bilova-1] 가 ^나 ^다 ^라 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.

[2] Dedekind, Richard (1897). 〈Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler〉. 《Festschrift der Technische Hochschule》 (독일어). 브라운슈바이크: Vieweg. 1–40쪽.

[3] Dedekind, Richard (1900). “Über die von drei Moduln erzeugte Dualgruppe”. 《Mathematische Annalen》 (독일어) 53 (3): 371–403. doi:10.1007/BF01448979. ISSN 0025-5831.

[4] Klein, Fritz (1932). “Über einen Zerlegungssatz in der Theorie der abstrakten Verknüpfungen”. 《Mathematische Annalen》 (독일어) 106 (1): 114–130. doi:10.1007/BF01455881. ISSN 0025-5831.

[HD-5] 가 ^나 ^다 Hardouin Duparc, Olivier B. M. (2014년 6월). “Crystallography, group theory, etymology, and ’pataphysics”. 《The Mathematical Intelligencer》 (영어) 36 (2): 54–61. doi:10.1007/s00283-013-9426-0. ISSN 0343-6993.

[6] Birkhoff, Garrett (1933). “On the combination of subalgebra”. 《Proceedings of the Cambridge Philosophical Society》 (영어) 29: 441–464.

[7] Schützenberger, Marcel-Paul (1945). “Sur certains axiomes de la théorie des structures”. 《Comptes Rendus de l’Académie des Sciences》 (프랑스어) 221: 218-220.

[1]

[2]

[3]

[4]

[5]

[6]

[7]