クリーネの不動点定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

数学順序理論束論におけるクリーネの不動点定理(クリーネのふどうてんていり、Kleene fixed-point theorem)とは、スティーヴン・コール・クリーネによって導入された以下の定理である。

最小元を持つ ω-完備半順序 上のスコット連続関数 最小不動点を持ち、それは のクリーネ鎖の上限に一致する。

ここで、クリーネ鎖とは、 の最小元 繰り返し適用することで得られる以下ののことである。

最小不動点を と書くことにすると、本定理は次式で表すことができる。

本定理はしばしばアルフレト・タルスキによるものと誤解されるが、本定理は不動点の具体的な構成方法を与えているという点でタルスキの不動点定理英語版(こちらは完備束上の単調関数に関する定理である)とは異なるものである。

証明[1][編集]

はじめに、 における のクリーネ鎖の存在性を示す。 の最小性より が成り立つので、この両辺に単調関数 (スコット連続関数はすなわち単調である)を繰り返し適用することで以下の通りクリーネ鎖 が得られる。

これは ω-完備半順序上の ω-鎖であるから、上限 を持つ。

続いて、 の不動点であることを示す。 これは のスコット連続性より次式の通り示される。(この式の最後の等号は より成り立つ)

最後に、最小不動点であることを示す。 の任意の不動点 を取ると、 の最小性より が成り立つ。 この両辺に単調関数 を繰り返し適用すると () が得られるが、 の不動点であるからすなわち が成り立つ。 よって 以下の元からなる鎖であり、 はその上限であるから、 もまた 以下である。 斯くして の最小不動点であることが示された。

関連項目[編集]

参考文献[編集]

  1. ^ Stoltenberg-Hansen, V.; Lindstrom, I.; Griffor, E. R. (1994) (英語). Mathematical Theory of Domains by V. Stoltenberg-Hansen. Cambridge University Press. pp. 24. doi:10.1017/cbo9781139166386. ISBN 0521383447. https://doi.org/10.1017/CBO9781139166386.