격자 (순서론)

expanded=격자 순서론에서 **격자**(格子, lattice)는 두 원소의 상한(**이음**, 조인)과 하한(**만남**, 미트)이 항상 존재하는 부분 순서 집합이다.
# 정의
(유계) 격자의 개념은 추상대수학적으로, 순서론적으로, 또는 범주론적으로 정의할 수 있으며, 이 세 정의는 서로 동치이다.
## 대수학적 정의
**유계 격자**(有界格子, 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 title=증명 흡수성: :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)에 다음과 같은 부분 순서 \le를 줄 수 있다. :a\le 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) 속에서, 만약 서로 동형인 두 대상이 항상 같다면, 이를 **(유계) 격자**라고 한다. 이 경우, 세 정의들은 각각 다음과 같이 대응한다. {| class="wikitable" |- | 원소 || 원소 || 대상 |- | 두 원소의 이음 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\le b || 사상 a\to b의 존재 |- | 이음의 항등원 \bot || 최소 원소 \min L || 시작 대상 0 |- | 만남의 항등원 \top || 최대 원소 \max L || 끝 대상 1 |}
## 격자 준동형
격자 준동형이 아닌 증가 함수. u\vee v=1이지만, u'\vee u'=u'\ne1'이다. 두 유계 격자 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\le b라면 마찬가지로 \phi(a)\le\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,\le_L,\wedge_L,\vee_L)에 대하여, 그 **반대 격자**(opposite lattice) L^{\operatorname{op는 집합 L에 다음과 같은 격자 연산을 부여한 격자이다. 모든 a,b\in L에 대하여, :a\vee_{L^{\operatorname{opb=a\wedge_Lb :a\wedge_{L^{\operatorname{opb=a\vee_Lb :a\le_{L^{\operatorname{opb=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^+ 역시 격자를 이룬다. 이 경우, 격자 연산은 다음과 같다. {| class="wikitable" |- ! 정수론 !! 격자 |- | 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)들의 집합은 격자를 이룬다. {| class="wikitable" |- ! 분할 !! 격자 |- | 분할의 세분 \forall p\in P\colon\exists q\in Q\colon p\subset q || P\le Q |- | 공통 세분 \\{p\cap q|p\in P,q\in Q\\} || P\wedge Q |- | 공통 역세분 \min\\{R|R\ge P,Q\\} || P\vee Q |}
## 열린집합의 격자
위상 공간 X의 열린집합들은 포함 관계에 대하여 격자를 이룬다. 이 격자는 완비 헤이팅 대수이다.
## 대수학에서의 격자
대칭군 S_4의 부분군의 격자]] 군 G의 부분군들의 집합은 유계 완비 격자를 이룬다. {| class="wikitable" |- ! 부분군 !! 격자 |- | 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)은 유계 완비 격자를 이룬다. {| class="wikitable" |- ! 아이디얼 !! 격자 |- | \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의 부분 벡터 공간들의 집합은 완비 격자를 이룬다. 이 격자는 양자 논리의 기반을 이룬다. {| class="wikitable" |- ! 벡터 공간 !! 격자 |- | A\subset B || A\le B |- | A\cap B || A\wedge B |- | \operatorname{span}(A,B) || A\vee B |- | \\{0\\} || \bot |- | V || \top |}
# 역사
19세기에 조지 불은 명제 논리의 분석을 위하여 1848년에 유계 격자의 일종인 불 대수를 도입하였다.언어=en252 이와 독자적으로, 리하르트 데데킨트는 19세기 말에 대수적 수론에서 "쌍대군"(두알그루페)의 개념을 도입하였으며,언어=de언어=de 이는 오늘날의 격자의 개념과 유사하다. 그러나 데데킨트의 이 개념은 당시에 주목받지 못했다.253 이후 1920년대에 격자 이론은 다시 연구되기 시작하였다. 프리츠 클라인바르멘(Fritz Klein-Barmen, 1892~1961)은 이 개념을 페르반트(조직, 기구, 군 부대)라고 명명하였고,언어=de117언어=en55, 주석 4 이 용어는 오늘날 독일어에서 사용되고 있다.253 개릿 버코프(1911~1996)는 이를 추상대수학에 응용하였고, 래티스)(격자)라는 용어를 도입하였다.언어=en55, 주석 4254 프랑스어 용어 트레이(창살, 전투복)는 1945년에 마르셀폴 쉬첸베르제(Marcel-Paul Schützenberger, 1920~1996)가 도입하였다.언어=fr55, 주석 4