超限帰納法のソースを表示

[[File:omega-exp-omega-labeled.svg|thumb|300px|<math>\omega^{\omega}</math> までの順序数の表現。螺旋の各回転は<math>\omega</math>の1回冪を表す。超限帰納法では、'''基本ケース'''(0に対応)、'''後続者ケース'''(後続順序数に対応)、'''極限ケース'''(極限順序数に対応)で証明する必要がある。]]

'''超限帰納法'''（ちょうげんきのうほう、{{lang-en-short|Transfinite induction}}）は、[[数学的帰納法]]の[[整列集合]]上への拡張である、例えば[[順序数]]や[[基数]]の集合の上で行う。この手法の正当性は[[ツェルメロ＝フレンケル集合論|ZFC]]の定理である。<ref>J. Schlöder, [https://jjsch.github.io/output/oa.pdf Ordinal Arithmetic]. Accessed 2022-03-24.</ref>

==各ケースにおける帰納法==
性質 <math>P(\alpha)</math> が全ての順序数 <math>\alpha</math> に定義されているとする。全ての <math>\beta < \alpha</math> に対して <math>P(\beta)</math> が正しいと仮定した上で、そして <math>P(\alpha)</math> も正しいことを示す。<ref>ここで、<math>P(0)</math> が真である場合を分けて説明する必要はない。0 より小さい <math>\beta</math> は存在しないので、<math>\beta<0</math>に対しては[[空虚な真]]であり、<math>P(\beta)</math> は真と考える。</ref> このとき超限帰納法は全ての順序数に対して <math>P</math> が真であることを結論する。

通常、超限帰納法による証明は次の3ケースに分解される:

* '''基本ケース:''' <math>P(0)</math> が真であることを証明する。
* '''後続者ケース:''' 全ての[[後続順序数]] <math>\alpha+1</math> に対して、<math>P(\alpha+1)</math> を <math>P(\alpha)</math> から証明する。(必要ならば全ての <math>\beta < \alpha</math> に対しての <math>P(\beta)</math> を仮定してもよい。)
* '''極限ケース:''' 全ての[[極限順序数]] <math>\lambda</math> に対して、<math>P(\lambda)</math> であることを <math>P(\beta)</math>（全ての <math>\beta < \lambda</math> について）から証明する。

この3つのケースは、考慮する順序数の種類を除けば全て同じである。これらは形式的には別々に考える必要はないが、実際には証明は別個に行う必要があるほど異なるのが普通である。0は[[極限順序数]]と見なされることがあり、極限順序数と同じケースとして証明で扱われることがある。

==超限再帰==
'''超限再帰'''は超限帰納法に似た手法である; 何かを全ての順序数について証明する代わりに、各順序数に対するオブジェクトからなる列を構成する。

例として、（無限次元でもよい）[[ベクトル空間]]の[[基底 (線型代数学)|基底]]は空集合から始めて、各順序数 ''α > 0'' に対してベクトルの[[線型包]]にないベクトル<math>\{v_{\beta}\mid\beta<\alpha\}</math> を選ぶことで作ることができる。この処理は、どのベクトルも選択できないときに停止する。

より正式には、超限再帰定理を次のように述べることができる：

'''超限再帰定理(バージョン1)'''. クラス関数<ref>クラス関数はルール(具体的には、論理式)であって、左手のクラスの各要素を右手のクラスの要素に割り当てるものである。ここでの例は定義域と終域が集合でなく、オブジェクトとして扱える[[写像|関数]]には該当しない。</ref> ''G'': ''V'' → ''V'' (ここで ''V'' は全ての集合からなる[[クラス (集合論)|クラス]])が与えられたとき、次の[[超限列]]が一意的に存在する。''F'': Ord → ''V'' (ここで Ord は全ての順序数からなるクラス) : 全ての順序数 ''α'' について<math>F(\alpha) = G(F \upharpoonright \alpha)</math>、ここで <math>\upharpoonright</math> は ''F'' の定義域を順序数 ''α'' へ制限することを表す。

帰納法の場合と同様に、異なる種類の順序数を別々に扱うことができる。超限再帰の別の定式化は以下の通り：

'''超限再帰定理(バージョン2)'''. 集合 ''g''<sub>1</sub>、クラス関数 ''G''<sub>2</sub>、''G''<sub>3</sub> が与えられたとき、次の関数 ''F'': Ord → ''V'' が一意的に存在する。
* ''F''(0) = ''g''<sub>1</sub>,
* ''F''(''α'' + 1) = ''G''<sub>2</sub>(''F''(''α'')), for all ''α'' ∈ Ord,
* <math>F(\lambda) = G_3(F \upharpoonright \lambda)</math>, for all limit ''λ'' ≠ 0.

''G''<sub>2</sub>, ''G''<sub>3</sub> の定義域は、上記の性質を意味のあるものにするのに十分広いことが必要であることに注意。これらの性質を満たす数列の一意性は、超限帰納法を用いて証明できる。

より一般的には、任意の[[整礎関係]] ''R''に対する超限再帰によってオブジェクトを定義することができる。(ここで ''R'' は集合でなく、[[真クラス]]であっても[[二項関係|集合状]]な関係であればよい; すなわち、任意の ''x'' に対し、''yRx''を満たす ''y''の集まりが集合になっていればよい)

==選択公理との関係==
帰納法や再帰を用いた証明や構成では、しばしば[[選択公理]]を用いて、超限帰納法で扱えるような整列された関係を作り出す。しかし、問題にしている関係がすでに整列されている場合は、選択公理を用いずに超限帰納法を用いることができる。<ref>実際、関係の定義域は集合である必要はなく、前段落で取り上げたように関係が集合状になっていればよい。</ref>例えば、[[ボレル集合]]に関する多くの結果は、ボレル階層上のランクに関する超限帰納法によって証明される。ボレル階層のランクは既に整列されているので、整列するために選択公理は必要ない。

次の[[ヴィタリ集合]]の構成は、選択公理を超限帰納法による証明に使うことができる一つの方法を示している:
: まず、[[実数]]を[[整列]]して（ここで[[整列可能定理]]に選択公理を用いる）、列 <math> \langle r_\alpha \mid \alpha < \beta \rangle </math> を得る。ここで&beta; は[[連続体濃度]]を持つ順序数である。''v''<sub>0</sub> は ''r''<sub>0</sub> とする。''v''<sub>1</sub> は ''r''<sub>''α''<sub>1</sub></sub> とする。ここで ''α''<sub>1</sub> は ''r''<sub>''α''<sub>1</sub></sub>&nbsp;&minus;&nbsp;''v''<sub>0</sub> が [[有理数]]でなくなる最小のものである。続けて各ステップでは、''r''数列のうち、''v''数列でこれまでに構成されたどの要素とも有理数差を持たない最小の実数を取り続けていく。''r'' 列の全ての実数がなくなるまで続ける。最後にできる''v''列はヴィタリ集合の列挙になっている。上記の議論は、実数を整列するために、冒頭で選択の公理を本質的な形で用いている。このステップの後、選択の公理は再び使われてはいない。

選択の公理の他の使い方はもっと微妙である。
例えば、超限再帰による構成では、''α''までの数列が与えられたとき、''A''<sub>''α''+1</sub>に''一意な''値を指定することはなく、''A''<sub>''α''+1</sub>が満たさなければならない''条件''だけを指定し、この条件を満たす集合が少なくとも一つ存在することを論じることがよくある。各段階でそのような集合の一意的な例を定義することができない場合、各段階でそのような集合を1つ選択するために（ある形式の）選択の公理を呼び出す必要があるかもしれない。[[可算集合|可算]]の長さの帰納法や再帰では、より弱い[[従属選択公理]]で十分である。集合論者にとって興味深い[[ツェルメロ＝フレンケル集合論]]のモデルには、従属選択の公理は満たすが完全な選択の公理は満たさないものがあるので、特定の証明が従属選択だけを必要とするという知識は有用である．

==関連項目==
* [[数学的帰納法]]
* [[Epsilon-induction|∈-induction]]
* [[超限数]]
* [[整礎関係]]
* [[ツォルンの補題]]
* [[イプシロン数]]

== 注釈等 ==
{{reflist}}

== 参考文献 ==
*{{Citation|last=Suppes|first=Patrick|author-link=Patrick Suppes|year=1972|title=Axiomatic set theory|publisher=[[Dover Publications]]|isbn=0-486-61630-4|chapter=Section 7.1|url=https://books.google.com/books?id=sxr4LrgJGeAC&q=%22Transfinite+induction%22}}

== 外部リンク ==
* {{MathWorld |title=Transfinite Induction |id=TransfiniteInduction |author=Emerson, Jonathan |author-link=Jonathan Emerson |author2=Lezama, Mark |author2-link=Mark Lezama |author3=Weisstein, Eric W. |author3-link=Eric W. Weisstein |name-list-style=amp }}

{{Mathematical logic}}
{{Set theory}}
{{DEFAULTSORT:ちようけんきのうほう}}
[[Category:数学的帰納法]]
[[Category:順序数]]
[[Category:再帰]]
[[Category:数学に関する記事]]