갈루아 연결(Galois connection)

17개의 사탕을 3개씩 봉지에 담으면 몇 봉지까지 채울 수 있을까요? 정수 n에 대해 '3n ≤ 17'이 참인 n은 n ≤ 5, 곧 $n\le\lfloor 17/3\rfloor$인 n입니다. 일반적으로 양의 정수 k와 모든 정수 n, x에 대해

$$k\,n\le x\iff n\le\lfloor x/k\rfloor$$

입니다. '3을 곱한 것이 x 이하인가'라는 질문이 'x를 3으로 나눈 몫 이하인가'라는 질문으로 정확히 옮겨집니다. 이처럼 두 순서 P, Q 사이의 단조 함수 $f: P\to Q$, $g: Q\to P$가 모든 p, q에 대해 $f(p)\le q\iff p\le g(q)$를 만족하면 이 짝을 갈루아 연결(Galois connection)이라 하고, f를 아래쪽(왼쪽) 짝, g를 위쪽(오른쪽) 짝이라 부릅니다. 순서는 두 대상 사이에 화살표가 많아야 하나인 범주⁠(category)⁠이고 단조 함수는 함자⁠(functor)⁠이므로, 갈루아 연결은 순서에서의 수반 함자⁠(adjoint functor)⁠입니다. 그 페이지에서 본 올림 ⊣ 포함 ⊣ 내림, 상 ⊣ 역상 ⊣ '모두'가 모두 갈루아 연결입니다.

짝의 한쪽은 다른 쪽을 완전히 정합니다. $g(q)$는 $f(p)\le q$인 p 가운데 가장 큰 것이고, $f(p)$는 $p\le g(q)$인 q 가운데 가장 작은 것입니다. ⌊x/3⌋이 '3n ≤ x인 가장 큰 n'인 것이 이 말입니다. 이 사실로 소수 부분⁠(fractional part)⁠을 한 번도 다루지 않고 증명할 수 있습니다. 양의 정수 a, b와 정수 x에 대해 $\lfloor\lfloor x/a\rfloor/b\rfloor = \lfloor x/(ab)\rfloor$입니다. 아무 정수 n에 대해

$$n\le\bigl\lfloor\lfloor x/a\rfloor/b\bigr\rfloor\iff bn\le\lfloor x/a\rfloor\iff abn\le x\iff n\le\lfloor x/(ab)\rfloor$$

이고, 모든 n에 대해 'n 이하'가 똑같이 참인 두 정수는 같기 때문입니다(n에 한쪽 값을 넣어 보면 됩니다). x = 100, a = 3, b = 4이면 ⌊100/3⌋ = 33, ⌊33/4⌋ = 8이고 ⌊100/12⌋ = 8입니다. 이 '아래에 있는 것들이 같으면 같다'는 논법은 요네다 보조정리⁠(Yoneda lemma)⁠의 순서판입니다. 또 아래쪽 짝은 상한(가장 작은 위 경계)을, 위쪽 짝은 하한(가장 큰 아래 경계)을 그것이 있을 때마다 보존합니다(왼쪽 수반은 쌍대극한⁠(colimit)⁠을, 오른쪽 수반은 극한⁠(limit)⁠을 보존). 정수처럼 한 줄로 늘어선 순서에서 두 수의 상한⁠(upper bound)⁠과 하한⁠(lower bound)⁠은 max와 min입니다. 그래서 $\lfloor\min(x, y)/k\rfloor = \min(\lfloor x/k\rfloor, \lfloor y/k\rfloor)$입니다.

집합의 연산⁠(set operations)⁠에도 갈루아 연결이 있습니다. 집합⁠(set)⁠ A를 하나 고정하면 모든 X, Y에 대해

$$A\cap X\subseteq Y\iff X\subseteq A^{c}\cup Y$$

