격자 (순서론) 문서 원본 보기

{{위키데이터 속성 추적}}
{{대수 구조|expanded=격자}}
[[순서론]]에서 '''격자'''(格子, {{llang|en|lattice}})는 두 원소의 [[상한과 하한|상한]]('''이음''', {{llang|en|join|조인}})과 [[상한과 하한|하한]]('''만남''', {{llang|en|meet|미트}})이 항상 존재하는 [[부분 순서 집합]]이다.

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

=== 대수학적 정의 ===
'''유계 격자'''(有界格子, {{llang|en|bounded lattice}}) <math>(L,\vee,\wedge,\bot,\top)</math>는 두 개의 이항 연산 <math>\land,\lor\colon L^2\to L</math> 및 두 상수 <math>\bot,\top\in L</math>가 주어지고, 다음 공리들을 만족시키는 [[대수 구조]]이다.
* <math>(L,\land,\top)</math>는 [[가환 모노이드]]를 이룬다. 즉, 임의의 <math>a,b,c\in L</math>에 대하여 <math>(a\land b)\land c=a\land(b\land c)</math>이며 <math>a\land b=b\land a</math>이며 <math>a\land\top=a</math>이다.
* <math>(L,\lor,\bot)</math>는 [[가환 모노이드]]를 이룬다. 즉, 임의의 <math>a,b,c\in L</math>에 대하여 <math>(a\lor b)\lor c=a\lor(b\lor c)</math>이며 <math>a\lor b=b\lor a</math>이며 <math>a\lor\bot=a</math>이다.
* (흡수성) 임의의 <math>a,b\in L</math>에 대하여, <math>a\vee(a\wedge b)=a\wedge(a\vee b)=a</math>
이로부터 다음 성질을 증명할 수 있다.
* (흡수성) <math>a\lor\top=\top</math>이며 <math>a\land\bot=\bot</math>
* (멱등성) <math>a\land a=a\lor a=a</math>
{{숨김 시작|title=증명}}
흡수성:
:<math>a\lor\top=(a\land\top)\lor\top=\top</math>
:<math>a\land\bot=(a\lor\bot)\land\bot=\bot</math>
멱등성:
:<math>a\wedge a=a\wedge(a\vee(a\wedge a))=a</math>
:<math>a\vee a=a\vee(a\wedge(a\vee a))=a</math>
{{숨김 끝}}
여기서 이항 연산 <math>\vee</math>를 '''이음''', <math>\wedge</math>를 '''만남'''이라고 하며, <math>\top</math>은 '''[[최대 원소]]''', <math>\bot</math>은 '''[[최소 원소]]'''라고 한다.

유계 격자의 정의에서 [[모노이드]]를 [[반군]]으로 약화시킨다면 (즉, 항등원의 존재를 생략한다면) '''격자'''의 개념을 얻는다. 즉, '''격자''' <math>(L,\vee,\wedge)</math>는 다음 세 공리들을 만족시키는 [[이항 연산]] <math>\vee,\wedge\colon L\times L\to L</math>이 주어진 [[대수 구조]]이다. 모든 <math>a,b,c\in L</math>에 대하여, 다음이 성립한다.
* <math>(L,\land)</math>는 [[가환 반군]]을 이룬다. 즉, 임의의 <math>a,b,c\in L</math>에 대하여 <math>(a\land b)\land c=a\land(b\land c)</math>이며 <math>a\land b=b\land a</math>이다.
* <math>(L,\lor)</math>는 [[가환 반군]]을 이룬다. 즉, 임의의 <math>a,b,c\in L</math>에 대하여 <math>(a\lor b)\lor c=a\lor(b\lor c)</math>이며 <math>a\lor b=b\lor a</math>이다.
* (흡수성) 임의의 <math>a,b\in L</math>에 대하여, <math>a\vee(a\wedge b)=a\wedge(a\vee b)=a</math>
이로부터 다음을 증명할 수 있다.

격자 <math>(L,\vee,\wedge)</math>에 다음과 같은 [[부분 순서]] <math>\le</math>를 줄 수 있다.
:<math>a\le b\iff a=a\wedge b\iff b=a\vee b</math>
(이 두 성질은 흡수 법칙에 따라 동등하다.)

