타르스키 고정점 정리

틀:위키데이터 속성 추적 순서론에서 타르스키 고정점 정리(틀:Llang) 또는 크나스터-타르스키 정리(틀:Llang)는 완비 격자에서 자신으로 가는 단조함수의 고정점이 존재한다는 정리이다.

이는 이론 컴퓨터 과학의 형식 의미론 및 추상 해석 분야에서 중요한 정리이다.

정의

완비 격자 $L$과 단조함수 $f:L\to L$가 주어졌다고 하자. 타르스키 고정점 정리에 따르면, $f$의 고정점의 집합

$\mathrm{fix}(f)=\{a\in L:f(a)=a\}$

역시 완비 격자를 이룬다. (그러나, $\mathrm{fix}(f)$가 $L$의 부분 격자일 필요는 없다. 즉, $\mathrm{fix}(f)$에서의 상한과 하한은 $L$에서와 일치하지 않을 수 있다.) 특히, $f$의 최대 고정점과 최소 고정점이 존재하며, 특히 $f$는 적어도 하나의 고정점을 갖는다. 또한, $f$의 최대·최소 고정점은 각각 다음과 같이 주어진다.

$\bigvee \mathrm{fix}(f)=\bigvee \{a\in L:a\le f(a)\}$

$\bigwedge \mathrm{fix}(f)=\bigwedge \{a\in L:a\ge f(a)\}$

증명

타르스키를 따라, 다음 순서대로 증명한다.

• (가) $\bigvee \{a\in L:a\le f(a)\}$는 $f$의 최대 고정점이다.
• (나) $\bigwedge \{a\in L:a\ge f(a)\}$는 $f$의 최소 고정점이다.
• (다) $\mathrm{fix}(f)$는 완비 격자이다.

명제 (가)의 증명. $M=\{a\in L:a\le f(a)\}$라고 하자. 임의의 $a\in M$에 대하여, $a\le \bigvee M$이므로, $a\le f(a)\le f(\bigvee M)$이다. 따라서 $\bigvee M\le f(\bigvee M)$이다. 반대로, $f(\bigvee M)\le f\left(f(\bigvee M)\right)$이므로, $M$의 정의에 따라 $f(\bigvee M)\in M$이다. 따라서 $f(\bigvee M)\le \bigvee M$이다. 따라서, $\bigvee M$은 $f$의 고정점이다. 모든 고정점은 $M$에 속하므로, $\bigvee M$은 $f$의 최대 고정점이다.

명제 (나)의 증명. $L$의 반대 격자 $L^{\mathrm{op}}$를 생각하자. $L^{\mathrm{op}}$ 역시 완비 격자를 이루며, $f$는 $L^{\mathrm{op}}$ 위에서도 단조함수이다. 따라서 $L^{\mathrm{op}}$에 대하여 명제 (가)가 성립한다. 이는 정확히 $L$에 대한 명제 (나)와 일치한다.

명제 (다)의 증명. $S$가 $\mathrm{fix}(f)$의 임의의 부분 집합이라고 하자. $\mathrm{fix}(f)$에서 $S$의 상한이 존재함을 보이면 충분하다. $S$의 $L$에서의 상한 $\bigvee S$를 생각하자. 그렇다면 구간 $[\bigvee S,\mathrm{\top }]=\{a\in L:a\ge \bigvee S\}$는 $S$의 상계의 집합이며, 완비 격자를 이룬다 (이는 부분 격자이기도 하지만, 부분 완비 격자가 아닐 수 있다). 임의의 $s\in S$에 대하여 $s=f(s)\le f(\bigvee S)$이므로, $\bigvee S\le f(\bigvee S)$이다. $a\in L$에 대하여, 만약 $a\ge \bigvee S$라면, $f(a)\ge f(\bigvee S)\ge \bigvee S$이다. 따라서, $f$를 $[\bigvee S,\mathrm{\top }]$ 위의 함수 $f^{\prime }:[\bigvee S,\mathrm{\top }]\to [\bigvee S,\mathrm{\top }]$로 여길 수 있다. 명제 (나)에 따라, $f^{\prime }$의 최소 고정점이 존재한다. 이는 $f$의 고정점이며, $S$의 상계가 되는 가장 작은 $f$의 고정점이다. 다시 말해, $S$의 $\mathrm{fix}(f)$에서의 상한이다.

고정점 집합이 부분 격자가 아닌 경우

고정점 집합은 완비 격자이지만, 부분 격자가 아닐 수 있다. 예를 들어, 다음과 같은 부분 순서 집합을 생각하자.

$L=\{\mathrm{\perp },a,a^{\prime },b,\mathrm{\top }\}$

