클레이니 고정점 정리

이 문서는 계산 가능성 이론의 고정점 정리에 관한 것입니다. 클레이니 재귀 정리에 대해서는 격자 이론의 클레이니 고정점 정리 문서를 참고하십시오.

수학의 순서론 및 격자 이론 분야에서 미국의 수학자 스티븐 클레이니의 이름을 딴 클레이니 고정점 정리(영어: Kleene fixed-point theorem)는 다음을 명시한다.

클레이니 고정점 정리. ${\displaystyle (L,\sqsubseteq )}$가 최소 원소를 갖는 완비 원순서 집합 (dcpo)이고, ${\displaystyle f:L\to L}$가 스콧 연속 (따라서 단조) 함수라고 가정하자. 그러면 ${\displaystyle f}$는 최소 고정점을 가지며, 이는 ${\displaystyle f}$의 상승 클레이니 연쇄의 상한이다.

실수 구간 [0,7]에서 일반적인 순서로 클레이니 정리를 사용하여 f(x) = ⁠1/10⁠x²+atan(x)+1의 최소 고정점 계산

f의 상승 클레이니 연쇄는

${\displaystyle \bot \sqsubseteq f(\bot )\sqsubseteq f(f(\bot ))\sqsubseteq \cdots \sqsubseteq f^{n}(\bot )\sqsubseteq \cdots }$

로 주어진 연쇄이며, L의 최소 원소 ⊥에 f를 반복 적용하여 얻어진다. 공식으로 표현하면 이 정리는 다음과 같이 명시한다.

${\displaystyle {\textrm {lfp}}(f)=\sup \left(\left\{f^{n}(\bot )\mid n\in \mathbb {N} \right\}\right)}$

여기서 ${\displaystyle {\textrm {lfp}}}$는 최소 고정점을 나타낸다.

타르스키 고정점 정리는 f를 어떤 시작점으로부터 반복하여 고정점을 계산하는 방법을 고려하지 않지만 (또한, 완비 격자의 단조함수에 관한 것이다), 이 결과는 종종 가법 함수에 대해 이를 증명한 알프레트 타르스키에게 귀속된다.^[1] 더욱이, 클레이니 고정점 정리는 초한 반복을 사용하여 단조함수로 확장될 수 있다.^[2]

증명

출처:^[3]

먼저 ${\displaystyle f}$의 상승 클레이니 연쇄가 ${\displaystyle L}$에 존재함을 보여야 한다. 이를 위해 다음을 증명한다.

보조정리. ${\displaystyle L}$이 최소 원소를 갖는 dcpo이고, ${\displaystyle f:L\to L}$가 스콧 연속이면, ${\displaystyle f^{n}(\bot )\sqsubseteq f^{n+1}(\bot ),n\in \mathbb {N} _{0}}$

증명. 귀납법을 사용한다:

• n = 0이라고 가정하자. 그러면 ${\displaystyle f^{0}(\bot )=\bot \sqsubseteq f^{1}(\bot ),}$ 왜냐하면 ${\displaystyle \bot }$는 최소 원소이기 때문이다.
• n > 0이라고 가정하자. 그러면 ${\displaystyle f^{n}(\bot )\sqsubseteq f^{n+1}(\bot )}$임을 보여야 한다. 정리하면 ${\displaystyle f(f^{n-1}(\bot ))\sqsubseteq f(f^{n}(\bot ))}$를 얻는다. 귀납 가정에 의해 ${\displaystyle f^{n-1}(\bot )\sqsubseteq f^{n}(\bot )}$가 성립하며, f는 단조 함수이므로 (스콧 연속 함수의 속성), 결과도 성립한다.

보조정리의 따름정리로 다음의 방향화된 ω-연쇄를 얻는다.

${\displaystyle \mathbb {M} =\{\bot ,f(\bot ),f(f(\bot )),\ldots \}.}$

dcpo의 정의에 따르면 ${\displaystyle \mathbb {M} }$은 상한 ${\displaystyle m}$을 가진다. 이제 남은 것은 ${\displaystyle m}$이 최소 고정점임을 보이는 것이다.

먼저 ${\displaystyle m}$이 고정점, 즉 ${\displaystyle f(m)=m}$임을 보인다. ${\displaystyle f}$는 스콧 연속이므로, ${\displaystyle f(\sup(\mathbb {M} ))=\sup(f(\mathbb {M} ))}$, 즉 ${\displaystyle f(m)=\sup(f(\mathbb {M} ))}$이다. 또한, ${\displaystyle \mathbb {M} =f(\mathbb {M} )\cup \{\bot \}}$이고 ${\displaystyle \bot }$는 상한을 결정하는 데 영향을 주지 않으므로: ${\displaystyle \sup(f(\mathbb {M} ))=\sup(\mathbb {M} )}$이다. 따라서 ${\displaystyle f(m)=m}$이므로 ${\displaystyle m}$은 ${\displaystyle f}$의 고정점이다.

${\displaystyle m}$이 실제로 최소 고정점임을 증명하는 것은 ${\displaystyle \mathbb {M} }$의 모든 원소가 ${\displaystyle f}$의 어떤 고정점보다도 작다는 것을 보여줌으로써 가능하다 (왜냐하면 상한의 속성에 의해, 집합 ${\displaystyle D\subseteq L}$의 모든 원소가 ${\displaystyle L}$의 어떤 원소보다 작으면 ${\displaystyle \sup(D)}$도 그 ${\displaystyle L}$의 동일한 원소보다 작기 때문이다). 이는 귀납법으로 수행된다. ${\displaystyle k}$가 ${\displaystyle f}$의 어떤 고정점이라고 가정하자. 이제 ${\displaystyle i}$에 대한 귀납법으로 ${\displaystyle \forall i\in \mathbb {N} :f^{i}(\bot )\sqsubseteq k}$임을 증명한다. 귀납의 기본 단계 ${\displaystyle (i=0)}$는 분명히 성립한다: ${\displaystyle f^{0}(\bot )=\bot \sqsubseteq k,}$ 왜냐하면 ${\displaystyle \bot }$는 ${\displaystyle L}$의 최소 원소이기 때문이다. 귀납 가설로서, ${\displaystyle f^{i}(\bot )\sqsubseteq k}$를 가정할 수 있다. 이제 귀납 단계를 수행한다: 귀납 가설과 ${\displaystyle f}$의 단조성 (다시 말하지만, ${\displaystyle f}$의 스콧 연속성에서 유추됨)으로부터 다음을 결론지을 수 있다: ${\displaystyle f^{i}(\bot )\sqsubseteq k~\implies ~f^{i+1}(\bot )\sqsubseteq f(k).}$ 이제 ${\displaystyle k}$가 ${\displaystyle f}$의 고정점이라는 가정에 의해, ${\displaystyle f(k)=k}$임을 알며, 이로부터 ${\displaystyle f^{i+1}(\bot )\sqsubseteq k}$를 얻는다.

같이 보기

• 다른 고정점 정리