=== 순서론적 정의 ===
[[원순서 집합]] <math>(L,\lesssim)</math>이 다음 조건을 만족시킨다면, '''유계 원격자'''(有界原格子, {{llang|en|bounded prelattice}})라고 한다.
* 모든 유한 집합은 [[상한]]을 갖는다. (특히, [[공집합]]의 경우, <math>L</math>은 [[최대 원소]]를 갖는다.)
* 모든 유한 집합은 [[하한]]을 갖는다. (특히, [[공집합]]의 경우, <math>L</math>은 [[최소 원소]]를 갖는다.)

[[원순서 집합]] <math>(L,\lesssim)</math>이 다음 조건을 만족시킨다면, '''원격자'''(原格子, {{llang|en|prelattice}})라고 한다.
* [[공집합]]이 아닌 모든 유한 집합은 [[상한]]을 갖는다.
* [[공집합]]이 아닌 모든 유한 집합은 [[하한]]을 갖는다.

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

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

[[원순서 집합]]([[작은 범주|작은]] [[얇은 범주]]) <math>(L,\lesssim)</math>가 다음 두 조건을 만족시키면, '''원격자'''(原格子, {{llang|en|prelattice}})라고 한다.
* [[시작 대상]]을 제외한 모든 유한 [[곱 (범주론)|곱]]을 갖는다.
* [[끝 대상]]을 제외한 모든 유한 [[쌍대곱]]을 갖는다.

[[원순서 집합]]([[작은 범주|작은]] [[얇은 범주]]) <math>(L,\lesssim)</math>가 다음 두 조건을 만족시키면, '''유계 원격자'''(有界原格子, {{llang|en|bounded prelattice}})라고 한다.
* 모든 유한 [[곱 (범주론)|곱]]을 갖는다.
* 모든 유한 [[쌍대곱]]을 갖는다.

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

이 경우, 세 정의들은 각각 다음과 같이 대응한다.
{| class="wikitable" style="text-align: center"
! 대수적 정의 !! 순서론적 정의 !! 범주론적 정의
|-
| 원소 || 원소 || 대상
|-
|  두 원소의 이음 <math>a\lor b</math> || 두 원소의 [[상한]] <math>\sup\{a,b\}</math> || 두 대상의 [[쌍대곱]] <math>a\sqcup b</math>
|-
|  두 원소의 만남 <math>a\land b</math> || 두 원소의 [[하한]] <math>\inf\{a,b\}</math> || 두 대상의 [[곱 (범주론)|곱]] <math>a\times b</math>
|-
| <math>a=a\land b</math> 또는 <math>b=a\lor b</math> || [[부분 순서]] <math>a\le b</math> || 사상 <math>a\to b</math>의 존재
|-
| 이음의 항등원 <math>\bot</math> || [[최소 원소]] <math>\min L</math> || [[시작 대상]] <math>0</math>
|-
| 만남의 항등원 <math>\top</math> || [[최대 원소]] <math>\max L</math> || [[끝 대상]] <math>1</math>
|}

