격자 (순서론)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

격자(lattice)는 추상대수학, 순서론, 범주론에서 정의될 수 있으며, 부분 순서 집합 또는 대수 구조로 표현된다. 격자는 두 개의 이항 연산(이음과 만남)을 가지며, 교환, 결합, 흡수 법칙을 만족한다. 격자는 전순서 집합, 멱집합, 약수, 분할, 열린 집합, 부분군, 아이디얼, 부분 벡터 공간 등 다양한 수학적 구조에서 나타난다. 격자는 완비성, 분배성, 모듈성, 반모듈성, 연속성, 대수성 등 다양한 성질을 가질 수 있으며, 원자, 아이디얼, 필터 등의 개념과 관련된다. 자유 격자, 격자 준동형, 반대 격자와 같은 개념도 존재한다. 격자 이론은 무의미한 위상수학, 프로그래밍 언어 의미론, 양자 논리 등 다양한 분야에 응용된다. 불 대수와 데데킨트의 연구를 거쳐 20세기 초에 클라인바르멘과 버코프에 의해 격자 이론이 발전했다.

더 읽어볼만한 페이지

격자 이론 - 직교 여원 격자
직교 여원 격자는 모든 원소가 여원을 가지는 유계 격자로서, 유계 분배 격자에서 최대 하나의 여원을 가지며 논리 회로 설계, 양자 컴퓨팅, 데이터 분석 등 다양한 분야에 응용된다.
격자 이론 - 완비 격자
완비 격자는 모든 부분 집합이 상한과 하한을 갖는 부분 순서 집합으로, 격자 이론에서 중요한 개념이며 다양한 수학 분야에서 활용된다.

격자 (순서론)
서론
정의	수학에서, 특히 순서론과 추상대수학에서, 격자(lattice)는 부분적으로 정렬된 집합으로, 집합의 모든 두 요소에 대해 최소 상계(join이라고도 함)와 최대 하계(meet이라고도 함)가 모두 존재한다.
형식적 정의
부분 순서 집합	격자는 부분 순서 집합(poset) (P, ≤)이다.
최소 상계와 최대 하계의 존재	P의 모든 원소 a와 b에 대해 최소 상계 (최소 공통 상계, join이라고도 함) a ∨ b와 최대 하계 (최대 공통 하계, meet이라고도 함) a ∧ b가 P 안에 존재한다.
격자로서의 대수 구조	격자는 또한 대수 구조 (L, ∨, ∧)로 특징지어질 수 있으며, 여기서 ∨와 ∧는 격자 항등식을 만족하는 두 개의 이항 연산이다.
격자 항등식
흡수 법칙	a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a
교환 법칙	a ∨ b = b ∨ a a ∧ b = b ∧ a
결합 법칙	a ∨ (b ∨ c) = (a ∨ b) ∨ c a ∧ (b ∧ c) = (a ∧ b) ∧ c
멱등 법칙	a ∨ a = a a ∧ a = a
추가적인 정의 및 개념
완비 격자	모든 부분 집합이 최소 상계와 최대 하계를 갖는 격자
분배 격자	a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)를 만족하는 격자
모듈러 격자	a ≤ c이면 a ∨ (b ∧ c) = (a ∨ b) ∧ c를 만족하는 격자
격자 이론의 응용
응용 분야	격자 이론은 다양한 수학 분야, 특히 추상대수학에서 응용된다. 또한, 논리학, 컴퓨터 과학, 정보 과학 등에서도 활용된다.
격자의 예시
집합의 멱집합	집합 X의 멱집합은 포함 관계에 따라 격자를 형성한다. 최소 상계는 합집합, 최대 하계는 교집합이다.
자연수의 약수 집합	자연수의 약수 집합은 약수 관계에 따라 격자를 형성한다.
닫힌 구간	실수의 닫힌 구간의 집합은 포함 관계에 따라 격자를 형성한다.

2. 정의

