폐포 연산자

틀:위키데이터 속성 추적 순서론에서 폐포 연산자(閉包演算子, 틀:Llang) 또는 폐포 연산(閉包演算, 틀:Llang)은 위상수학의 폐포와 유사한 성질들을 만족시키는 함수이다. 위상수학적 폐포와 달리 유한 합집합을 보존할 필요가 없다. 완비 격자를 판단하는 데 쓰일 수 있다. 보편 대수학과 계산 복잡도 이론 등에서 응용된다.

정의

폐포 연산자

부분 순서 집합 $(P,\le )$ 위의 폐포 연산자는 다음 세 조건을 만족시키는 함수 $c:P\to P$이다. 임의의 $x,y\in P$에 대하여,

• (확장성) $x\le c(x)$
• (증가성) $x\le y⟹c(x)\le c(y)$
• (멱등성) $c(c(x))=c(x)$

범주론적으로, 폐포 연산자는 (범주로 본) 부분 순서 집합 위의 모나드이다. 폐포 연산자 $c$가 주어진 부분 순서 집합 $(P,\le )$의 닫힌 원소(틀:Llang)는 $x=c(x)$인 원소 $x\in P$이다. 이는 $c(x)$ 꼴의 원소와 동치이다. 닫힌 원소들의 집합은 ($P$의 순서를 물려받았을 때) 부분 순서 집합 $c[P]$을 이룬다. 만약 $P$가 어떤 집합 $S$의 부분 집합들을 모은 멱집합 $\mathrm{Pow}(S)$이라면, $c$는 단순히 $S$ 위의 폐포 연산자라고 하고, 닫힌 원소는 닫힌집합이라고 부른다.

대수적 폐포 연산자

대수적 격자 $L$ 위의 폐포 연산자 $c:L\to L$가 다음 조건을 만족시키면, 대수적 폐포 연산자(代數的閉包演算子, 틀:Llang)라고 한다.

• 임의의 $x\in L$에 대하여, $c(x)=\underset{y\ll y\le x}{\bigvee }c(y)$

여기서 $y\ll y$는 $y$가 $L$의 콤팩트 원소임을 나타낸다. 예를 들어, $L=\mathrm{Pow}(S)$가 멱집합인 경우, 콤팩트 원소는 $S$의 유한 부분 집합이며, 대수적 폐포 연산자 조건은 임의의 집합의 폐포가 유한 부분 집합들의 폐포의 합집합임을 나타낸다.

성질

순서론적 성질

폐포 연산자가 주어진 격자의 닫힌 원소들의 부분 순서 집합은 격자를 이룬다. 폐포 연산자가 주어진 완비 격자의 닫힌 원소들의 부분 순서 집합은 완비 격자를 이룬다. 대수적 폐포 연산자가 주어진 대수적 격자의 닫힌 원소들의 부분 순서 집합은 대수적 격자를 이룬다. (닫힌 원소 격자의 콤팩트 원소는 정확히 원래 격자의 콤팩트 원소의 폐포이다.) 반대로, 모든 완비 격자는 폐포 연산자가 주어진 멱집합의 닫힌 원소 격자와 동형이며, 모든 대수적 격자는 대수적 폐포 연산자가 주어진 멱집합의 닫힌 원소 격자와 동형이다. 틀:증명 격자 $(L,\vee ,\wedge )$ 및 폐포 연산자 $c:L\to L$에 대하여, $c[L]$이 다음과 같은 이음·만남 연산에 대하여 격자를 이룸을 쉽게 보일 수 있다.

$x{\vee }_{c[L]}y=c(x\vee y)$

$x{\wedge }_{c[L]}y=x\wedge y$

마찬가지로, 완비 격자 $L$ 및 폐포 연산자 $c:L\to L$에 대하여, $c[L]$은 다음 상한·하한에 대하여 완비 격자를 이룬다.

$\underset{c[L]}{\bigvee }S=c(\bigvee S)$

$\underset{c[L]}{\bigwedge }S=\bigwedge S$

대수적 격자 $L$ 및 대수적 폐포 연산자 $c:L\to L$가 주어졌다고 하자. 그렇다면, $c[L]$은 완비 격자이다. $x\in L$이 $L$의 콤팩트 원소이며, $c(x)\le \underset{c[L]}{\bigvee }S$라고 하자. 대수적 격자의 정의 및 $x$의 콤팩트성에 따라,

$x\le c(y_1)\vee \cdots \vee c(y_m)$

$y_i\ll y_i\le \bigvee S(i=1,\dots ,m)$

라고 하자. 다시 $y_i$의 콤팩트성에 따라

$y_i\le s_{i1}\vee \cdots \vee s_{i{n}_i}(i=1,\dots ,m)$

