격자(수학)

격자 모양으로 배열된 점에 대한 내용은 격자점 문서 참고하십시오.

[[대수학\|대수학 Algebra ]]
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	이론
기본 대상		연산 · 항등식( 가비의 이 · 곱셈 공식( 통분 · 약분) · 인수분해) · 부등식( 절대부등식) · 방정식( 풀이 · 근( 무연근 · 허근 · 비에트의 정리( 근과 계수의 관계) · 제곱근( 이중근호 · 개방법) · 환원 불능) · 부정 · 불능) · 비례식 · 다항식 · 산술( 시계 산술)
수 체계		자연수( 소수) · 정수( 음수) · 유리수 · 실수( 무리수( 대수적 무리수 · 초월수) · 초실수) · 복소수( 허수) · 사원수 · 팔원수 · 대수적 수 · 벡터 공간
다루는 대상과 주요 토픽
대수적 구조
	군(group)	대칭군 · 기본군 · 자유군 · 리 군 · 괴물군 · 점군 · 순환군 · 군의 작용 · 동형 정리 · 실로우 정리
	환(ring)	아이디얼
	체(field)	갈루아 이론 · 분해체
	대수	가환대수 · 리 대수 · 불 대수( 크로네커 델타)
마그마· 반군· 모노이드		자유 모노이드 · 가환 모노이드
선형대수학		벡터 · 행렬 · 텐서( 텐서곱) · 벡터 공간( 선형사상) · 가군(module) · 내적 공간( 그람-슈미트 과정 · 수반 연산자)
정리·추측
대수학의 기본정리 · 나머지 정리 · 유클리드 호제법 · 부분분수분해 · PID 위의 유한생성 가군의 기본정리 · 산술·기하 평균 부등식 · 바이어슈트라스 분해 정리 · 호지 추측^미해결 · 가환대수에서의 호몰로지 추측^미해결
관련 하위 분야
범주론		함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 · 토포스 이론 · 타입 이론
대수 위상수학		연속변형성 · 사슬 복합체 · 호몰로지 대수학( 호몰로지 · 코호몰로지) · mapping class group · 닐센-서스턴 분류
대수기하학		대수다양체 · 층 · 스킴 · 에탈 코호몰로지 · 모티브
대수적 정수론		타원곡선 · 디오판토스 방정식 · 유리근 정리 · 모듈러성 정리
가환대수학		스펙트럼 정리
표현론		실베스터 행렬
기타 및 관련 문서
수학 관련 정보 · 추상화 · 1학년의 꿈 · 노름 · 혼합계산 · 분배법칙 · 교환법칙 · 결합법칙 · 교재			}}}}}}}}}

이산수학 Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all"	이론
<colbgcolor=#3CC> 기본 대상	수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열	등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합	경우의 수( 공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프	수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제

기타	P-NP 문제^미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설^미해결 · 콜라츠 추측^미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서	논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학	}}}}}}}}}

1. 개요2. 정의

2.1. 순서를 이용한 정의

2.1.1. 부분순서집합2.1.2. 상한과 하한2.1.3. 반격자와 격자

2.2. 대수학적 정의2.3. 두 정의 사이의 관계

3. 종류

3.1. 유계격자3.2. 여원을 가지는 격자3.3. 분배격자3.4. 전순서집합3.5. 불 격자

1. 개요

lattice

격자는 임의의 원소쌍의 상한과 하한이 존재하는 부분순서집합을 뜻한다. 격자는 크게 두 가지 방법으로 정의할 수 있으며, 둘 다 같은 대상을 나타낸다.

2. 정의

2.1. 순서를 이용한 정의

2.1.1. 부분순서집합

집합 [math(A)]에 대해 다음 조건을 만족하는 이항관계 [math({\preceq}\bigl(\subseteq A^2\bigr))]를 부분순서[partial order]라고 한다.

반사성\[reflexivity\]: 임의의 원소 [math(a(\in A))]에 대해 [math(a\preceq a)]이다.
반대칭성\[antisymmetry\]: 임의의 원소 [math(a,b(\in A))]에 대해 [math(a\preceq b)]이고 [math(b\preceq a)]이면 [math(a=b)]이다.
추이성\[transitivity\]: 임의의 원소 [math(a,b,c(\in A))]에 대해 [math(a\preceq b)]이고 [math(b\preceq c)]이면 [math(a\preceq c)]이다.