격자는 추상대수학, 순서론, 범주론적으로 정의할 수 있으며, 이 세 정의는 서로 동치이다.^[1]

순서론적 관점에서, 부분 순서 집합 $(L, \leq)$ 에서 모든 두 원소 $\{ a, b \} \subseteq L$ 가 최소 상계 ( $a \vee b$ ) 및 최대 하계 ( $a \wedge b$ )를 가지면 격자라고 한다.

대수적 관점에서, 격자는 집합 $L$ 과 그 위의 두 이항 연산 $\vee$ 및 $\wedge$ 으로 구성된 대수 구조 $(L, \vee, \wedge)$ 이며, 다음의 흡수 법칙과 멱등 법칙을 만족한다.

흡수 법칙: $a \vee (a \wedge b) = a$ , $a \wedge (a \vee b) = a$
멱등 법칙: $a \vee a = a$ , $a \wedge a = a$

순서론적 정의와 대수적 정의는 동치인데, 순서론적 격자에서 이항 연산

\vee

와

\wedge

를 정의할 수 있고, 반대로 대수적 격자에서 부분 순서

\leq

를 정의(

a \leq b \iff a = a \wedge b

또는

a \leq b \iff b = a \vee b

)할 수 있기 때문이다.

범주론적 정의는 #범주론적 정의에서 다룬다.

2. 1. 대수적 정의

추상대수학에서, '''유계 격자'''(有界格子, 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$

여기서 이항 연산

\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$

'''유계 격자'''는 최대 원소(1 또는

\top

으로 표시)와 최소 원소(0 또는

\bot

으로 표시)를 추가적으로 갖는 격자이며, 다음을 만족한다.

:

0 \leq x \leq 1 \;\text{ for every } x \in L.

유계 격자는

(L, \vee, \wedge, 0, 1)

형태의 대수적 구조로 정의될 수도 있는데, 여기서

(L, \vee, \wedge)

는 격자이고,

0

(격자의 바닥)는 결합 연산

\vee

에 대한 항등원이며,

1

(격자의 천장)는 교집합 연산

\wedge

에 대한 항등원이다.

:

a \vee 0 = a

:

a \wedge 1 = a

집합 ''L'' 및 ''L'' 위의 이항 연산

\lor

,

\land

로 구성된 대수적 구조

(L, \lor, \land)

가 '''격자'''가 되려면, ''L''의 임의의 원소 ''a'', ''b'', ''c''에 대해 다음의 공리적인 항등식을 만족해야 한다.

교환율	결합율	흡수율
$a \lor b = b \lor a$	$a \lor(b \lor c) = (a \lor b)\lor c$	$a \lor(a \land b) = a$
$a \land b = b\land a$	$a \land(b \land c) = (a \land b)\land c$	$a \land (a \lor b) = a$

또한 다음 두 개의 항등식을 공리로 가정하는 경우도 많지만, 실제로는 흡수율을 두 번 사용하여 유도할 수 있다.

;멱등율

: $a \lor a = a,\quad a \land a = a.$

이러한 공리는 $(L, \lor)$ 및 $(L, \land)$ 가 모두 반격자가 되도록 요구한다. 또한 흡수율은 격자가 단순한 임의의 반격자의 쌍이 아니라, 쌍을 이루는 두 개의 반격자 사이에 적절한 상호 관계가 있음을 가정한다. 특히, 서로의 반격자 사이에 쌍대성을 보인다.

대수적인 의미에서의 '''유계 격자'''는 대수적 구조 $(L, \lor, \land, 1, 0)$ 이며, $(L, \lor, \land)$ 는 격자이며, 0(격자의 최소 원소)은 결합 $\lor$ 에 관한 항등원이며, 1(격자의 최대 원소)은 교차 $\land$ 에 관한 항등원이다.

2. 2. 순서론적 정의

부분 순서 집합

(L, \leq)

에서, 모든 두 원소 부분 집합

\{ a, b \} \subseteq L

이 결합 (최소 상계,

a \vee b

로 표시) 및 쌍대 만남 (최대 하계,

a \wedge b

로 표시)을 가지면 '''격자'''라고 한다.

\,\wedge\,

및

\,\vee\,

는 이항 연산이 되며, 두 연산 모두 주어진 순서에 대해 단조적이다. 즉,

a_1 \leq a_2

및

b_1 \leq b_2

이면

a_1 \vee b_1 \leq a_2 \vee b_2

및

a_1 \wedge b_1 \leq a_2 \wedge b_2

가 된다.

수학적 귀납법에 따라 격자의 모든 비어 있지 않은 유한 부분 집합은 최소 상계와 최대 하계를 갖는다.

'''유계 격자'''는 최대 원소(최대, 상한 원소라고도 하며

1,

또는

\top

으로 표시)와 최소 원소(최소, 하한이라고도 하며

0

또는

\bot

으로 표시)를 추가적으로 갖는 격자이며, 다음을 만족한다.

:

0 \leq x \leq 1 \;\text{ for every } x \in L.

부분 순서 집합은 모든 유한 집합(공집합 포함)의 원소가 결합과 교집합을 가질 때 유계 격자이다. 포셋의 모든 원소

x

에 대해 다음은 자명하게 참이다.

:

\text{ for all } a \in \varnothing, x \leq a

그리고

:

\text{ for all } a \in \varnothing, a \leq x,

따라서 포셋의 모든 원소는 공집합의 상계이자 하계이다. 이는 공집합의 결합이 최소 원소

\bigvee\varnothing = 0,

이고, 공집합의 교집합이 최대 원소

\bigwedge\varnothing = 1.

임을 의미한다.

2. 3. 범주론적 정의

원순서 집합은 작은 얇은 범주로 간주할 수 있으며, 이 경우 격자는 곱과 쌍대곱을 통해 정의된다.

원순서 집합(작은 얇은 범주)

(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\le b$	사상 $a\to b$ 의 존재
이음의 항등원 $\bot$	최소 원소 $\min L$	시작 대상 $0$
만남의 항등원 $\top$	최대 원소 $\max L$	끝 대상 $1$

2. 4. 격자 준동형

두 격자

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)

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

두 유계 격자

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)