인 $s_{ij}\in S$를 취할 수 있다. 이 경우

$c(x)\le c(s_{11}\vee \cdots \vee s_{m{n}_m})=s_{11}{\vee }_{c[L]}\cdots {\vee }_{c[L]}{s}_{m{n}_m}$

이다. 이에 따라, $c(x)$는 $c[L]$의 콤팩트 원소이다. 반대로, $y\in c[L]$이 $c[L]$의 콤팩트 원소라고 하자. 그렇다면,

$y=c(y)=\underset{x\ll x\le y}{\bigvee }c(x)$

이므로,

$y\le c(x_1)\vee \cdots \vee c(x_n)$

$x_i\ll x_i\le y$

이다. 따라서

$y=c(x_1\vee \cdots \vee x_n)$

이며, $x_1\vee \cdots \vee x_n\in L$은 (유한 개의 콤팩트 원소의 이음이므로) 콤팩트 원소이다. 이에 따라, $c[L]$의 콤팩트 원소는 정확히 $L$의 콤팩트 원소 $x$에 대하여 $c(x)$ 꼴로 나타낼 수 있는 원소이다. 대수적 폐포 연산자의 정의에 따라, $c[L]$의 모든 원소는 $c[L]$의 콤팩트 원소들의 $L$에서의 이음이며, 특히 이는 $c[L]$에서의 이음이다. 즉, $c[L]$은 대수적 격자이다.

이제, 임의의 완비 격자 $L$가 주어졌다고 하자. 다음 함수를 정의하자.

$c:\mathrm{Pow}(L)\to \mathrm{Pow}(L)$

$c:S\mapsto \downarrow \bigvee S$

그렇다면, $c$는 $L$(의 멱집합) 위의 폐포 연산자이며, $L$과 $c[\mathrm{Pow}(L)]$ 사이에 자연스러운 동형

$x\mapsto \downarrow x$

이 존재한다.

마찬가지로, 임의의 대수적 격자 $L$에 대하여,

$c:\mathrm{Pow}(k(L))\to \mathrm{Pow}(k(L))$

$c:S\mapsto \{x\in k(L):x\le \bigvee S\}$

은 $L$의 콤팩트 원소의 집합 $k(L)$ 위의 대수적 폐포 연산자이며,

$x\mapsto \{y\in k(L):y\le x\}$

는 $L$과 $c[\mathrm{Pow}(k(L))]$ 사이의 동형이다. 틀:증명 끝

닫힌 원소들이 대수적 격자를 이루는, 대수적 격자 위의 폐포 연산자는 대수적 폐포 연산자일 필요가 없다. 틀:증명 무한 집합 $S\bigsqcup \{s\}$의 멱집합 $\mathrm{Pow}(S\bigsqcup \{s\})$ 위에 다음과 같은 함수를 정의하자.

• 만약 $X$가 $S$의 진부분 집합이라면, $c(X)=X$
• 만약 $s\in X$이거나 $X=S$라면, $c(X)=S\bigsqcup \{s\}$

이는 $S\bigsqcup \{s\}$ 위의 폐포 연산자이다. 그 닫힌집합은 $S$의 진부분 집합과 $S\bigsqcup \{s\}$로 이루어지며, 이들은 ($S$의 멱집합과 동형인) 대수적 격자를 이룬다. 그러나 $s\in S\bigsqcup \{s\}=c(S)$이며, $s\in c(X)$인 $S$의 유한 부분 집합 $X$은 존재하지 않는다. (이는 $S$가 무한 집합이므로, $S$의 모든 유한 부분 집합은 진부분 집합이기 때문이다.) 따라서 $c$는 대수적 폐포 연산자가 아니다. 틀:증명 끝

완비 격자 위의 폐포 연산자들의 (점별 순서에 의한) 부분 순서 집합은 완비 격자를 이룬다. 대수적 격자 위의 대수적 폐포 연산자들의 (점별 순서에 의한) 부분 순서 집합은 대수적 격자를 이룬다.틀:Rp 이는 폐포 연산자 격자의 부분 격자이지만, 부분 완비 격자가 아닐 수 있다.틀:Rp

닫힌 원소 집합일 조건

집합 $S$의 부분 집합들의 집합 $𝒞\subseteq \mathrm{Pow}(S)$에 대하여, 다음 두 조건이 서로 동치이다.틀:Rp

• $𝒞$는 어떤 폐포 연산자 $c:\mathrm{Pow}(S)\to \mathrm{Pow}(S)$에 대한 닫힌 원소들의 집합이다.
• (임의 교집합에 대한 닫힘) 임의의 $ℱ\subset 𝒞$에 대하여, $\bigcap ℱ\in 𝒞$