부분순서는 어떤 두 원소 사이에 순서 관계가 있음을 나타내지만, 꼭 모든 원소 사이에 순서 관계가 있을 필요는 없다. 예를 들어, 집합의 부분집합 관계 [math(\subseteq)]를 생각하자. 이 관계는 다음과 같이 반사성, 비대칭성, 추이성을 모두 만족하므로 부분순서이다.

반사성
임의의 집합 [math(A)]를 생각하자. 임의의 원소 [math(a(\in A))]에 대해 [math(a\in A)]이므로 [math(A\subseteq A)]이다.
반대칭성
[math(A\subseteq B)]와 [math(B\subseteq A)]를 만족하는 임의의 집합 [math(A,B)]를 생각하면 집합의 상등 정의에 의해 [math(A=B)]이다.
추이성
[math(A\subseteq B)]와 [math(B\subseteq C)]를 만족하는 임의의 집합 [math(A,B,C)]를 생각하자. 임의의 원소 [math(a(\in A))]에 대해, [math(A\subseteq B)], [math(a\in A)]에서 [math(a\in B)]이고, [math(B\subseteq C)], [math(a\in B)]에서 [math(a\in C)]이므로, [math(A\subseteq C)]이다.

부분순서 [math({\preceq})]가 주어진 집합 [math(A)]를 부분순서집합\[partially ordered set, poset\]이라고 하고, [math((A,{\preceq}))]로 표기한다. 앞에서 [math({\subseteq})]가 부분순서임을 알았으므로 원소가 집합인 임의의 집합은 부분순서집합임을 알 수 있다. 예를 들어, 집합 [math(P=\{\{1\},\{1,2\},\{2,3\}\})]이라고 정의된 집합 [math(P)]는 부분순서 [math({\subseteq})][1]를 가지므로 부분순서집합이고, [math((P,{\subseteq}))]로 표기한다. 같은 방식으로 [math(Q=\{\{1\},\{3\},\{1,2,3\},\{1,3,4\},\{1,2,3,4\}\})]라고 정의된 집합 [math(Q)]와 부분순서 [math({\subseteq})][2]로 구성된 [math((Q,{\subseteq}))]도 부분순서집합이다. 집합이 아닌 원소를 가지는 예시로는 [math(R=\{1,e,\pi\})]라고 정의된 집합 [math(R)]와 부분순서 [math({\le})][3]로 구성된 부분순서집합 [math((R,{\le}))]가 있다.

집합 [math(A)]에 대해 다음 조건을 만족하는 이항관계 [math({\prec}\bigl(\subseteq A^2\bigr))]를 순부분순서[strict partial order]라고 한다.

비반사성\[irreflexivity\]: 임의의 원소 [math(a(\in A))]에 대해 [math(a\nprec a)]이다.
비대칭성\[asymmetry\]: 임의의 원소 [math(a,b(\in A))]에 대해 [math(a\prec b)]이면 [math(b\nprec a)]이다.[4]
추이성: 임의의 원소 [math(a,b,c(\in A))]에 대해 [math(a\prec b)]이고 [math(b\prec c)]이면 [math(a\prec c)]이다.

순부분순서의 예시로는 진부분집합 관계 [math({\subset})]가 있다. 사실 임의의 부분순서에 대해, 부분순서에서 반사적인 원소만 빼는 방식으로 순부분순서를 자연스럽게 정의할 수 있다. 예를 들어 앞의 [math((P,{\subseteq}))]에서 순부분순서 [math({\subset})]를 [math({\subset}=\{(\{1\},\{1,2\})\})]라고 정의할 수 있다. 이제부터는 임의의 부분순서집합 [math((A,{\preceq}))]에 대해, 부분순서 [math({\preceq})]와 순부분순서 [math({\prec})], 그리고 이의 역관계 [math({\succeq})]와 [math({\succ})]를 자연스럽게 정의해 사용하기로 한다. 주의해야 할 것은, [math({\npreceq})]와 [math({\succ})]가 같을 이유가 없고, [math({\nprec})]와 [math({\succeq})]가 같을 이유가 없다는 점이다.

2.1.2. 상한과 하한

부분순서집합 [math((A,{\preceq}))]의 임의의 원소 [math(a)]에 대해 [math(g\nprec a)]를 만족하는 원소 [math(g(\in A))]를 [math(A)]의 극대원소\[maximal element\]라고 한다. 또, 임의의 원소 [math(a(\in A))]에 대해 [math(m\nsucc a)]를 만족하는 원소 [math(m(\in A))]을 [math(A)]의 극소원소\[minimal element\]라고 한다. 부분순서집합에서 극대원소와 극소원소는 하나만 존재할 수도, 여러 개가 존재할 수도, 존재하지 않을 수도 있다. 예를 들어, 앞에서 본 [math((P,{\subseteq}))]의 극대원소로는 [math(\{1,2\})], [math(\{2,3\})]이 있고, 극소원소로는 [math(\{1\})], [math(\{2,3\})]이 있다. [math((Q,{\subseteq}))]의 극대원소로는 [math(\{1,2,3,4\})]가 유일하며, 극소원소로는 [math(\{1\})], [math(\{3\})]이 있다. 또, [math((R,{\le}))]의 극대원소로는 [math(\pi)]가 유일하고, 극소원소로는 [math(1)]이 유일하다.