임을 쉽게 보일 수 있다. 따라서, 유계 격자 준동형은 증가 함수이다. 반면, 증가 함수이지만 격자 준동형이 아닌 함수도 존재한다.

두 격자 사이의 적절한 사상 개념은 위 대수적 정의에서 쉽게 파생된다. 두 격자

\left(L, \vee_L, \wedge_L\right)

과

\left(M, \vee_M, \wedge_M\right)

이 주어졌을 때, ''L''에서 ''M''으로의 '''격자 준동형사상'''은 모든

a, b \in L:

에 대해 다음을 만족하는 함수

f : L \to M

이다.

f\left(a \vee_L b\right) = f(a) \vee_M f(b),

f\left(a \wedge_L b\right) = f(a) \wedge_M f(b).

따라서

f

는 두 개의 기본 반격자의 준동형사상이다. 더 많은 구조를 가진 격자를 고려할 때, 사상은 추가 구조도 "존중"해야 한다. 특히, 두 유계 격자

L

과

M

사이의 '''유계 격자 준동형사상''' (보통 "격자 준동형사상"이라고 함)

f

는 또한 다음과 같은 속성을 가져야 한다.

f\left(0_L\right) = 0_M,

f\left(1_L\right) = 1_M.

순서론적 공식에서 이러한 조건은 격자 준동형사상이 이진 만남과 결합을 보존하는 함수임을 나타낸다. 유계 격자의 경우, 최소 및 최대 원소의 보존은 공집합의 결합 및 만남의 보존일 뿐이다.