입니다. 'A이면서 X인 것은 모두 Y다'와 'X인 것은 모두 A가 아니거나 Y다'는 같은 말이기 때문입니다. 곧 'A와 교집합⁠(intersection)⁠'의 위쪽 짝은 'A의 여집합⁠(complement)⁠과 합집합⁠(union)⁠'이고, 논리로 옮기면 '그리고'의 위쪽 짝이 '이면'($A\Rightarrow Y = \lnot A\vee Y$)입니다(불 대수⁠, Boolean algebra⁠). 여집합을 쓰지 않고 '이면'을 이 성질 하나로 정의한 것이 직관주의 논리⁠(intuitionistic logic)⁠의 대수인 헤이팅 대수입니다.

갈루아 연결을 한 바퀴 돌면 언제나 닫힘 연산(closure operator)이 나옵니다. $c = g\circ f$라 하면 c는 단조이고, $p\le c(p)$(늘리기만 한다)이며, $c(c(p)) = c(p)$(두 번 해도 한 번 한 것과 같다)입니다. 증명은 짧습니다. $f(p)\le f(p)$를 연결로 옮기면 $p\le gf(p)$이고, $g(q)\le g(q)$를 옮기면 $fg(q)\le q$입니다. 앞의 것에 f를 씌우면 $f(p)\le fgf(p)$, 뒤의 것에 q = f(p)를 넣으면 $fgf(p)\le f(p)$이므로 $fgf = f$이고, 여기에 g를 씌우면 $cc = c$입니다. 익숙한 '가장 작은 ~'이 모두 이렇게 나옵니다. 벡터⁠(vector)⁠들의 집합 S와 부분공간 W 사이에는 '$\mathrm{span}(S)\subseteq W\iff S\subseteq W$'라는 갈루아 연결이 있고, 그 닫힘 연산이 S를 포함하는 가장 작은 부분공간, 곧 선형 생성입니다(열공간⁠, column space⁠). 볼록 껍질, 위상수학⁠(topology)⁠의 닫힘, 관계의 추이적 닫힘, 원소⁠(element)⁠들이 생성하는 부분군⁠(subgroup)⁠이 모두 같은 모양입니다. 닫힘 연산을 바꾸지 않는 원소(c(p) = p)를 닫힌 원소라 합니다. Q 쪽에서 이에 해당하는 것은 fg(q) = q인 원소입니다. f와 g는 이 두 모임 사이에서 서로를 되돌리는 순서 동형⁠(isomorphism)⁠이 됩니다(위의 fgf = f와, 같은 방법으로 얻는 gfg = g 덕분입니다). 이것이 갈루아 연결이 '대응'을 낳는 일반 원리입니다.

방향이 뒤집히는 판도 있습니다. 대상의 집합 X, 성질의 집합 Y, 그리고 '대상 x가 성질 y를 가진다'는 관계가 있다고 합시다. 대상들의 모임 A에 대해 A′을 'A의 대상이 모두 가진 성질'의 집합으로, 성질들의 모임 B에 대해 B′을 'B의 성질을 모두 가진 대상'의 집합으로 정하면

$$A\subseteq B'\iff B\subseteq A'$$

입니다. 두 쪽 모두 'A의 모든 대상이 B의 모든 성질을 가진다'는 뜻이기 때문입니다. 대상을 늘리면 공통 성질은 줄어드므로 두 함수는 순서를 뒤집지만, 한 바퀴 돈 $A\mapsto A''$는 여전히 닫힘 연산입니다. 1940년 개럿 버코프가 이 구성을 '극성'(polarity)이라 불렀고, 1982년 루돌프 빌레는 여기서 형식 개념 분석(formal concept analysis)을 만들었습니다. A′ = B이고 B′ = A인 쌍 (A, B)를 '개념'이라 부르는데, A는 개념에 속하는 것들(외연), B는 그것들을 정의하는 성질(내포)입니다. 아래는 1부터 9까지의 수와 네 성질로 만든 예입니다. 고르는 쪽: . 표의 칸을 눌러 고르고, 오른쪽 격자의 점을 누르면 그 개념으로 갑니다.

