타르스키 고정점 정리

순서론에서 **타르스키 고정점 정리**(Tarski’s fixed point theorem) 또는 **크나스터-타르스키 정리**(Knaster–Tarski theorem)는 완비 격자에서 자신으로 가는 단조함수의 고정점이 존재한다는 정리이다. 이는 이론 컴퓨터 과학의 형식 의미론 및 추상 해석 분야에서 중요한 정리이다.
# 정의
완비 격자 L과 단조함수 f\colon L\to L가 주어졌다고 하자. **타르스키 고정점 정리**에 따르면, f의 고정점의 집합 :\operatorname{fix}(f)=\\{a\in L\colon f(a)=a\\} 역시 완비 격자를 이룬다. (그러나, \operatorname{fix}(f)가 L의 부분 격자일 필요는 없다. 즉, \operatorname{fix}(f)에서의 상한과 하한은 L에서와 일치하지 않을 수 있다.) 특히, f의 최대 고정점과 최소 고정점이 존재하며, 특히 f는 적어도 하나의 고정점을 갖는다. 또한, f의 최대·최소 고정점은 각각 다음과 같이 주어진다. :\bigvee\operatorname{fix}(f)=\bigvee\\{a\in L\colon a\le f(a)\\} :\bigwedge\operatorname{fix}(f)=\bigwedge\\{a\in L\colon a\ge f(a)\\}
## 증명
타르스키를 따라, 다음 순서대로 증명한다. * (가) \textstyle\bigvee\\{a\in L\colon a\le f(a)\\}는 f의 최대 고정점이다. * (나) \textstyle\bigwedge\\{a\in L\colon a\ge f(a)\\}는 f의 최소 고정점이다. * (다) \operatorname{fix}(f)는 완비 격자이다. 명제 (가)의 증명. M=\\{a\in L\colon a\le f(a)\\}라고 하자. 임의의 a\in M에 대하여, \textstyle a\le\bigvee M이므로, \textstyle a\le f(a)\le f\left(\bigvee M\right)이다. 따라서 \textstyle\bigvee M\le f\left(\bigvee M\right)이다. 반대로, \textstyle f\left(\bigvee M\right)\le f\left(f\left(\bigvee M\right)\right)이므로, M의 정의에 따라 \textstyle f\left(\bigvee M\right)\in M이다. 따라서 \textstyle f\left(\bigvee M\right)\le\bigvee M이다. 따라서, \textstyle\bigvee M은 f의 고정점이다. 모든 고정점은 M에 속하므로, \textstyle\bigvee M은 f의 최대 고정점이다. 명제 (나)의 증명. L의 반대 격자 L^{\operatorname{op를 생각하자. L^{\operatorname{op 역시 완비 격자를 이루며, f는 L^{\operatorname{op 위에서도 단조함수이다. 따라서 L^{\operatorname{op에 대하여 명제 (가)가 성립한다. 이는 정확히 L에 대한 명제 (나)와 일치한다. 명제 (다)의 증명. S가 \operatorname{fix}(f)의 임의의 부분 집합이라고 하자. \operatorname{fix}(f)에서 S의 상한이 존재함을 보이면 충분하다. S의 L에서의 상한 \textstyle\bigvee S를 생각하자. 그렇다면 구간 \textstyle\left[\bigvee S,\top\right]=\left\\{a\in L\colon a\ge\bigvee S\right\\}는 S의 상계의 집합이며, 완비 격자를 이룬다 (이는 부분 격자이기도 하지만, 부분 완비 격자가 아닐 수 있다). 임의의 s\in S에 대하여 \textstyle s=f(s)\le f\left(\bigvee S\right)이므로, \textstyle\bigvee S\le f\left(\bigvee S\right)이다. a\in L에 대하여, 만약 \textstyle a\ge\bigvee S라면, \textstyle f(a)\ge f\left(\bigvee S\right)\ge\bigvee S이다. 따라서, f를 \textstyle\left[\bigvee S,\top\right] 위의 함수 \textstyle f'\colon\left[\bigvee S,\top\right]\to\left[\bigvee S,\top\right]로 여길 수 있다. 명제 (나)에 따라, f'의 최소 고정점이 존재한다. 이는 f의 고정점이며, S의 상계가 되는 가장 작은 f의 고정점이다. 다시 말해, S의 \operatorname{fix}(f)에서의 상한이다.
## 고정점 집합이 부분 격자가 아닌 경우
고정점 집합은 완비 격자이지만, 부분 격자가 아닐 수 있다. 예를 들어, 다음과 같은 부분 순서 집합을 생각하자. :L=\\{\bot,a,a',b,\top\\} :\bot 그렇다면, L은 완비 격자를 이룬다. 이제 f\colon L\to L이며 :f(x)=x\qquad(x=\bot,a,a',\top) :f(b)=\top 라고 하자. f는 L 위의 단조함수이며, a와 a'은 f의 고정점이지만, a\vee a'=b는 f의 고정점이 아니다. (a와 a'의 \operatorname{fix}(f)에서의 상한은 b가 아닌 \top이다.) 따라서, \operatorname{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의 고정점이 되기 위해 필요한 조건을 가지는 최소의 집합을 찾아낸다.
# 역
반대로, 모든 단조함수의 고정점이 존재하는 격자는 완비 격자이다.zbl=0064.26101313, Theorem 2 즉, 타르스키 고정점 정리는 완비 격자의 정의로 삼을 수 있다. 그러나 모든 단조함수가 고정점이 존재하는 부분 순서 집합은 완비 격자일 필요가 없다.
## 역의 증명
격자 L이 완비 격자 위에 항상 고정점이 없는 단조함수 f\colon L\to L를 구성하면 족하다. 두 부분 집합 A,B\subseteq L에 대하여, 다음 조건들을 생각하자. * (라) A는 정렬 전순서 집합이다. * (마) B의 반대 순서 집합 B^{\operatorname{op는 정렬 전순서 집합이다. * (바) 임의의 a\in A 및 b\in B에 대하여, a * (사) 동시에 A의 상계이자 B의 하계인 L의 원소가 존재하지 않는다. 만약 A와 B가 위 조건들을 만족시킨다면, 함수 :f\colon L\to L :f\colon x\mapsto\begin{cases} \min\\{a\in A\colon a\not\le x\\}&\forall b\in B\colon x\le b\\\ \max\\{b\in B\colon x\not\le b\\}&\exist b\in B\colon x\not\le b \end{cases} 는 단조함수이며, 고정점이 존재하지 않는다. 따라서, 조건 (라)~(사)를 만족시키는 A와 B를 찾는 것으로 족하다. 모든 부분 집합의 상한이 존재하는 부분 순서 집합은 완비 격자이므로, 상한이 없는 L의 부분 집합 \\{a*_\alpha\colon\alpha<\kappa\\}가 존재한다. 편의상 그 크기 \kappa가 최소라고 하자. L이 격자이므로, \kappa은 0이거나 무한 기수이다. 이제, 임의의 순서수 \alpha<\kappa에 대하여, \\{a*_\beta\colon\beta<\alpha\\}의 크기는 \kappa미만이므로, 상한 :a'_\alpha=\bigvee_{\beta<\alpha}a*_\beta 이 존재한다. (a'_\alpha\colon\alpha<\kappa)는 단조 초한 점렬이지만, 순단조가 아닐 수 있다. 중복된 항을 제거하여 순단조 초한 점렬 (a_\alpha\colon\alpha<\kappa)로 만들자 (길이가 \kappa인 것은 \kappa의 최소성을 사용하여 보일 수 있다). 이 경우, A=\\{a_\alpha\colon\alpha<\kappa\\}는 정렬 전순서 집합이다. 만약 A의 상한이 존재한다면, 이는 \\{a*_\alpha\colon\alpha<\kappa\\}의 상한이 되어 모순이 일어난다. 따라서 A의 상한이 존재하지 않는다. A의 상계들로 구성된 순감소 초한 점렬들의 집합 위에 다음과 같은 부분 순서를 주자. :(x_\alpha'\colon\alpha'<\alpha)\preceq(y_\beta'\colon\beta'<\beta)\iff\alpha\le\beta,\;x=y\restriction\alpha 즉, 끝에 항을 추가하면 더 큰 초한 점렬을 얻는다. 초른 보조정리에 따라, 이 부분 순서에 따른 극대 원소 (b_\alpha\colon\alpha<\lambda)가 존재한다 (\lambda가 기수일 필요는 없다). B=\\{b_\alpha\colon\alpha<\lambda\\}의 반대 순서 집합 B^{\operatorname{op은 정렬 전순서 집합이다. 만약 \textstyle\bigwedge B가 존재한다면, \textstyle\bigwedge B 역시 A의 상계이다. A의 상한이 존재하지 않으므로, \textstyle\bigwedge B\not\le b인 A의 상계 b\in L가 존재한다. 이 경우, \textstyle\bigwedge B\wedge b는 A의 상계이며, \textstyle\bigwedge B\wedge b<\bigwedge B이다. 이는 (b_\alpha\colon\alpha<\lambda)의 극대성과 모순이다. 따라서, B의 하한 역시 존재하지 않는다. 이제, A=\\{a_\alpha\colon\alpha<\kappa\\}와 B=\\{b_\alpha\colon\alpha<\lambda\\}에 대하여 조건 (사)를 증명하는 일만 남았다. 귀류법을 사용하여, b\in L이 A의 상계이자 B의 하계라고 하자. 그렇다면, (b_\alpha\colon\alpha<\lambda)의 극대성에 따라 b\in B이다. 따라서 b는 B의 하한이며, 이는 모순이다.
# 일반화
격자 L의, 공집합이 아닌 두 부분 격자 M, N에 대하여, 다음과 같은 이항 관계를 정의하자. :M\preceq N\iff\forall a\in M\forall b\in N\colon a\wedge b\in M,\;a\vee b\in N 특히, 만약 M\preceq N이라면, 임의의 a\in M에 대하여, a\le b인 b\in N이 존재하며, 마찬가지로 임의의 b\in N에 대하여, a\le b인 a\in M이 존재한다. 즉, M\subseteq\mathop\downarrow N이며 N\subseteq\mathop\uparrow M이다. 이 이항 관계는 공집합이 아닌 부분 격자의 집합 위의 부분 순서를 이룬다. L의 원소는 자연스럽게 L의 부분 격자로 여길 수 있다. 이 경우, 부분 격자의 순서는 원소의 순서를 확장한다. 따라서, 아래의 정리는 타르스키 고정점 정리를 일반화한다. 다음이 주어졌다고 하자. * 완비 격자 L * 단조함수 f\colon L\to(\operatorname{Sub}(L),{\preceq}|_{\operatorname{Sub}(L)}). 여기서 (\operatorname{Sub}(L),{\preceq}|_{\operatorname{Sub}(L)})은 L의 부분 완비 격자의, 위에서 정의한 순서에 따른 부분 순서 집합이다. (부분 완비 격자는 완비 격자인 부분 격자보다 더 강한 개념이다. 전자는 모든 상한과 하한이 원래 격자와 일치하지만, 후자는 모든 유한 집합의 상한·하한의 일치만을 요구한다.) 그렇다면, f의 고정점 집합 :\operatorname{fix}(f)=\\{a\in L\colon a\in f(a)\\} 은 완비 격자를 이룬다.zbl=0809.90138297, Theorem 1 또한, f의 최대·최소 고정점은 다음과 같다. :\bigvee\operatorname{fix}(f)=\bigvee\\{a\in L\colon a\in\mathop\downarrow f(a)\\} :\bigwedge\operatorname{fix}(f)=\bigwedge\\{a\in L\colon a\in\mathop\uparrow f(a)\\}
## 일반화의 증명
타르스키 고정점 정리의 증명과 유사하게, 다음 네 명제를 보인다. 이들 가운데 명제 (아)와 (자), 명제 (차)와 (카)는 서로 쌍대이므로 하나씩만 증명하여도 좋다. * (아) M=\\{a\in L\colon a\in\mathop\downarrow f(a)\\}에 대하여, \textstyle\bigvee M은 f의 최대 고정점이다. * (자) N=\\{a\in L\colon a\in\mathop\uparrow f(a)\\}에 대하여, \textstyle\bigwedge N은 f의 최소 고정점이다. * (차) 모든 S\subseteq\operatorname{fix}(f)의 \operatorname{fix}(f)에서의 상한이 존재한다. * (카) 모든 S\subseteq\operatorname{fix}(f)의 \operatorname{fix}(f)에서의 하한이 존재한다. 명제 (아)의 증명. \operatorname{fix}(f)\subseteq M이므로, \textstyle\bigvee M\in\operatorname{fix}(f)이면 충분하다. 임의의 a\in M가 주어졌다고 하자. M의 정의에 따라, x_a\in f(a)이며 a\le x_a라고 하자. \textstyle a\le\bigvee M이며 f가 단조함수이므로, \textstyle y_a\in f\left(\bigvee M\right)이며 x_a\le y_a라고 하자. \textstyle f\left(\bigvee M\right)이 부분 완비 격자이므로, \textstyle\bigvee_{a\in M}y_a\in f\left(\bigvee M\right)이다. 임의의 a\in M에 대하여 a\le x_a\le y_a이므로, \textstyle\bigvee M\le\bigvee_{a\in M}y_a이다. f의 단조성에 따라, \textstyle\bigvee_{a\in M}y_a\le z인 \textstyle z\in f\left(\bigvee_{a\in M}y_a\right)가 존재한다. 즉, \textstyle\bigvee_{a\in M}y_a\in M이며, 따라서 \textstyle\bigvee_{a\in M}y_a\le\bigvee M이다. 따라서, \textstyle\bigvee M=\bigvee_{a\in M}y_a\in f\left(\bigvee M\right)은 f의 고정점이 맞다. 명제 (차)의 증명. \textstyle\bigvee S가 S의 L에서의 상한이라고 하자. 그렇다면, \textstyle\left[\bigvee S,\top\right]은 완비 격자를 이룬다. 임의의 s\in S에 대하여, s\in f(s)이며 \textstyle s\le\bigvee S이므로, s\le x_s인 \textstyle x_s\in f\left(\bigvee S\right)가 존재한다. 이 경우, \textstyle\bigvee_{s\in S}x_s\in f\left(\bigvee S\right)이며 \textstyle\bigvee S\le\bigvee_{s\in S}x_s이다. 따라서, f의 단조성에 의하여, 만약 \textstyle a\in\left[\bigvee S,\top\right]라면, \textstyle g(a)=f(a)\cap\left[\bigvee S,\top\right]은 공집합이 아니다. 또한, f(a)는 L의 부분 완비 격자이다. 따라서, g(a)는 \textstyle\left[\bigvee S,\top\right]의 부분 완비 격자를 이룬다. 즉, a\mapsto g(a)는 단조함수 \textstyle g\colon\left[\bigvee S,\top\right]\to(\operatorname{Sub}(\left[\bigvee S,\top\right]),{\preceq}|_{\operatorname{Sub}(\left[\bigvee S,\top\right])})를 정의한다. 명제 (자)에 따라, g의 최소 고정점이 존재하며, 이는 S의 \operatorname{fix}(f)에서의 상한이다.
# 역사
브로니스와프 크나스터 (1893~1980) 알프레트 타르스키 (1901~1983) 1927년 브로니스와프 크나스터(Bronisław Knaster)와 알프레트 타르스키가 멱집합 격자 위 단조함수의 고정점의 존재를 증명하였다.arxiv=zbl=0064.26004286, 각주 2 타르스키 고정점 정리의 오늘날 형태는 1939년 타르스키가 도입하였으며, 1939년~1942년 동안 타르스키의 몇몇 공개 강의에서 소개되었다.286, 각주 2 타르스키 고정점 정리의 역은 앤 모렐(Anne C. Morel)이 증명하였다. 타르스키 고정점 정리의 다중 값 일반화는 저우린(周林)이 초모듈러 게임(supermodular game)의 내시 균형의 존재를 보이기 위하여 증명 및 사용하였다.