격자의 모든 준동형사상은 관련 순서 관계에 대해 반드시 단조적이다. 극한 보존 함수를 참조하라. 그 반대는 사실이 아니다. 단조성은 필요한 만남과 결합의 보존을 의미하지 않는다. 순서 보존 전단사는 그 역도 순서 보존적인 경우 준동형사상이다.

동형사상을 가역 사상으로 정의하면, 격자 동형사상은 단순한 전단사 격자 준동형사상이다. 마찬가지로, 격자 자기 준동형사상은 격자에서 자기 자신으로의 격자 준동형사상이며, 격자 자기 동형사상은 전단사 격자 자기 준동형사상이다. 격자와 그 준동형사상은 범주론을 형성한다.

2. 5. 반대 격자

주어진 격자

(L,\le_L,\wedge_L,\vee_L)

에 대하여, 그 '''반대 격자'''(opposite lattice^영어)

L^{\operatorname{op}}

는 집합

L

에 다음과 같은 격자 연산을 부여한 격자이다. 모든

a,b\in L

에 대하여,

:

a\vee_{L^{\operatorname{op}}}b=a\wedge_Lb

:

a\wedge_{L^{\operatorname{op}}}b=a\vee_Lb

:

a\le_{L^{\operatorname{op}}}b=a\ge_Lb

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

3. 예

임의의 집합 $A$ 에 대해, $A$ 의 모든 부분 집합의 모음은 부분 집합 포함 관계를 통해 순서를 매겨 격자를 얻을 수 있다. 이 격자에서 상한은 집합의 합집합에 의해 제공되고 하한은 집합의 교집합에 의해 제공된다. (그림 1 참조)
임의의 집합 $A$ 에 대해, $A$ 의 모든 유한 부분 집합의 모음은 포함 관계에 의해 정렬되며, $A$ 가 유한인 경우에만 경계가 정해진다.
임의의 집합 $A$ 에 대해, $A$ 의 모든 분할의 모음은 세분화를 기준으로 정렬된 격자이다. (그림 3 참조)^[1]
일반적인 순서에서 양의 정수는 "min"과 "max" 연산 하에서 경계가 없는 격자를 형성한다. 1은 바닥이고, 꼭대기는 없다. (그림 4 참조)
자연수의 데카르트 곱은 $(a, b) \leq (c, d)$ if $a \leq c \text{ and } b \leq d.$ 로 정렬된다. 쌍 $(0, 0)$ 은 바닥 원소이고, 꼭대기는 없다. (그림 5 참조)
자연수는 최대공약수와 최소공배수를 취하는 연산 하에서 격자를 형성하며, 나누어떨어짐이 순서 관계이다. $1$ 은 바닥이고, $0$ 은 꼭대기이다. 그림 2는 유한 부분 격자를 보여준다.^[1]
모든 완비 격자는 유계 격자이다.

3. 1. 전순서

전순서 집합

(T,\le)

은 격자를 이룬다. 이 경우

:

a\vee b=\max\{a,b\}

:

a\wedge b=\min\{a,b\}

이다.

3. 2. 부분 집합 격자

집합

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\}

또한 격자를 이룬다.

임의의 집합

A

에 대해,

A

의 모든 부분 집합의 모음 (이를

A

의 멱집합이라고 부름)은 부분 집합 포함 관계를 통해 순서를 매겨

A

자신과 공집합으로 경계가 정해진 격자를 얻을 수 있다. 이 격자에서 상한은 집합의 합집합에 의해 제공되고 하한은 집합의 교집합에 의해 제공된다 (그림 1 참조).

임의의 집합

A

에 대해,

A

의 모든 유한 부분 집합의 모음은 포함 관계에 의해 정렬되며,

A

가 유한인 경우에만 경계가 정해진다.

임의의 집합 ''A''에 대해, ''A''의 멱집합은 포함 관계에 의해 정해지는 순서에 관해 격자가 된다. 이것은 ''A'' 자신을 최대 원소, 공집합을 최소 원소로 하는 유계 격자이다. 교집합 및 합집합에 의해 각각 주어진다.