집합 $S$의 부분 집합들의 집합 $𝒞\subseteq \mathrm{Pow}(S)$에 대하여, 다음 두 조건이 서로 동치이다.틀:Rp

• $𝒞$는 어떤 대수적 폐포 연산자 $c:\mathrm{Pow}(S)\to \mathrm{Pow}(S)$에 대한 닫힌 원소들의 집합이다.
• 다음 두 조건을 만족시킨다.
  • (임의 교집합에 대한 닫힘) 임의의 $ℱ\subset 𝒞$에 대하여, $\bigcap ℱ\in 𝒞$
  • (사슬의 합집합에 대한 닫힘) 임의의 사슬 $ℱ\subset 𝒞$에 대하여, $\bigcup ℱ\in 𝒞$

타르스키 여분이 없는 기저 정리

집합 $S$ 위의 폐포 연산자 $c:\mathrm{Pow}(S)\to \mathrm{Pow}(S)$ 및 음이 아닌 정수 $n\in \mathbb{N}$이 주어졌다고 하자. 다음과 같은 함수 ${\varphi }_{c,n}:\mathrm{Pow}(S)\to \mathrm{Pow}(S)$를 정의하자.

${\varphi }_{c,n}(X)=\bigcup _{Y\subseteq X}^{|Y|<n}c(Y)$

이를 사용하여, 일련의 함수 ${\varphi }_{c,n}^{\alpha }$들을 다음과 같이 재귀적으로 정의할 수 있다.

• 따름 순서수 $\alpha =\beta +1$에 대하여, ${\varphi }_{c,n}^{\beta +1}={\varphi }_{c,n}{\varphi }_{c,n}^{\beta }$
• 극한 순서수 $\alpha$에 대하여, ${\varphi }_{c,n}^{\alpha }(X)=X\cup \bigcup _{\beta <\alpha }{\varphi }_{c,n}^{\beta }(X)$

만약 $c={\varphi }_{c,n}^{\omega }$라면, $c$가 계수 $n$의 폐포 연산자(틀:Llang)라고 한다. (사실, 임의의 폐포 연산자 $c$에 대하여, ${\varphi }_{c,n}^{\omega }$는 계수 $n$의 폐포 연산자이며, 점별 순서를 부여하였을 때 이는 ${\varphi }_{c,n}^{\omega }\le c$를 만족하는 것들 가운데 최대이다.)

폐포 연산자 $c:\mathrm{Pow}(S)\to \mathrm{Pow}(S)$가 주어진 집합 $S$의 극소 생성 집합(틀:Llang)은 다음 두 조건을 만족시키는 부분 집합 $X\subseteq S$이다.

• $c(X)=S$
• 임의의 진부분 집합 $Y⊊X$에 대하여, $c(Y)⊊S$

다음이 주어졌다고 하자.

• 집합 $S$
• 음이 아닌 정수 $n\in \mathbb{N}$
• 계수 $n$의 폐포 연산자 $c:\mathrm{Pow}(S)\to \mathrm{Pow}(S)$
• 음이 아닌 정수 $i\le j$. 또한,
  • 크기 $i,j$의 극소 생성 집합이 존재한다.
  • 크기 $i<|X|<j$의 극소 생성 집합 $X$이 존재하지 않는다.

타르스키 여분이 없는 기저 정리(틀:Llang)에 따르면, $j\le i+n-2$이다. 특히, 계수 3의 폐포 연산자의 경우, 극소 생성 집합들의 크기는 연속된 정수들로 이루어진다. 틀:증명 크기 $|X|=j$의 극소 생성 집합 $X$를 취하자. 임의의 유한 극소 생성 집합 $Y$에 대하여, $m(Y)$가 $Y\subseteq {\varphi }_{c,n}^{m(Y)}(X)$인 최소의 음이 아닌 정수라고 하자. 그렇다면, $X$의 극소성에 따라 $Y=X$이거나 $m(Y)>0$이다. 이제, 다음 조건들을 만족시키는 $Y\subseteq S$를 고르자.

• $Y$는 극소 생성 집합이다.
• $|Y|\le i$
• 크기 $i$ 이하의 극소 생성 집합 가운데, $m(Y)$가 최소이다.
• $m(-)$ 값이 최소인, 크기 $i$ 이하의 극소 생성 집합 가운데, $|Y\setminus {\varphi }_{c,n}^{m(Y)-1}(X)|$가 최소이다.

또한, $y_0\in Y\setminus {\varphi }_{c,n}^{m(Y)-1}(X)$라고 하자. $y_0\in {\varphi }_{c,n}^{m(Y)}(X)$이므로, $y_0\in {\varphi }_{c,n}(Z)$, $|Z|\le n-1$인 $Z\subseteq {\varphi }_{c,n}^{m(Y)-1}(X)$가 존재한다. 따라서