부분순서집합 [math((A,{\preceq}))]의 임의의 원소 [math(a)]에 대해 [math(g\succeq a)]를 만족하는 원소 [math(g(\in A))]를 [math(A)]의 최대원소\[greatest element\]라고 한다. 또, 임의의 원소 [math(a(\in A))]에 대해 [math(m\preceq a)]를 만족하는 원소 [math(m(\in A))]을 [math(A)]의 최소원소\[least element\]라고 한다. 부분순서집합에서 최대원소와 최소원소는 존재하지 않을 수도 있지만, 존재한다면 유일하다. 예를 들어, [math((P,{\subseteq}))]에서는 최대원소와 최소원소 모두 존재하지 않지만, [math((Q,{\subseteq}))]에서는 최대원소만 [math(\{1,2,3,4\})]로 유일하게 존재한다. [math((R,{\le}))]에서는 최대원소와 최소원소가 각각 [math(\pi)], [math(1)]로 둘 다 유일하게 존재한다.

부분순서집합 [math((A,{\preceq}))]의 부분집합 [math(B)]를 생각하자. 임의의 원소 [math(b(\in B))]에 대해 [math(g\succeq b)]를 만족하는 원소 [math(g(\in A))]를 [math(B)]의 상계\[upper bound\]라고 한다. 또, 임의의 원소 [math(b(\in B))]에 대해 [math(m\preceq b)]를 만족하는 원소 [math(m(\in A))]을 [math(B)]의 하계\[lower bound\]라고 한다. 상계와 하계는 굳이 [math(B)]의 원소일 필요가 없으며, 하나만 존재할 수도, 여러 개가 존재할 수도, 존재하지 않을 수도 있다. 예를 들어, [math((P,{\subseteq}))]의 부분집합 [math(\{\{1,2\},\{2,3\}\})]은 상계와 하계를 가지지 않지만, 부분집합 [math(\{\{1,2\}\})]는 상계로는 [math(\{1,2\})]를, 하계로는 [math(\{1\})]과 [math(\{1,2\})]를 가진다.

부분순서집합 [math((A,{\preceq}))]와 부분집합 [math(B)]에 대해, [math(B)]의 상계 중 최소인 원소를 [math(B)]의 상한\[supremum\] 또는 최소상계\[least upper bound\]라고 하고, [math(B)]의 하한 중 최대인 원소를 [math(B)]의 하한\[infimum\] 또는 최대하계\[greatest lower bound\]라고 한다. 상한과 하한은 존재하지 않을 수도 있지만, 존재하다면 유일하다. 예를 들어, [math((Q,{\subseteq}))]의 부분집합 [math(\{\{1,2,3\},\{1,3,4\}\})]는 상계로 [math(\{1,2,3,4\})]를 가지며 이 집합이 상한이다. 하지만, 하계로는 [math(\{1\})]과 [math(\{3\})]을 가짐에도 불구하고 최소원소가 없어 하한은 존재하지 않는다.

2.1.3. 반격자와 격자

이제 격자를 정의하자. 임의의 원소쌍의 상한이 존재하는 부분순서집합을 이음반격자\[join-semilattice\]라고 한다. 상한은 존재하면 유일하므로 이음반격자의 임의의 원소쌍의 상한은 유일하게 존재한다. 예를 들어, [math((P,{\subseteq}))]와 [math((Q,{\subseteq}))]는 각각 원소쌍 [math(\{\{1,2\},\{2,3\}\})], [math(\{\{1\},\{3\}\})]의 상한이 존재하지 않으므로 이음반격자가 아니다. 하지만, [math((R,{\le}))]는 각각 임의의 원소쌍의 상한이 존재하므로 이음반격자이다. 임의의 원소쌍의 하한이 존재하는 부분순서집합을 만남반격자\[meet-semilattice\]라고 한다. 하한은 존재하면 유일하므로 이음반격자의 임의의 원소쌍의 하한은 유일하게 존재한다. 예를 들어, [math((P,{\subseteq}))]와 [math((Q,{\subseteq}))]는 각각 원소쌍 [math(\{\{1,2\},\{2,3\}\})], [math(\{\{1\},\{3\}\})]의 하한이 존재하지 않으므로 만남반격자가 아니다. 하지만, [math((R,{\le}))]는 임의의 원소쌍의 하한이 존재하므로 만남반격자이다. 이음반격자와 만남반격자를 통틀어 반격자\[semilattice\]라고 한다.