임의의 집합 ''A''에 대해, ''A''의 유한 부분 집합에 포함 관계 순서를 부여한 것도 또한 격자가 된다. 이 격자가 유계가 되는 것은 ''A'' 자신이 유한일 때이며, 또한 그 경우에 한한다.

3. 3. 약수의 격자

양의 정수

n

의 약수들은 격자를 이룬다. 이때 격자 연산은 다음과 같다.^[1]

정수론	격자
$a\mid b$ (약수 관계)	$a\le b$
$\operatorname{lcm}(a,b)$ (최소공배수)	$a\vee b$
$\gcd(a,b)$ (최대공약수)	$a\wedge b$

3. 4. 분할 격자

집합의 분할들의 집합은 격자를 이룬다.

분할	격자
분할의 세분 $\forall p\in P\colon\exists q\in Q\colon p\subset q$	$P\le Q$
공통 세분	$P\wedge Q$
공통 역세분	$P\vee Q$

임의의 집합 $A$ 에 대해, $A$ 의 모든 분할의 모음은 세분화를 기준으로 정렬된 격자이다 (그림 3 참조).^[1]

3. 5. 열린집합의 격자

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

3. 6. 대수학에서의 격자

군

G

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

부분군	격자
$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)$ 은 유계 완비 격자를 이룬다.

아이디얼	격자
$\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$ 의 부분 벡터 공간들의 집합은 완비 격자를 이룬다. 이 격자는 양자 논리의 기반을 이룬다.

벡터 공간	격자
$A\subset B$	$A\le B$
$A\cap B$	$A\wedge B$
$\operatorname{span}(A,B)$	$A\vee B$
$\{0\}$	$\bot$
$V$	$\top$

4. 성질

격자는 완비성, 조건부 완비성, 분배성, 모듈성, 반모듈성 등 다양한 성질을 가질 수 있다.

분배 격자: 분배 법칙을 만족하는 격자이다. 6개 미만의 원소를 갖는 비분배 격자는 M₃과 N₅뿐이며, M₃ 또는 N₅와 동형인 부분 격자를 갖지 않는 격자만이 분배 격자이다.^[6]
모듈 격자: 분배 격자보다 약한 조건인 모듈 법칙을 만족하는 격자이다. N₅와 동형인 부분 격자를 갖지 않는 격자가 모듈 격자이다.^[6] 가군의 부분 가군 격자, 환의 양쪽 아이디얼 격자, 군의 정규 부분군 격자 등이 모듈 격자의 예시이다.
반모듈 격자: 버코프 조건을 만족하는 격자이다.^[8]

4. 1. 완비성

부분 순서 집합은 모든 부분 집합이 결합과 만남을 모두 가질 때 완비 격자라고 한다. 특히 모든 완비 격자는 유계 격자이다. 일반적으로 유계 격자 준동형 사상은 유한한 결합과 만남만 보존하는 반면, 완비 격자 준동형 사상은 임의의 결합과 만남을 보존해야 한다.

완비 반격자인 모든 부분 순서 집합은 또한 완비 격자이다.

'''조건부 완비 격자'''는 공집합이 아니고 위로 유계인 모든 부분 집합이 결합(최소 상계)을 갖는 격자이다. 이러한 격자는 실수의 완비성 공리를 가장 직접적으로 일반화한 것이다. 조건부 완비 격자는 완비 격자이거나, 완비 격자에서 최대 원소 1을 제거한 것이거나, 완비 격자에서 최소 원소 0을 제거한 것이거나, 또는 완비 격자에서 최대 원소와 최소 원소를 모두 제거한 것 중 하나이다.^[3]^[4]

4. 2. 조건부 완비성