=== 격자 준동형 ===
[[파일:Monotonic but nonhomomorphic map between lattices.gif|섬네일|오른쪽|격자 준동형이 아닌 [[증가 함수]]. <math>u\vee v=1</math>이지만, <math>u'\vee u'=u'\ne1'</math>이다.]]
두 유계 격자 <math>L,L'</math> 사이의 '''유계 격자 준동형'''({{llang|en|bounded lattice homomorphism}})은 유한 이음과 만남을 보존하는 함수 <math>\phi\colon L\to L'</math>이다. 즉, 다음 성질을 만족시키는 함수이다. 임의의 유한 부분 집합 <math>S\in L</math>에 대하여,
:<math>\bigvee\phi(S)=\phi\left(\bigvee S\right)</math>
:<math>\bigwedge\phi(S)=\phi\left(\bigwedge S\right)</math>
이 경우, 만약 <math>a\le b</math>라면 마찬가지로 <math>\phi(a)\le\phi(b)</math>임을 쉽게 보일 수 있다. 따라서, 유계 격자 준동형은 [[증가 함수]]이다. 반면, 증가 함수이지만 격자 준동형이 아닌 함수도 존재한다.

두 격자 <math>L,L'</math> 사이의 '''격자 준동형'''({{llang|en|lattice homomorphism}})은 공집합이 아닌 유한 이음과 만남을 보존하는 함수 <math>\phi\colon L\to L'</math>이다. 즉, 다음 성질을 만족시키는 함수이다. 임의의 유한 부분 집합 <math>S\in L</math>에 대하여, 만약 <math>S</math>가 [[공집합]]이 아니라면,
:<math>\bigvee\phi(S)=\phi\left(\bigvee S\right)</math>
:<math>\bigwedge\phi(S)=\phi\left(\bigwedge S\right)</math>
모든 유계 격자 준동형은 격자 준동형이지만, 그 역은 성립하지 않는다.

=== 반대 격자 ===
주어진 격자 <math>(L,\le_L,\wedge_L,\vee_L)</math>에 대하여, 그 '''반대 격자'''({{llang|en|opposite lattice}}) <math>L^{\operatorname{op}}</math>는 집합 <math>L</math>에 다음과 같은 격자 연산을 부여한 격자이다. 모든 <math>a,b\in L</math>에 대하여,
:<math>a\vee_{L^{\operatorname{op}}}b=a\wedge_Lb</math>
:<math>a\wedge_{L^{\operatorname{op}}}b=a\vee_Lb</math>
:<math>a\le_{L^{\operatorname{op}}}b=a\ge_Lb</math>
즉, [[부분 순서]]가 반대 방향이 되고, 만남과 이음이 서로 치환된다.

== 예 ==
=== 전순서 ===
[[전순서 집합]] <math>(T,\le)</math>은 격자를 이룬다. 이 경우
:<math>a\vee b=\max\{a,b\}</math>
:<math>a\wedge b=\min\{a,b\}</math>
이다.

=== 부분 집합 격자 ===
[[파일:Hasse diagram of powerset of 3.svg|섬네일|오른쪽|세 원소를 가진 집합의 [[부분 집합]]의 격자]]
[[집합]] <math>S</math>의 [[멱집합]] <math>\mathcal P(S)=\{A\subset S\}</math>은 부분 집합 관계 <math>\subset</math>을 통해 [[부분 순서 집합]]을 이룬다. 이 부분 순서 집합은 격자를 이루며, 이 경우 집합 <math>S</math>의 어떤 두 부분 집합의 이음과 만남은 각각 두 부분 집합의 [[합집합]]과 [[교집합]]이다.
:<math>A\subset B\iff A\le B</math>
:<math>A\cup B=A\vee B</math>
:<math>A\cap B=A\wedge B</math>
마찬가지로, <math>S</math>의 유한 부분 집합들의 집합 <math>\{A\subset S\colon |A|<\aleph_0\}</math> 또한 격자를 이룬다.

=== 약수의 격자 ===
[[파일:Lattice of the divisibility of 60.svg|섬네일|오른쪽|60의 약수들의 격자]]
양의 정수 <math>n</math>에 대하여, <math>n</math>의 (양의 정수인) 약수들은 격자를 이룬다. 마찬가지로, 모든 양의 정수의 격자 <math>\mathbb Z^+</math> 역시 격자를 이룬다. 이 경우, 격자 연산은 다음과 같다.
{| class="wikitable"
|-
! 정수론 !! 격자
|-
| <math>a\mid b</math> (약수 관계) || <math>a\le b</math>
|-
| <math>\operatorname{lcm}(a,b)</math> ([[최소공배수]]) || <math>a\vee b</math>
|-
| <math>\gcd(a,b)</math> ([[최대공약수]]) || <math>a\wedge b</math>
|}
이는 환 <math>\mathbb Z/n</math> 또는 <math>\mathbb Z</math>의 [[아이디얼]]들의 격자의 특수한 경우이다.

=== 분할 격자 ===
집합 <math>S</math>의 [[집합의 분할|분할]] <math>P\subset\mathcal P(S)</math>들의 집합은 격자를 이룬다.

{| class="wikitable"
|-
! 분할 !! 격자
|-
| 분할의 세분 <math>\forall p\in P\colon\exists q\in Q\colon p\subset q</math> || <math>P\le Q</math>
|-
| 공통 세분 <math>\{p\cap q|p\in P,q\in Q\}</math> || <math>P\wedge Q</math>
|-
| 공통 역세분 <math>\min\{R|R\ge P,Q\}</math> || <math>P\vee Q</math>
|}

=== 열린집합의 격자 ===
[[위상 공간 (수학)|위상 공간]] <math>X</math>의 [[열린집합]]들은 포함 관계에 대하여 격자를 이룬다. 이 격자는 [[완비 격자|완비]] [[헤이팅 대수]]이다.

=== 대수학에서의 격자 ===
[[파일:Symmetric group S4; lattice of subgroups Hasse diagram; all 30 subgroups.svg|섬네일|오른쪽|[[대칭군 (군론)|대칭군]] <math>S_4</math>의 부분군의 격자]]
[[군 (수학)|군]] <math>G</math>의 부분군들의 집합은 유계 완비 격자를 이룬다.
{| class="wikitable"
|-
! 부분군 !! 격자
|-
| <math>H\subset H'</math> || <math>H\le H'</math>
|-
| <math>H\cap H'</math> || <math>H\wedge H'</math>
|-
| <math>\langle H\cup H'\rangle</math> (<math>H\cup H'</math>으로 생성되는 부분군) || <math>H\vee H'</math>
|-
| 1 ([[자명군]]) || <math>\bot</math>
|-
| <math>G</math> || <math>\top</math>
|}
마찬가지로, 주어진 군의 [[정규 부분군]]들 역시 [[완비 격자|완비]] [[모듈러 격자]]를 이룬다.

[[유사환]] <math>R</math>의 [[아이디얼]]들의 집합 <math>\operatorname{Ideal}(R)</math>은 유계 [[완비 격자]]를 이룬다.
{| class="wikitable"
|-
! 아이디얼 !! 격자
|-
| <math>\mathfrak a\subset\mathfrak b</math> || <math>\mathfrak a\le\mathfrak b</math>
|-
| <math>\mathfrak a\cap\mathfrak b</math> || <math>\mathfrak a\wedge\mathfrak b</math>
|-
| <math>\mathfrak a+\mathfrak b</math> || <math>\mathfrak a\vee\mathfrak b</math>
|-
| <math>\{0\}</math> || <math>\bot</math>
|-
| <math>R</math> || <math>\top</math>
|}

[[벡터 공간]] <math>V</math>의 부분 벡터 공간들의 집합은 [[완비 격자]]를 이룬다. 이 격자는 [[양자 논리]]의 기반을 이룬다.
{| class="wikitable"
|-
! 벡터 공간 !! 격자
|-
| <math>A\subset B</math> || <math>A\le B</math>
|-
| <math>A\cap B</math> || <math>A\wedge B</math>
|-
| <math>\operatorname{span}(A,B)</math> || <math>A\vee B</math>
|-
| <math>\{0\}</math> || <math>\bot</math>
|-
| <math>V</math> || <math>\top</math>
|}

== 역사 ==
19세기에 [[조지 불]]은 [[명제 논리]]의 분석을 위하여 1848년에 유계 격자의 일종인 [[불 대수]]를 도입하였다.<ref name="Bilova">{{서적 인용|이름=Štěpánka|성=Bilová|장=Lattice theory — its birth and life|제목=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| 날짜=2001| pages=250–257| publisher=Prometheus| editor=Eduard Fuchs|장url=http://dml.cz/dmlcz/401261|zbl=1009.01014|isbn=80-7196-219-8|언어=en}}</ref>{{rp|252}}
이와 독자적으로, [[리하르트 데데킨트]]는 19세기 말에 [[대수적 수론]]에서 "쌍대군"({{llang|de|Dualgruppe|두알그루페}})의 개념을 도입하였으며,<ref>{{서적 인용|성=Dedekind|이름=Richard |저자링크=리하르트 데데킨트|날짜=1897|장=Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler|제목=Festschrift der Technische Hochschule|위치=[[브라운슈바이크]]|출판사=Vieweg|쪽=1–40|언어=de}}</ref><ref>{{저널 인용|성=Dedekind|이름=Richard |저자링크=리하르트 데데킨트|제목=Über die von drei Moduln erzeugte Dualgruppe|날짜=1900|doi=10.1007/BF01448979|저널=Mathematische Annalen|권=53|호=3|쪽=371–403|issn=0025-5831|언어=de}}</ref> 이는 오늘날의 격자의 개념과 유사하다. 그러나 데데킨트의 이 개념은 당시에 주목받지 못했다.<ref name="Bilova"/>{{rp|253}}

이후 1920년대에 격자 이론은 다시 연구되기 시작하였다. 프리츠 클라인바르멘({{llang|de|Fritz Klein-Barmen}}, 1892~1961)은 이 개념을 {{llang|de|Verband|페르반트}}(조직, 기구, 군 부대)라고 명명하였고,<ref>{{저널 인용|제목=Über einen Zerlegungssatz in der Theorie der abstrakten Verknüpfungen|이름=Fritz|성=Klein|날짜=1932|저널=Mathematische Annalen|doi=10.1007/BF01455881|issn=0025-5831|권=106|호=1|쪽=114–130|언어=de}}</ref>{{rp|117}}<ref name="HD">{{저널 인용|제목=Crystallography, group theory, etymology, and ’pataphysics|저널=The Mathematical Intelligencer|이름=Olivier B. M.|성=Hardouin Duparc|날짜=2014-06|doi=10.1007/s00283-013-9426-0|issn=0343-6993|권=36|호=2|쪽=54–61|언어=en}}</ref>{{rp|55, 주석 4}} 이 용어는 오늘날 [[독일어]]에서 사용되고 있다.<ref name="Bilova"/>{{rp|253}} [[개릿 버코프]](1911~1996)는 이를 [[추상대수학]]에 응용하였고, {{llang|en|lattice|래티스}})(격자)라는 용어를 도입하였다.<ref>{{저널 인용|성=Birkhoff|이름=Garrett|저자링크=개릿 버코프|날짜=1933|제목=On the combination of subalgebra|저널=Proceedings of the Cambridge Philosophical Society|권=29|쪽=441–464|언어=en}}</ref><ref name="HD"/>{{rp|55, 주석 4}}<ref name="Bilova"/>{{rp|254}} 프랑스어 용어 {{llang|fr|treillis|트레이}}(창살, [[전투복]])는 1945년에 마르셀폴 쉬첸베르제({{llang|fr|Marcel-Paul Schützenberger}}, 1920~1996)가 도입하였다.<ref>{{저널 인용|성=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|언어=fr}}</ref><ref name="HD"/>{{rp|55, 주석 4}}

== 참고 문헌 ==
{{각주}}
* {{서적 인용|성=Donnellan|이름=Thomas|날짜=1968|제목=Lattice theory|출판사=Pergamon|zbl=0194.32503|언어=en}}
* {{서적 인용|성=Grätzer|이름=G.|날짜=1971|제목=Lattice theory: first concepts and distributive lattices|출판사=W. H. Freeman|zbl=0232.06001|총서=A Series of Books in Mathematics|언어=en}}
* {{서적 인용 | last=Davey | first=B.A. | 공저자=H. A. Priestley |title=Introduction to lattices and order | 판=2판 | publisher=Cambridge University Press | isbn=978-0-521-78451-1 | 날짜=2002|doi=10.1017/CBO9780511809088|zbl=1002.06001|언어=en}}
* {{서적 인용|이름=Garrett|성= Birkhoff|저자링크=개릿 버코프|날짜=1967|제목=Lattice theory|판=3판|권=25|총서=AMS Colloquium Publications|출판사=American Mathematical Society|언어=en}}
* {{서적 인용|이름=Robert P. |성=Dilworth|공저자=Peter Crawley|날짜=1973|제목=Algebraic theory of lattices|url=https://archive.org/details/algebraictheoryo0000craw |출판사=Prentice-Hall|isbn=978-0-13-022269-5|언어=en}}
* {{서적 인용|이름=Peter T.|성=Johnstone|제목=Stone spaces|총서=Cambridge Studies in Advanced Mathematics|권=3|출판사=Cambridge University Press|날짜=1983-04|mr=0698074|zbl=0499.54001|url=http://www.cambridge.org/us/academic/subjects/mathematics/logic-categories-and-sets/stone-spaces?format=HB|isbn=978-052123893-9|언어=en}}
* {{저널 인용|제목=The Many Lives of Lattice Theory|이름=Gian-Carlo|성=Rota|저자링크=잔카를로 로타|url=http://www.ams.org/notices/199711/comm-rota.pdf|저널=Notices of the American Mathematical Society|날짜=1977-12|권=44|호=11|쪽=1440–1445|zbl=0908.06001|언어=en}}

== 외부 링크 ==
* {{위키공용분류-줄}}
* {{eom|title=Lattice}}
* {{매스월드|id=Lattice|title=Lattice}}
* {{매스월드|id=LatticeTheory|title=Lattice theory}}
* {{매스월드|id=LatticeAutomorphism|title=Lattice automorphism}}
* {{매스월드|id=LatticeHomomorphism|title=Lattice homomorphism}}
* {{매스월드|id=LatticeEmbedding|title=Lattice embedding}}
* {{매스월드|id=LatticeEndomorphism|title=Lattice endomorphism}}
* {{매스월드|id=LatticeIsomorphism|title=Lattice isomorphism}}
* {{nlab|id=lattice|title=Lattice}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Lattice|제목=Lattice|웹사이트=ProofWiki|언어=en}}
{{전거 통제}}

[[분류:격자 이론| ]]