$\mathrm{\perp }<a,a^{\prime }<b<\mathrm{\top }$

그렇다면, $L$은 완비 격자를 이룬다. 이제 $f:L\to L$이며

$f(x)=x(x=\mathrm{\perp },a,a^{\prime },\mathrm{\top })$

$f(b)=\mathrm{\top }$

라고 하자. $f$는 $L$ 위의 단조함수이며, $a$와 $a^{\prime }$은 $f$의 고정점이지만, $a\vee a^{\prime }=b$는 $f$의 고정점이 아니다. ($a$와 $a^{\prime }$의 $\mathrm{fix}(f)$에서의 상한은 $b$가 아닌 $\mathrm{\top }$이다.) 따라서, $\mathrm{fix}(f)$는 $L$의 부분 격자가 아니다.

귀결

완비 격자는 공집합일 수 없으므로, 이 정리는 상기한 $f$에 적어도 한개의 고정점이 있음을, 나아가서 최소 고정점이 있음을 보장한다.

조건을 추가하여 임의의 부분 순서 집합에 대하여 유사한 결과를 증명할 수 있다. 이를 동역학계 이론에 적용하여 프랙탈의 일종인 반복함수계(iterated function system) 연구에 사용할 수 있다.

모든 증가수열 $x_n$에 대해 $f(\lim x_n)=\lim f(x_n)$이면, $f$의 최소 고정점은 $\lim f_n(0)$이며, 이는 정리의 구성적 버전(Kleene fixed-point theorem)을 제공한다.

이론 컴퓨터 과학에서, 단조함수에 대한 최소 고정점 정리는 프로그램 의미론을 정의하는 데 사용된다. 이 경우 특히 격자 L을 특정 집합의 모든 부분집합들을 모은 것, 즉 멱집합 격자로 가정하는 특수한 케이스에 대하여 집중하는 것이 일반적이다. 그리고 나서 f의 고정점이 되기 위해 필요한 조건을 가지는 최소의 집합을 찾아낸다.

역

반대로, 모든 단조함수의 고정점이 존재하는 격자는 완비 격자이다.틀:Rp 즉, 타르스키 고정점 정리는 완비 격자의 정의로 삼을 수 있다. 그러나 모든 단조함수가 고정점이 존재하는 부분 순서 집합은 완비 격자일 필요가 없다.

역의 증명

격자 $L$이 완비 격자 위에 항상 고정점이 없는 단조함수 $f:L\to L$를 구성하면 족하다. 두 부분 집합 $A,B\subseteq L$에 대하여, 다음 조건들을 생각하자.

• (라) $A$는 정렬 전순서 집합이다.
• (마) $B$의 반대 순서 집합 $B^{\mathrm{op}}$는 정렬 전순서 집합이다.
• (바) 임의의 $a\in A$ 및 $b\in B$에 대하여, $a<b$
• (사) 동시에 $A$의 상계이자 $B$의 하계인 $L$의 원소가 존재하지 않는다.

만약 $A$와 $B$가 위 조건들을 만족시킨다면, 함수

$f:L\to L$