'''조건부 완비 격자'''는 공집합이 아니고 상계를 가지는 모든 집합이 결합(최소 상계)을 갖는 격자이다. 이러한 격자는 실수의 완비성 공리를 가장 직접적으로 일반화한 것이다. 조건부 완비 격자는 완비 격자이거나, 완비 격자에서 최대 원소 1, 최소 원소 0, 또는 둘 다를 제외한 격자이다.^[3]^[4]

4. 3. 분배성

격자는 두 개의 이항 연산을 가지므로, 그중 하나가 다른 하나에 대해 분배되는지 묻는 것은 자연스럽다. 즉, 다음의 쌍대 법칙 중 하나가 모든 세 요소

a, b, c \in L,

에 대해 성립하는지 확인한다.

;

\vee

의

\wedge

에 대한 분배 법칙

:

a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c).

;

\wedge

의

\vee

에 대한 분배 법칙

:

a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c).

첫 번째 또는 동등하게는(결과적으로) 두 번째 공리를 만족하는 격자를 '''분배 격자'''라고 한다.^[5] 6개 미만의 요소를 가진 유일한 비-분배 격자는 M₃와 N₅이다.^[6] 격자가 M₃ 또는 N₅와 동형인 부분 격자를 갖지 않는 경우에만 분배 격자이다.^[7] 각 분배 격자는 집합의 격자(결합과 교집합을 각각 합과 만남으로 사용)와 동형이다.

프레임 및 완전 분배 격자와 같은 더 특수한 격자 클래스를 정의하는 데 사용되는 분배의 더 강력한 개념은 순서론에서의 분배 법칙을 참조하라.

4. 4. 모듈성

어떤 응용 분야에서는 분배 조건이 너무 강력하여 모듈 격자가 사용된다. 모듈 격자는 다음 모듈 법칙을 만족하는 격자이다.

:

a \leq c

이면

a \vee (b \wedge c) = (a \vee b) \wedge c.

(모듈 법칙)

이는 다음의 모듈 항등식과 동치이다.

:

(a \wedge c) \vee (b \wedge c) = ((a \wedge c) \vee b) \wedge c.

(모듈 항등식)

격자가 N₅와 동형인 부분 격자를 갖지 않는 경우에만 격자는 모듈 격자이다.^[6]

분배 격자는 모듈 격자이다. 가군의 부분 가군 격자, 환의 양쪽 아이디얼 격자, 군의 정규 부분군 격자 등은 모듈 격자의 예시이다. 자동 추론에 사용되는 일계 논리 용어 집합은 비모듈 격자이다.

4. 5. 반모듈성

반모듈 격자는 버코프 조건을 만족하는 격자이다.^[8]

:

L

의 각

x

와

y

에 대해,

x

와

y

가 모두

x \wedge y

를 덮으면,

x \vee y

는

x

와

y

를 모두 덮는다.

어떤 격자의 쌍대가 반모듈 격자이면 그 격자를 아래쪽 반모듈 격자라고 한다. 유한 격자의 경우, 아래쪽 반모듈 격자는 위의 버코프 조건에서

\vee

와

\wedge

를 교환하고, "덮는다"를 "에 의해 덮인다"로 교환하고, 부등식을 반대로 하여 성립한다.^[8]

4. 6. 연속성과 대수성

영역 이론에서, 부분 순서 집합의 원소를 "훨씬 더 단순한" 원소로 근사하는 것은 자연스러운 일이다. 모든 원소가 해당 원소보다 훨씬 아래에 있는 원소의 방향 집합의 상한으로 얻을 수 있는 연속 포셋 클래스가 바로 그것이다. 이러한 방향 집합을 얻기 위해 포셋의 컴팩트 원소로 추가로 제한할 수 있다면, 포셋은 심지어 대수적 포셋이 된다. 두 개념 모두 격자에 다음과 같이 적용할 수 있다.

'''연속 격자'''는 포셋으로서 연속인 완비 격자이다.
'''대수적 격자'''는 포셋으로서 대수적인 완비 격자이다.