이음반격자이면서 만남반격자인 부분순서집합, 즉, 임의의 원소쌍의 상한과 하한이 존재하는 부분순서집합을 격자\[lattice\]라고 한다. [math((R,{\le}))]는 이음반격자이면서 만남반격자이므로 격자이다.

다음은 순서를 이용해 정의한 격자의 예시이다.

이하 관계 [math({\le})]를 가지는 실수 집합 [math((\R,{\le}))]
집합 [math(A)]에 대해, 부분집합 관계 [math({\subseteq})]를 가지는, [math(A)]의 멱집합 [math((\mathcal P(A),{\subseteq}))]
나누어떨어짐 관계 [math(|)][5]를 가지는 양의 정수 집합 [math((\Z^+,|))]

2.2. 대수학적 정의

이번에는 대수학적으로 격자를 정의한다. 다음 조건을 만족하는 연산 [math({\land}:S^2\rightarrow S)]을 가지는 집합 [math(S)]를 반격자\[semilattice\]라고 하고, [math((S,{\land}))]로 표기한다.

결합법칙[associativity]: 임의의 원소 [math(a,b,c(\in S))]에 대해 [math((a\land b)\land c=a\land(b\land c))]이다.
교환법칙[commutativity]: 임의의 원소 [math(a,b(\in S))]에 대해 [math(a\land b=b\land a)]이다.
멱등법칙\[idempotency\]: 임의의 원소 [math(a(\in S))]에 대해 [math(a\land a=a)]이다.

다음 조건을 만족하는 연산 [math({\lor}:L^2\rightarrow L)]과 [math({\land}:L^2\rightarrow L)]을 가지는 집합 [math(L)]을 격자\[lattice\]라고 하고, [math((L,{\lor},{\land}))]로 표기한다. 이때 [math({\lor})]을 이음 연산, [math({\land})]을 만남 연산이라고 한다.

결합법칙: 임의의 원소 [math(a,b,c(\in L))]에 대해 [math((a\lor b)\lor c=a\lor(b\lor c))]이고 [math((a\land b)\land c=a\land(b\land c))]이다.
교환법칙: 임의의 원소 [math(a,b(\in L))]에 대해 [math(a\lor b=b\lor a)]이고 [math(a\land b=b\land a)]이다.
멱등법칙: 임의의 원소 [math(a(\in L))]에 대해 [math(a\lor a=a)]이고 [math(a\land a=a)]이다.[6]
흡수법칙\[absorption\]: 임의의 원소 [math(a,b(\in L))]에 대해 [math(a\lor(a\land b)=a)]이고 [math(a\land(a\lor b)=a)]이다.

다음은 대수학적으로 정의한 격자의 예시이다.

최댓값 연산 [math(\max:\R^2\rightarrow\R)]와 최솟값 연산 [math(\min:\R^2\rightarrow\R)]을 가지는 실수 집합 [math((\R,\max,\min))]
집합 [math(A)]에 대해, 합집합 연산 [math({\cup})]과 교집합 연산 [math({\cap})]을 가지는, [math(A)]의 멱집합 [math((\mathcal P(A),{\cup},{\cap}))]
최소공배수 연산 [math(\mathrm{lcm}:\left(\Z^+\right)^2\rightarrow\Z^+)]과 최대공약수 연산 [math(\gcd:\left(\Z^+\right)^2\rightarrow\Z^+)]를 가지는 양의 정수 집합 [math((\Z^+,\mathrm{lcm},\gcd))]

2.3. 두 정의 사이의 관계

이제 두 정의가 같음을 보인다. 먼저 순서를 이용해 정의한 격자 [math((A,{\preceq}))]를 생각하자. [math(A)] 위의 이항연산 [math({\lor}:A^2\rightarrow A)]과 [math({\land}:A^2\rightarrow A)]을 각각 원소쌍의 상한과 하한으로 정의한다. 즉, 임의의 원소 [math(a,b(\in A))]에 대해 [math(a\lor b)]와 [math(a\land b)]는 각각 [math(\{a,b\})]의 상한과 하한을 나타낸다. 격자의 정의에서 원소쌍의 상한과 하한이 유일하게 존재하므로 두 연산이 잘 정의됨을 알 수 있다. 이제 이 두 연산이 대수학적 정의를 만족함을 보이자.