$f:x\mapsto \{\begin{array}{cc}\min \{a\in A:a\le ̸x\}& \mathrm{\forall }b\in B:x\le b\\ \max \{b\in B:x\le ̸b\}& \mathrm{\exists }b\in B:x\le ̸b\end{array}$

는 단조함수이며, 고정점이 존재하지 않는다. 따라서, 조건 (라)~(사)를 만족시키는 $A$와 $B$를 찾는 것으로 족하다. 모든 부분 집합의 상한이 존재하는 부분 순서 집합은 완비 격자이므로, 상한이 없는 $L$의 부분 집합 $\{a^{\prime }{\text{'}}_{\alpha }:\alpha <\kappa \}$가 존재한다. 편의상 그 크기 $\kappa$가 최소라고 하자. $L$이 격자이므로, $\kappa$은 0이거나 무한 기수이다. 이제, 임의의 순서수 $\alpha <\kappa$에 대하여, $\{a^{\prime }{\text{'}}_{\beta }:\beta <\alpha \}$의 크기는 $\kappa$미만이므로, 상한

$a{\text{'}}_{\alpha }=\underset{\beta <\alpha }{\bigvee }{a}^{\prime }{\text{'}}_{\beta }$

이 존재한다. $(a{\text{'}}_{\alpha }:\alpha <\kappa )$는 단조 초한 점렬이지만, 순단조가 아닐 수 있다. 중복된 항을 제거하여 순단조 초한 점렬 $(a_{\alpha }:\alpha <\kappa )$로 만들자 (길이가 $\kappa$인 것은 $\kappa$의 최소성을 사용하여 보일 수 있다). 이 경우, $A=\{a_{\alpha }:\alpha <\kappa \}$는 정렬 전순서 집합이다. 만약 $A$의 상한이 존재한다면, 이는 $\{a^{\prime }{\text{'}}_{\alpha }:\alpha <\kappa \}$의 상한이 되어 모순이 일어난다. 따라서 $A$의 상한이 존재하지 않는다. $A$의 상계들로 구성된 순감소 초한 점렬들의 집합 위에 다음과 같은 부분 순서를 주자.

$({x_{\alpha }}^{\prime }:{\alpha }^{\prime }<\alpha )⪯({y_{\beta }}^{\prime }:{\beta }^{\prime }<\beta )⟺\alpha \le \beta ,x=y\upharpoonright \alpha$

즉, 끝에 항을 추가하면 더 큰 초한 점렬을 얻는다. 초른 보조정리에 따라, 이 부분 순서에 따른 극대 원소 $(b_{\alpha }:\alpha <\lambda )$가 존재한다 ($\lambda$가 기수일 필요는 없다). $B=\{b_{\alpha }:\alpha <\lambda \}$의 반대 순서 집합 $B^{\mathrm{op}}$은 정렬 전순서 집합이다. 만약 $\bigwedge B$가 존재한다면, $\bigwedge B$ 역시 $A$의 상계이다. $A$의 상한이 존재하지 않으므로, $\bigwedge B\le ̸b$인 $A$의 상계 $b\in L$가 존재한다. 이 경우, $\bigwedge B\wedge b$는 $A$의 상계이며, $\bigwedge B\wedge b<\bigwedge B$이다. 이는 $(b_{\alpha }:\alpha <\lambda )$의 극대성과 모순이다. 따라서, $B$의 하한 역시 존재하지 않는다. 이제, $A=\{a_{\alpha }:\alpha <\kappa \}$와 $B=\{b_{\alpha }:\alpha <\lambda \}$에 대하여 조건 (사)를 증명하는 일만 남았다. 귀류법을 사용하여, $b\in L$이 $A$의 상계이자 $B$의 하계라고 하자. 그렇다면, $(b_{\alpha }:\alpha <\lambda )$의 극대성에 따라 $b\in B$이다. 따라서 $b$는 $B$의 하한이며, 이는 모순이다.

일반화

격자 $L$의, 공집합이 아닌 두 부분 격자 $M$, $N$에 대하여, 다음과 같은 이항 관계를 정의하자.

$M⪯N⟺\mathrm{\forall }a\in M\mathrm{\forall }b\in N:a\wedge b\in M,a\vee b\in N$

특히, 만약 $M⪯N$이라면, 임의의 $a\in M$에 대하여, $a\le b$인 $b\in N$이 존재하며, 마찬가지로 임의의 $b\in N$에 대하여, $a\le b$인 $a\in M$이 존재한다. 즉, $M\subseteq \downarrow N$이며 $N\subseteq \uparrow M$이다. 이 이항 관계는 공집합이 아닌 부분 격자의 집합 위의 부분 순서를 이룬다. $L$의 원소는 자연스럽게 $L$의 부분 격자로 여길 수 있다. 이 경우, 부분 격자의 순서는 원소의 순서를 확장한다. 따라서, 아래의 정리는 타르스키 고정점 정리를 일반화한다.

다음이 주어졌다고 하자.

• 완비 격자 $L$
• 단조함수 $f:L\to (\mathrm{Sub}(L),⪯{|}_{\mathrm{Sub}(L)})$. 여기서 $(\mathrm{Sub}(L),⪯{|}_{\mathrm{Sub}(L)})$은 $L$의 부분 완비 격자의, 위에서 정의한 순서에 따른 부분 순서 집합이다. (부분 완비 격자는 완비 격자인 부분 격자보다 더 강한 개념이다. 전자는 모든 상한과 하한이 원래 격자와 일치하지만, 후자는 모든 유한 집합의 상한·하한의 일치만을 요구한다.)

그렇다면, $f$의 고정점 집합

$\mathrm{fix}(f)=\{a\in L:a\in f(a)\}$

은 완비 격자를 이룬다.틀:Rp 또한, $f$의 최대·최소 고정점은 다음과 같다.

$\bigvee \mathrm{fix}(f)=\bigvee \{a\in L:a\in \downarrow f(a)\}$

$\bigwedge \mathrm{fix}(f)=\bigwedge \{a\in L:a\in \uparrow f(a)\}$

일반화의 증명

타르스키 고정점 정리의 증명과 유사하게, 다음 네 명제를 보인다. 이들 가운데 명제 (아)와 (자), 명제 (차)와 (카)는 서로 쌍대이므로 하나씩만 증명하여도 좋다.

• (아) $M=\{a\in L:a\in \downarrow f(a)\}$에 대하여, $\bigvee M$은 $f$의 최대 고정점이다.
• (자) $N=\{a\in L:a\in \uparrow f(a)\}$에 대하여, $\bigwedge N$은 $f$의 최소 고정점이다.
• (차) 모든 $S\subseteq \mathrm{fix}(f)$의 $\mathrm{fix}(f)$에서의 상한이 존재한다.
• (카) 모든 $S\subseteq \mathrm{fix}(f)$의 $\mathrm{fix}(f)$에서의 하한이 존재한다.

명제 (아)의 증명. $\mathrm{fix}(f)\subseteq M$이므로, $\bigvee M\in \mathrm{fix}(f)$이면 충분하다. 임의의 $a\in M$가 주어졌다고 하자. $M$의 정의에 따라, $x_a\in f(a)$이며 $a\le x_a$라고 하자. $a\le \bigvee M$이며 $f$가 단조함수이므로, $y_a\in f(\bigvee M)$이며 $x_a\le y_a$라고 하자. $f(\bigvee M)$이 부분 완비 격자이므로, $\underset{a\in M}{\bigvee }{y}_a\in f(\bigvee M)$이다. 임의의 $a\in M$에 대하여 $a\le x_a\le y_a$이므로, $\bigvee M\le \underset{a\in M}{\bigvee }{y}_a$이다. $f$의 단조성에 따라, $\underset{a\in M}{\bigvee }{y}_a\le z$인 $z\in f\left(\underset{a\in M}{\bigvee }{y}_a\right)$가 존재한다. 즉, $\underset{a\in M}{\bigvee }{y}_a\in M$이며, 따라서 $\underset{a\in M}{\bigvee }{y}_a\le \bigvee M$이다. 따라서, $\bigvee M=\underset{a\in M}{\bigvee }{y}_a\in f(\bigvee M)$은 $f$의 고정점이 맞다.

명제 (차)의 증명. $\bigvee S$가 $S$의 $L$에서의 상한이라고 하자. 그렇다면, $[\bigvee S,\mathrm{\top }]$은 완비 격자를 이룬다. 임의의 $s\in S$에 대하여, $s\in f(s)$이며 $s\le \bigvee S$이므로, $s\le x_s$인 $x_s\in f(\bigvee S)$가 존재한다. 이 경우, $\underset{s\in S}{\bigvee }{x}_s\in f(\bigvee S)$이며 $\bigvee S\le \underset{s\in S}{\bigvee }{x}_s$이다. 따라서, $f$의 단조성에 의하여, 만약 $a\in [\bigvee S,\mathrm{\top }]$라면, $g(a)=f(a)\cap [\bigvee S,\mathrm{\top }]$은 공집합이 아니다. 또한, $f(a)$는 $L$의 부분 완비 격자이다. 따라서, $g(a)$는 $[\bigvee S,\mathrm{\top }]$의 부분 완비 격자를 이룬다. 즉, $a\mapsto g(a)$는 단조함수 $g:[\bigvee S,\mathrm{\top }]\to (\mathrm{Sub}([\bigvee S,\mathrm{\top }]),⪯{|}_{\mathrm{Sub}([\bigvee S,\mathrm{\top }])})$를 정의한다. 명제 (자)에 따라, $g$의 최소 고정점이 존재하며, 이는 $S$의 $\mathrm{fix}(f)$에서의 상한이다.

역사

브로니스와프 크나스터 (1893~1980)

알프레트 타르스키 (1901~1983)

1927년 브로니스와프 크나스터(틀:Llang)와 알프레트 타르스키가 멱집합 격자 위 단조함수의 고정점의 존재를 증명하였다.틀:Rp 타르스키 고정점 정리의 오늘날 형태는 1939년 타르스키가 도입하였으며, 1939년~1942년 동안 타르스키의 몇몇 공개 강의에서 소개되었다.틀:Rp 타르스키 고정점 정리의 역은 앤 모렐(틀:Llang)이 증명하였다. 타르스키 고정점 정리의 다중 값 일반화는 저우린(틀:Zh)이 초모듈러 게임(틀:Llang)의 내시 균형의 존재를 보이기 위하여 증명 및 사용하였다.

같이 보기

• 고정점 정리
• 완비 격자

참고 문헌

• 틀:저널 인용
• 틀:저널 인용
• 틀:저널 인용

외부 링크

• 틀:매스월드