이 두 클래스 모두 흥미로운 속성을 가지고 있다. 예를 들어, 연속 격자는 특정 항등식을 만족하는 대수적 구조(무한 연산을 포함하는)로 특징지을 수 있다. 대수적 격자에 대해서는 그러한 특성화를 알 수 없지만, 스콧 정보 시스템을 통해 "구문론적"으로 설명할 수 있다.

4. 7. 여원과 의사 여원

최대 원소 1과 최소 원소 0을 가진 유계 격자

L

에서, 두 원소

x

와

y

가 다음 조건을 만족하면 서로의 여원이라고 한다.

:

x \vee y = 1 \quad \text{ 그리고 } \quad x \wedge y = 0.

일반적으로 유계 격자의 일부 원소는 여원을 갖지 않거나, 둘 이상의 여원을 가질 수 있다. 예를 들어, 집합

\{0, 1/2, 1\}

은 순서에 따라 유계 격자가 되지만,

\tfrac{1}{2}

는 여원을 갖지 않는다. 모든 원소가 여원을 갖는 유계 격자를 여원 격자라고 한다.

분배 격자인 여원 격자는 불 대수이다. 분배 격자에서,

x

의 여원은 존재한다면 유일하다. 여원소가 유일한 경우,

\lnot x = y

또는

\lnot y = x

로 표기한다. 이는 격자 이론에서 논리적 부정과 유사한 단항 연산이다.

헤이팅 대수는 모든 원소가 여원을 갖지 않을 수 있는 분배 격자의 예시이다. 헤이팅 대수의 모든 원소

z

는

\lnot x

로 표시되는 의사 여원을 갖는다. 의사 여원은

x \wedge y = 0

을 만족하는 가장 큰 원소

y

이다. 헤이팅 대수의 모든 원소의 의사 여원이 실제로 여원이면, 그 헤이팅 대수는 불 대수이다.

4. 8. 요르단-데데킨트 사슬 조건

어떤 부분 순서 집합에서,

x_0

에서

x_n

까지의 '''사슬'''은

x_0 < x_1 < x_2 < \ldots < x_n

을 만족하는

\left\{ x_0, x_1, \ldots, x_n\right\}

와 같은 집합이다.

이 사슬의 '''길이'''는 원소의 개수보다 1 작거나, ''n''과 같다. 만약 사슬에서 모든

1 \leq i \leq n

에 대해

x_i

가

x_{i-1}

을 덮는다면, 이 사슬을 '''극대 사슬'''이라고 한다.

격자에서

x < y

를 만족하는 임의의 두 원소

x

,

y

에 대해,

x

에서

y

까지의 모든 극대 사슬의 길이가 같다면, 이 격자는 '''요르단-데데킨트 사슬 조건'''을 만족한다고 한다.

4. 9. 등급/순위

등급 격자는 순위 함수를 가지는 격자이다. 때로는 랭크 격자라고도 불리지만, 다른 의미로는 랭크 포셋을 참조한다. 등급 격자는 순서와 호환되는 랭크 함수

r : L \to \N

(때로는

\mathbb{Z}

)를 가진다. 순서와 호환된다는 것은

x < y

일 때마다

r(x) < r(y)

임을 의미한다. 또한,

y

가

x

를 덮을 때

r(y) = r(x) + 1

을 만족해야 한다. 격자 원소에 대한 랭크 함수의 값은 랭크라고 불린다.

격자 원소

y

가 다른 원소

x

를 덮는다는 것은,

y > x

이지만,

y > z > x

를 만족하는

z

가 존재하지 않는다는 것을 의미한다. 여기서

y > x

는

x \leq y

이고

x \neq y

임을 의미한다.

5. 자유 격자

