타르스키 고정점 정리

순서론에서 타르스키 고정점 정리(영어: Tarski’s fixed point theorem) 또는 크나스터-타르스키 정리(영어: Knaster–Tarski theorem)는 완비 격자에서 자신으로 가는 단조함수의 고정점이 존재한다는 정리이다.

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

정의

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

${\displaystyle \operatorname {fix} (f)=\{a\in L\colon f(a)=a\}}$

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

${\displaystyle \bigvee \operatorname {fix} (f)=\bigvee \{a\in L\colon a\leq f(a)\}}$

${\displaystyle \bigwedge \operatorname {fix} (f)=\bigwedge \{a\in L\colon a\geq f(a)\}}$

증명

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

• (가) ${\displaystyle \textstyle \bigvee \{a\in L\colon a\leq f(a)\}}$는 ${\displaystyle f}$의 최대 고정점이다.
• (나) ${\displaystyle \textstyle \bigwedge \{a\in L\colon a\geq f(a)\}}$는 ${\displaystyle f}$의 최소 고정점이다.
• (다) ${\displaystyle \operatorname {fix} (f)}$는 완비 격자이다.

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

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

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

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

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

${\displaystyle L=\{\bot ,a,a',b,\top \}}$

${\displaystyle \bot <a,a'<b<\top }$

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

${\displaystyle f(x)=x\qquad (x=\bot ,a,a',\top )}$

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

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

귀결

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

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

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

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

역

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

역의 증명

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

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

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

${\displaystyle f\colon L\to L}$

${\displaystyle f\colon x\mapsto {\begin{cases}\min\{a\in A\colon a\not \leq x\}&\forall b\in B\colon x\leq b\\\max\{b\in B\colon x\not \leq b\}&\exists b\in B\colon x\not \leq b\end{cases}}}$

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

${\displaystyle a'_{\alpha }=\bigvee _{\beta <\alpha }a''_{\beta }}$

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

${\displaystyle (x_{\alpha }'\colon \alpha '<\alpha )\preceq (y_{\beta }'\colon \beta '<\beta )\iff \alpha \leq \beta ,\;x=y\upharpoonright \alpha }$

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

일반화

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

${\displaystyle M\preceq N\iff \forall a\in M\forall b\in N\colon a\wedge b\in M,\;a\vee b\in N}$

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

다음이 주어졌다고 하자.

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

그렇다면, ${\displaystyle f}$의 고정점 집합

${\displaystyle \operatorname {fix} (f)=\{a\in L\colon a\in f(a)\}}$

은 완비 격자를 이룬다.^{[2]:297, Theorem 1} 또한, ${\displaystyle f}$의 최대·최소 고정점은 다음과 같다.

${\displaystyle \bigvee \operatorname {fix} (f)=\bigvee \{a\in L\colon a\in \mathop {\downarrow } f(a)\}}$

${\displaystyle \bigwedge \operatorname {fix} (f)=\bigwedge \{a\in L\colon a\in \mathop {\uparrow } f(a)\}}$

일반화의 증명

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

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

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

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

역사

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

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

1927년 브로니스와프 크나스터(폴란드어: Bronisław Knaster)와 알프레트 타르스키가 멱집합 격자 위 단조함수의 고정점의 존재를 증명하였다.^{[3][4]:286, 각주 2} 타르스키 고정점 정리의 오늘날 형태는 1939년 타르스키가 도입하였으며, 1939년~1942년 동안 타르스키의 몇몇 공개 강의에서 소개되었다.^{[4]:286, 각주 2} 타르스키 고정점 정리의 역은 앤 모렐(영어: Anne C. Morel)이 증명하였다.^[1] 타르스키 고정점 정리의 다중 값 일반화는 저우린(중국어: 周林)이 초모듈러 게임(영어: supermodular game)의 내시 균형의 존재를 보이기 위하여 증명 및 사용하였다.^[2]

같이 보기

• 고정점 정리
• 완비 격자