결합법칙
임의의 원소 [math(a,b,c(\in A))]에 대해, [math(\{a\lor b,c\})]의 모든 상계의 집합을 [math(G_1)], [math(\{a,b\lor c\})]의 모든 상계의 집합을 [math(G_2)]라고 하자. 그러면 [math(G_1)]과 [math(G_2)]는 다음을 만족한다.

[math(G_1)]의 임의의 원소 [math(g)]를 생각하자. [math(g\succeq a\lor b)], [math(a\lor b\succeq a)]에서 [math(g\succeq a)]이다. 또, [math(g\succeq a\lor b)], [math(a\lor b\succeq b)]에서 [math(g\succeq b)]이고, [math(g\succeq b)], [math(g\succeq c)]에서 [math(g)]가 [math(\{b,c\})]의 상계이므로, [math(\{b,c\})]의 상한 [math(b\lor c)]에 대해 [math(g\succeq b\lor c)]이다. 따라서 [math(g)]는 [math(\{a,b\lor c\})]의 상계, 즉, [math(G_2)]의 원소이고, 여기서 [math(G_1\subseteq G_2)]이다.
[math(G_2)]의 임의의 원소 [math(g)]를 생각하자. [math(g\succeq b\lor c)], [math(b\lor c\succeq b)]에서 [math(g\succeq b)]이고, [math(g\succeq a)], [math(g\succeq b)]에서 [math(g)]가 [math(\{a,b\})]의 상계이므로, [math(\{a,b\})]의 상한 [math(a\lor b)]에 대해 [math(g\succeq a\lor b)]이다. 또, [math(g\succeq b\lor c)], [math(b\lor c\succeq c)]에서 [math(g\succeq c)]이다. 따라서 [math(g)]는 [math(\{a\lor b,c\})]의 상계, 즉, [math(G_1)]의 원소이고, 여기서 [math(G_2\subseteq G_1)]이다.

교환법칙
임의의 원소 [math(a,b(\in A))]에 대해 [math(a\lor b)]와 [math(b\lor a)] 모두 [math(\{a,b\})]의 상한을 나타낸다. 따라서 [math(a\lor b=b\lor a)]이다. 같은 방식으로 [math(a\land b=b\land a)]임도 보일 수 있다.
멱등법칙
임의의 원소 [math(a(\in A))]는 [math(a\succeq a)]에서 [math(\{a\}(=\{a,a\}))]의 상계이고, [math(\{a\})]의 임의의 상계 [math(g(\in A))]에 대해 [math(g\succeq a)]이므로 [math(a)]는 [math(\{a\})]의 상한이다. 따라서 [math(a\lor a=a)]이다. 같은 방식으로 [math(a\land a=a)]임도 보일 수 있다.
흡수법칙
임의의 원소 [math(a,b(\in A))]를 생각하자. [math(a\succeq a)], [math(a\succeq a\land b)]에서 [math(a)]는 [math(\{a,a\land b\})]의 상계이고, [math(\{a,a\land b\})]의 임의의 상계 [math(g(\in A))]에 대해 [math(g\succeq a)]이므로 [math(a)]는 [math(\{a,a\land b\})]의 상한이다. 따라서 [math(a\lor(a\land b)=a)]이다. 같은 방식으로 [math(a\land(a\lor b)=a)]임도 보일 수 있다.

따라서 순서를 이용해 정의한 격자가 격자의 대수학적 정의를 만족함을 알 수 있다.

이번에는 대수학적으로 정의한 격자 [math((L,{\lor},{\land}))]을 생각하자. [math(L)] 위의 이항관계 [math({\preceq}\bigl(\subseteq L^2\bigr))]를 [math({\preceq}=\bigl\{(a,b)\in L^2\mathbin|a\lor b=b\bigr\})]이라고 정의한다. 먼저 이 관계가 부분순서임을 보이자.

반사성
임의의 원소 [math(a(\in L))]에 대해 [math(a\lor a=a)]이므로 [math(a\preceq a)]이다.
반대칭성
[math(a\preceq b)]와 [math(b\preceq a)]를 만족하는 임의의 원소 [math(a,b(\in L))]에 대해 [math(a\lor b=b)]이고 [math(b\lor a=a)]이므로 [math(a=b\lor a=a\lor b=b)]이다.
추이성
[math(a\preceq b)]와 [math(b\preceq c)]를 만족하는 임의의 원소 [math(a,b,c(\in L))]에 대해 [math(a\lor b=b)], [math(b\lor c=c)]에서 [math(a\lor c=a\lor(b\lor c)=(a\lor b)\lor c=b\lor c=c)]이므로 [math(a\preceq c)]이다.