$c(Y\setminus \{y_0\}\cup Z)=c(c(Y\setminus \{y_0\}\cup Z))\supseteq c(c(Y\setminus \{y_0\})\cup {\varphi }_{c,n}(Z))\supseteq c(Y)=S$

이다. $Y\setminus \{y_0\}\cup Z$가 유한 집합이므로, 극소 생성 집합 $W\subseteq Y\setminus \{y_0\}\cup Z$을 취할 수 있다.

$W\subseteq Y\cup Z\subseteq {\varphi }_{c,n}^{m(Y)}(X)\cup {\varphi }_{c,n}^{m(Y)-1}(X)={\varphi }_{c,n}^{m(Y)}(X)$

이므로 $m(W)=m(Y)$이다. 또한, $y_0\in Y\setminus {\varphi }_{c,n}^{m(Y)-1}(X)$이므로,

$|W\setminus {\varphi }_{c,n}^{m(Y)-1}(X)|\le |(Y\setminus \{y_0\}\cup Z)\setminus {\varphi }_{c,n}^{m(Y)-1}(X)|=|(Y\setminus \{y_0\})\setminus {\varphi }_{c,n}^{m(Y)-1}(X)|<|Y\setminus {\varphi }_{c,n}^{m(Y)-1}(X)|$

이다. $Y$의 선택에 따라 $|W|>i$이며, 다시 $i$와 $j$에 대한 가정에 따라

$j\le |W|\le |Y\setminus \{y_0\}\cup Z|\le |Y|+|Z|-1\le i+n-2$

이다. 틀:증명 끝

예

(범주로 본) 두 부분 순서 집합 $(P,{\le }_P)$, $(Q,{\le }_Q)$ 사이의 수반 함자의 쌍

$f:P\leftrightarrows Q:g$

이 주어졌다고 하자. (순서론에서 이는 갈루아 연결이라고 한다.) 그렇다면,

$gf:P\to P$

$fg:Q\to Q$

는 각각 $P$와 $Q$ 위의 폐포 연산자를 이룬다.

폐포 연산자의 예로는 다음이 있다.

부분 순서 집합 $P$	$P$의 콤팩트 원소	$P$의 대수적 격자 여부	닫힌 원소들의 집합 $c[P]$	$c[P]$의 콤팩트 원소	$c[P]$의 대수적 격자 여부	폐포 연산자 $c:P\to P$	대수적 폐포 연산자 여부
위상 공간 $X$의 멱집합 $\mathrm{Pow}(X)$	$X$의 유한 부분 집합	참	위상수학적 닫힌집합의 격자	유한 집합의 폐포	거짓일 수 있음	위상수학적 폐포	거짓일 수 있음
가환환 $R$의 아이디얼 격자	유한 생성 아이디얼		반소 아이디얼 격자	주 아이디얼의 소근기	참틀:Rp	소근기틀:Rp	참
부호수 $F$의 대수 구조 $(A,F_A)$의 멱집합 $\mathrm{Pow}(A)$	$A$의 유한 부분 집합		부분 대수 격자 $\mathrm{Sub}(A)$	유한 생성 부분 대수	참	$S\mapsto \bigcup _{n=0}^{\mathrm{\infty }}{e}^n(S)$	참
부호수 $F$의 대수 구조 $(A,F_A)$ 위의 이항 관계의 집합 $\mathrm{Pow}(A\times A)$	유한 이항 관계		합동 관계 격자 $\mathrm{Cong}(A)$	유한 생성 합동 관계	참	$S\mapsto \bigcup _{n=0}^{\mathrm{\infty }}{f}^n(S)$	참

여기서,

• 부호수 $F$의 대수 구조 $(A,F_A)$의 부분 집합 $S\subseteq A$에 대하여, 틀:Mindent
• 부호수 $F$의 대수 구조 $(A,F_A)$ 위의 이항 관계 $S\subseteq A\times A$에 대하여, 틀:Mindent

임의의 군의 부분군을 생성하는 함수는 계수 3의 폐포 연산자이다. 타르스키 여분이 없는 기저 정리에 따라, 임의의 군의 극소 생성 집합의 크기의 집합은 연속된 정수들로 구성된다. 보다 일반적으로, $n-1$항 이하의 연산들로 구성된 대수 구조의 부분 대수 생성 함수는 계수 $n$의 폐포 연산자이다.

역사

폐포 연산자에 관한 연구는 E. H. 무어의 1910년 저서 《Introduction to a form of general analysis》에 처음으로 등장한다.

외부 링크

• 틀:Eom
• 틀:Nlab