超限再帰定理

数学では、超限再帰定理は、関数は整列集合上の再帰を用いて定義できると述べています。例えば、${\displaystyle \mathbb {N} }$しかし、一般的な整列集合にも当てはまる。

整列集合はそれぞれ順序数と同型であるため、この定理は順序数を用いて表現されることも多い。

超限再帰は超限帰納法の一例であり、後者は整列集合上で機能します（実際、このような帰納法の実現可能性は整列性と同値です）。特に、この定理は整列集合に対して述べることができます。${\displaystyle A}$は半順序集合であり、次のように書きます。${\displaystyle A^{a}=\{b\in A\mid b<a\}.}$

超限再帰定理は順序数に対してもよく述べられる。簡単な例を挙げると次のようになる。${\displaystyle X}$そしてクラス関数${\displaystyle G}$値は${\displaystyle X}$すべての関数のクラスで定義されます。次に、各序数について${\displaystyle \alpha }$一意関数が存在する

${\displaystyle f:\alpha \to X}$

つまり、すべての序数に対して${\displaystyle \beta <\alpha }$つまり、${\displaystyle \beta \in \alpha }$または${\displaystyle \beta \subsetneq \alpha }$、

${\displaystyle f(\beta )=G(f|_{\beta })}$。

順序数は整列集合であるため、上記のバージョンは整列バージョンから導かれる（${\displaystyle \beta =\alpha ^{\beta }}$）よく聞かれるのは${\displaystyle G}$すべての関数に対して定義される必要があるが、これは定理を述べるための便利な方法にすぎない。実際には、通常は のみを定義する。${\displaystyle G(f)}$関数について${\displaystyle f:\alpha \to X}$、${\displaystyle \alpha }$すべての序数、そして拡張${\displaystyle G}$その他の関数はすべて任意です。

いつ${\displaystyle A=\mathbb {N} }$ここでの証明はN. JacobsonのBasic Algebra I ^{[ 2 ]}に掲載されており、全く同じ証明が任意の整列集合にも適用されます。証明自体はHalmos ^{[ 1 ]から引用されています。}

部分集合${\displaystyle E\subset A\times X}$閉鎖されています（${\displaystyle G}$）各関数について${\displaystyle f:A^{a}\to X,\,a\in A}$そのグラフは${\displaystyle E}$、 我々は持っています${\displaystyle (a,G(f))}$は${\displaystyle E}$。 例えば、${\displaystyle A\times X}$閉店しました。