{3, 5}를 고르면 공통 성질은 {홀수, 소수⁠(prime number)⁠}이고, 이 두 성질을 가진 수를 다시 모으면 7이 따라 들어와 {3, 5, 7}이 됩니다. 주어진 성질로는 3, 5와 7을 구별할 수 없다는 뜻입니다. 개념들은 외연의 포함 관계로 순서를 이루고, 두 개념에는 언제나 가장 큰 공통 아래 개념과 가장 작은 공통 위 개념이 있습니다(완비 격자⁠, complete lattice⁠). 그래서 개념 격자는 자료에서 분류 체계를 자동으로 뽑아내는 방법으로 쓰입니다. 표에 성질 하나를 더하면 격자가 어떻게 달라지는지를 보는 것이 곧 '새 기준이 무엇을 새로 가르는가'를 보는 일입니다.

이름의 주인공은 갈루아입니다. 수 체계⁠(number system)⁠ L = ℚ(√2, √3), 곧 $a + b\sqrt2 + c\sqrt3 + d\sqrt6$(a, b, c, d는 유리수⁠(rational number)⁠) 꼴의 수 전체를 생각합시다. 덧셈과 곱셈을 지키고 유리수를 그대로 두는 L의 전단사(자기 동형)는 √2를 ±√2로, √3을 ±√3으로 보내는 방법 네 가지뿐입니다. √2의 제곱이 2이므로 √2가 가는 곳도 제곱이 2여야 하기 때문입니다. 이 넷이 이루는 군을 G라 합시다. '자기 동형 g가 수 x를 움직이지 않는다'는 관계는 위의 대상–성질 관계와 똑같은 극성을 줍니다. 수들의 모임에는 그것들을 모두 고정하는 자기 동형들의 모임을, 자기 동형들의 모임에는 그것들이 모두 고정하는 수들의 모임을 대응시키는 것입니다. 수를 고르면 군과 체가 어떻게 따라오는지 보세요. α에 넣을 항을 위 줄에서 누르면 바뀝니다.

갈루아 이론의 기본 정리는 이 극성에서 모든 것이 닫혀 있는 경우를 말합니다. 정확히 적으면 이렇습니다. 체의 확대 K ⊆ L이 유한 갈루아 확대⁠(Galois extension)⁠라고 합시다. 곧 L은 K 위에서 유한 차원이고, K 계수의 어떤 다항식⁠(polynomial)⁠의 근을 모두 담는 가장 작은 체(분해체⁠, splitting field⁠)이며, 그 다항식이 중근⁠(multiple root)⁠을 갖지 않습니다(유리수처럼 표수가 0인 체에서는 마지막 조건이 저절로 성립합니다). G = Gal(L/K)를 K를 고정하는 L의 자기 동형들의 군이라 하면, 중간체 E(K ⊆ E ⊆ L)를 $\mathrm{Gal}(L/E)$로, 부분군 H를 그 고정체⁠(fixed field)⁠ $L^H$로 보내는 두 함수는 서로를 되돌리는 전단사⁠(bijective)⁠이고 포함 관계를 뒤집습니다. 게다가 $[L:E] = |\mathrm{Gal}(L/E)|$(차원이 군의 크기)이고, E가 다시 K의 갈루아 확대일 필요충분조건은 $\mathrm{Gal}(L/E)$가 G의 정규 부분군인 것이며, 그때 $\mathrm{Gal}(E/K)\cong G/\mathrm{Gal}(L/E)$입니다. 위의 L = ℚ(√2, √3)은 $(x^2 - 2)(x^2 - 3)$의 분해체라 정리가 적용되고, 중간체 다섯과 부분군 다섯이 정확히 짝지어집니다. 가정이 빠지면 대응이 깨집니다. ℚ(∛2)는 실수⁠(real number)⁠ 안에 있어 x³ − 2의 다른 두 근을 담지 못하므로(분해체가 아님), ∛2를 옮길 곳이 없어 자기 동형이 항등 하나뿐입니다. 그러면 ℚ와 ℚ(∛2)가 같은 군 {e}에 대응해, 체 ℚ는 닫힌 원소⁠(closed element)⁠가 아닙니다. 극성 자체는 어떤 확대에서나 있고, 정리의 내용은 '갈루아 확대에서는 모든 중간체와 모든 부분군이 닫혀 있다'는 것입니다.