따라서 [math({\preceq})]가 부분순서이고 [math((L,{\preceq}))]이 부분순서집합임을 알 수 있다. 이제 [math(L)]의 임의의 원소쌍 [math(\{a,b\})]의 상한과 하한이 존재함을 보이자.

[math(a\lor(a\lor b)=(a\lor a)\lor b=a\lor b)]에서 [math(a\preceq a\lor b)]이고, [math(b\lor(a\lor b)=(a\lor b)\lor b=a\lor(b\lor b)=a\lor b)]에서 [math(b\preceq a\lor b)]이므로, [math(a\lor b)]는 [math(\{a,b\})]의 상계이다. 또, [math(\{a,b\})]의 임의의 상계 [math(g(\in L))]에 대해, [math(a\lor g=g)], [math(b\lor g=g)]에서 [math((a\lor b)\lor g=a\lor(b\lor g)=a\lor g=g)]이므로 [math(a\lor b\preceq g)]이다. 따라서 [math(a\lor b)]는 [math(\{a,b\})]의 상한이다. 같은 방식으로 [math(a\land b)]가 [math(\{a,b\})]의 하한임도 보일 수 있다.[7]

따라서 대수학적으로 정의한 격자가 순서를 이용한 격자의 정의를 만족함을 알 수 있고, 두 정의가 같은 대상을 나타냄을 알 수 있다. 두 정의 문단에서 보인 격자 예시는 순서대로 같은 격자를 나타낸다. 즉, [math((\R,{\le})=(\R,\max,\min))]이고, [math((\mathcal P(A),{\subseteq})=(\mathcal P(A),{\cup},{\cap}))], [math((\Z^+,|)=(\Z^+,\mathrm{lcm},\gcd))]이다. 일반적으로 순서를 이용해 정의한 격자에서는 이음 연산과 만남 연산을 각각 원소쌍의 상한과 하한으로 자연스럽게 정의할 수 있고, 대수학적으로 정의한 격자에서는 부분순서를 [math(a\preceq b\Leftrightarrow a\lor b=b\Leftrightarrow a\land b=a)]이라고 자연스럽게 정의할 수 있다.

3. 종류

3.1. 유계격자

최대원소와 최소원소가 존재하는 격자를 유계격자\[bounded lattice\]라고 한다. 예를 들어, 격자 [math((\mathcal P(\{1,2,3\}),\subseteq))]은 최대원소 [math(\{1,2,3\})]과 최소원소 [math(\varnothing)]을 가지고, 격자 [math(([0,1],\le))]은 최대원소 [math(1)]과 최소원소 [math(0)]을 가지므로 모두 유계격자이지만, 격자 [math((\R,\le))]는 최대원소와 최소원소 모두 존재하지 않으므로 유계격자가 아니다. 일반적으로 최대원소는 [math(1)], 최소원소는 [math(0)]으로 표기한다.

3.2. 여원을 가지는 격자

유계격자 [math((A,\preceq))]의 어떤 원소 [math(a)]에 대해, [math(a\lor b=1)]과 [math(a\land b=0)]을 만족하는 원소 [math(b(\in A))]를 [math(a)]의 여원\[complement\]이라고 한다. 예를 들어, [math(0)]의 여원은 [math(1)]뿐이고, [math(1)]의 여원은 [math(0)]뿐이다. 여원은 원소에 따라 하나만 존재할 수도, 여러 개가 존재할 수도, 존재하지 않을 수도 있다. 모든 원소가 여원을 가지는 유계격자를 여원을 가지는 격자\[complemented lattice\]라고 한다. 예를 들어, 유계격자 [math((\mathcal P(\{1,2,3\}),\subseteq))]은 임의의 원소 [math(a(\in\mathcal P(\{1,2,3\})))]에 대해 여원 [math(\{1,2,3\}\setminus a(\in\mathcal P(\{1,2,3\})))]를 가지므로 여원을 가지는 격자이다. 하지만, 유계격자 [math(([0,1],\le))]은 원소 [math(\dfrac{1}{2})]의 여원이 존재하지 않으므로 여원을 가지는 격자가 아니다.

3.3. 분배격자

이음 연산 [math(\lor)]과 만남 연산 [math(\land)]이 다음 조건을 만족하는 격자 [math((L,\lor,\land))]을 분배격자\[distributive lattice\]라고 한다.