させて${\displaystyle F}$すべての閉部分集合の共通部分である${\displaystyle A\times X}$（に関して${\displaystyle G}$）これもまた閉じている。我々は証明する。${\displaystyle F}$関数のグラフ${\displaystyle A\to X}$つまり、繊維${\displaystyle p^{-1}(a)}$投影のために${\displaystyle p:F\subset A\times X\to A}$それぞれにちょうど１つの要素があります${\displaystyle a}$で${\displaystyle A}$そのためには、強力な帰納法を用います。${\displaystyle A}$つまり、${\displaystyle \#p^{-1}(b)=1}$すべての${\displaystyle b<a}$我々は示す${\displaystyle \#p^{-1}(a)=1}$。

帰納的仮説により、関数は次のようになる。${\displaystyle f:A^{a}\to X,\,b\mapsto {\text{p^{-1}(b) の一意な要素}$グラフは${\displaystyle F}$。 以来${\displaystyle F}$閉鎖されています、${\displaystyle (a,G(f))}$は${\displaystyle F}$。 したがって、${\displaystyle \#p^{-1}(a)\geq 1}$等式であることを示すために、そうでないと仮定してみましょう。つまり、あるペアが存在するということです。${\displaystyle (a,y)\neq (a,G(f))}$で${\displaystyle F}$我々はセットを主張する

${\displaystyle E:=F-\{(a,y)\}}$

は閉じている。したがって、${\displaystyle g:A^{b}\to X}$グラフが にある関数とする${\displaystyle E}$。 もし${\displaystyle b=a}$すると、${\displaystyle f=g}$帰納的仮説により、実際、それらのグラフは${\displaystyle F}$、

${\displaystyle \{f(c),g(c)\}\subset p^{-1}(c)}$

各${\displaystyle c<a}$。 したがって、${\displaystyle (b,G(g))\in E}$以来${\displaystyle y\neq G(f)=G(g)}$そして${\displaystyle F}$閉鎖されています。${\displaystyle b\neq a}$もう一度${\displaystyle (b,G(g))}$は${\displaystyle E}$として${\displaystyle F}$閉じられています。これで主張が証明され、${\displaystyle E\subsetneq F}$最小性とは矛盾する${\displaystyle F}$最後に、同様の、しかしより簡単な帰納法によって、一意性が成り立つ。${\displaystyle \square }$

超限再帰の用途によっては、クラス内の値を持つ関数を構築する必要がある場合があります。その場合、置換公理を使用して、関数が確実に得られるようにする必要があります。${\displaystyle f}$終域がクラスであっても。

以下に、そのようなニーズの例を示します。^{[ 4 ] [ 5 ]}次のようなことを示したいとします。

整列集合はそれぞれ、一意の順序数と一意的に同型である。

問題は、先験的にどの順序数を使うべきか分からないことである。したがって、超限帰納法の各段階で、新しい順序数を構築する。正確には、整列集合が与えられた場合${\displaystyle X}$そして要素${\displaystyle a}$で${\displaystyle X}$構築したと仮定します

${\displaystyle g_{b}:X^{b}{\overset {\sim }{\to }}\alpha _{b}}$

どこ${\displaystyle X^{b}=\{c\mid c<b\}}$これらの同型性を同型性へと拡張します。${\displaystyle X^{a}\simeq \alpha }$ある序数に対して${\displaystyle \alpha }$。 もし${\displaystyle a=s(b)}$は後継者です。つまり、厳密な上限の中で最小の要素です。${\displaystyle b}$それから私たちは${\displaystyle f|_{X^{b}}=g_{b}}$そして${\displaystyle f(a)=\alpha _{b}}$。 それから

${\displaystyle f:X^{a}{\overset {\sim }{\to }}s(\alpha _{b}):=\alpha _{b}\cup \{\alpha _{b}\},}$

右側の和集合は和集合の公理により存在する。${\displaystyle a=\sup(X^{a})}$そして、考えてみると${\displaystyle g_{b}}$順序対の集合として、

${\displaystyle f=\bigcup _{b<a}g_{b}.}$

右側の和集合は置換公理と和集合公理によって構成される。実際、前者は集合を​​保証する。${\displaystyle \{g_{b}\mid b<a\}}$は集合である。${\displaystyle \alpha }$のイメージである${\displaystyle f}$これは明らかに序数であり、${\displaystyle f:X^{a}{\overset {\sim }{\to }}\alpha }$最後に、一意性を確認します。超限帰納法により、順序数間の同型写像は恒等写像であることがわかります。次に、${\displaystyle f:X{\overset {\sim }{\to }}\alpha ,g:X{\overset {\sim }{\to }}\beta }$、 我々は持っています${\displaystyle g\circ f^{-1}:\alpha {\overset {\sim }{\to }}\beta }$はアイデンティティであり、${\displaystyle f=g}$。${\displaystyle \square }$

同じ議論は、対象が${\displaystyle X}$はクラスである。証明は順序数に関する強い帰納法による（同じ証明は整列集合にも適用できるが、ここでは簡略化のために順序数を用いる）。したがって、すべての に対して定理が真であると仮定する。${\displaystyle \beta <\alpha }$帰納的仮説により、各${\displaystyle \beta <\alpha }$私たちには独自の機能があります${\displaystyle g_{\beta }:\beta \to X}$再帰条件を満たす。${\displaystyle h_{\beta }:\beta \to X}$によって与えられる${\displaystyle \gamma \mapsto G(g_{\beta }|_{\gamma })}$極限の場合、すなわち、${\displaystyle \alpha }$は極限順序数であり、関数とそのグラフを識別し、和集合を考える。

${\displaystyle \bigcup _{\beta <\alpha }h_{\beta }.}$

和集合の形成は和集合の公理によって正当化されるが、上記の和集合が集合であるためには、集合が必要である。

${\displaystyle \{h_{\beta }\mid \beta <\alpha \}}$

集合であること。言い換えれば、地図のイメージ${\displaystyle \beta \mapsto h_{\beta }}$集合であること、そしてそれが置換公理によって保証されること。最後に、この和集合は関数のグラフである。${\displaystyle f:\alpha \to X}$これは、必要な再帰条件を満たしています。後継ケースも同様に処理されます。${\displaystyle \square }$

• ハルモス、ポール（1960）。素朴な集合論。プリンストン、ニュージャージー州：D.ヴァン・ノストランド社。
• 「第 IV 章 超限再帰」。公理的集合論。論理学と数学の基礎に関する研究。第 21 巻。1958 年。pp  . 100–113。doi : 10.1016/S0049-237X(08)71575-1。 
• ポール・テイラー著『数学の実践的基礎』

• 超限再帰定理 - ProofWiki