이 대응이 방정식의 문제를 군의 문제로 바꿉니다. 거듭제곱근을 차례로 붙여 가는 체의 사슬이 부분군의 사슬로 옮겨지고, 그래서 다항식이 사칙연산과 거듭제곱근으로 풀리는 것은 그 다항식의 갈루아 군⁠(Galois group)⁠이 '가해군⁠(solvable group)⁠'일 때와 같습니다(표수 0에서). 일반 5차 방정식의 군은 가해군이 아니므로 근의 공식⁠(quadratic formula)⁠이 없습니다(다항식). 갈루아는 1830–32년 이 생각을 적었지만 생전에 인정받지 못했고, 원고는 1846년 조제프 리우빌이 출판했습니다. 체와 군의 대응을 오늘날의 형태로 다듬은 것은 데데킨트를 거쳐 1940년대 에밀 아르틴의 강의였고, 1944년 오이스테인 오레가 순서 사이의 이런 짝 일반에 '갈루아 연결'이라는 이름을 붙였습니다. 오레의 정의는 갈루아의 경우처럼 순서를 뒤집는 짝이었고, 오늘날에는 순서를 지키는 판(이 페이지 첫머리의 정의)과 뒤집는 판을 모두 이 이름으로 부릅니다.

컴퓨터 과학에서는 1977년 파트리크 쿠소와 라디아 쿠소의 추상 해석(abstract interpretation)이 갈루아 연결 위에 서 있습니다. 프로그램 변수가 가질 수 있는 정수들의 집합(구체적 영역)과 '음수, 0, 양수, 모름' 같은 요약(추상적 영역) 사이에 $\alpha(S)\sqsubseteq a\iff S\subseteq\gamma(a)$인 짝을 두면, 요약 위에서 계산한 결론이 실제 실행에 대해서도 참이라는 것(건전성)이 이 연결에서 나옵니다. 요약은 정보를 잃지만 틀리지는 않습니다. 비행 제어 소프트웨어의 실행 오류가 없음을 보이는 정적 분석기가 이 원리를 씁니다(호어 논리⁠(Hoare logic)⁠, 영역 이론⁠(domain theory)⁠). 논리에서도 같은 극성이 있습니다. 문장들의 집합 T에는 그 문장을 모두 만족하는 구조들을, 구조들의 모임에는 그 구조 모두에서 참인 문장들을 대응시키면, 문장 쪽 닫힘 연산이 'T에서 참이 따라 나오는 문장 전체'이고, 1차 논리⁠(first-order logic)⁠에서는 괴델의 완전성 정리⁠(completeness theorem)⁠에 따라 이것이 'T에서 증명되는 문장 전체'와 같습니다.

이어지는 곳. 갈루아 연결은 수반 함자가 순서에서 취하는 모습이라, 그 페이지의 올림과 내림, ∃ ⊣ 역상 ⊣ ∀가 모두 이 페이지의 예이고, 왼쪽 짝이 최댓값을 보존한다는 것은 수반이 쌍대극한을 보존한다는 정리의 순서판입니다. '그리고'와 '이면'의 짝은 집합의 연산과 불 대수에서 출발해 직관주의 논리의 헤이팅 대수⁠(Heyting algebra)⁠에 이릅니다. 한 바퀴 돌면 나오는 닫힘 연산은 열공간의 선형 생성, 위상수학의 닫힘과 같은 구조이고, 순서에서 모나드⁠(monad)⁠가 바로 닫힘 연산이라는 것은 모나드와 이어집니다. 체와 군의 대응은 갈루아의 이론과 군, 근의 공식이 없는 까닭은 다항식으로 이어지고, 호어 논리에서는 최강 후조건⁠(strongest postcondition)⁠과 최약 전조건⁠(weakest precondition)⁠이 갈루아 연결을 이루고, 반복문의 뜻은 영역 이론처럼 순서 위의 가장 작은 고정점⁠(fixed point)⁠으로 정합니다. 두 요소가 서로 '아래를 모두 보면 같다'는 논법은 요네다 보조정리의 가장 작은 경우입니다.