클레이니 고정점 정리

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

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

f의 상승 클레이니 연쇄는

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

여기서 는 최소 고정점을 나타낸다.

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

 증명 
출처:

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

보조정리. 이 최소 원소를 갖는 dcpo이고, 가 스콧 연속이면, 

증명. 귀납법을 사용한다:
 n = 0이라고 가정하자. 그러면  왜냐하면 는 최소 원소이기 때문이다.
 n > 0이라고 가정하자. 그러면 임을 보여야 한다. 정리하면 를 얻는다. 귀납 가정에 의해 가 성립하며, f는 단조 함수이므로 (스콧 연속 함수의 속성), 결과도 성립한다.

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

dcpo의 정의에 따르면 은 상한 을 가진다. 이제 남은 것은 이 최소 고정점임을 보이는 것이다.

먼저 이 고정점, 즉 임을 보인다. 는 스콧 연속이므로, , 즉 이다. 또한, 이고 는 상한을 결정하는 데 영향을 주지 않으므로: 이다. 따라서 이므로 은 의 고정점이다.

이 실제로 최소 고정점임을 증명하는 것은 의 모든 원소가 의 어떤 고정점보다도 작다는 것을 보여줌으로써 가능하다 (왜냐하면 상한의 속성에 의해, 집합 의 모든 원소가 의 어떤 원소보다 작으면 도 그 의 동일한 원소보다 작기 때문이다). 이는 귀납법으로 수행된다. 가 의 어떤 고정점이라고 가정하자. 이제 에 대한 귀납법으로 임을 증명한다. 귀납의 기본 단계 는 분명히 성립한다:  왜냐하면 는 의 최소 원소이기 때문이다. 귀납 가설로서, 를 가정할 수 있다. 이제 귀납 단계를 수행한다: 귀납 가설과 의 단조성 (다시 말하지만, 의 스콧 연속성에서 유추됨)으로부터 다음을 결론지을 수 있다:  이제 가 의 고정점이라는 가정에 의해, 임을 알며, 이로부터 를 얻는다.

 같이 보기 
 다른 고정점 정리

 각주 

분류:순서론
분류:고정점 정리