분배법칙[distributivity]: 임의의 원소 [math(a,b,c(\in L))]에 대해 [math(a\land(b\lor c)=(a\land b)\lor(a\land c))]이다.[8]

예를 들어, 격자 [math((\{\varnothing,\{1\},\{2\},\{3\},\{1,2,3\}\},\subseteq))]은 [math(\{1\}\land(\{2\}\lor\{3\})=\{1\}\land\{1,2,3\}=\{1\})]이지만 [math((\{1\}\land\{2\})\lor(\{1\}\land\{3\})=\varnothing\lor\varnothing=\varnothing)]이므로 분배격자가 아니다. 하지만, 격자 [math((\R,\le))]는 이음 연산 [math(\max)]와 만남 연산 [math(\min)] 사이의 분배법칙이 성립하므로 분배격자이다.

3.4. 전순서집합

집합 [math(A)]에 대해 다음 조건을 만족하는 이항관계 [math({\preceq}\bigl(\subseteq A^2\bigr))]를 전순서[total order]라고 한다.

반사성: 임의의 원소 [math(a(\in A))]에 대해 [math(a\preceq a)]이다.
반대칭성: 임의의 원소 [math(a,b(\in A))]에 대해 [math(a\preceq b)]이고 [math(b\preceq a)]이면 [math(a=b)]이다.
추이성: 임의의 원소 [math(a,b,c(\in A))]에 대해 [math(a\preceq b)]이고 [math(b\preceq c)]이면 [math(a\preceq c)]이다.
강한 연결성\[strong connectivity\]: 임의의 원소 [math(a,b(\in A))]에 대해 [math(a\preceq b)] 또는 [math(b\preceq a)]이다.

전순서는 임의의 두 원소 사이에 순서 관계가 있음을 나타낸다. 전순서가 주어진 집합을 전순서집합\[totally ordered set\]이라고 한다.

집합 [math(A)]에 대해 다음 조건을 만족하는 이항관계 [math({\prec}\bigl(\subseteq A^2\bigr))]를 순전순서\[strict total order\]라고 한다.

비반사성: 임의의 원소 [math(a(\in A))]에 대해 [math(a\nprec a)]이다.
비대칭성: 임의의 원소 [math(a,b(\in A))]에 대해 [math(a\prec b)]이면 [math(b\nprec a)]이다.[9]
추이성: 임의의 원소 [math(a,b,c(\in A))]에 대해 [math(a\prec b)]이고 [math(b\prec c)]이면 [math(a\prec c)]이다.
연결성\[connectivity\]: 서로 다른 임의의 원소 [math(a,b(\in A))]에 대해 [math(a\prec b)] 또는 [math(b\prec a)]이다.

순전순서는 순부분순서와 비슷하게 전순서에서 반사적인 원소만 빼는 방식으로 자연스럽게 정의할 수 있다.

전순서는 부분순서이므로 전순서 [math({\preceq})]가 주어진 집합 [math(A)]를 부분순서집합 [math((A,{\preceq}))]로 생각할 수 있다. 이제 이 전순서집합이 격자임을 보이자. 임의의 원소 [math(a,b(\in A))]에 대해 일반성을 잃지 않고 [math(a\preceq b)]라고 가정하자. [math(b\succeq a)], [math(b\succeq b)]에서 [math(b)]는 [math(\{a,b\})]의 상계이고, [math(\{a,b\})]의 임의의 상계 [math(g(\in A))]에 대해 [math(b\preceq g)]이므로 [math(b)]는 [math(\{a,b\})]의 상한이다. 같은 방식으로 [math(a)]가 [math(\{a,b\})]의 하한임도 보일 수 있다. 따라서 [math((A,{\preceq}))]는 격자이다.

추가적으로 [math((A,{\preceq}))]의 이음 연산과 만남 연산이 분배법칙을 만족함을 보일 수 있다. 임의의 원소 [math(a,b,c(\in A))]에 대해, 가능한 순서 관계는 [math(a\preceq b\preceq c)], [math(a\preceq c\preceq b)], [math(b\preceq a\preceq c)], [math(b\preceq c\preceq a)], [math(c\preceq a\preceq b)], [math(c\preceq b\preceq a)]의 6가지뿐이다. [math(a\preceq b\preceq c)]인 경우, [math(a\land(b\lor c)=a\land c=a)], [math((a\land b)\lor(a\land c)=a\lor a=a)]에서 [math(a\land(b\lor c)=(a\land b)\lor(a\land c))]이다. 같은 방식으로 나머지 5가지 경우에 대해서 분배법칙이 성립함도 보일 수 있다. 따라서 이음 연산과 만남 연산이 분배법칙을 만족하므로 [math((A,{\preceq}))]는 분배격자이다.

