타르스키 고정점 정리

타르스키 고정점 정리(Tarski's fixed-point theorem), 혹은 크나스터-타르스키 정리(Knaster-Tarski theorem)는 완비 격자에서 단조 함수의 고정점에 관한 정리이다 [1].

멱집합 격자에서의 고정점 정리를 브로니스와프 크나스터와 알프레트 타르스키가 증명한 바 있다. 이후 알프레트 타르스키가 완비 격자로 일반화 하였다.

진술

\(\langle L, \leq \rangle\)를 완비 격자, \(f : L \to L\)를 단조 함수라고 하자. 이때 \(f\)는 최소 고정점 \(\mu = \bigwedge \{x \in L \mid f(x) \leq x\}\)와 최대 고정점 \(\nu = \bigvee \{x \in L \mid x \leq f(x)\}\)를 갖는다. 또한 \(f\)의 고정점들의 집합을 \(P\)라고 할 때, \(\langle P, \leq \rangle\)은 완비 격자를 이룬다.

참고문헌