휘트먼은 집합 $X$ 에 대한 다항식을 기반으로 자유 격자 구성을 제공했다.^[1] 자유 반격자는 $X$ 의 모든 유한 부분 집합으로 구성되며, 반격자 연산은 일반적인 집합 합집합으로 주어진다.^[1] 자유 반격자는 보편 성질을 갖는다.^[1]

6. 중요한 격자 이론적 개념

결합 기약 원소: $x = a \vee b$이면 $x = a$ 또는 $x = b$가 $L$의 모든 원소 $a$, $b$에 대해 성립하는 $L$의 원소 $x$를 말한다. $L$이 하한 원소 $0$을 가질 경우, 일부 저자는 $x \neq 0$을 요구하기도 한다.^[11] 이 조건을 임의 개수의 결합 $\bigvee_{i \in I} a_i$로 일반화하면 $x$를 완전 결합 기약 원소($\vee$-기약 원소)라고 한다. 이 개념의 쌍대 개념은 만남 기약 원소($\wedge$-기약 원소)이다.
결합 소수 원소: $x \leq a \vee b$이면 $x \leq a$ 또는 $x \leq b$가 성립하는 $L$의 원소 $x$를 말한다. 일부 저자는 $x \neq 0$을 요구하기도 한다.^[11] 이 조건을 일반화하여 완전 결합 소수 원소 개념을 얻을 수 있다. 이 개념의 쌍대 개념은 만남 소수 원소이다. 모든 결합 소수 원소는 결합 기약 원소이고, 모든 만남 소수 원소는 만남 기약 원소이다. $L$이 분배 격자인 경우 그 역도 성립한다.

$L$이 하한 원소 0을 갖는 경우, 다음 개념들이 정의된다.

원자: $0 < x$이고 $0 < y < x$인 $L$의 원소 $y$가 존재하지 않는 $L$의 원소 $x$이다.
원자적: $L$의 모든 0이 아닌 원소 $x$에 대해, $a \leq x$인 $L$의 원자 $a$가 존재하는 경우이다.
원자주의적: $L$의 모든 원소가 원자들의 상한인 경우이다.

아이디얼과 필터는 격자 이론에서 중요한 부분 집합이다.

7. 응용

격자 이론은 다음과 같은 다양한 분야에서 응용된다.

무의미한 위상수학
부분군 격자
스펙트럼 공간
불변 부분 공간
폐포 연산자
추상 해석
포섭 격자
퍼지 집합 이론
일계 논리의 대수화
프로그래밍 언어의 의미론
도메인 이론
온톨로지 (컴퓨터 과학)
다중 상속
형식적 개념 분석
블룸 필터
정보 흐름
서수 최적화
양자 논리
중앙값 그래프
지식 공간
정규 언어의 유도
유추 모델링

일부 응용 분야에서는 집합이 부분 격자일 뿐이다. 즉, 모든 요소 쌍이 만남 또는 결합을 갖는 것은 아니다.

8. 역사

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

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

참조

_[1] 논문
_[2] 서적 A Course in Universal Algebra http://www.thoralf.u[...] Springer-Verlag
_[3] 웹사이트 Complete Lattices https://www.math.ucl[...] 2010
_[4] 서적 Set Theory and Metric Spaces AMS Chelsea Publishing
_[5] 논문 https://books.google[...]
_[6] 논문 Theorem 4.10 https://books.google[...]
_[7] 논문 Theorem 10.21 https://books.google[...]
_[8] 간행물 Enumerative Combinatorics (vol. 1) Cambridge University Press
_[9] 저널 Free Lattices I
_[10] 저널 Free Lattices II
_[11] conference Continuous posets, prime spectra of completely distributive complete lattices, and Hausdorff compactifications 1981
_[12] 간행물 Ueber Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler
_[13] 서적 A Course in Universal Algebra. http://www.thoralf.u[...] Springer-Verlag
_[14] 문서 Nation
_[15] 서적 Prometheus
_[16] 서적
_[17] 저널
_[18] 저널
_[19] 저널
_[20] 저널
_[21] 저널

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com