3.5. 불 격자

여원을 가지는 격자이면서 분배격자인 격자를 불 격자\[Boolean lattice\] 또는 불 대수\[Boolean algebra\]라고 한다. 불 격자는 임의의 원소의 여원이 유일하게 존재한다는 성질이 있다. 불 격자 [math((A,{\preceq}))]의 어떤 원소 [math(a)]가 서로 다른 여원 [math(b,c(\in A))]를 가진다고 가정하자. 그러면 [math(b=b\land1=b\land(a\lor c)=(b\land a)\lor(b\land c)=0\lor(b\land c)=(a\land c)\lor(b\land c)=(a\lor b)\land c=1\land c=c)]에서 모순이 발생한다. 따라서 불 격자의 임의의 원소는 각각 유일한 여원을 가진다. 그래서 추가로 여원 연산 [math(\lnot)]을 정의할 수 있다.

임의의 유한 불 격자는 어떤 유한집합의 멱집합과 부분순서 [math({\subseteq})]로 구성된 격자와 동치이다. 유한멱집합의 원소의 개수는 [math(2)]의 거듭제곱수이므로 유한 불 격자의 원소의 개수도 [math(2)]의 거듭제곱수이다. 원소의 개수가 가장 작은 불 격자는 원소의 개수가 [math(1\bigl(=2^0\bigr))]인 불 격자이다. 이를 자명한 불 격자라고 하며, 여기서는 [math(0=1)]이 성립한다.

자명하지 않은 불 격자 중 원소의 개수가 최소인 격자는, 보통 불 대수라고 하면 떠올리는, 원소의 개수가 [math(2bigl(=2^1bigr))]인 불 격자이다. [math(0)]은 거짓, [math(1)]은 참, [math({\lor})]은 논리합 연산, [math({\land})]은 논리곱 연산, [math(\lnot)]은 부정 연산이라고 생각하면 모두 잘 작동함을 알 수 있다.

[1] 여기서는 [math({\subseteq}=\{(\{1\},\{1\}),(\{1\},\{1,2\}),(\{1,2\},\{1,2\}),(\{2,3\},\{2,3\})\})]이다. [2] 여기서는 [math({\subseteq}=\{(\{1\},\{1\}),(\{1\},\{1,2,3\}),{\cdots},(\{1,2,3,4\},\{1,2,3,4\})\})]이다. [3] 여기서는 [math({\le}=\{(1,1),(1,e),(1,\pi),(e,e),(e,\pi),(\pi,\pi)\})]이다. [4] 비대칭성은 비반사성과 추이성에서 유도할 수 있으므로 조건에서 빼기도 한다. 여기서는 부분순서와의 비교를 위해 명시했다. [5] [math(m\mathbin|n)]은 [math(n)]이 [math(m)]으로 나누어떨어짐을 나타낸다. 예를 들어, [math(2\mathbin|4)]이다. [6] 멱등법칙은 흡수법칙에서 유도할 수 있으므로 조건에서 빼기도 한다. 여기서는 반격자와의 비교를 위해 명시했다. [7] 참고로 [math(a\lor b=b)]이면 [math(a\land b=a\land(a\lor b)=a)]이고, [math(a\land b=a)]이면 [math(a\lor b=(a\land b)\lor b=b\lor(a\land b)=b\lor(b\land a)=b)]이다. 따라서 [math({\preceq}=\bigl\{(a,b)\in L^2\mathbin|a\land b=a\bigr\})]라고 생각할 수 있다. [8] 이것만 만족하면 임의의 원소 [math(a,b,c(\in L))]에 대해 [math(a\lor(b\land c)=(a\lor b)\land(a\lor c))]이기도 하다. [9] 비대칭성은 비반사성과 추이성에서 유도할 수 있으므로 조건에서 빼기도 한다. 여기서는 전순서와의 비교를 위해 명시했다.

격자(수학)

1. 개요

2. 정의

2.1. 순서를 이용한 정의

2.1.1. 부분순서집합

2.1.2. 상한과 하한

2.1.3. 반격자와 격자

2.2. 대수학적 정의

2.3. 두 정의 사이의 관계

3. 종류

3.1. 유계격자

3.2. 여원을 가지는 격자

3.3. 분배격자

3.4. 전순서집합

3.5. 불 격자

분류