代数学および離散数学において
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/05 03:00 UTC 版)
「不動点定理」の記事における「代数学および離散数学において」の解説
クナスター・タルスキーの定理（英語版）は、完備束上の任意の単調写像は少なくとも一つの不動点（実際には「最小の不動点」）が存在することを述べる。詳しくはブルバキ・ヴィットの定理を参照されたい。この定理は静的コード解析の一つの形式である抽象解釈において応用を持つ。 ラムダ計算における共通のテーマの一つとして、「与えられたラムダ式の不動点を求める」というものがある。ラムダ式には必ず不動点が存在し、「ラムダ式を入力すると、その式の不動点が出力として得られる」という関数が不動点コンビネータである。不動点コンビネータの1つにYコンビネータがあり、これは再帰的定義を記述する際に用いられる重要なものである。不動点定理を適用する対象の関数は、論理的な観点からは同一の関数だが、その理論の展開は多岐にわたっている。プログラム言語の表示的意味論の分野では、再帰的定義の意味論を構築するために、クナスター・タルスキーの定理のある特別な場合を用いている。また、計算可能性理論においても、クリーネの再帰定理を使えば、再帰的関数を同様に定義することができる。なお、これらの各分野で用いている定理は等価ではなく、クナスター・タルスキーの定理というのは、表示的意味論で用いている定理よりもずっと強い定理である。ただし、チャーチ・チューリングのテーゼの観点では、これらの直感的な意味合いは同じであり、「再帰関数は、関数を関数にうつすある汎関数の最小の不動点として表すことができる」ということに他ならない。 ところで、初めに紹介した「関数の繰り返し適用によって不動点を求める」という手法は、集合論でも用いる手法である。正規関数の不動点補題（英語版）では、「順序数から順序数への連続な狭義単調増加関数には、少なくとも1つの（実際には多数の）不動点が存在する」ことを述べている。また、半順序集合の閉包作用素（英語版）には必ずいくつかの不動点が存在し、それらが、この閉包作用素に関する意味で「閉」な元である（これが、閉包作用素を先に定義する最大の理由である）。 元の個数が奇数であるような有限集合上の任意の対合は不動点を持つ。より一般に、元の有限集合上の任意の対合に対して、不動点の数と元の数の偶奇性は一致する。ドン・ザギエはこれらの観察の下でフェルマーの二平方和定理の一文証明を与えた。これは整数の三つ組の成す同じ集合上の二つの対合を記述することで成り立っており、一方はただ一つの不動点を持つことが平易にわかるもので、他方は与えられた素数 (ただし mod 4 で 1 のもの) を二平方和でおのおの表現したものに対する不動点を持つ。前者は奇数個の不動点を持つから後者もそうで、従って必ず所期の形の表現が存在することがわかる。
※この「代数学および離散数学において」の解説は、「不動点定理」の解説の一部です。
「代数学および離散数学において」を含む「不動点定理」の記事については、「不動点定理」の概要を参照ください。
- 代数学および離散数学においてのページへのリンク
